Scott Hanselman

I kinda like the Erlang one the best. It reminds me of how you might describe the Fibo seq in a math book.

Scott,

All but the Ruby implementation must be thrown to the trash immediately!
Fibonacci is the perfect example of bad use of recursion: It doesn't scale at all.
Why?
Look at F(n) = F(n-1)+F(n-2).
Develop it somewhat:
F(n) = (F(n-2)+F(n-3)) + F(n-2) -> So far you already computed F(n-2) twice. Go one level deeper and you realize you compute F(n-3) 4 times! Who said exponential? ;-)

The loop implementation used in your Ruby sample solves this problem.

My current favorite Fibonacci implementation is the Thread Pool example from MSDN.

Language-wise, I prefer the C# versions as they are the clearest to me.
However, the algorithm is not very efficient. While not as easy to read, the following is much more efficient:

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;

I prefer to use the single formula solution rather than the recurrance one. As Serge says, recurrance brings performance issues. You can't even compute F(50) on a fast machine. Try to use the formula given at the link
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html

But the syntax are beautiful, though.

Actually the one that Brian gave is the formula.

Can I win a prize for this confusing version from ruby?

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?

Hmmm.

Have to agree with Serge in part, however a tail recursive implementation in Erlang will smoke the Ruby example.

Hi Scott,

How did you get the C#3.0 version to compile? Func is generic, as far as I can tell. Am I missing something?

I like the idea, but I'm not sure I think concise = best.

Which of the code snippets would I be most glad to see 6 months after writing it?

Maybe Don Box is right when he claimed VB was good to read. :)

Still, I love your idea of posting this kind of stuff. It makes me think, which is always good.

Best regards,
Richard
http://richardbushnell.net

I compiled it with VS 2008, I think Func is inside System.Core.

If I understand the F# code correctly: 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.

Oh God, I don't understand any of this any more. I need to get out of programming! <:-\

Scott - the obvious one you've not got is the Haskell version for returning an infinite list of Fibonacci numbers:

fibonacci n = fib!!n where fib = 1 : 1 : zipWith (+) fib (tail fib)

That should mess with your head some :-)

Basically, the 'zipWith (+) fib (tail fib)' takes the infinite list of fibonacci numbers returned by fib and the same list with its first element removed and returns a third list made up of the sum of the elements with the same index (so result[n] = fib[n] + (tail fib)[n]). The '1:1:' at the start seeds fib with the members it needs to be able to deduce the rest of the list.

Is it performant? Well, using ghci (the REPL version of the GHC compiler, using bytecode, IIUC), the 60000th fibonacci number returns pretty much instantaneously). I tried 600000, but it was wanting too much memory :-)

Scott - the obvious one you've not got is the Haskell version for returning an infinite list of Fibonacci numbers:

fibonacci n = fib!!n where fib = 1 : 1 : zipWith (+) fib (tail fib)

That should mess with your head some :-)

Basically, the 'zipWith (+) fib (tail fib)' takes the infinite list of fibonacci numbers returned by fib and the same list with its first element removed and returns a third list made up of the sum of the elements with the same index (so result[n] = fib[n] + (tail fib)[n]). The '1:1:' at the start seeds fib with the members it needs to be able to deduce the rest of the list.

Is it performant? Well, using ghci (the REPL version of the GHC compiler, using bytecode, IIUC), the 60000th fibonacci number returns pretty much instantaneously). I tried 600000, but it was wanting too much memory :-)

Well the F# one does it for me followed a close 2nd by C#. Not so sure about the ruby swap on next iteration, using that kind of syntax could introduce some very hard to find issues in code , tdd or no tdd

Scott,
There's a subtle bug on your C# version. Instead of:

static int Fibonacci (int x)
{
if (x <= 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

Perl:
Compact recursive version. Got to agree with Serge that calculating fibonacci numbers via recursion is very bad, it's tempting because it seems obvious but this example effectively grinds to a halt on a 2.2Ghz Core Duo at around Fib(32).

sub fib {
(local $fib=shift)<=2 ? 1 : fib3($fib-2) + fib2($fib-1);
}

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 fibloop {
my ($limit,$n1,$n2)=(shift(),1,1);
while (--$limit) {
$n1+=$n2;
($n2,$n1)=($n1,$n2);
}
return($n1);
}

Anyone know how to preserve some indenting for code snippets in comments?

Hi Scott,

I use an iterative version in http://codeplex.com/dsa.

This is a pretty implementation in Ruby that uses pattern matching, Its not ultra efficient but it is pretty, provided you have the multi gem installed (see here)

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

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

How about boo? Not sure how to format as code, so whitespace won't be visible:

def fibonacci():
a, b = 0, 1
while true:
yield b
a, b = b, a+b

Oh, I know more about it.

The bug in the C#3 example is that it's not showing the generic type parameters. It's actually Func<int, int> at the start. You can see it if you view the source of the post. :)

I wouldn't recommend running fib(50), though.

The problem that I (and clearly many others) have with the examples is that they don't use accumulators. I mean, I know we're not meant to worry about performance, but O(2^n) is unacceptable for anything other than very small numbers. Sadly, once you strip out the naive implementation, it's not possible to express using the "nice" C#3 syntax.

e.g.

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 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;
}
}

