Fibonacci Functions

May 20th, 2008 by DeWitt Clinton

Tim Bray recently wrote in a short post entitled Language-Book Principles:

I am getting really, really bored with factorial and Fibonacci algorithms. It is really remarkably infrequent that I implement any code that looks much like either.

To which I responded:

Ah, but they do matter! You can tell a *lot* about how a language works by looking at those simple examples. Does it encourage and/or optimize for tail-recursion? Does the language use strong typing / type annotations / type inference? Parameter pattern matching? Does it feel functional vs. imperative? Compare a Fibonacci implementation in Lisp to ML to C to Java to Scala and the differences are immediately apparent.

Here are some examples, courtesy of LiteratePrograms, slightly modified by me in a few cases. Any bugs introduced are my fault entirely, I’m sure.

A trivial, elegant, and painfully overflowing recursive implementation in C:

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

Again in C, but using iteration instead of recursion:

unsigned long fib(unsigned long n)
{
  unsigned long f0 = 0;
  unsigned long f1 = 1;
  unsigned long result = 0;
  if (n == 0) return 0;
  while (n--) {
    result = f1;
    f1 = f0 + f1;
    f0 = result;
  }
  return result;
}

A tail recursive Fibonacci generator in Lisp:

(defun fib-trec (n)
  (labels ((calc-fib (n a b)
                     (if (= n 0)
                         a
                       (calc-fib (- n 1) b (+ a b)))))
          (calc-fib n 0 1)))

(GNU Clisp 2.43 on my OSX box evals (fib-trec 5000) instantly, so I guess it must be optimizing the tail call.)

A marginally cleaner but otherwise identical version in Scheme:

(define (fib n)
  (letrec ((fib-aux (lambda (n a b)
    (if (= n 0)
        a
        (fib-aux (- n 1) b (+ a b))))))
  (fib-aux n 0 1)))

A succinct and iterative approach in Python:

def fib(n):
  a, b = 0, 1
  for i in xrange(n):
    a, b = b, a + b
  return a

The same idea, but using generators:

def fib():
  a, b = 0, 1
  while True:
    a, b = b, a + b
    yield a

And again in Python, this time using memoization:

def fib(n):
  memo = {0:0, 1:1}
  if not n in memo:
     memo[n] = fib(n-1) + fib(n-2)
  return memo[n]

(You can move the declaration of memo to speed it up on successive calls.)

A limited precision (32 or 64 bit) implementation in OCaml:

let rec i_fib a b = function
| 0 -> a
| 1 -> b
| k when k > 1 -> i_fib b (a+b) (k-1)
| _  -> raise (Invalid_argument)

(If you don’t like the ML then you have no soul.)

Same thing, this time in Haskell:

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

(Can you tell I’m a fan of parameter pattern matching and type annotation/inference?)

A very pretty tail recursive implementation in Scala:

def fib(n:Int) = fib_tr(n, 1, 0) 
 
def fib_tr(n: Int, b: Int, a: Int): Int = n match {
  case 0 => a 
  case _ => fib_tr(n-1, a + b, b)
}

(Okay, I may have just fallen in love with Scala.)

And lastly, for Tim, a fast implementation in Erlang:

fibo3(N) ->
    {Fib, _} = fibo3(N, {1, 1}, {0, 1}),
    Fib.
 
fibo3(0, _, Pair) -> Pair;
fibo3(N, {Fib1, Fib2}, Pair) when N rem 2 == 0 ->
    SquareFib1 = Fib1*Fib1,
    fibo3(N div 2, {2*Fib1*Fib2 - SquareFib1, SquareFib1 + Fib2*Fib2}, Pair);
fibo3(N, {FibA1, FibA2}=Pair, {FibB1, FibB2}) ->
    fibo3(N-1, Pair, {FibA1*FibB2 + FibB1*(FibA2 - FibA1), FibA1*FibB1 + FibA2*FibB2}).

I see great beauty in all* of these.

*Well, except for the Erlang, which I find to be pathological.

This entry was posted on Tuesday, May 20th, 2008 by DeWitt Clinton and is filed under programming. You can bookmark this post at delicious. You can digg this post. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

