High-performance Fibonacci numbers program 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:

Interview question

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

The sequence Fn of Fibonacci numbers is defined by the following relation:

Some examples of Fibonacci numbers:

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 optimise 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 optimisation 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 optimise 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 optimise 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. Fourtanetully, 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!


Tags:

#algorithm #fibonacci #go #interview #optimisation #performance #sequence


You may also be interested in:



comments powered by Disqus