Hacker News
new
|
past
|
comments
|
ask
|
show
|
jobs
|
submit
login
msds
on Dec 17, 2014
|
parent
|
context
|
favorite
| on:
The Nth Fibonacci Number in O(log N)
If you diagonalize the matrix in the problem, the formula pops out pretty quickly.
hacknat
on Dec 17, 2014
[–]
Nice catch, is that from Knuth's book?
dbaupp
on Dec 17, 2014
|
parent
[–]
Diagonalization is a fairly standard mathematical trick for doing matrix powers easily. If X is some matrix that can be diagonalised as
X = P^(-1) D P
then
X^n = (P^(-1) D P)^n = P^(-1) D^n P
Guidelines
|
FAQ
|
Lists
|
API
|
Security
|
Legal
|
Apply to YC
|
Contact
Search:
