Merge branch 'main' of github.com:braxtonhall/fib

1 files changed, 40 insertions, 0 deletions

diff --git a/entries/shayanh/matrix.go b/entries/shayanh/matrix.go
new file mode 100644
index 0000000..3f374cb
--- /dev/null
+++ b/entries/shayanh/matrix.go
@@ -0,0 +1,40 @@
+package main
+
+type fibmat [2][2]int
+
+func matmul(m1 fibmat, m2 fibmat) (m3 fibmat) {
+	for i := 0; i < 2; i++ {
+		for j := 0; j < 2; j++ {
+			for k := 0; k < 2; k++ {
+				m3[i][j] += m1[i][k] * m2[k][j]
+			}
+		}
+	}
+	return
+}
+
+func matpow(m fibmat, n int) fibmat {
+	if n == 0 {
+		return [2][2]int{
+			{1, 0},
+			{0, 1},
+		}
+	} else if n%2 == 0 {
+		t := matpow(m, n/2)
+		return matmul(t, t)
+	} else {
+		t := matpow(m, n-1)
+		return matmul(t, m)
+	}
+}
+
+func fib(n int) int {
+	m := matpow(
+		[2][2]int{
+			{1, 1},
+			{1, 0},
+		},
+		n,
+	)
+	return m[0][1]
+}