- We can represent any number with a power of (2 or 3 or anything). Evidence? The binary system 🙂
So we can represent any number with
log nbits and using 2 as the exponent.
f(n) = f(n-1) + f(n-2)=>
f(n) = 1*f(n-1) + 1*f(n-2)
[f(n)] = |1 1| * |f(n-1)| |f(n-2)|
We should make the matrix a square because that would make matrix multiplication possible as a matrix exponent.
Eventually we need an exponential of the first matrix.
| f(n) | = | 1 1 | * | f(n-1) | | f(n-1) | | 1 0 | | f(n-2) | | f(n) | = | 1 1 | *pow(n-1) | f(1) | | f(n-1) | | 1 0 | | f(0) |
- Use memoization. Get the Nth number. Represent the number as binary. e.g.
- We need to calculate
23 -1 = 22ndexponent.
22 = 10110
- We need f(0) * f(2) * f(4).
Written with StackEdit.