Of course, then you get to use the completely wonderful evaluation syntax:

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

You could also use pattern matching to create what I believe is a more readable concise solution in F# and Haskell.

In the c# version, system.core defines Func with generic requirements. In a console only project, you need to define the function like this...

Func<int,int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

I suspect that those who are able to compile the application are using a Func that is declared elsewhere.

Best regards,

Hey Now Scott,
I really like this series. I haven't heard Fibonacci for about 10 years. As soon as I saw it it caught my attention & thought I remember that.
Hanselminutes Fan,
Catto

I think Mike (above) got it wrong
I made it

> fib:fib(1000).
43466557686937456435688527675040625802564660517371780402481729089536555
41794905189040387984007925516929592259308032263477520968962323987332247
1161642996440906533187938298969649928516003704476137795166849228875

I think he computed fib(1001)

Question - to sort out the sheep from the goats - how many of the above programs get the answer right - and how long do they take? Does the program that computes the square root of five get the same answer as I do for fib(10000)?

Here's my program (iterative Erlang)

-module(fib).
-export([time_fib/1, fib/1]).

time_fib(N) -> timer:tc(fib, fib, [N]).

fib(N) -> fib(N, 1, 0).

fib(0, _, B) -> B;
fib(N, A, B) -> fib(N-1, B, A+B).


fib 10000 took 53 ms to compute (on a very slow 1.062 GHz machine)

> fib:time_fib(10000)
{53086,
3364476487643178326662161200510754331030214846068006390656476997468008
1442166662368155595513633734025582065332680836159373734790483865268263
0408924630564318873545443695598274916066020998841839338646527313000888
3026923567361313511757929743785441375213052050434770160226475831890652
7890855154366159582987279682987510631200575428783453215515103870818298
9697916131278562650331954871402142875326981879620469360978799003509623
0229102636813149319527563022783762844154036058440257211433496118002309
1208287046088923962328835461505776583271252546093591128203925285393434
6209042452489294039017062338889910858410651831733604374707379085526317
6432573399371287193758774689747992630583706574283016163740896917842637
8624212835258112820516370298089332099905707920064367426202389783111470
0540749984592503606335609338838319233867830561364353518921332797329081
3373264265263398976392272340788292817795358057099369104917547080893184
1056146322338217465637321248226383092103297701648054726243842374862411
4530938122065649140327510866433945175121615265453613331113140424368548
0510676584349352383695965342807176877532834823434555736671973139274627
3629108210679280784718035329131176778924659089938635459327894523777674
4061922403376386740040213303432974969020283281459334188268176838930720
0363479562311710310129195316979460763273758925353077255237594378843450
4067715555779056450443016640119462580972216729758615026968443146952034
6149322911059706762432685159928347098912847067408620085871350162603120
7190317208609408129832158107728207635318662461127824553720853236530577
5956430072517744315051539600905168603220349163222640885248852433158051
5348496224348482993809050704834824493274537326245677558790891871908036
6205800959474315005240253270974699531877072437682590741993963226598414
7498193609285223945039707165443156421328157688908058783183404917434556
2705202235648464951961124602683139709750693826487066132645076650746115
1267752274862159864253071129844118262266105716351506926002986170494542
5047491378115154139941550671256271197133252763631939606902895650288268
608362241082050562430701794976171121233066073310059947366875}

If I normalize the time to 1G clock it took 50 ms to compute fib(10000) -

for each of the above programs a) did you get the same answer and b) how long did it take
(normalized to a 1GH clock rate)


/Joe Armstrong

I think something went wrong with Joe Mansfield closing the italic. The Fibbonacci sequence works well for a code example of iteration, but if you are really interested in the nth fib number, then use the math. I like the C# 3.0 example. It is taking some work for me to fully grasp the new language features, but I like them.

What about Powershell ?

http://getpowershell.wordpress.com/2008/01/24/fibonacci-series-in-powershell/

Andy
http://www.get-powershell.com

What are some uses for Fibonacci numbers in real life code? I took this in college and forgot what it was good for.

How about examples of code where.. this is how you used to do it in .NET 2.0 .. now this is how you can do the same thing neatly in .NET 3.5.?

I seem to recall something about Fibonacci allowing you to build a spiral by drawing lines of lengths equaling the numbers in the sequence. Was that the Golden Spiral? I guess I could Google it, but I'm feeling lazy right now.

Here's my Scheme version (not 100% sure of its syntax, but the general idea is there):

(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)

Hey Scott... Just wanted to point out a small potential problem with your lambda recursion. =)

I copied your def of fib, and added some more after it...

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() + "???");

This will output:

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. =)

As a programmer i liked the C# version while as a student of maths i like Erlang. But can i raise a question, i have seen many guys approaching towards these so called dynamic or 5th Generation languages. But look at the syntax in Ruby/F# etc, could anybody after writing it understand it (might be even just few weeks after). So what is our direction and where we are heading too.
As for as i can remember, the basic intent to create new languages is to provide a solid platform to the developers so that they can produce the softwares with more productivity and more stability (certianly the understanding the code written plays an important part in such virtues.)
I hope you got my point ??? so what you think :)

