Today I learned a neat way to compute the n.th Fibonacci number in O(log n) time. The idea is that we can compute the Fibonacci Q-Matrix in O(log n) by using recursive powering:
And here is a simple implementation in F#:
let q1 = 1I,1I,1I,0I
let mult (a11,a12,a21,a22) (b11,b12,b21,b22) =
a11 * b11 + a12 * b21,
a11 * b12 + a12 * b22,
a21 * b11 + a22 * b21,
a21 * b12 + a22 * b22
let sq x = mult x x
let rec pow x n =
match n with
| 1 -> x
| z when z % 2 = 0 -> pow x (n/2) |> sq
| _ -> pow x ((n-1)/2) |> sq |> mult x
let fib n =
let _,x,_,_ = pow q1 n
x
printfn "%A" (fib 49)
Tags: divide-and-conquer, F#, fibonacci
While you’re at it, you can just calculate a closed form solution using the eigenvalues and eigenvectors of [1 1; 1 0] that works in O(1) 🙂
Here’s the gist:
http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci-sequence.html
Comment by Matt — Monday, 20. December 2010 um 2:42 Uhr
Hi Matt,
you can’t calc a power of a real number (with arbitrary precision) in O(1) on a standard computer.
Regards Steffen
Comment by Steffen Forkmann — Monday, 20. December 2010 um 8:04 Uhr
[…] Steffen Forkmann’s Compute Fib(n) in O(log n) “Today I learned a neat way to compute the n.th Fibonacci number in O(log n) time. The idea is that we can compute the Fibonacci Q-Matrix in O(log n) by using recursive powering” […]
Pingback by F# Discoveries This Week 12/30/2010 « F# Central — Thursday, 30. December 2010 um 5:52 Uhr