# High-performance Fibonacci numbers generator in Go

In this post, I would like to share how to implement a high-performance Fibonacci numbers generator in Go. I decided to write this post after I found the following interview question:

Write a program that calculates a given Fibonacci number. Demonstrate the ability to optimize your solution. What approach would you take in order to be able to calculate any Fibonacci number?

So what the Fibonacci numbers really are? Fibonacci numbers are no more than a sequence Fn of numbers defined by the following relation:

\begin{aligned}F_n & = F_{n-1} + F_{n-2} \\ F_0 & = 0 \\ F_1 & = 1 \end{aligned}

A few examples of Fibonacci numbers:

\begin{aligned} F_2 & = 1 \\ F_3 & = 2 \\ F_4 & = 3 \\ F_5 & = 5 \\ F_6 & = 8 \\ F_7 & = 13 \\ F_8 & = 21 \\ F_9 & = 34 \\ F_{10} & = 55 \\ & \dots \\ F_{42} & = 267,914,296 \\ \end{aligned}

## Recursive approach

When you look at the Fibonacci algorithm, it seems to be very straightforward to implement in nearly any programming language. Our Go implementation is as follows:

package fib

func Fibonacci(n uint) uint {
if n <= 1 {
return n
}
return Fibonacci(n-1) + Fibonacci(n-2)
}


We add our Fibonacci function unit tests. We also need a benchmark function because there was a request to demonstrate the ability to optimize our solution. So we add the following test and benchmark functions.

package fib

import "testing"

func BenchmarkFibonacci(b *testing.B) {
for i := 0; i < b.N; i++ {
Fib(10)
}
}

func BenchmarkFibonacci(b *testing.B) {
for i := 0; i < b.N; i++ {
Fib(20)
}
}

func TestFibonacci(t *testing.T) {
data := []struct {
n    uint
want uint64
}{
{0, 0}, {1, 1}, {2, 1}, {3, 2}, {4, 3}, {5, 5}, {6, 8}, {10, 55}, {42, 267914296},
}

for _, d := range data {
if got := Fibonacci(d.n); got != d.want {
t.Errorf("Invalid Fibonacci value for N: %d, got: %d, want: %d", d.n, got, d.want)
}
}
}


When you run the above unit test function, it finishes successfully. So our implementation is correct. Now let’s check the performance test results. The performance results are important as they give us a reference point to our optimization process.

BenchmarkFibonacci_10-8   5000000      368 ns/op     0 B/op     0 allocs/op
BenchmarkFibonacci_20-8     30000    45743 ns/op     0 B/op     0 allocs/op


As you can see the performance test shows that calculation of 10th Fibonacci number takes about 368 ns/op (results on your machine may be slightly different), however, calculations of 20th Fibonacci number takes 45,743 ns/op, which is around 125 times longer!. Really? Why is that? If you amend the Fibonacci function and add a function execution counter, you see that the function is executed 177 times for 10th Fibonacci number and 21,891 times for the 20th one. When you carefully trace or debug function call, you notice that there are lots of redundant calls. And thanks to that we can demonstrate the ability to optimize our implementation of the Fibonacci algorithm.

## Sequential approach

Our recursive implementation provides correct results but it is very inefficient. So what can we do in order to improve that? Well, first, let’s have a look at the Fibonacci algorithm. Simplifying it, the algorithm is nothing but a sum of N numbers. So let’s take this approach. We start from 0 and 1 and we will start adding subsequent sums.

package fib

func Fibonacci(n uint) uint64 {
if n <= 1 {
return uint64(n)
}

var n2, n1 uint64 = 0, 1

for i := uint(2); i < n; i++ {
n2, n1 = n1, n1+n2
}

return n2 + n1
}


Our unit test passes successfully. Now let’s check our benchmarks.

BenchmarkFibonacci_10-8  200000000   6.71 ns/op    0 B/op   0 allocs/op
BenchmarkFibonacci_20-8  100000000  12.8 ns/op     0 B/op   0 allocs/op


Now we can see an enormous improvement. First, calculation of the 10th number of Fibonacci sequence takes about 50 times faster than in the recursive approach. Second, calculation of the 20th number of the Fibonacci sequence is twice as long as calculation of the 10th number. That means we got nearly linear growth. So the implementation of sequential approach demonstrates the ability to optimize our solution.

Our Fibonacci function returns a 64 bit unsigned integer value. Maximum value that can be stored in that data type is 18,446,744,073,709,551,615. That means we can return correct value of 93th Fibonacci number, which is 12,200,160,415,121,876,738. The 94th sequence number (19,740,274,219,868,223,167) would require 65-bit long variable.

## Calculation of large Fibonacci numbers

How shall I approach this problem? The first reaction would be to use 128-bit integer variable. Unfortunately, Go does not have one (yet). But even then, there is one of the Fibonacci numbers that will not fit into 128-bit integer and we would need 256-bit integer and so on. Fortunately, Go has a package called math/big and its Int type that will be very handy in this implementation.

Our Fibonacci implementation using the sequential approach and big.Int looks as follows:

package fib

// FibonacciBig calculates Fibonacci number using bit.Int
func FibonacciBig(n uint) *big.Int {
if n <= 1 {
return big.NewInt(int64(n))
}

var n2, n1 = big.NewInt(0), big.NewInt(1)

for i := uint(1); i < n; i++ {
n2.Add(n2, n1)
n1, n2 = n2, n1
}

return n1
}


And our unit test and benchmark functions

func BenchmarkFibonacciBig_10(b *testing.B) {
for i := 0; i < b.N; i++ {
FibonacciBig(10)
}
}

func BenchmarkFibonacciBig_20(b *testing.B) {
for i := 0; i < b.N; i++ {
FibonacciBig(20)
}
}

func TestFibonacciBig(t *testing.T) {
data := []struct {
n    uint
want int64
}{
{0, 0}, {1, 1}, {2, 1}, {3, 2}, {4, 3}, {5, 5}, {6, 8}, {10, 55}, {42, 267914296},
}

for _, d := range data {
if got := FibonacciBig(d.n); got.Int64() != d.want {
t.Errorf("Invalid Fibonacci value for N: %d, got: %d, want: %d", d.n, got, d.want)
}
}
}


The unit function finished successfully. The benchmark functions show the FibonacciBig is not that efficient as Fibonacci function, however, it is still efficient enough.

BenchmarkFibonacciBig_10-8   5000000  324 ns/op   160 B/op  4 allocs/op
BenchmarkFibonacciBig_20-8   3000000  512 ns/op   160 B/op  4 allocs/op


Now we can calculate correct values of high Fibonacci numbers e.g.

package main

import (
"fmt"
"github.com/t-pwk/go-fibonacci"
)

func main() {
fmt.Println("100: ", fib.FibonacciBig(100))
fmt.Println("200: ", fib.FibonacciBig(200))
fmt.Println("300: ", fib.FibonacciBig(300))
fmt.Println("400: ", fib.FibonacciBig(400))
}


Gives

100:  354224848179261915075
200:  280571172992510140037611932413038677189525
300:  222232244629420445529739893461909967206666939096499764990979600
400:  176023680645013966468226945392411250770384383304492191886725992896575345044216019675


Fibonacci implementation in Go can be found at https://github.com/T-PWK/go-fibonacci .

Happy coding!