Like someone else pointed out, there's a (minor) bug in the C# version; F0 of the sequence incorrectly returns 1, when it should be 0.

I know it's syntactic sugar, but rather than doing:

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.

This has been fun. Here's an example using iterators in C# 2.0. I wonder if a Linq query could be layered on top.

I stood on Brian's shoulders for the Fib(int n) function -- that was cool, I had never seen it before!

I liked Julian Birch's Boo implemenation, so I used the yield statement and added start and count params to replicate the Skip/First capability


<code>
static System.Collections.Generic.IEnumerable<int> 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;


</code>

Please ignore my stupid comment -- I just say that Julian's implementation _was_ a c# example. I should read more carefully.

Woah... I get to be first to post a Python version?

def fibonacci(n):
starter, next = 1,1
s = str(starter) + "," + str(next)
for i in range(n-2):
s = s + "," + str(starter + next)
(starter,next) = (next, starter + next)
print s

ugh, pasted something I already had and looked at the code above, all of which use the recursive approach:

def fib(n):
if n < 2: return 1
else: return fib(n-1) + fib(n-2)

@joe armstrong Because of the algorithm I used I considered the first two numbers (both 1's) to be the 0th and 1st Fibonacci Numbers. i.e.
0-1-2-3-4-5-6 # n
1-1-2-3-5-8-11 # nth Fibonacci Number

Don't forget about XSL! This one does the job in Saxon:


<xsl:function name="m:fibonacci" saxon:memo-function="yes">
<xsl:param name="n" as="xs:integer">
<xsl:result as="xs:integer"
select="if ($n=0) then 0
else if ($n=1) then 1
else m:fibonacci($n-1) + m:fibonacci($n-2)"/>
</xsl:function>

@Joe Armstrong.

Thanks for contributing, and thanks for Erlang ;)

great way using C# 3.0? are you kidding me?

it's as slow as the basic C# 2.0 implementation
it's harder to read
but the best thing is that you can't debug it...or how do you set breakpoints there???

> but the best thing is that you can't debug it...or how do you set breakpoints there???

It's easy. You just put a line-break in. Visual Studio's "active compile" senses the difference between the assignment and the lambda body, but if they are on one line, you can't set separate breakpoints. If you put the lambda body on a separate line, you can.

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.

Scott,
it seems you have made each of these examples overly complex. For example it appears to me that your C# 2.0 example won't work (-it only accepts a single integer value, so if 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.

As I see it first we have to determine the goal, return the full sequence or to return a given value for a set number of iterations. presuming the former:
Public Function FibSeq(ByVal size As Integer) As Decimal()
Dim array(size) As Decimal

array(0) = 0
array(1) = 1

For i = 2 To 50
array(i) = array(i - 1) + array(i - 2)
Next
Return array
End Function

is both cleaner and easier to maintain (and it works... especially for checking results..)

presuming the later:
Public Function FibSeqRes(ByVal generation As Integer) As Decimal
Dim array(1) As Decimal
Dim curgen As Decimal

array(0) = 0
array(1) = 1
For i = 2 To generation
curgen = array(0) + array(1)
array(0) = array(1)
array(1) = curgen
Next
Return curgen
End Function

provides a more robust and maintainable solution.

Neither solution needs the added complexity or performance hit of recursion which in this case doesn't really seem to provide any benefit, and as this comment section demonstrates the proposed solutions are difficult to debug and correct.
(btw yes I used VB on purpose :-)

> It's easy. You just put a line-break in.

thank you Waterbreath!

</i> Thanks to everyone for your fixes and thoughtful analysis!

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.

The PowerShell version (right out of Bruce Payette's excellent Windows PowerShell in Action) is pretty succinct:

$c=$p=1; while ($c -lt 1000) { $c; $c,$p = ($c+$p), $c }

which will print out the fib sequence up to a value of 1000.

Could someone please close me?

Fibonacci numbers with C++.

With recursion using regular funtion:



<sub>#include <iostream>
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 ) );
}</sub>



And with template funtion:


<sub>#include <iostream>
const unsigned int ITERATIONS = 10;

template <typename T>
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;
}</sub>

And with Perl.


<sub>#!/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";
}</sub>

And if you wanted to calculate Fibonacci numbers in your F-18 Hornet, you would like to use Ada95 program to do that:


<sub>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;</sub>

Hopefully this works.

</i>

@OJL Ooooh I need to get me one of them Hornets to test out my ADA Implementation of Towers of Hanoi ;-)

Even knowing that the recursion way to calculate fibonacci is not efficient than iterative one, I always liked the C code.

int fibonacci(int n) { return n <= 1 ? n : fib(n-1) + fib(n-2); }

Miranda's version (linear time):

fib 0 = 1
fib 1 = 1
fib (n+2) = flist!(n+1) + flist!n
where
flist = map fib [ 0.. ]

Does anyone care to post an Assembler version? :)

Oracle SQL, use Oracle 10 or 11

This solution uses SQL, not PL/SQL ! A PL/SQL solution would be very different! Please try to understand that PL/SQL and SQL are something different.

variable n number;
exec :n := 15;

