Fibonacci benchmark correctly in Golang and Ruby

fib.rb

require 'matrix'

class Fibonacci < BasicObject

  def initialize(n)
    if n < 0
      raise ArgumentError, "only accept positive number"
    end

    unless n.is_a?(::Integer)
      raise ArgumentError, "only accept integer number"
    end

    @n = n
  end

  def iterate_adding
	  a, b = 0, 1
	  @n.times { a, b = b, a+b }
	  a
  end

  def matrix_multiplying
    m = ::Matrix[[0, 1], [1, 1]] ** @n
    v = m * ::Vector[0, 1]
    v[0]
  end

  def fast_doubling
    return _fast_doubling(@n)[0]
  end

  private
  # (Private) Returns the tuple (F(n), F(n+1)).
  def _fast_doubling(n)
    if n == 0
      return [0,1]
    end

    a, b = _fast_doubling(n / 2)
	  c = a * (b * 2 - a)
	  d = a * a + b * b

	  if n % 2 == 0
      return [c,d]
    else
      return [d, c+d]
    end
  end

end

if __FILE__ == $0
  require 'benchmark/ips'

  number = 100_000
  fib = Fibonacci.new(number)

  Benchmark.ips do |x|
    x.report("iterate adding #{number}"){ fib.iterate_adding }
    x.report("fast doubling #{number}"){ fib.fast_doubling }
    x.report("matrix multiplying #{number}"){ fib.matrix_multiplying }
    x.compare!
  end

end

FIB_BENCH_RESULT_LINUX

wujiang@jiang-docker:~$ ruby fib.rb 
Warming up --------------------------------------
iterate adding 100000
                         1.000  i/100ms
fast doubling 100000   168.000  i/100ms
matrix multiplying 100000
                        37.000  i/100ms
Calculating -------------------------------------
iterate adding 100000
                          4.113  (± 0.0%) i/s -     21.000  in   5.107523s
fast doubling 100000      1.694k (± 1.5%) i/s -      8.568k in   5.058085s
matrix multiplying 100000
                        373.944  (± 1.1%) i/s -      1.887k in   5.046696s

Comparison:
fast doubling 100000:     1694.3 i/s
matrix multiplying 100000:      373.9 i/s - 4.53x  slower
iterate adding 100000:        4.1 i/s - 411.97x  slower

wujiang@jiang-docker:~$ go test -bench=. -benchmem nouse/fib
goos: linux
goarch: amd64
pkg: nouse/fib
BenchmarkInterateAdding-4             20         101774749 ns/op         9600379 B/op     600016 allocs/op
BenchmarkFastDoubling-4             3000            444254 ns/op           10187 B/op        634 allocs/op
PASS
ok      nouse/fib       4.512s

FIB_BENCH_RESULT_MACOS

~/workspace $ ruby fib.rb 
Warming up --------------------------------------
iterate adding 100000
                         1.000  i/100ms
fast doubling 100000    61.000  i/100ms
matrix multiplying 100000
                        16.000  i/100ms
Calculating -------------------------------------
iterate adding 100000
                          5.071  (±19.7%) i/s -     25.000  in   5.020282s
fast doubling 100000    622.227  (± 4.3%) i/s -      3.111k in   5.010048s
matrix multiplying 100000
                        167.441  (± 4.2%) i/s -    848.000  in   5.073008s

Comparison:
fast doubling 100000:      622.2 i/s
matrix multiplying 100000:      167.4 i/s - 3.72x  slower
iterate adding 100000:        5.1 i/s - 122.71x  slower

~/workspace $ go test -bench=. -benchmem nouse/fib
goos: darwin
goarch: amd64
pkg: nouse/fib
BenchmarkInterateAdding-4             20          64970037 ns/op         9600654 B/op     600016 allocs/op
BenchmarkFastDoubling-4             5000            285778 ns/op           10188 B/op        634 allocs/op
PASS
ok      nouse/fib       2.842s

fib_test.go

package fib

import (
	big "github.com/ncw/gmp"
	"testing"
)

func iterateAdding(n int) *big.Int {
	a := big.NewInt(0)
	b := big.NewInt(1)

	for i := 0; i < n; i++ {
		a.Add(a, b)
		a, b = b, a
	}
	return a
}

func fastDoubling(n int) *big.Int {
	a, _, _ := _fastDoubling(n)
	return a
}

// (Private) Returns the tuple (F(n), F(n+1)).
func _fastDoubling(n int) (*big.Int, *big.Int, *big.Int) {
	if n == 0 {
		return big.NewInt(0), big.NewInt(1), new(big.Int)
	}

	a, b, c := _fastDoubling(n / 2)

	// (2*b - a)*a
	c.Mul(a, b)
	c.Lsh(c, 1)

	a.Mul(a, a)
	c.Sub(c, a)
	// a*a + b*b
	b.Mul(b, b)
	b.Add(b, a)
	if n%2 == 0 {
		return c, b, a
	}

	a.Add(c, b)
	return b, a, c
}

func BenchmarkInterateAdding(b *testing.B) {
	for i := 0; i < b.N; i++ {
		iterateAdding(100000)
	}
}

func BenchmarkFastDoubling(b *testing.B) {
	for i := 0; i < b.N; i++ {
		fastDoubling(100000)
	}
}

TODO

Compare with gmp implementation https://gmplib.org/manual/Fibonacci-Numbers-Algorithm.html

F[2k+1] = 4*F[k]^2 - F[k-1]^2 + 2*(-1)^k
F[2k-1] =   F[k]^2 + F[k-1]^2

F[2k] = F[2k+1] - F[2k-1]
At each step, k is the high b bits of n. If the next bit of n is 0 then F[2k],F[2k-1] is used, or if it’s a 1 then F[2k+1],F[2k] is used, and the process repeated until all bits of n are incorporated. Notice these formulas require just two squares per bit of n.