## The Weekly Source Code 13 - Fibonacci Edition

If you're new to this, each week I post some snippets of particularly interesting (read: beautiful, ugly, clever, obscene) source and the project it came from. This started from a belief that reading source is as important (or more so) as writing it. We read computer books to become better programmers, but unless you're reading books like Programming Pearls, you ought to peruse some Open Source projects for inspiration.

And so, Dear Reader, I present to you the *thirteenth *in a *infinite *number of posts of "**The Weekly Source Code**." Here's some source I was reading this week. I wanted to see what a Fibonacci number generator looked like in a number of different languages.

Remember (from Wikipedia) that the Fibonacci sequence looks like this:

...after two starting values, each number is the sum of the two preceding numbers. The first Fibonacci numbersalso denoted as F_{n}, for n = 0, 1, … , are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, ...

Here's a few implementations I thought contrasted nicely. There's also a great writeup on Fibonacci related things on Dustin Campbell's blog.

### F#

- Here's a basic Fibonacci function in F#.
let rec fib n = if n < 2 then 1 else fib (n-2) + fib(n-1)

- Or, if you want input and output as an F# console application:
let fib_number = int_of_string (System.Environment.GetCommandLineArgs().GetValue(1).ToString());; let rec fib n = if n < 2 then 1 else fib (n-2) + fib(n-1);; Printf.printf "\nThe Fibonacci value of %u is: %u\n" fib_number (fib fib_number);; exit 0;;

### Ruby

- Here it is in Ruby, from RubyTips.org:
x1,x2 = 0,1; 0.upto(size){puts x1; x1 += x2; x1,x2 = x2,x1}

- But that's really hard to read and kind of smooshed onto one line. A more typical console app would look like this:
class FibonacciGenerator def printFibo(size) x1,x2 = 0, 1 0.upto(size){puts x1;x1+=x2; x1,x2= x2,x1} # note the swap for the next iteration end f = FibonacciGenerator.new f.printFibo(10) # print first 10 fibo numbers end

### C#

- There's many ways to do this in C#, so let's start with a basic C# 2.0 implementation.
static int Fibonacci (int x) { if (x <= 1) return 1; return Fibonacci (x-1) + Fibonacci (x-2); }

- Now, here's a great way using C# 3.0 (actually, .NET 3.5 and System.Func from the new System.Core:
Func<INT , int> fib = null; fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

### Scala

- Lots of folks are excited about Scala, and many are calling it "the latest programmer's shiny object." It's interesting not just for its syntax, but it's full interoperability with Java. Here's a recursive Fibonacci in Scala.
def fib( n: Int): Int = n match { case 0 => 0 case 1 => 1 case _ => fib( n -1) + fib( n-2) }

### Erlang

- Here's Fibonacci in Erlang, and you can find many other implementations at LiteratePrograms.org, a great site for reading source!
fibo(0) -> 0 ; fibo(1) -> 1 ; fibo(N) when N > 0 -> fibo(N-1) + fibo(N-2) .

Which is your favorite? I like the C# 3.0 one and the F# ones. Also the Ruby double variable swap is pretty cool. They just feel right, although a close runner-up is the LOLCode implementation of Fibonacci from a few weeks back.

#### About Scott

Scott Hanselman is a former professor, former Chief Architect in finance, now speaker, consultant, father, diabetic, and Microsoft employee. He is a failed stand-up comic, a cornrower, and a book author.

About Newsletter

static int Fib(int n) { return (int)Math.Floor((Math.Pow(GoldenRation, n) - Math.Pow((1.0 - GoldenRation), n)) / Math.Sqrt(5.0)); } private readonly static double GoldenRation = (1.0 + Math.Sqrt(5.0)) / 2.0;

puts (1...size).inject([1,1]){|i,j|[i[1],i[0]+i[1]]}[1]Assuming it works as advertised the 1000th Fib number is 7033036771142281582183525487718354977018126983635873274260490 5087154537118196933579742249494562611733487750449241765991088 1863632654502236471060120533741212738673391111981393731255987 67690091902245245323403501 Anybody want to check my math?

**let rec fib n = if n < 2 then 1 else fib (n-2) + fib(n-1)**fib(0) and fib(1) both return 1 due to "if n < 2 then 1". fib(2) returns the sum of fib(0) and fib(1). Both return 1, so fib(2) gives 2, which does not seem correct. Shouldn't this read: let rec fib n = let rec fib n = if n < 2 then n else fib (n-2) + fib(n-1) So for values smaller than 2, the function will return the input value, which is correct for 0 and 1.

