euler2

VHDL: Even Fibonacci numbers

Project Euler problem 2 calculates the Fibonacci sequence

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms

This is the sort of thing problem that I've seen people asked to do fairly often in hardware. We're going to use the same top level entity that we described here.  To calculate the Fibonacci sequence you need two registers. To get the next Fibonacci number you need an adder, and to get the sum of the even numbers, you need an accumulator. Two comparators tell you when you're number is even, and when you've hit the max input value. 

block diagram for a hardware implementation

block diagram for a hardware implementation

Translating this directly into VHDL works out pretty well like this: 

And running that through a simple simulation with a clk, enable, and reset and monitoring the results_valid will get us a simple test bench. Taking a quick look at the start of the simulation shows us if we're on the right track. 

We can see the Fibonacci sequence in the sum register, and the even signal toggling each times it's even and the results accumulator summing these even numbers. 

We can see the Fibonacci sequence in the sum register, and the even signal toggling each times it's even and the results accumulator summing these even numbers. 

And that's about it. We could change the generic we pass in for the max_value to get this to run up to any maximum. One of the things that surprised me is how fast we got to the solution brute forcing our way through each Fibonacci number.