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 numbers also denoted as Fn, 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, ...
...after two starting values, each number is the sum of the two preceding numbers. The first Fibonacci numbers also denoted as Fn, for n = 0, 1, … , are:
Here's a few implementations I thought contrasted nicely. There's also a great writeup on Fibonacci related things on Dustin Campbell's blog.
let rec fib n = if n < 2 then 1 else fib (n-2) + fib(n-1)
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;;
x1,x2 = 0,1; 0.upto(size){puts x1; x1 += x2; x1,x2 = x2,x1}
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
static int Fibonacci (int x) { if (x <= 1) return 1; return Fibonacci (x-1) + Fibonacci (x-2); }
Func<INT , int> fib = null; fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
def fib( n: Int): Int = n match { case 0 => 0 case 1 => 1 case _ => fib( n -1) + fib( n-2) }
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.
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]
sub fib {(local $fib=shift)<=2 ? 1 : fib3($fib-2) + fib2($fib-1);}
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) }
+++++++++++>+>>>>++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-<-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<-]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<+>>[-]]<<<<<<<]>>>>>[++++++++++++++++++++++++++++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++++++++++++++++++++++++++++++++++++++++++++++.[-]<<<<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<[-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]
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; } }
static IEnumerable<int> 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)))))))
Func<int, int> fib = null;fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;Console.WriteLine("10th Fibonacci #: " + fib(10).ToString());Func<int, int> fib2 = fib;fib = n => n + 1;Console.WriteLine("Increment the number 10: " + fib(10).ToString());Console.WriteLine("10th Fibonacci #: " + fib2(10).ToString() + "???");
10th Fibonacci #: 55Increment the number 10: 1110th Fibonacci #: 19???
static int Fibonacci (int x){ if (x <= 1) return x; return Fibonacci (x-1) + Fibonacci (x-2);}
static int Fibonacci (int x){ return (x <= 1) ? x : Fibonacci (x-1) + Fibonacci (x-2);}
fib = n =>n > 1 ? fib(n - 1) + fib(n - 2) : n;
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.)
If we attempt the code correction proposed in this thread, passing a 5 results in 5... there seems to be a disconnect here.
</i>
class foo
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
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; }
fibo(0) -> 0;fibo(1) -> 1;fibo(N) when N > 1 -> cache(fun() -> fibo(N-1) + fibo(N-2) end).
cache(Fun) -> case get(Fun) of undefined -> Value = Fun(), put(Fun, Value), Value; Value -> Value end.
static ulong fib(int n) { ulong f1 = 0; ulong f2 = 1;[snip]....[/snip] return f1 }
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) { long p = 0, n = 1, i = n0; for ( ; i > 0;fib(ref p, ref n, ref i)) ; return p; }
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)
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<long> lst = new List<long>() { 0, 1 }; while (--n0 > 0) lst.Add(lst[lst.Count - 1] + lst[lst.Count - 2]); return lst[lst.Count - 1];}
// Don't see any way to avoid this check, but since non-recursive, not a perf problem anyway if (n0 == 0) return 0; List<long> lst = new List<long>() { 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) { long p = 0, n = 1, nt; for (; n0 > 0; n0--) { nt = p + n; p = n; n = nt; } return p; }
long p = 0, n = 1, nt; for (; n0 > 0; n0--) { nt = p + n; p = n; n = nt; } return p;
nt = p + n; p = n; n = nt;