with data as (select level le from dual connect by level <= :n)
select fibo
from data
model
dimension by (le)
measures ( 0 fibo)
rules
(
fibo[1] = 0
, fibo[2] = 1
, fibo[le>2]=fibo[cv(le)-2]+fibo[cv(le)-1]
)
;


FIBO
----------
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377

(by the way, the idea of using 'connect by level <' is from someone name Mikito, you can google him or her.)

See here for another way of calculating Fibonacci with Oracle SQL:

http://asktom.oracle.com/pls/asktom/f?p=100:11:0::::P11_QUESTION_ID:15844208486026

Although I don't have access to an interpreter to check my code, a standard M solution would be:

S A=0,B=1 W !,A,”, “,B,”, “ F S C=A+B W C, “, “ S A=B,B=C

I don't like the C# 2.0 solution.

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

should be:

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

Much more readable and maintenable.

What does programming or computing have to do with Zen?

David
p.s. replies referencing Zen and the Art of Motorcycle Maintenance do not count.

Scott,

It’s probably too late to participate in the discussion, but here is my 5 cents.
Performance-enabled :) version in Haskell looks almost as nice as recurrent (classical) one:

fib n = fibw n 1 1
fibw n prev cur = if n <= 2 then cur else fibw (n - 1) cur (prev + cur)

As one can see, it’s O(n) in time. And there is a tail recursion which is pretty good as well.
For example, on my Intel CoreDuo 2GHz CPU it took only 8 seconds to calculate fib 200000.

Here is another way of skinning the cat in performance-friendly way (sorry, ugly C# code here):

public static ulong GetFibonacciNumberMatrix(ulong n) {
if (n < 2) return n;
ulong[,] matrix = { { 0, 1 }, { 1, 1 } };
ulong[,] result = { { 0, 1 }, { 1, 1 } };
while (n > 0) {
if ((n & 1) == 1) {
MatrixMultiply(matrix, result, result);
}
n >>= 1;
MatrixMultiply(matrix, matrix, matrix);
}
return result[0, 0];
}
private static void MatrixMultiply(ulong[,] multiplicand, ulong[,] factor, ulong[,] result) {
ulong[,] temp = { { 0, 1 }, { 1, 1 } };
temp[0, 0] = multiplicand[0, 0] * factor[0, 0] + multiplicand[0, 1] * factor[1, 0];
temp[0, 1] = multiplicand[0, 0] * factor[0, 1] + multiplicand[0, 1] * factor[1, 1];
temp[1, 0] = multiplicand[1, 0] * factor[0, 0] + multiplicand[1, 1] * factor[1, 0];
temp[1, 1] = multiplicand[1, 0] * factor[1, 0] + multiplicand[1, 1] * factor[1, 1];
result[0, 0] = temp[0, 0];
result[0, 1] = temp[0, 1];
result[1, 0] = temp[1, 0];
result[1, 1] = temp[1, 1];
}

It’s even faster (theoretically) then O(n), it’s O(lg(n))!

But my favorite one is the next (shamelessly stolen from http://blogs.msdn.com/madst/archive/2007/05/11/recursive-lambda-expressions.aspx):

delegate T SelfApplicable<T>(SelfApplicable<T> self);

public static ulong GetFibonacciNumberLambda(ulong n) {
SelfApplicable<Func<Func<Func<ulong, ulong>, Func<ulong, ulong>>, Func<ulong, ulong>>>
Y = y => f => x => f(y(y)(f))(x);
Func<Func<Func<ulong, ulong>, Func<ulong, ulong>>, Func<ulong, ulong>> Fix = Y(Y);
Func<Func<ulong, ulong>, Func<ulong, ulong>> F = fib => x => x < 2 ? x : fib(x - 2) + fib(x - 1);
Func<ulong, ulong> fibonacci = Fix(F);
return fibonacci(n);
}

Not really good from performance point of view but, gosh, it does work!!!

int fabi(int i)
{
if(i==0)
return 0;
else if(i==1)
return 1;
else if (i==2)
return 1+2;
else if (i==3)
return 1+2+3;
//TODO make it complete

}

Next time we show how to finish this algorithm :-)

My favorite Fibonacci implementation is the How to: Use a Thread Pool (C# Programming Guide)
example from MSDN.

Well I haven't seen a solution on other sites, but I tried to do a small solution with practical results, without recursion. Even though I can't calculate a bigger number than what ulong allows, the limit is near f(93).

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;
}

or the compacted version:

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;
}

And calculating the elapsed time using the high res system timer in a Pentium 4 @ 2.8GHz

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.

test

class foo

coool

VB.NET Code:

    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

Assembly Z-80a

ORG 0100H

LD A,10
PUSH A
CALL FIBO
RET

FIBO:
POP A
OR A
JR NC,FIBO1
DEC A
PUSH A
PUSH A
CALL FIBO
POP A
DEC A
PUSH A
CALL FIBO
RET
FIBO1:
LD A,1
RET

a good example to use tmp memory buffer instead of recursive.

While fibonacci is probably not the most useful algorithm to implement, the fact that its natural implementation is a recursive one, and thus performs rather horribly for larger input, makes it an ideal candidate for optimization methods that can be easily extended to other algorithms as well.

