AK's weblog

I just stumbled across a pretty cool algorithm to compute Fibonacci number algorithm. So, I guess everybody knows the traditional recursive definition

fib(n) = fib(n-1) + fib(n-2)

fib(1) = 1

fib(0) = 1

Well, the disadvantage of this algorithm is that you can only compute fib(n) when you've computed fib(n-1) and fib(n-2) before. Well, with Binet's formula, you can compute the nth Fibonacci number without knowing any other Fibonacci number. The following C sample code shows how:

#include <math.h>

#include <stdio.h>



float fib(unsigned int n) {

  double a, b;

  a = (1.0/2.0)*(1.0+sqrt(5));

  b = (1.0/2.0)*(1.0-sqrt(5));

  return ((1.0/sqrt(5))*(pow(a,n+1)-pow(b,n+1)));

}





int main(void) {

  unsigned int n;

  for (n=0;n<100;++n) {

    printf("%f\n",fib(n));

  }

  return 0;

}