Computing the Fibonacci Numbers

This page contains various implementations of ways to compute the Fibonacci number. The first make use of the well-known defining equation

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

and is quite slow as it recursively calls itself excessively (and causes therefore a delay in loading this page). The second function has several small values precomputed and uses the equations

  fibonacci(2n)   = 2*fibonacci(n)*fibonacci(n+1)-fibonacci(n)*fibonacci(n);
  fibonacci(2n+1) = fibonacci(n)*fibonacci(n)+fibonacci(n+1)*fibonacci(n+1);
  fibonacci(2n+2) = 2*fibonacci(n)*fibonacci(n+1)+fibonacci(n+1)*fibonacci(n+1).

These equations permit to compute a Fibonacci number by calling the function at values of half the size. This brings down the exponential complexity of the first implementation to a linear number of calls of subroutines (measured in input n). So, for fibonacci(n), one would need fibonacci(m) and fibonacci(m+1) where m is the downrounded value of n/2.

One can bring this further down by computing fibonacci(n) and fibonacci(n+1) both simulatneously from fibonacci(m) and fibonacci(m+1). As functions have only one return value, an adjustment with less function calls could be made by storing fibonacci(m+1) in the global variable nextfib when fibonacci(m) is called. The resulting implementation needs only a logarithmic number of recursive calls when computing the fibonacci number at n.

  var nextfib;
  function fastfibonacci(y)
    { var z; var a; var b;
      switch(y)
        { case 0: nextfib = 1; return(0); break;
          case 1: nextfib = 1; return(1); break;
          case 2: nextfib = 2; return(1); break;
          case 3: nextfib = 3; return(2); break;
          case 4: nextfib = 5; return(3); break;
          case 5: nextfib = 8; return(5); break;
          default: z = Math.floor(y*0.5+0.1);
            a = fastfibonacci(z); b = nextfib;
            if (y%2 == 0) { nextfib = a*a+b*b; return(2*a*b-a*a); }
            else { nextfib = 2*a*b+b*b; return(a*a+b*b); } break; } }

Below are sample outputs of all three functions. As Fibonacci numbers grow fast in size, it becomes impossible to display all digits for large n. The values beyond 78 have rounding errors and are therefore not shown.

Remarks on the Complexity
Note that the complexity analysis given here counts additions and multiplications as unit time operations. This might be a bit rough, given the size of the numbers involved. For a more realistic analysis, one could also count the time usage for addition as O(n) and multiplication as O(n log n log log(n)), see the corresponding Wikipedia page. Then the corresponding complexities would be exponential, O(n (log(n))^2*O(log log(n))) and O(n log(n) log log(n)), for the three algorithms given here. Also the direct formula would due to the square roots and powers not be much better than the fastest algorithm above.