Merge pull request #11 from shayanh/main

added shayanh's entry

2 files changed, 43 insertions, 0 deletions

diff --git a/README.md b/README.md
index a3926aa..3944068 100644
--- a/README.md
+++ b/README.md
@@ -31,6 +31,9 @@ For a submission to the upcoming "Reclaim your space" exhibition at [Hatch Art G
 ### [`Metroxe`](https://github.com/Metroxe)
 - [`html`](./entries/Metroxe/index.html)
 
+### [`shayanh`](https://github.com/shayanh)
+- [`matrix`](./entries/shayanh/matrix.go)
+
 ### [`Tarcisio-Teixeira`](https://github.com/Tarcisio-Teixeira)
 - [`logn?`](./entries/Tarcisio-Teixeira/fib.py)
 
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]
+}