One optimization that can often be used, when you can't change the recursive nature of the algorithm, and the algorithm will repeatedly calculate the same data over and over again, the Memoize pattern is very useful.

Basically you wrap the function in a form of cache that tracks the input parameters and their corresponding outputs, only calling the actual function when input parameters are unknown.

A trivial C# implementation is as follows:

public Func<Int32, Int32> Memoize(Func<Int32, Int32> func)
{
Dictionary<Int32, Int32> cache = new Dictionary<Int32, Int32>();
return delegate(Int32 key)
{
Int32 result;
if (cache.TryGetValue(key, out result))
return result;
cache[key] = result = func(key);
return result;
};
}

Func<Int32, Int32> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
fib = Memoize(fib);

With this setup it is possible to calculate even the largest fibonacci numbers with blazing speeds.

Note that similar constructs can easily be made both generic and multi-argument supportive without much more work.

I think you need to add several more language examples. Those that you have just aren't enough, what about Pascal, Cobol, and RPG. RPG is definitely important, I mean, isn'tit only functional. :o

j/k <- feeling like a sarcastic a** today. :)

Guys,

Do you not think that there are worthier computing problems to be solved than a Fib series?
Kiddin......:)

I like these posts because they bring out the worst in me. There is best simply because there is worst.

Oracle PL/SQL with a 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;
/

What's wrong with building up a list ....

static int fib(int x)
{
List<int> fibNums = new List<int>();
//seed nums
fibNums.Add(0);
fibNums.Add(1);

for(int i=2; i<x; i++)
{
fibNums.Add(fibNums[x-1] + fibNums[x-2])
}

return fibNums[x-1];
}

... recursion needn't be complex :)

Why use recursion though? Surely it has a MUCH bigger memory and time penalty over, the following(
Also isn't this MUCH easier to read?)

		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;
		}

I like the non-iterative Python much better:

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

I have heard that the stock prices jump from plateau to plateau
and the Fibonacci series characterizes somehow the price level.
I am not sure how accurate is this theory. If there are enough people
believing in it, it could become true.

i think the recursive algorithms is too slow,u should implement by some straight forword algorithms

Well, the C# 3.0 and 2.0 comparisons were pretty lame.

The 2.0 was solved with a longer function name, and less compressed code. Here's how *I* would've solved the 2.0 puzzle - even more efficient than the 3.0:

static int fib(int x) { return((x<=1)?1:(fib(x-1)+fib(x-2))); }

Zomg!!!11oneone! C# 2.0 is better than 3.0!

Actually I prefer C# 2.0 version

This makes my head go crazy. It reminds me of PI and Prime Numbers.

Here's a recursive Erlang version that runs in linear time.

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.

PERL, with dynamic programming (caching results, so the time complexity is linear instead of exponential)

use Memoize;
memoize('fib');

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

I suppose it's fun to compare languages, but who gets paid for writing fibonacci functions?

Hi Scott,

I tried this in VS 2008 using a partial class:

using System;
using System.Func;
public partial class Fibo : System.Web.UI.Page
{
protected void Page_Load(object sender, EventArgs e)
{
Func<INT, int> fib = null;
Label1.Text=Convert.ToString(fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n);

}
}

I got the following error:
Error 1 Using the generic type 'System.Func<TResult>' requires '1' type arguments C:\Users\billz\Desktop\ASP.NET Book\ch11\Fibonachi\Fibo.aspx.cs 2 14 C:\...\Fibonachi\

Not sure what I did wrong.

Thanks,
Bill

eraoul, I'm impressed! Is there anything Perl doesn't have a module for? :-)

BTW, if you add 'use bigint;' at the top, you can do fib(10000).

Hi Bill, This is a new C# learner. I managed to solve your problem by replacing Func<INT, int> by Func<int, int>, e.g. converting INT into lower case.
Actually fib is a function so you cannot simply write
Label1.Text=Convert.ToString(fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n);
Instead, you'll have to write
fib=n=>n>1?fib(n-1)+fib(n-2):n);
Label1.Text=func(9);
which means the result is the ninth number in Fibonacci Series not counting zero in the first place.
My English is not good, wish my comment is of help.

Yours Kenneth

Sorry, in the above comment I mistook Label1.Text=fib(9) for Label1.Text=func(9). :-)

As for the slowness of the recursion, I've previously made proposals for introducing memorization into C# (and .NET in general I guess) which would partially solve the problem. http://icr.vox.com/library/post/a-proposal-for-const-functions-in-c-1.html
As it's a sequence Fibonacci makes a prime candidate for memorization.

I find factorial a much more useful problem than Fibonacci, mainly because of it's use in calculating binomial coefficients which I seem to do all the time :S

Serge Wautier's post is correct. The mathematical definitions of many functions are naturally recursive. Direct implementations of those definitions using recursion to perform the calculations always perform terribly.

Designing a method that performs well is often very difficult, but also often very useful. If nobody thought outside of the recursion box, there would be no FFT (Fast Fourier Transform) and digital filtering would be a purely theoretical subject.

As stated previously by some; I think recursive algorithms is a big mistake. It looks very nice though...

recursive algorithms for fibonacci* that is!

I'm a fan of C#
BTW, how did you compile it with INT instead of int in C# 3.0 ?:)))

