# Rash thoughts about .NET, C#, F# and Dynamics NAV.

## Sunday, 19. December 2010

### Compute Fib(n) in O(log n)

Filed under: F# — Steffen Forkmann at 17:07 Uhr

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: , ,

1. 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) đź™‚

Comment by Matt — Monday, 20. December 2010 um 2:42 Uhr

2. 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

3. […] 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