An Unreasonably Deep Dive into Project Euler Problem 2
First, the problem definition:
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.
Classic Fibonacci problem, with a slight twist due to the summation on top. Spoiler alert: a simple loop is fastest. Keep reading to see why.
First Attempt: Recursion
The Fibonacci sequence is defined as f(n) = f(n-1) + f(n-2) where the first two elements are defined in this problem as f(1) = 1 and f(2) = 2.
This means
f(3) = f(2) + f(1) = 2 + 1 = 3,
f(4) = f(3) + f(2) = 3 + 2 = 5,
and so on.
This recursive definition translates easily into most programming languages although, as we’ll see, the performance isn’t the best.
func fibsRecursion(limit int) int {
if limit <= 2 {
return limit
}
return fibsRecursion(limit-2) + fibsRecursion(limit-1)
}
This function takes an input limit and will generate the nth Fibonacci number. The function alone doesn’t solve our problem, because we still need to calculate the whole sequence of numbers, check if each is even, and add the even ones to the sum. We can wrap that functionality in a small for loop.
func sumEvenFibsRecursion(limit int) int {
sum := 0
next := 0
for i := 1; next < limit; i++ {
next = fibsRecursion(i)
if isEven(next) {
sum += next
}
}
return sum
}
Where isEven is a small helper function to cut down on typing.
func isEven(x int) bool {
if math.Mod(float64(x), 2) == 0 {
return true
}
return false
}
Ok, now we can calculate Fibonacci numbers, iterate up to a limit, check if they are even, and sum them. There are also tests and a benchmark, for completeness.
package main
import "testing"
const LIMIT int = 3999999
const SUM_LIMIT int = 4613732
func TestIsEven(t *testing.T) {
if (isEven(4) != true) || (isEven(3) != false) {
t.Fatal("isEven returned incorrect value")
}
}
func TestFibsRecursion(t *testing.T) {
firstTen := []int{1, 2, 3, 5, 8, 13, 21, 34, 55, 89}
for i, v := range firstTen {
fib := fibsRecursion(i + 1)
if fib != v {
t.Fatal("recursion gave", fib, "want", v)
}
}
}
func TestSumEvenFibsRecursion(t *testing.T) {
result := sumEvenFibsRecursion(LIMIT)
if result != SUM_LIMIT {
t.Fatal("wanted", SUM_LIMIT, "got", result)
}
}
func BenchmarkSumEvenFibsRecursion(b *testing.B) {
for i := 0; i < b.N; i++ {
sumEvenFibsRecursion(LIMIT)
}
}
We can run the tests and see that everything passes.
=== RUN TestIsEven
--- PASS: TestIsEven (0.00s)
=== RUN TestFibsRecursion
--- PASS: TestFibsRecursion (0.00s)
=== RUN TestSumEvenFibsRecursion
--- PASS: TestSumEvenFibsRecursion (0.05s)
Now on to the benchmark so we can look at the performance characteristics of this approach.
BenchmarkSumEvenFibsRecursion-4 30 46091679 ns/op
That is extremely slow, as expected. The recursive approach is doing a ton of unnecessary work. Additionally, tail-call optimization is not always supported in Go, at least there was no plan to implement TCO more broadly, which also can result in memory usage or performance characteristics that are difficult to analyze or plan for.
From a time and space complexity perspective, we can think of the space complexity first. There will be a function call, recursively, for each Fibonacci number calculated. So if we want the first 5 numbers, we’ll have 5 function calls on the stack. The depth of the stack is O(n) and memory requirement will be N * frameSize, where frameSize is the size of the frame inserted into the stack with each function call.
On the time complexity side, the short version is the bound on time complexity is O(2^n).
The slightly longer version is that the tight bound is O(Phi^n) where Phi is the so-called golden ratio 1.618… and n is the nth Fibonacci number. In other words, it’s still exponential but with a slightly smaller base. To see why, consider that the recurrence relation use to generate the sequence is proportional to the time complexity required to calculated it. At that point you can use the closed-form approximation for the Fibonacci sequence numbers themselves. Since the numbers in the sequence grow as O(Phi) then the time complexity grows that way too.
Second Attempt: Iteration
In the recursive case, we were recalculating the Fibonacci numbers all the time, which leads to a lot of wasted computation. Consider that for computing F(4) (the fourth Fibonacci number) we would compute F(3) + F(2) + F(1), but we already have F(2) and F(1) when we computed F(3), so why computer them again? Instead of starting from a limit and calling functions all the way down as our recursive function did, we can simply build up the list of Fibonacci numbers from the bottom. This allows us to use numbers already calculated to calculate the next number in the sequence.
func sumEvenFibsSlice(limit int) int {
fibs := []int{1, 2}
newElement := 0
for i := 2; newElement < limit; i++ {
newElement = fibs[i-1] + fibs[i-2]
fibs = append(fibs, newElement)
}
return sumEvens(fibs)
}
In this example, we start with a slice that has the first two numbers as given in the problem, and then appends the remaining numbers onto the slice until the new element in the sequence is greater than or equal to the limit, at which point we return the sum of the even numbers in the slice.
We can write the test and benchmark code as before.
func TestSumEvenFibsSlice(t *testing.T) {
if sumEvenFibsSlice(LIMIT) != SUM_LIMIT {
t.Fatal("")
}
}
func BenchmarkSumEvenFibsSlice(b *testing.B) {
for i := 0; i < b.N; i++ {
sumEvenFibsSlice(LIMIT)
}
}
Which gives us passing tests and a new benchmark number.
BenchmarkSumEvenFibsSlice-4 200000 6210 ns/op
This is a faster approach compared to the recursive solution, by a lot. In fact the recursive solution takes about 7400 times longer, so we’re on the right track.
Now that we have an iterative solution, many newcomers to Go will think that it makes sense to spin off a thread/goroutine to do the calculations and pass the results back over a channel for our function to use.
Winner: a simple loop
Slices perform acceptably, but they’re still relatively slow. We can do better by using a simple loop and accumulating our sum along the way. The code starts index i and j at 1, and adds and swaps them until the limit is reached. The benefit of this approach is that we are only using a few integer values, and we are only iterating until we reach the limit, so this approach is linear for our values.
NOTE that there is a caveat here as we are dealing with values which fit into a normal int type in Go. If the integers become too big and we need to use arbitrarily-large integers, we will have different performance characteristics. For our purposes though, the simple looping approach has O(n) time complexity.
func sumEvenFibsLoop(limit int) int {
sum := 0
for i, j := 1, 1; j < limit; i, j = i+j, i {
if isEven(i) {
sum += i
}
}
return sum
}
Test and benchmark:
func TestSumEvenFibsLoop(t *testing.T) {
if sumEvenFibsLoop(LIMIT) != SUM_LIMIT {
t.Fatal("sumevenfibloop")
}
}
func BenchmarkSumEvenFibsLoop(b *testing.B) {
for i := 0; i < b.N; i++ {
sumEvenFibsLoop(LIMIT)
}
}
BenchmarkSumEvenFibsLoop-4 300000 5535 ns/op
The performance of this approach is the best so far, but just barely. It outperforms the slice approach, but not by much.
Digression: Channels
A common thing newcomers do when they pick up Go is they reach for channels and goroutines. Although these are awesome tools and it’s great they are so easy to use in the language, they aren’t always good for performance. The short reason is that channels are essentially a mutable data structure, and therefore require locks. Locks are an enemy of performance, so in many tasks you will slow down your computations if you use channels and goroutines.
For example, we can use the standard approach of creating a function which returns a channel of values. We’ll drop our iterative solution from before into a function which is spun off as its own goroutine.
func fibsChannel(limit int) chan int {
output := make(chan int)
go func() {
defer close(output)
for i, j := 1, 1; j < limit; i, j = i+j, i {
output <- i
}
}()
return output
}
We can use this for our specific problem in the following way.
func sumEvenFibsChannel(limit int) int {
sum := 0
fibs := fibsChannel(limit)
for f := range fibs {
if isEven(f) {
sum += f
}
}
return sum
}
along with the accompanying tests and benchmarks.
func TestFibsChannel(t *testing.T) {
firstTen := []int{1, 2, 3, 5, 8, 13, 21, 34, 55, 89}
fibs := fibsChannel(90)
for _, v := range firstTen {
chanVal := <-fibs
if v != chanVal {
t.Fatal("fibChannel incorrect. Expected", v, "but received", chanVal)
}
}
}
func TestSumEvenFibsChannel(t *testing.T) {
if sumEvenFibsChannel(LIMIT) != SUM_LIMIT {
t.Fatal("")
}
}
func BenchmarkSumEvenFibsChannel(b *testing.B) {
for i := 0; i < b.N; i++ {
sumEvenFibsChannel(LIMIT)
}
}
All the tests pass, and we can get a look at the performance of the channels approach.
BenchmarkSumEvenFibsChannel-4 100000 18677 ns/op
At 18,677 ns/op the channels approach takes around 3 times as long as the slices approach, and about 3.4 times as long as the simple loop, so although channels and goroutines are a wonderful part of the language, they are not a good fit for all problems.
Digression: Solution by approximation
It was briefly mentioned earlier that the runtime complexity of the recursive solution is O(Phi^n) where Phi is the Golden Ratio. With some further analysis you can show that the Nth Fibonacci number can be approximated by 1/sqrt(5) * Phi^(n+1). We can use this method to generate our Fibonacci numbers as well.
func fibApprox(n int) int {
fib := (1 / math.Sqrt(5)) * math.Pow(math.Phi, float64(n+1))
return int(fib + 0.5) // BUG: This only works for postive numbers
}
func TestFibApprox(t *testing.T) {
firstTen := []int{1, 2, 3, 5, 8, 13, 21, 34, 55, 89}
for i, v := range firstTen {
fib := fibApprox(i + 1)
if fib != v {
t.Fatal("got", fib, "want", v)
}
}
}
func TestSumEvenFibsApprox(t *testing.T) {
if sumEvenFibsApprox(LIMIT) != SUM_LIMIT {
t.Fatal("")
}
}
func BenchmarkSumEvenFibsApprox(b *testing.B) {
for i := 0; i < b.N; i++ {
sumEvenFibsApprox(LIMIT)
}
}
However, although we have a closed-form solution it is not yet faster than our simple loop implementation.
BenchmarkSumEvenFibsApprox-4 200000 7769 ns/op
Part of the reason for this is because for the numbers we’re dealing with, which fit into 64 bit integers, the simple loop has an apparently linear time complexity. However, once we get into arbitrarily large numbers and need something from math/big then we won’t have the same performance characteristics and the closed-form solution may be faster, even though it does contain exponentiation. Recall that exponentiation by squaring has a computational complexity of about O(log n).
Bonus Round: Bitwise and for even/odd checking
Although the fastest approach we tested was the simple loop, we were still using the isEven() function, which used modular arithmetic to tell us if the integer was even or not. I also wanted to check to see if there would be a significant speedup from switching to bitwise operations to check the parity of the numbers.
The short version is that replacing the math.Mod() call with a bitwise and, we can determine the parity of the number in a much more computationally-efficient way.
func isEven(x int) bool {
if x&1 == 0 {
return true
}
return false
}
I had benchmarks for isEven() before and after.
Before:
BenchmarkIsEvenEven-4 30000000 43.5 ns/op
BenchmarkIsEvenOdd-4 30000000 44.8 ns/op
After:
BenchmarkIsEvenEven-4 2000000000 0.34 ns/op
BenchmarkIsEvenOdd-4 2000000000 0.34 ns/op
This is a performance improvement of 130 times.
When we use this bitwise version for the parity checking in the other algorithms, we see the expected speedups.
BenchmarkSumEvenFibsSlice-4 3000000 455 ns/op
BenchmarkSumEvenFibsRecursion-4 30 46208502 ns/op
BenchmarkSumEvenFibsLoop-4 30000000 49.7 ns/op
BenchmarkSumEvenFibsChannel-4 100000 11670 ns/op
BenchmarkSumEvenFibsApprox-4 1000000 1766 ns/op
If we wanted to further speed up the simple loop, we could remove the overhead of the function call to isEven() and inline the bitwise and.
func sumEvenFibsLoop(limit int) int {
sum := 0
for i, j := 1, 1; j < limit; i, j = i+j, i {
if i&1 == 0 {
sum += i
}
}
return sum
}
Which cuts off a bit more time, about 11%.
BenchmarkSumEvenFibsLoop-4 30000000 44.0 ns/op
Conclusion
Project Euler problems, in addition to fun programming exercises, can be great ways to refresh mathematics and computer science skills you may have forgotten or may not have used in a while. For this problem alone we got into time and memory complexity, recurence relations, recursion, channels and goroutines, bitwise operations, and testing and benchmarking in Go.
We could have gone further down the rabbit hole, especially on the mathematics side of things, but then it would be turtles all the way down and we wouldn’t be able to move on to other problems.