## 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

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.

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;

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html

But the syntax are beautiful, though.

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?

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

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

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

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

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

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

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?

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

+++++++++++

>+>>>>++++++++++++++++++++++++++++++++++++++++++++

>++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>

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

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

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

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

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

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

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

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

def fibonacci():

a, b = 0, 1

while true:

yield b

a, b = b, a+b

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

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,

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

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

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

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

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.

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>

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

def fib(n):

if n < 2: return 1

else: return fib(n-1) + fib(n-2)

0-1-2-3-4-5-6 # n

1-1-2-3-5-8-11 # nth Fibonacci Number

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

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

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.

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

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.

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

With recursion using regular funtion:

_{#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 ) );}}

And with template funtion:

_{#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;}}

_{#!/usr/bin/perlmy $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;}

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

fib 0 = 1

fib 1 = 1

fib (n+2) = flist!(n+1) + flist!n

where

flist = map fib [ 0.. ]

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

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

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.

David

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

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

example from MSDN.

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.

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

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

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.

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

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.

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

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;

}

def fibonnaci(n):

#Print Fibonacci sequence up to n

a,b = 0, 1

while b < n:

print b

a, b = b, a + b

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.

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!

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

}

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

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

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

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

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.

BTW, how did you compile it with INT instead of int in C# 3.0 ?:)))

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.

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

static void fib(ref long pp, ref long np, ref long ip){ long nt = pp + np; pp = np; np = nt; ip--; }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.

static long Fib(long n0)

{

long p = 0, n = 1, i = n0;}

for ( ; i > 0;fib(ref p, ref n, ref i)) ;

return p;

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

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;

Java has a library where you can use big numbers which is suited for this kind of applications...want to see a solution, anybody ?

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.

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

Still, its an interesting post.

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.

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;

/

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

<process> fib( n: Int): Int = n <defined>

{

<base> 0 = 0

<base> 1 = 1

<select> = fib( n -1) + fib( n-2)

}

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

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)

}

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

An example in O would be:

<recurs> fib = (a-1) #:(b-2)?1{swp[a,b]}

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.

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

};

}

**Just click HERE**

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

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,

delegate int Self(Self f, int n);The explicit delegate constructor call is required by the compiler in order to allow immediate execution of the first lambda.

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

);

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

Recursive fib in languages that don't support tail recursion is just bad..

Stack overflow FTL!

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

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

}

}

}

}

}

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

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?

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

int fibo(int n, int pp = 0, int p = 1)

{

return n < 2 ? n : pp + fibo(n - 1, p + pp, pp);

}

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, 0A

MOV AX, 0

MOV BX, 1

L1:

DEC CX

JCXZ L9

ADD AX, BX

XCHG AX, BX

JMP L1

L9:

RET

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]

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

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

Comments are closed.