1941

28
+14  Q:

## What's your favorite implementation of producing the Fibonacci sequence?

What's your favorite implementation of producing the Fibonacci sequence? Best, most creative, most clever, fastest, smallest, written in weirdest language, etc., etc.

For those not familiar with this staple of programming exam question / interview question, check this out:

Fibonacci Sequence at Wikipedia

The question would be, write a simple program which will spit out the first n numbers of the Fibonacci sequence.

So, if n == 12, we produce:

0 1 1 2 3 5 8 13 21 34 55 89 144

Your implementation becomes more interesting when you set n to larger values. How long does it take your implementation to return a 25 number sequence? How about 100?

+4  A:

F#

``````#light

let fib =
let rec inner l r =
seq {
let next = l + r
yield next
yield! inner r next
}
seq {
yield 0
yield 1
yield! inner 0 1
}

let fibItem n = fib |> Seq.skip n |> Seq.hd
printfn "%d" (fibItem 10)
``````
I like the use of an infinite lazy sequence. That's nice. Very nice.
seq monad ftw (oh sorry, 'computational workflow')
A:

Recursive Way:

``````public static int fib(int n)
{
// Base Case
if (n <= 2)
return 1;
else
return fib(n-1) + fib(n-2);
}
``````
that doesn't produce the first n numbers, only the nth.
that algorithm can also be greatly accelerated with a little memoization, unless you *like* calculating everything fib(n-1) times.
this is elegantly short, but try computing fib(100) with it. it runs in exponential time, so... not exactly efficient.
+4  A:

Ruby:

`````` (0..12).inject([0,1]){ |x,y| print x[0].to_s+" " ; [x[1],x[0]+x[1]]}
``````
+8  A:

Ah la Duff's device

``````unsigned long fib(unsigned long i)
{
int a = 1, b = 1, c = 1;
switch(i%3)
while(i > 3)
{
i-=3;
b = a + c;  printf("%lu\n", b);
case 2: a = b + c;  printf("%lu\n", a);
case 1: c = a + b;  printf("%lu\n", c);
case 0:
}
return c;
}
``````
+1  A:

Perl Oneliner:

``````perl -e 'my @i=(0,1); (print q{ },\$i[0]) and @i=(\$i[1],\$i[0]+\$i[1]) for (0..12);'
``````

Increment 12 as neeeded.

+3  A:

I came across this little beauty the other day:

``````function f(\$n)
{
\$sqrt5 = pow(5, 0.5);
\$gr = (1+\$sqrt5)/2;
return floor(0.5+(pow(\$g, \$n)/\$sqrt5));
}
``````

Mmmmmm, non-recursive :)

Apparently though, it is fairly quickly limited by rounding errors due to the binary representations of floating point numbers... ah well, 'tis cool none-the-less.

yeah, also sub-optimal as soon as you want more than 2 results, like the questions says ;). Using this repeatedly to generate a sequence would give you FLOP death vs good ol INTs
On x86, the errors start for me at n=32.
Non-recursive yes, but also non-iterative. Not practical, but very cool :)
+2  A:

Produces an infinite list of Fibonacci numbers in F# using unfolding:

``````#light
let fibs = (1I, 1I) |> Seq.unfold(fun (n0, n1) -> Some(n0, (n1, n0 + n1)))
``````

[EDIT]: now supports bigint's.

Two small additions will give you the Nth item of fib. F# rocks.let fibs = (0, 1) |> Seq.unfold(fun (n0, n1) -> Some(n0, (n1, n0 + n1)))let fibsItem n = fibs |> Seq.Skip n |> Seq.hd
Indeed, thought i'd just show an alternative lazy list impl. Thanks.
+25  A:
``````static int[] fibs = { 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, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169,
63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, };

static int fib(int n) {
return fibs[n];
}
``````
The fastest implementation I have seen yet!
That's what I call memoization.
Haha! we somewhat cheated in a programming contest and did that, we had a huuuuuge copy pasta of pre generated code for a giant array....it helped gain some speed for sure :)
+1. And if n is beyond the range, you may want to actually calculate it. But point taken.
+1  A:

+18  A:

You can't beat Haskell for this. The simple solution is very close the mathematical defintion:

``````fibonacci 0     = 0
fibonacci 1     = 1
fibonacci n + 2 = fibonacci (n) + fibonacci (n + 1)
``````

Or, for linear performance, you can take advantage of laziness and infinite lists:

``````fibonacci = numbers
where numbers = 0 : 1 : zipWith (+) numbers (tail numbers)
``````
The first solution is not valid in Haskell 2010 due to the removal of n+k patterns.
+14  A:

How 'bout meta-programming?

``````template<int N> struct fibonacci
{
static const int value = fibonacci<N - 1>::value + fibonacci<N - 2>::value;
};

template<> struct fibonacci<1>
{
static const int value = 1;
};

template<> struct fibonacci<0>
{
static const int value = 0;
};

cout << fibonacci<128>::value;
``````
+1 for quirk factor :)
Ow. you make my brain hurt. :)
So... where is the output of the values?
+1  A:

compile time Meta in the D Programming language

``````template fib(uint i)
{
static if(i == 0)
const uint fib = 0;
else static if(i == 1)
const uint fib = 1;
else
const uint fib = fib!(i-1) + fib!(i-2);
}
``````

BTW as a side effect of template's reusing previously generated results, this is O(n) in the general case and over the life of the program, it is O(max(n)), that is its cost is proportional only to the largest value fed in.

Like for Joel's answer, where do you output the results?
`fib!(n)` can be used as a constant.
+6  A:

Well, here's a Python implementation using a generator. The use of range and zip in the last line is the obligatory obfuscation :p

```>>> def fib():
...     x, y = 1, 1
...     while True:
...         yield x
...         x, y = y, x + y
...
>>> [x for _, x in zip(range(12), fib())]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
```
A:

PowerShell using a pipe:

``````0..20 | %{ \$i=0;\$j=1} { \$o = \$i+\$j; \$i=\$j; \$j=\$o; \$o}
``````
er, you'd have to put 0..N if you wanted N of them... You didn't think I wrote a function, did you?
+6  A:

Esoteric! And surprisingly fast.

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

// This program doesn't terminate; you will have to kill it.
// Daniel B Cristofani (cristofdathevanetdotcom)
// http://www.hevanet.com/cristofd/brainfuck/
``````
This is more of an art project than it is a code project. I like it.
+2  A:

``````int fib(n)
{
if (n<2) return 1;
return fib(n-1) + fib(n-2);
}
``````

This is your brain on basic:

``````int s[999999];
int fib(int i)
{
_1: int t=0; s[t++] = i; s[t++] = 0; s[t] = 0;
_10: if (s[t-2] < 2) { s[t-2] = 1; t-=3; }
_20: if (t < 0) return s[0];
_30: if (s[t] == 1) goto _60;
_40: if (s[t] == 2) goto _70;
_50: s[t++]++; s[t++]=s[t-3]-1; s[t++]=0; s[t]=0; goto _10;
_60: s[t-1]=s[t+1]; s[t++]++; s[t++]=s[t-3]-2; s[t++]=0; s[t]=0; goto _10;
_70: s[t-2]=s[t-1]+s[t+1]; t-=3; goto _20;
}
``````

Any questions?

Thankyou, now I see why brainfuck was invented; to be more readable.
Heh heh. I was bored one day in a programming languages class and implemented the top example by writing the recursive elements (arguments, program counter, return value, in that order) into the int array. What else are you going to do while a prof drones on about how LISP is the coolest language ever created?
Write a solution in LISP, of course.
Too easy, and not very edifying. Now, implementing the call stack yourself - that's educational.
+5  A:

Python with memoization:

``````class memoize:
# class as decorator
def __init__(self, function):
self.function = function
self.memoized = {}

def __call__(self, *args):
try:
return self.memoized[args]
except KeyError:
self.memoized[args] = self.function(*args)
return self.memoized[args]

@memoize
def fibonacci_memoized(n):
if n in (0, 1): return n
return fibonacci_memoized(n - 1) + fibonacci_memoized(n - 2)
``````

Let's compare:

``````Beginning trial for fibonacci_memoized(30).
fibonacci_memoized(30) = 832040 in 0.000516s.

Beginning trial for fibonacci(30).
fibonacci(30) = 832040 in 1.147118s.
``````

The memoized function is over 2223 times faster.

fibonacci(332): 1082459262056433063877940200966638133809015267665311237542082678938909 in 0.009884s

This is really cool example about memoization, +1, but sorry for screwing up your 1337 karma.
+1  A:

In Scala. Similar to the Haskell infinite list approach, but not quite as concise:

``````val fib: Stream[Int] = 0 :: 1 :: fib.zipWith(fib.tail) { _ + _ }
``````

Note that this is slightly cheating since I assume you have the following implicit conversion in scope:

``````class StreamSyntax[A](str: =>Stream[A]) {
def ::(hd: A) = Stream.cons(hd, str)

def zipWith[B, C](that: Stream[B])(f: (A, B)=>C) = {
str zip that map { case (x, y) => f(x, y) }
}
}

implicit def convertSyntax[A](str: =>Stream[A]) = new StreamSyntax(str)
``````
A:

Oddly few of these answers take advantage of the question: how to compute the first N Fibonacci numbers. Since Fib (n) = Fib(n-1) + Fib(n-2), the obvious technique is to store Fib(n) in array and compute the next Fib number from the array, computing the first N values in O(N) time with a small constant factor. Since I like odd languages, here it is coded in vanilla PARLANSE (a parallel language for which we aren't using the parallelism in this case):

``````[answer (array natural 0 dynamic)]

(define FibSeq
(action (procedure [N natural])
(do [n natural] 2 N 1
)do
);;
)action
)define
``````

Since PARLANSE and many compiled-to-machine-code languages (such as C) have machine-sized values, this only works for Fib(n)<2^32 (or whatever your machine word size limits are), but produces "new" results with ~~ 10 machine instructions per result.

If you need Fib(n) > machine word size, you need to go to infinite precision arithmetic (in any of the langauges that can do that) and the cost goes up several orders of magnitude.

The Python memoized version has the same basic idea, but IMHO this seems easier to read.

A:

Here, you can have the Fibonacci algorithm in different languages (sorry, the comments in the page are in french).

A:
``````10 INPUT "Terms to display: ", N
20 GOSUB 9000
30 END
9000 A = 0
9010 B = 1
9020 PRINT A
9030 IF N > 0 THEN PRINT B ELSE RETURN
9040 IF N < 2 THEN RETURN
9050 FOR I = 2 TO N
9060 C = A + B : PRINT C
9070 A =  B : B = C
9080 NEXT I
9090 RETURN
``````

Written for (my memory of) the GW-BASIC of my youth; runs as written on bwBASIC.

+1  A:

C#

``````public static long[] GenerateFibonacciNumbers(int n)
{
long[] arr = new long[n];
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i < n; i++)
{
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr;
}
``````
+1 my favorite solution
+1  A:

Runtime solution for the D programing language:

``````struct Fib_(T)
{
int opApply(int delegate(ref T i) dg)
{
T i, j = 1, k = 1, m;
i = 1; if(int r = dg(i)) return r;
i = 1; if(int r = dg(i)) return r;
while(true)
{
i = m = j + k; if(int r = dg(i)) return r;
i = j = k + m; if(int r = dg(i)) return r;
i = k = m + j; if(int r = dg(i)) return r;
}
}
}
template Fib(T) { Fib_!(T) Fib; }
``````

usage:

``````foreach(long f; Fib!(long)) writef("%s\n", f);
``````
+2  A:

Using R:

``````n <- 20

l1 <- (1+sqrt(5))/2 ; l2 <- (1-sqrt(5))/2

P <- matrix(c(0,1,1,0),nrow=2)
S <- matrix(c(l1,1,l2,1),nrow=2)
L <- matrix(c(l1,0,0,l2),nrow=2)
C <- c(-1/(l2-l1),1/(l2-l1))

y<-c(0)
sapply(seq(1,10,2),function(k) y <<- rbind(y,P %*% S %*% L^k %*% C))
y
``````
+14  A:

This is my favourite implementation of the fibonacci sequence:

This isn't exactly what I was looking for, but this is the best answer so far.
A:

I have this in VBA. I used double just to get high numbers.

``````Sub fib(i As Integer)
Dim j As Double, a As Double, b As Double
j = 0
a = 0
b = 1
While j < i
Debug.Print a
b = b + a
a = b - a
j = j + 1
Wend

End Sub
``````
A:

MIT Scheme:

``````(define (fibo x y iters)
(begin
(display x) (newline)
(if (= iters 0)
'()
(fibo y (+ x y) (- iters 1))
)
)
)
``````

And run with:

``````(lambda ()
(display "How many terms?: ")
)
``````

(I'm new to Scheme - I don't know how to actually benchmark code yet, so I can't give benchmarks)

A:

non-recursive, linear runtime (and quite simple):

``````void fibPrintFirstN(int n) {
int f1 = 0;
int f2 = 1;
while(n-- > 0) {
printf("%d\n", f1);
f1 += f2;
f2 = f1;
}
}
``````