Fibonacci matrix-exponentiation: Difference between revisions
m
→{{header|Haskell}}
(→{{header|Haskell}}: Matrix exponentiation for a symmetric matrix) |
|||
Line 379:
seeFib :: Integer -> String
seeFib n = start ++ xs ++ " ... " ++ (show . rem x $
where
start = "Fibonacci(2^" ++ (show n) ++") = "
x = fib (2^n)
xs = take 20 $ show x
Line 478:
</pre>
===Matrix exponentiation for a symmetric matrix===
We will use a property of commuting symmetric matrices.
<lang Haskell>import System.CPUTime (getCPUTime)▼
<lang Haskell>-- https://yutsumura.com/symmetric-matrices-and-the-product-of-two-matrices/
▲-- if X,Y are two symmetric matrices of same size and if they commute then X*Y is a symmetric matrix
▲-- it means to compute Z = X*Y, only terms on and below the diagonal should be computed (then use Z[j][i] = Z[i][j]).
▲-- At each step of the exponentiation of a symmetric matric, we multiply 2 symmetric matrices which commute.
phi :: Double
| |||