The syntax on C# is quite lame, but hey, what else would you expect from .net ultimate MS lock-in? getting ridiculous already.

Yo Adrian ---

I agree... why use recursion?
I like your solution :

[-

	
	static ulong fib(int n)
		{
			ulong f1 = 0;
			ulong f2 = 1;

[snip]....[/snip]
		return f1
		}

-]
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, "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.

Whats a binomial coefficient ?

Where does that relate to fib numbers ?

How does C# 3.0 differ from C# 2.0 when you are using the same objects (int) with the same code ???

Has anyone tested the performance of running identicle code in both versions of .net to see if there actually is a difference ?

Why the hell am i asking so many questions ?

.... OMG i'm losing my mind .... Math overload ....


This may just be me but doesn't the framework manage memory in such a way that functions that are called over and over are made most easy to get to in ram ?

So what is the difference between this ...

int Fib(int i)
{
// recursive code
}

... and this ?

int Fib(int i)
{
// loop in here
}

is there a noticable difference over say 10,000 iterations ?

Yeh i ask a lot of questions but someone wise once said to me ...
"Always try to be the dumbest person in the room ... you learn more and no1 expects anything of you."

The solution Julian Birch gave is along the right track in my opinion but far messier than need be. Actually, the following solution doesn't use any 3.5 features at all and is really quick and doesn't re-evaluate fib for smaller values which is the big perf problem:

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;

}

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):

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<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];

}

I just realized that in my previous comment I keep referring to the "recursive" version whereas in fact neither solution there is recursive. Also, although it's a few more lines, inlining the static function there makes the function about twice as fast again so the best code I've found is just the relatively simple:

static long Fib(long n0)
{

long p = 0, n = 1, nt;
for (; n0 > 0; n0--)
{

nt = p + n; p = n; n = nt;

}
return p;

}

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).

I can't believe nobody provided a Java solution, looks like ppl hate java.
Java has a library where you can use big numbers which is suited for this kind of applications...want to see a solution, anybody ?

I prefer this syntax with a single return statement, esentially the same for C, C++, C#, Java, and all other C-based languages:

public static int Fibonacci(int x)
{
return (x <= 1) ? 1 : Fibonacci(x - 1) + Fibonacci(x - 2);
}

Of course, unrolling into a loop a la the Ruby algorithm is a good idea depending on intended usage.

How is the c# 3.0 better again? I like the 2.0 b/c its much easier to understand. Unless the c# 3.5 compiles into more efficient IL or machine code, I don't see any benefit of compressing code.

I agree with Zinfidel; non-recursive solution would be more efficient.

Still, its an interesting post.

Since the Fibonacci series for many numbers must have been computed by people hundreds or thousands of times, I'm surprised no one suggests a serialized version. As in, save off computed values to an XML file, and use a LINQ query to see if its already there first, or go out on the web and search for one.

Even if the exact match is not there all you need are the two nearest Fib(n)'s below your desired number and then you can start from there and work up.

As far as recursion -- yes, what a lot of redundant computation. But again, based on the world's knowledge of existing...

In fact, I guess it would be a challenge because the best algorithm would have to beat the best search to be useful.

Then, of course, there's quantum search where we might be able to make the Fib(n)'s ... resonate.

@ John A. Bailo

What is the difference between a cached version and a serialized version?

This Oracle PL/SQL solution is a cached solution for the problem. It uses the result cache that Oracle provides. If you first calculate fib(5) and next calculate fib(7) it will use the result cache to get fib(5), fib(4), fib(3), fib(2).... Others have provided C# solutions with caching.


PL/SQL with caching:


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;
/

Recursive SML solution: fun fibo 0 = 0 | fibo 1 = 1 | fibo n = fibo(n-1) + fibo(n-2)

For a real-world solution which uses the Fibonacci sequence, I've found it much more efficient to store them in an array rather than calculate them for each call to the relevant function. I must admit a fib calculator is a nice bit of mental exercize, but I am hard pressed to think of a real world application where I'd want to calculate it rather than retrieve it from storage of some sort or other.

Here is a better implementation done using the O++ language developed by MIT. It uses parallel computing to separate each function call and increase efficiency.

-------------------------------------------------------------------

<process> fib( n: Int): Int = n <defined>
{
<base> 0 = 0
<base> 1 = 1
<select> = fib( n -1) + fib( n-2)
}

----------------------------------------------------------------------

Ha hahaha,

You're still using O.... welcome to 2004, n00b, why don't you look up some of their documentation and you can easily see why here is a better implementation done using the O++ language developed by MIT. It uses parallel computing to separate each function call and increase efficiency.

Hopefully, you'll catch on....

-------------------------------------------------------------------

<process> fib( n: Int): Int = n <defined>
{
<base> 0 = 0
<base> 1 = 1
<select> = fib( n -1) + fib( n-2)
}

----------------------------------------------------------------------

The examples given in Erlang and Haskell are both quite good as a reference, however I prefer to use the O programming language developed a few years ago at MIT for calculating mathematical equations using recursive method calls. Its terse syntax and built in memory management allow for an efficient computation even for rather large numbers.

