*nth*fibonacci number for a job interview. We got talking about the shortest possible function to do this.

A fibonacci number is the sum of the two previous fibonacci numbers. The first and second fibonacci numbers are defined to be 1. That makes the third 2 (1 + 1), the fourth, 3 (2 + 1) and the fifth, 5 (3 + 2). Cake.

1, 1, 2, 3, 5, 8, 13, 21, ..

### Beautiful, Recursive and Horribly Inefficient

A clean and simple implementation in C might look like this:

int fibonacci(int n) { if (n == 0) return 0; else if (n == 1 || n == 2) return 1; return fibonacci(n - 1) + fibonacci(n - 2); }

Since I'm not a golfer, and code golf and mini golf are the only kinds of golf I play, I came up with the following in (bad) C.

f(n){return n<3?1:f(n-1)+f(n-2);}

Now, this one isn't correct for 0, which should return 0, so let's revise it at the expense of four more characters.

f(n){return n<3?n?1:0:f(n-1)+f(n-2);}

That works. Kind of. The highest

Okay, but the real problem with these functions is how phenomenally

As it turns out, to calculate

So we need to rework it and make the shortest version that isn't super inefficient. Since 46 in the maximum n that fits in a signed 32-bit int (and 47 unsigned), we could just make a precomputed look-up table.

That's as fast as you're probably going to get, but it's ugly and not particularly short.

You can also do it iteratively, without any recursion at all:

It's starting to get a little longer, though, so I don't bother to shove it on one line or abbreviate int fib(int n) into f(n) like with the shortest ones above. This function can be literally billions of times faster that the first ones.

*n*you can pass it is 46 (returning 1,836,311,903), because after that it overflows the 32 bit signed int (which holds a maximum value of*2*= 2,147,483,647).^{31}-1Okay, but the real problem with these functions is how phenomenally

*slow*they are. You wouldn't be able to get much past 46 anyway without rendering your machine absolutely useless. This is a classic recursive function, that is, a function that calls itself. This fibonacci function itself is often used to demonstrate the elegance of many functional languages. For example, here it is in OCaml:let rec fib = function | 0 -> 0 | 1 -> 1 | n -> fib (n-1) + fib (n-2)

As it turns out, to calculate

*f(46)*, you end up calling f() 3,672,623,805 times!*f(47)*makes 5.9 billion and*f(50)*makes nearly 20 billion calls. The recursive fibonacci sequence grows in number of calls on the order of*2*, which makes it roughly equivalent to the rice and chessboard puzzle.^{n}### Ugly Lookup Table

So we need to rework it and make the shortest version that isn't super inefficient. Since 46 in the maximum n that fits in a signed 32-bit int (and 47 unsigned), we could just make a precomputed look-up table.

int fib(int n) { static int fibs[] = { 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, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903 }; return fibs[n]; }

That's as fast as you're probably going to get, but it's ugly and not particularly short.

### Iterative and Fast

You can also do it iteratively, without any recursion at all:

int fib(int n) { if (!n) return 0; int p = 0, q = 1; for (int i = 2; i < n; i++) { int t = p; p = q; q = t + p; } return p + q; }

It's starting to get a little longer, though, so I don't bother to shove it on one line or abbreviate int fib(int n) into f(n) like with the shortest ones above. This function can be literally billions of times faster that the first ones.

### Returning to Recursion, with Memoization

*But..*I've got a short recursive version that outperforms this one on the whole, especially when called more than once, because it builds up a look-up table dynamically, with a simple technique broadly called memoization.f(n){static int m[64]={0,1,1,0};return !n||m[n]?m[n]:(m[n]=f(n-1)+f(n-2));}

Fast and short.

### No Recursion, No Iteration, Just a Formula

Let's do one more.

There is a closed form calculation of the fibonacci number that requires neither iteration nor recursion. You just calculate it and there you go. Here is my shortest implementation of that:

f(n){double A=sqrt(5),B=A/2;return(pow(0.5+B,n)-pow(0.5-B,n))/A;}

Short. No iteration, no recursion. Over several calls, I figure this will be slower than the previous function, but it's way slicker.

## No comments:

Post a Comment