Leonardo Pisano (Leonardo Fibonacci, or simply Fibonacci meaning "filius nacci", the son of Nacci) was born in Pisa, Italy in about 1170 (the place where I live). He is well known for his Fibonacci Numbers.
Can you compute the Fibonacci numbers in optimal time?
We can write the Fibonacci formula in matrix form
ReplyDeletex(i+1) | 1 1 | x(i)
= | |
x(i) | 1 0 | x(i-1)
or y(i) = F y(i-1) and y(0) = [0 1], or simply
y(i) = F^n y(0). We must efficently calculate F^n.
This can be calculated using the Caley-Hamilton Theorem (A matrix is root of its characteristic polynomial). We obtain p(a) = -a(1-a) -1 and then F^2-F-I = 0 ==> F^2 = F+I. The divide et impera.