diff options
| -rw-r--r-- | README.md | 3 | ||||
| -rw-r--r-- | entries/shayanh/matrix.go | 40 |
2 files changed, 43 insertions, 0 deletions
@@ -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] +} |