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

Question

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?

Answer 1

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)

Answer 2

Recursive Way:

public static int fib(int n)
{
    // Base Case
    if (n <= 2)
        return 1;     
    else 
        return fib(n-1) + fib(n-2);     
}

Answer 3

Ruby:

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

Answer 4

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

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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

Answer 9

How about as music?

Answer 10

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)

Answer 11

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;

Answer 12

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.

Answer 13

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]

Answer 14

PowerShell using a pipe:

0..20 | %{ $i=0;$j=1} { $o = $i+$j; $i=$j; $j=$o; $o}

Answer 15

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/

Answer 16

This is your brain:

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?

Answer 17

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.

See http://avinashv.net/2008/04/python-decorators-syntactic-sugar/ for details.

fibonacci(332): 1082459262056433063877940200966638133809015267665311237542082678938909 in 0.009884s

Answer 18

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)

Answer 19

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])
      (;;  (resize answer 0 N)
           (= answer:0 0)
           (= answer:1 1)
           (do [n natural] 2 N 1
               (= answer:n (+ answer:(-- n)  answer(- n 2))
           )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.

Answer 20

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

Answer 21

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.

Answer 22

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

Answer 23

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

Answer 24

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

Answer 25

This is my favourite implementation of the fibonacci sequence:

Answer 26

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

Answer 27

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?: ")
  (fibo 0 1 (read))
)

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

Answer 28

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