**return 1; // Should not return 1 when x = 0**return Fibonacci (x-1) + Fibonacci (x-2); } It should be: static int Fibonacci (int x) { if (x <= 1)

**return x;**return Fibonacci (x-1) + Fibonacci (x-2); } I love this reading-source-is-important series of yours, thanks! j

Here's a more efficient looping version based on the Ruby example - it scales linearly and copes with any reasonable value of input (anything over Fib(1476) overflows Perl's standard arithmetic functions).sub fib { (local $fib=shift)<=2 ? 1 : fib3($fib-2) + fib2($fib-1); }

Anyone know how to preserve some indenting for code snippets in comments?sub fibloop { my ($limit,$n1,$n2)=(shift(),1,1); while (--$limit) { $n1+=$n2; ($n2,$n1)=($n1,$n2); } return($n1); }

multi (:fib, 0) { 1 } multi (:fib, 1) { 1 } multi (:fib, Integer) { |n| fib(n-1) + fib(n-2) }I like the feel of the Haskell / Erlang / ML implementations best they seem less verbose But my favourite of all must be BrainF***s implementation

+++++++++++ >+>>>>++++++++++++++++++++++++++++++++++++++++++++ >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<< -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]] >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++ +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++ ++++++++++++++++++++++++++++++++++++++++++++.[-]<< <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]

static int Fibonacci(int count) { int dummy; return Fibonacci(count, out dummy); } static int Fibonacci(int count, out int previous) { switch (count) { case 0: previous = 0; return 0; case 1: previous = 0; return 1; default: int previousPrevious; previous = Fibonacci(count-1, out previousPrevious); return previous + previousPrevious; } }The boo implementation is much nicer. The same algorithm in C# runs like this:

static IEnumerableOf course, then you get to use the completely wonderful evaluation syntax:FibonacciSequence() { yield return 0; yield return 1; int x = 0; int y = 1; int z; while (true) { z = x + y; yield return z; x = y; y = z; } }

FibonacciSequence().Skip(42).First()

