Geeks With Blogs
Bob Palmer's Developer Blog .NET, SQL, and Silverlight Development

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


Comments on this post: Fibonacci numbers in F#

# re: Fibonacci numbers in F#
Requesting Gravatar...
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

Left by fbcocq on Apr 04, 2010 10:13 AM

# re: Fibonacci numbers in F#
Requesting Gravatar...
Thanks for the feedback! I went ahead and adjusted the original code to use the BigInt v. default of Int - and that's a very nice alternate solution.
Left by Bob Palmer on Apr 04, 2010 10:27 AM

# re: Fibonacci numbers in F#
Requesting Gravatar...
this is my version of FIBONACCI (happy coding)

let rec fibonacci num1 num2 x =
let x = (x - 1)
printf "%A " num1
match x with
| _ when x > 0 -> fibonacci (num2) (num1+num2) x
|_->()
Left by Winston Gubantes on Jul 06, 2010 5:58 AM

# re: Fibonacci numbers in F#
Requesting Gravatar...
First of all thank you for the code - I had similar idea but could not wrap my head around accumulator and tail, it clicked when I read this article.

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
Left by sremani on Sep 20, 2014 7:54 AM

Your comment:
 (will show your gravatar)


Copyright © BobPalmer | Powered by: GeeksWithBlogs.net