Skip to content

Instantly share code, notes, and snippets.

@mengzhuo
Created June 12, 2017 02:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mengzhuo/267267c78162844b9d898adfbb4b7f56 to your computer and use it in GitHub Desktop.
Save mengzhuo/267267c78162844b9d898adfbb4b7f56 to your computer and use it in GitHub Desktop.
Fibnacci by Quick Pow Matrix
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)
}
}
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]
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment