Tag Archives: python

Fastest way to compute Fibonacci Number

While we all know that matrix exponentiation is asymptotically fastest way to compute NthFibonacci number, there is a still faster way- If we know F(k) and F(k+1), then we can find F(2k) = F(k)[2F(k+1) – F(k)] F(2k+1) = F(k+1)2 + F(k)2 This is fast doubling. Here … Continue reading

Posted in Programming | Tagged | 8 Comments