As you may have gathered from some of my previous posts, I've been spending some quality time at Project Euler. Normally I do my solutions in C#, but since I have also started learning F#, it only made sense to switch over to F# to get my math coding fix.

This week's post is just a small snippet - spefically, a simple function to return a fibonacci number given it's place in the sequence. One popular example uses recursion:

let rec fib n = if n < 2 then 1 else fib (n-2) + fib(n-1)

While this is certainly elegant, the recursion is absolutely brutal on performance. So I decided to spend a little time, and find an option that achieved the same functionality, but used a recursive function. And since this is F#, I wanted to make sure I did it without the use of any mutable variables.

Here's the solution I came up with:

let rec fib (n1 : bigint) (n2 : bigint) c =

if c = 1 then

n2

else

fib n2 (n1+n2) (c-1);;

let GetFib num =

(fib 1I 1I num);;

printfn "%O" (GetFib 1000);;

Essentially, this function works through the sequence moving forward, passing the two most recent numbers and a counter to the recursive calls until it has achieved the desired number of iterations. At that point, it returns the latest fibonacci number.

(Edited to change from Int to BigInt - Thanks for the feedback!)

Enjoy!

Posted on Saturday, April 3, 2010 7:27 PM | Back to top

Your solution is causing an integer overflow at some point and delivering wrong results. See here for a hint at what point int stops being adequate: http://planetmath.org/encyclopedia/ListOfFibonacciNumbers.html

Here's mine:

let fibGen (a : bigint, b : bigint) = let next = a + b Some(next, (b, next))

let res = Seq.unfold fibGen (0I, 1I) |> Seq.nth 1000

http://planetmath.org/encyclopedia/ListOfFibonacciNumbers.html

Here's mine:

let fibGen (a : bigint, b : bigint) =

let next = a + b

Some(next, (b, next))

let res = Seq.unfold fibGen (0I, 1I)

|> Seq.nth 1000

let rec fibonacci num1 num2 x =

let x = (x - 1)

printf "%A " num1

match x with

| _ when x > 0 -> fibonacci (num2) (num1+num2) x

|_->()

My slight modification (in my case n=1 fib1 = 0..) and var name change for my understanding.

let rec fib prev curr counter = if counter = 2 then

curr

else

//printfn "%A" counter

fib curr (curr + prev) (counter - 1)

let getFib n = fib 0 1 n