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

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)