David Madden Says:
May 20th, 2008 at 8:01 am

Ok, I apologize if this turns the post into a dumping ground for every Fibonacci function under the sun, but I found this a while ago on the net (sadly I cant remember who the author is) and liked it.

It uses a block to define the function when a value is added to the hash.

fib = Hash.new{ |h, n| n < 2 ? h[n] = n : h[n] = h[n - 1] + h[n - 2] }
puts fib[15]

dbt Says:
May 20th, 2008 at 9:29 am

that is some pathological erlang.

fib(0) -> 0;
fib(1) -> 1;
fib(N) when N > 1 -> fib(N-1) + fib(N-2).

(If you really truly must optimize it, clearly a fib_server is the way to go).

DeWitt Clinton Says:
May 20th, 2008 at 9:34 am

@dbt - Thanks! Can you write up a quick fib_server. This I have to see.

@David - Cute. Write through caching ftw.

dbt Says:
May 20th, 2008 at 12:37 pm

Try this. gen_server has a lot of boiler plate but it gets the idea across.

http://pianosa.googlecode.com/svn/trunk/erlang/fib_server.erl

Dylan Schiemann Says:
May 20th, 2008 at 12:55 pm

Eugene Lazutkin recently wrote an article about AOP in JavaScript with Dojo… the example of at the end is of course a Fibonacci function in JavaScript:

http://lazutkin.com/blog/2008/may/18/aop-aspect-javascript-dojo/

DeWitt Clinton Says:
May 20th, 2008 at 2:12 pm

@dbt - Holy cow.

Alec Muffett Says:
May 20th, 2008 at 11:50 pm

Yes, yes, very salutary and quite wonderful - but how do you get to see the result in each language? :-)

dbt Says:
May 21st, 2008 at 8:16 am

@DeWitt — is that a good holy cow or a bad one? :)

One thing I don’t take into consideration is the cost of iterating down the list vs. calculating. I could see something like:

calc(Val, #cache{first=First} = Cache) when First/5 >= Val ->
… implement normal recursive fib rather than iterating all the way down the list.

Anyway, you use the server state to store all the fib values, and you can use that to calculate the next value. Should be pretty straight forward…

Link Bundle - May 21 | franzone.com Says:
May 21st, 2008 at 8:36 am

[...] Fibonacci Functions DeWitt Clinton writes a very interesting article which analyzes the differences in several programming languages by comparing implementations of the fibonacci algorithm. [...]

dbt Says:
May 21st, 2008 at 8:45 am

also, note that the non-caching fib() is pretty damn fast. Check out fib2/1 at the above link… 2.1s to calculate fib2(100000) on a relatively slow PC.

DeWitt Clinton Says:
May 21st, 2008 at 8:45 am

@dbt - A very good holy cow. : ) Imagine how much code it would take to implement the same thing in Java, for example.

dbt Says:
May 21st, 2008 at 9:25 am

(note that a two line change — one if I had made a macro for {local, ?SERVER} — turns it into a network service (for other linked fib clients)….

BTW I’ll point out my trivially recursive example is pathological in the case of large numbers, and I’d recommend instead the fib2 in my fib_server.erl code above.

dbt Says:
May 21st, 2008 at 9:28 am

(er, for other linked erlang vms.)

Andy Lipscomb Says:
May 21st, 2008 at 4:09 pm

And a memo-izing version in REALbasic:

Sub fibonacci(position as integer) as uint64
static f(1) as uint64
dim q as integer
f(0)=0
f(1)=1
q = ubound(f)
do until q >= position
f.Append f(q)+f(q-1)
q = q+1
loop
return f(position)

Fibonacci This » EphBlog Says:
May 22nd, 2008 at 9:11 am

[...] Clinton ‘98 is a fan of Fibonacci functions and other simple examples for evaluating computer languages. You can tell a *lot* about how a [...]

Alex Morega Says:
May 28th, 2008 at 12:04 pm

To pick a knit: your python memorization example is not actually memorizing. Perhaps if the “memo” dict was outside fib… :)

DeWitt Clinton

16 Responses to “Fibonacci Functions”