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

"Every solution will only lead to new problems."

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:

Fibonacci Q-Matrix

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

printfn "%A" (fib 49)
Tags: , ,

Monday, 6. December 2010

Sudoku solver in F#

Filed under: F#,Kata — Steffen Forkmann at 15:07 Uhr

On my flight to the US I had a small competition with my dad. He was solving a Sudoku and I tried to write a generic solver in the same time. I admit he was a little bit faster but anyway I put my code on github.

Tags: ,