An example in O would be:
<recurs> fib = (a-1) #:(b-2)?1{swp[a,b]}

O....

try they rewrote the entire language after the hadron collector incident.

And what's with these posts... I put up a comment about Scott using the deprecated language of O and here my comment gets pushed in before his... Maybe if some more people out there would start using O++ then this wouldn't happen.

It's compact framework allows it to useable on the web as well as for multi-threaded application development and it's terse language requirement is easy on the compiler and doesn't cause half of the problems that O used to.

Nice small source code is a important element. But what about performance ? Which is the best one ?

This calculates the 500th number in the sequence in 0.1 seconds on my old slow single-code laptop by memoizing the fibonacci function. Both C# 2.0 and 3.0 versions included (hi lambdas).

// 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, TResult>(T t);

public static void Main()
{
    Func<long, long> 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<long, long>(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 <long,long>
    // or lambda parameter (long x) type, or both (redundant))

    long result = Fib(100);
}

public static Func<T, TResult> Memoize<T, TResult>(Func<T, TResult> f)
{
    Dictionary<T, TResult> cache = new Dictionary<T, TResult>();

    return delegate(T t)
           {
               TResult value;

               if(!cache.TryGetValue(t, out value))
               {
                   value = f(t);
                   cache.Add(t, value);
               }

               return value;
           };
}

i meant single-core laptop...

...and make that 0.01 seconds for Fib(500)! (sorry for spamming)

How about Java script? Just click HERE

P.S. I think html enabled comments is bad idea ... ;)

You could get it in one line too in C# 2.0, like this:

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

So I think the main difference with C# 3.0 is the function type (or its declaration), basically,

C# 3.0, recursive lambda expression:

delegate int Self(Self f, int n);

Func<int, int> 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
    );

The explicit delegate constructor call is required by the compiler in order to allow immediate execution of the first lambda.

Recursive and caching (by self-modifying code) in Tcl:

proc fib0 {} { return 1 }
proc fib1 {} { return 1 }

proc fib n {
if {[string equal "" [info commands fib$n]]} {
proc fib$n {} [list return [expr [fib[expr $n - 1]] + [fib[expr $n - 2]]] ]
}
fib$n
}

for {set i 0} {$i < 10} {incr i} {puts [fib $i]}

fib should be implemented iteratively.
Recursive fib in languages that don't support tail recursion is just bad..

Stack overflow FTL!

Hi Scott,

Check out this -- Fibonacci and Factorial......

static void Main(string[] args)
{
int n = 5;
for (int i = 0; i < 10; i++)
{
Console.WriteLine(" " + Fib(i));
}
Console.WriteLine("**********************");
Console.WriteLine("Factorial Calc");
for (int i = 0; i < 10; i++)
{
Console.WriteLine(" " + Fact(i));
}
}

public static int Fib(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}

public static int Fact(int n)
{
if (n == 0)
return 1;
else
return n * Fact(n - 1);
}


Thanks,
Yash

How about this one, it told me that

Number 5000 =

3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858
8829738134831020089549829403614301569114789383642165639441069102145056341337065586562382546567007125259299038549
3381392883637834751890876297071203333705292310769300851809384980180384781399674888176555465378829164426891298038
4613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714
1748832984228914912731040543287532980442736768229772449877498745556919077038806370468327948113589737399931101062
1930814901857081539785437919530561751076105307568878376603366735544525884488624161921055345749367589784902798823
4351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302
9174910889841552098544324865940797935713168416928680395453095453886981146650820668628974206393234384884652409887
4239587380197699382031717420893226546887936400263079778005875912967138963421425257911687275560036031137054775472
4604639987588046985178408674382863125

Can anyone verify that for me ?

Regards Dries


Following : Code that generated this number

class Bignum
{
public byte [] digits=new byte[5000];

public Bignum(int x)
{
int i = 0;
while (x>0)
{
digits[i] = (byte) (x%10);
i++;
x /= 10;
}
}

public new string ToString()
{
string str = string.Empty;
int i = digits.Length - 1;
bool trailingzero = true;
while (i>=0)
{
if (digits[i]!=0)
{
trailingzero = false;
}
if (!trailingzero)
{
str += (char) (digits[i] + '0');
}
i--;
}
return (str);
}

public bool add(Bignum val)
{
byte carry = 0;
for (int x=0;x<digits.Length;x++)
{
digits[x] += (byte)(val.digits[x]+carry);
carry = (byte)(digits[x]/10);
digits[x] %= 10;

}
return (carry != 0);
}

//
// Test routine :
//
public static void Test()
{

//
// For a test calculate the fibo nr's
//
Bignum a = new Bignum(0);
Bignum b = new Bignum(1);
bool carry = false;
int cur = 2;

while (!carry)
{
carry = a.add(b); // stop if we have a carry

if (!carry)
{
System.Diagnostics.Debug.WriteLine(cur.ToString()+" = " + a.ToString());
cur++;
carry = b.add(a); // stop if we have a carry
if (!carry)
{
System.Diagnostics.Debug.WriteLine(cur.ToString() + " = " + b.ToString());
cur++;
}
}
}

}
}

And as a reply to Joe Armstrong, his value for fib 10000 is correct according to my calculations.

