From e5de46c67d3edeb6e4bc96889a6594ab77f07265 Mon Sep 17 00:00:00 2001
From: Shayan Hosseini
Date: Sun, 23 Oct 2022 17:25:21 -0700
Subject: added shayanh's entry

---
 entries/shayanh/matrix.go | 40 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 40 insertions(+)
 create mode 100644 entries/shayanh/matrix.go

(limited to 'entries/shayanh/matrix.go')

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]
+}
-- 
cgit v1.2.3-70-g09d2