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

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