Fibnacci by Quick Pow Matrix

fib_test.go

package mfib

import "testing"

func TestFib(t *testing.T) {
	target := []struct{ a, b int }{
		{1, 1},
		{2, 1},
		{3, 2},
		{4, 3},
		{5, 5},
		{6, 8},
		{25, 75025},
	}
	for _, fib := range target {
		if N(fib.a) != fib.b {
			t.Errorf("Fib(%d) Error: expect=%d, get = %d", fib.a, fib.b, N(fib.a))
		}
	}
}

func BenchmarkFib(b *testing.B) {
	for i := 0; i < b.N; i++ {
		N(25)
	}
}

quick.go

package mfib

import "fmt"

type matrix [2][2]int

func (m matrix) String() string {
	return fmt.Sprint(m[0], "\n", m[1])
}

func quickMatrixPow(pow int) (y matrix) {

	x := matrix{[2]int{1, 1}, [2]int{1, 0}}
	y = matrix{[2]int{1, 0}, [2]int{0, 1}}

	for ; pow > 0; pow = pow >> 1 {
		if pow&1 == 1 {
			y = mul(y, x)
		}
		x = mul(x, x)
	}
	return
}

func mul(a, b matrix) (c matrix) {
	c = matrix{}
	c[0][0] = a[0][0]*b[0][0] + a[0][1]*b[1][0]
	c[0][1] = a[0][0]*b[0][1] + a[0][1]*b[1][1]
	c[1][0] = a[1][0]*b[0][0] + a[1][1]*b[1][0]
	c[1][1] = a[1][0]*b[0][1] + a[1][1]*b[1][1]
	return
}

func N(x int) int {
	switch x {
	case 1:
		return 1
	case 2:
		return 1
	default:
		return quickMatrixPow(x - 1)[0][0]
	}
}