Hi Scott, here's a simpler Ruby version:

def fibonacci(n)
  a, b = 0, 1
  n.times { a, b = a + b, a }
  a
end

Personally 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. :)

Hi Scott,

I do not know what your purpose of making us to calculate fibs. The recursion algorithm to me totally makes no sense since it time consuming and memory horror. Maybe 5000 times recursion will exhaust stack space out of your program. And the looping version seems get a little bit advanced unless you can live with a long time waiting while calculating fib(5000).

The real problem here, I think, it does not challenge my programming skill. It is a mathematical skill indeed. Since the fib can be described as

fib = [1 1;1 0]^n * [1 ; 0];

So my program in MatLab is as simple as

function fib_pair_v = fibm(n)
fib_pair_v = [1 1;1 0]^n * [1 ; 0];
end

Is this what you need?

hi
i am from iran and love c# for learning .
help me , pleas .
bye

Sorry for disturb this "heavy thread" (at least for my poor brain)...but isn't all this stuff a little bit "unreadable"...

In my opinion this is far more easy.....to read ...and understand!

Public Function Fibonacci(ByVal i) As Integer
If i = 0 Then Return 0
If i < 2 Then Return 1
Return Fibonacci(i - 1) + Fibonacci(i - 2)
End Function

Bye
rMark

I have a function that is recursive and does not calculate the same values twice: (c++)

int fibo(int n, int pp = 0, int p = 1)
{
return n < 2 ? n : pp + fibo(n - 1, p + pp, pp);
}

Fibonacci Series are not really used for anything in a practical sense, but the sequence is related to the golden section which is a ratio that is found in nature. Some flowers the Nautilus shell show this ratio in their design. In addition, the Rose window at the Cathedral of Chatres uses the ratio for the spiral shapes. Mario Mertz did some modern piece at the Guggenheim in the 80s which was based on the series.

Nemerle version with tail recursion:
def fib(n, a = BigInteger(0), b = BigInteger(1))
{
..match(n)
..{
....| 0 => a
....| 1 => b
....| _ => fib(n-1, b, a+b)
..}
}

used Mono.Math.BigInteger class.
Pentium 4 @ 3.2GHz
fib(10000) = 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
time = 15.6msec

fib(100000) = 259740693472217241661550340212759154......5609970015699780289236362349895374653428746875
time = 859msec

fib(1000000) = 1953282128707757731632014947596256332443542996...(~200000 digits)....37205802043347225419033684684301719893411568996526838242546875
time = 1min 40.3sec

Assembly:

MOV CX, 10
MOV AX, 0
MOV BX, 1
L1:

Oops, premature submission...

Assembly:
MOV CX, 0A
MOV AX, 0
MOV BX, 1
L1:
DEC CX
JCXZ L9
ADD AX, BX
XCHG AX, BX
JMP L1
L9:
RET

How about in Shakespeare Programming Language?

Fibonacci in Denmark.

Hamlet, a man of more words than action.
Guildenstern, his friend, the Keeper of N.
Rosencrantz, a counter of insects.
Ophelia, a temporary fling.

Act I: The initiation of the quest.

Scene I: A meeting of old friends.

[Enter Hamlet and Guildenstern]

Hamlet:
Open your heart!

Guildenstern:
Thou art as canny as a fox. Remember thyself!

[Exit Guildenstern]

[Enter Rosencrantz]

Hamlet:
Thou art as polished as the difference between a
gleaming brazen idol and a lodestone.

[Exeunt]


Act II: A calculated endeavor.

Scene I: The luck of the draw.

[Enter Rosencrantz and Guildenstern]

Rosencrantz:
Am I more fortunate than you?

Guildenstern:
If so, let us proceed to Scene IV.

[Exeunt]

Scene II: A romantic interlude.

[Enter Hamlet and Ophelia]

Hamlet:
Thou art as obstinant as myself.

Ophelia:
Recall our pleasant times together. Thou art as
romantic as the sum of myself and yourself. Remember me.

[Exit Ophelia]

Scene III: The plot thickens.

[Enter Rosencrantz]

Hamlet:
Thou art as remarkable as the sum of yourself and a flea!

Rosencrantz:
Let us proceed to Scene I.

[Exeunt]

Scene IV: All is revealed.

[Enter Hamlet and Ophelia]

Ophelia:
Speak your mind!

[Exeunt]

Here is a pattern matching example with tail recursion, avoiding double calculations using F#. F#'s current build does not support pattern matching against bigints for the moment, hence the '| _ when' and '| (a, _, x) when' passages. As bigints are used, an arbitrary large fib result can be calculated.

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)

After read this entire blog, believe me, I read, the better implementation in my opinion was posted by

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 msec

No 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??

>99% delay (for big numbers) is due to bignumber implementation.

There is a "Clever" Algorithm with O(log n).
PLT Scheme (interpreted language with builtin bignumber type):
(define (fib n)
(define (fib-aux a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-aux a
b
(+ (* p p) (* q q))
(+ (* q q) (* 2 p q))
(/ count 2)))
(else
(fib-aux (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
(fib-aux 1 0 0 1 n))

(fib 1,000,000) -> 1547msec
(fib 10,000,000) -> 41.7sec