(define (fib n) ( ....(if (= 0 n) 1 ........(if (= 1 n) 1 ............(+ (fib (- n 1)) (fib (- n 2))) ))))(Couldn't figure out how to get spacing to work, so the periods should be spaces)

FuncThis will output:fib = null; fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n; Console.WriteLine("10th Fibonacci #: " + fib(10).ToString()); Func fib2 = fib; fib = n => n + 1; Console.WriteLine("Increment the number 10: " + fib(10).ToString()); Console.WriteLine("10th Fibonacci #: " + fib2(10).ToString() + "???");

10th Fibonacci #: 55 Increment the number 10: 11 10th Fibonacci #: 19???The problem is that your lambda is a closure around the variable "fib", so if you change what's in there later on, the lambda will automatically use the new expression stored there, rather than continuing to call itself. This is why Y-Combinators can be useful

*even in C#*. They give you one central compile-time symbol that allows your recursive lambdas to be "decoupled" from the variable references that they happened to be stored in at the time of declaration. This kind of thing you will not find explained in most online explanations of the workings of lambdas or the Y-Combinator... because it's inherently obvious if you think in pure-functional languages that this comes from: they have no variable names, so you can't refer back to them like this. In answer to that precise situation, I'm in the process of working up a couple posts on practical applications of lambdas and Y-Combinators for C# programmers, over at my (still very young) blog Turbulent Intellect. =)

static int Fibonacci (int x) { if (x <= 1) return x; return Fibonacci (x-1) + Fibonacci (x-2); }I like:

static int Fibonacci (int x) { return (x <= 1) ? x : Fibonacci (x-1) + Fibonacci (x-2); }The second is cleaner to me, although I suppose it's just a preference thing.

```
static System.Collections.Generic.IEnumerable
``` Fibonacci(int start, int count)
{
for(int iteration = start; iteration < start + count; iteration++)
yield return Fib(iteration);
}
static int Fib(int n)
{
return (int)Math.Floor((Math.Pow(GoldenRation, n) - Math.Pow((1.0 - GoldenRation), n)) / Math.Sqrt(5.0));
}
private readonly static double GoldenRation = (1.0 + Math.Sqrt(5.0)) / 2.0;

fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;(I have no idea how to keep the indentation in the code samples....) But again I would direct you to my previous comment, as a warning against careless use of recursion in lambdas.

for example I pass 21 I get 17711 which doesn't map correctly to the fibonacci sequence - the next sequence value would be 34, and the 21st value by my count is 6765.)Wrong: the 21st value is 10946. You're forgetting that the Fib sequence is traditionally denoted by Fn where n = 0, 1, 2...etc. Scott's code (both original and slightly modified) returns the correct value. 17711 is the 22nd value; 6765 is the 20th value.

If we attempt the code correction proposed in this thread, passing a 5 results in 5... there seems to be a disconnect here.Exactly--the 5th value in fib is 5: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, ... There is no disconnect here; F5 is 5. F0 is 0. F21 is 10946.

_{ #include count unsigned int ITERATIONS = 10; unsigned int f( unsigned int n ); int main() { for ( unsigned int i = 0; i < ITERATIONS; ++i ) { std::cout << f( i ) << std::endl; } return 0; } unsigned int f( unsigned int n ) { if ( n < 2 ) { return n; } return ( f( n - 1 ) + f( n - 2 ) ); } }And with template funtion:

_{ #include const unsigned int ITERATIONS = 10; template T f( T n ) { if ( n < 2 ) { return n; } return ( f( n - 1 ) + f( n - 2 ) ); } int main() { for ( unsigned int i = 0; i < ITERATIONS; ++i ) { std::cout << f( i ) << std::endl; } return 0; } }

_{ #!/usr/bin/perl my $iterations = 10; sub f($) { if ( $_[0] < 2 ) { return $_[0]; } return ( f( $_[0] - 1 ) + f( $_[0] - 2 ) ); } for ( my $i = 0; $i < $iterations; ++$i ) { print f( $i ) . "\n"; } }

_{ with Text_IO, Ada.Integer_Text_IO; use Text_IO, Ada.Integer_Text_IO; procedure Fibonacci is Iterations : constant Natural := 10; function F( N : Natural ) return Natural is begin if N < 2 then return N; end if; return ( F( N - 1 ) + F( N - 2 ) ); end F; begin for Index in 0..Iterations loop Put( F( Index ) ); Put_Line( "" ); end loop; end Fibonacci; }

Dim results As Long() Function Fibo(ByVal n As Integer) As Long If n = 0 Then Return 0 If n < 3 Then Return 1 ' The array can be of size n - 2 because we don't need slots for the n < 3 case. ReDim Preserve results(n - 2) Dim f As Func(Of Integer, Long) = AddressOf Me.calculator Return calculator(n) End Function Function calculator(ByVal x As Integer) As Long If x = 0 Then Return 0 ElseIf x < 3 Then Return 1 Else Dim index As Integer = x - 3 Dim result As Long = results(index) If result = 0 Then result = calculator(x - 1) + calculator(x - 2) results(index) = result End If Return result End If End Function

**result cache**create or replace function fibonacci (p_n in number) return number result_cache is begin if p_n in (0,1) then return 1; else return fibonacci(p_n - 1) + fibonacci(p_n - 2); end if; end; / If you do

**first**select fibonacci(5) from dual; FIBONACCI(5) ------------ 8 {After this fibonacci(5) is cached. (fibonacci(4), fibonacci(3) ... are cached too)} and

**next**select fibonacci(7) from dual; FIBONACCI(5) ------------ 21 It will use the result_cache because fibonacci(5) is cached. Now fibonacci(7) and fibonaci(6) are cached too. This result cache is cross session. If you don't want a result cache do: create or replace function fibonacci (p_n in number) return number is begin if p_n in (0,1) then return 1; else return fibonacci(p_n - 1) + fibonacci(p_n - 2); end if; end; /

static ulong fib(int n) { ulong f1 = 0; ulong f2 = 1; ulong f3 = 1; int i = 0; while (i < n) { f3 = f1 + f2; f1 = f2; f2 = f3; i++; } return f1; }

def fibonnaci(n): #Print Fibonacci sequence up to n a,b = 0, 1 while b < n: print b a, b = b, a + b

fibo(0) -> 0; fibo(1) -> 1; fibo(N) when N > 1 -> cache(fun() -> fibo(N-1) + fibo(N-2) end).The only change from the original Erlang implementation is the use of a cache function, which avoids redundant computation by remembering computed values. Erlang's process dictionary makes this function a doddle:

cache(Fun) -> case get(Fun) of undefined -> Value = Fun(), put(Fun, Value), Value; Value -> Value end.The true beauty of this solution is that the function itself serves as the cache key, thus we can cache any idempotent computation, not just fibo.

use Memoize; memoize('fib'); sub fib { my $n = shift; return $n if $n < 2; fib($n-1) + fib($n-2); }

static ulong fib(int n) { ulong f1 = 0; ulong f2 = 1; [snip]....[/snip]-] But you need to return f3 NOT f1 -- I ran it and tried it so trust me. Did you write the code without testing? Impressive? I know another guy who debugs in his brain. :-) Shakespeare said,return f1}

*"He who parses code with his brain, twitcheth when he recites code, alas. but soft what light through yon window shines -- 'tis my compiler, she is the east."*Seriously, I agree with your non-recursive version. You are obviously the smartest banana in the bunch.

static void fib(ref long pp, ref long np, ref long ip){ long nt = pp + np; pp = np; np = nt; ip--; } static long Fib(long n0) {One thing to point out is that for the price of one additional time through the loop, you can avoid the ugly check for 0 that so many of the solutions have. This actually isn't a "price" in the recursive solution but a savings since the check for 0 is done every recursive call. In light of this example, it's really a bit hard to justify why I'd want to use any of the 3.5 features. I don't think they'd make this either faster or terser. Maybe I'm wrong, though. I'm brand new to 3.5 and I was hoping I could use an anonymous type/lambda function for fib but there doesn't seem to be any way to specify an anonymous type as the argument to a lambda expression. I was hoping for something like (and again, I know this doesn't work):long p = 0, n = 1, i = n0; for ( ; i > 0;fib(ref p, ref n, ref i)) ; return p;}

fib = var (int p, int n, int i) =>new(n, n+p, i-1)Assuming you get my intention here, is there any way to do this? I gave up and just made fib a static and everything works fine. In the end, I'm not sure the static doesn't read easier and run faster. I also implemented this using a list and this recursive version is about twice as fast as the list version.

static long Fib(long n0) {// Don't see any way to avoid this check, but since non-recursive, not a perf problem anyway if (n0 == 0) return 0; List}lst = new List () { 0, 1 }; while (--n0 > 0) lst.Add(lst[lst.Count - 1] + lst[lst.Count - 2]); return lst[lst.Count - 1];

static long Fib(long n0) {Using this method took about 30 ms to figure all fibonacci numbers between 1-93 one thousand times on my machine (93 because it's the biggest F(n) that still fits in a long).long p = 0, n = 1, nt; for (; n0 > 0; n0--) {}nt = p + n; p = n; n = nt;} return p;

// this is declared in .NET 3.5 (System.Core.dll), but you can just declare it yourself in .NET 2.0 public delegate TResult Func(T t); public static void Main() { Func Fib = null; Fib = Memoize( delegate(long x) { return (x <= 1) ? x : Fib(x - 1) + Fib(x - 2); }); // or using lambdas in C# 3.0: Fib = Memoize (x => (x <= 1) ? x : Fib(x - 1) + Fib(x - 2)); // same as Fib = Memoize((long x) => (x <= 1) ? x : Fib(x - 1) + Fib(x - 2)); // (notice type "long" declared as generic type parameter // or lambda parameter (long x) type, or both (redundant)) long result = Fib(100); } public static Func Memoize (Func f) { Dictionary cache = new Dictionary (); return delegate(T t) { TResult value; if(!cache.TryGetValue(t, out value)) { value = f(t); cache.Add(t, value); } return value; }; }

**Just click HERE**P.S. I think html enabled comments is bad idea ... ;)

delegate int Self(Self f, int n); FuncThe explicit delegate constructor call is required by the compiler in order to allow immediate execution of the first lambda.fib = i => new Self((f, j) => j <= 2 ? 1 : f(f, j - 1) + f(f, j - 2)) ( (f, j) => j <= 2 ? 1 : f(f, j - 1) + f(f, j - 2), i );

def fibonacci(n) a, b = 0, 1 n.times { a, b = a + b, a } a endPersonally I find the Ruby variant the most elegant, because it has no if/case statements and it doesn't use recursion. If fact, this little function packs in a lot of the reasons why Ruby code is so beautiful (n.times, the swap, compact code). OK, I'm gushing about Ruby again... I'll stop. :)

let fib (n) = match n with | _ when n = 0I -> 0I | _ when n = 1I -> 1I | n -> let rec fibaid tuple = match tuple with | (a, _, x) when a = 0I -> x | (n, previous, current) -> fibaid (n-(1I), current, previous + current) fibaid (n-(1I), 0I, 1I)

**Jose Luis Chavez del Cid**

f(1000) in 0.79 msec. f(10000) in 0.96 msec. f(100,000) in 2.92 msec. f(1,000,000) in 12.99 msecNo other recursive technique had this performance!

public static ulong Fibonacci(ulong n) { ulong t = 0, i = 0, v = 0, w; do { w = v; v = t; t = i < 2 ? i : t + w; } while (i++ < n); return t; } f(1000) in 0.79 msec. f(10000) in 0.96 msec. f(100,000) in 2.92 msec. f(1,000,000) in 12.99 msec ... No other recursive technique had this performance!Do you use

**ulong**??

Comments are closed.