summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorCasey Robinson <casey@rampantmonkey.com>2015-06-15 16:19:34 -0400
committerCasey Robinson <casey@rampantmonkey.com>2015-06-15 16:19:34 -0400
commitc18576b145260e3b99c3c3aeef58b651d7a2e906 (patch)
treee7e470651afcf16981121cc46592f8366532a138
parent03477a4796c7f71cc4e025f2942431beea1549e4 (diff)
downloadfibgo-master.tar.gz
fibgo-master.tar.bz2
fibgo-master.zip
matrix form (a la Knuth)HEADmaster
-rw-r--r--main.go71
1 files changed, 71 insertions, 0 deletions
diff --git a/main.go b/main.go
index 7b909ea..59eb247 100644
--- a/main.go
+++ b/main.go
@@ -32,6 +32,10 @@ func main() {
fallthrough
case "memoize":
fmt.Printf("fib(%d) = %d\n", n, memoize(n))
+ case "q":
+ fallthrough
+ case "qmatrix":
+ fmt.Printf("fib(%d) = %d\n", n, qmatrix(n))
default:
fmt.Printf("Unknown/unimplemented method %s\n", *method)
}
@@ -74,3 +78,70 @@ func memoizeInternal(n int, cache map[int] int) int {
cache[n] = res
return res
}
+
+type matrix [][]int
+
+func qmatrix(n int) int {
+ cache := make(map[int] matrix)
+ return qmatrixInternal(n, cache)
+}
+
+func qmatrixInternal(n int, cache map[int] matrix) int {
+ if n < 2 {
+ return n
+ }
+
+ var q matrix
+ q = append(q, []int{1,1})
+ q = append(q, []int{1,0})
+ fmt.Printf("%d %d\n%d %d\n", q[0][0], q[0][1], q[1][0], q[1][1])
+
+
+ var matricies []matrix
+ i := 0
+ for n > 0 {
+ exp := n & 0x1
+ n = n >> 1
+ pow := exp << uint(i)
+ i += 1
+ if exp != 0 {
+ matricies = append(matricies, matrixPowerOfTwo(q, pow, cache))
+ }
+ }
+
+ fmt.Println("%q\n", matricies)
+
+ for len(matricies) > 1 {
+ m1 := matricies[len(matricies)-1]
+ matricies = matricies[:len(matricies)-1]
+ m2 := matricies[len(matricies)-1]
+ matricies = matricies[:len(matricies)-1]
+ matricies = append(matricies, matrixMultiply(m1,m2))
+ }
+ return matricies[0][0][1]
+}
+
+func matrixMultiply(a, b matrix) matrix {
+ c11 := a[0][0]*b[0][0] + a[0][1]*b[1][0]
+ c12 := a[0][0]*b[0][1] + a[0][1]*b[1][1]
+ c21 := a[1][0]*b[0][0] + a[1][1]*b[1][0]
+ c22 := a[1][0]*b[0][1] + a[1][1]*b[1][1]
+ var c matrix
+ c = append(c, []int{c11, c12})
+ c = append(c, []int{c21, c22})
+ return c
+}
+
+func matrixPowerOfTwo(m matrix, p int, cache map[int] matrix) matrix {
+ if p == 1 {
+ return m
+ }
+ if val, ok := cache[p]; ok {
+ return val
+ }
+
+ k := matrixPowerOfTwo(m, p/2, cache)
+ res := matrixMultiply(k,k)
+ cache[p] = res
+ return res
+}