Each new term in the Fibonacci sequence is generated by adding the previous two terms.
By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms. – Project Euler #2
That didn’t take long. It’s only the second problem and we already have a problem where the direct solution will take an intractably long amount of time.
Directly, we could write out a function to generate Fibonacci numbers from it’s definition (a Fibonacci number is the sum of the previous two Fibonacci numbers) and sum them directly:
; calculate the nth Fibonacci number
(define (fib n)
(if (<= n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
; sum Fibonacci numbers under n
(define (sum-fibs-under n)
(let loop ([i 1] [sum 0])
(define fibi (fib i))
(cond
[(and (< fibi n) (even? fibi))
(loop (+ i 1) (+ sum fibi))]
[(< fibi n)
(loop (+ i 1) sum)]
[else
sum])))
With all that, it takes about 5 seconds to solve the problem:
> (time (sum-even-fibs-under 4000000))
cpu time: 4900 real time: 4897 gc time: 0
4613732
Still, it feels like we should be able to make this run faster. After all, we’re only adding a few numbers (it turns out the first Fibonacci number over 4 million is fib33 = 5,702,887).
The question to ask is what is making this code slow?
Think about what’s necessary to calculate (fib 10). You need (fib 9) and (fib 8). What do you need for (fib 9) in turn? You need (fib 8) (again) and (fib 7). This will continue over and over again, until you get down to (fib 2). You’ll need a whopping 34 calls to (fib 2). For (fib 30), that number is 514,229. Yet the value of each call to fib never changes. So why are we calculating it over and over again?
The short answer to that is excellent question! What if we had some way to tell Racket to remember the previous values? Well, we do. It’s called memoization.
In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs. – Wikipedia: Memoization
Sounds like exactly what we want. I’ve already written an article about writing a memoized version of define in Racket, so go read that if you’re more interested in the details. Otherwise, functionally it’s just a matter of swapping define with define-memoized:
; calculate the nth Fibonacci number
(define-memoized (fib-memo n)
(if (<= n 2)
n
(+ (fib-memo (- n 1)) (fib-memo (- n 2)))))
Now instead of 5 seconds, the code runs essentially instantly:
> (time (sum-even-fibs-under-memo 4000000))
cpu time: 0 real time: 1 gc time: 0
4613732
This works because instead of recalculating each number, we’re storing the results. So we really are adding only those less than 30 numbers.
But this all requires that we know about / rely on memoization. That’s actually a reasonable requirement (it’s a really useful technique and something every programmer should at least be familiar with), but can we do it without?
Well, I wouldn’t be asking the question if you couldn’t. 😄
To do this, think about the way you write a list of Fibonacci numbers. You start with the first two (1 and 2) then just repeatedly add the last two on the list. You’re never looking at anything more than the last two numbers. We can turn that into code by keep track of two values in a loop: this and next, representing the current Fibonacci number and the next one. Then for each time through the loop, the next number becomes this one and the sum of the two become the new next. Add some functionality for only adding even numbers to the running sum:
; sum Fibonacci numbers under n
(define (sum-fibs-under-inline n)
(let loop ([this 1] [next 2] [sum 0])
(cond
[(> this n)
sum]
[else
(loop next (+ this next) (if (even? this)
(+ sum this)
sum))])))
Since we’re only going through about 30 iterations of the loop, it should be essentially instantaneous:
> (time (sum-fibs-under-inline 4000000))
cpu time: 0 real time: 0 gc time: 0
4613732
Finally, if you wanted, this problem is also really easy to solve by hand. Just write out the list, remove the odd values, and sum them up. There are only ~30 after all.
1 x
2 => 2
3 x
5 x
8 => 8
13 x
21 x
34 => 34
55 x
89 x
144 => 144
233 x
377 x
610 => 610
987 x
1597 x
2584 => 2584
4181 x
6765 x
10946 => 10946
17711 x
28657 x
46368 => 46368
75025 x
121393 x
196418 => 196418
317811 x
514229 x
832040 => 832040
1346269 x
2178309 x
3524578 => 3524578
-------
4613732
There’s an interesting pattern there with every third number being even. This actually makes sense though, if you think about it, since we know that adding odd+even=odd and odd+odd=even. So we need two odd numbers in a row to make the third one even, but then the next two after that will be odd+even=odd and even+odd=odd before we can restart the cycle again.
In any case, there you have it. Four ways to solve the second Project Euler problem.
As always, you can download my code for this or any Project Euler problem I’ve uploaded here.