Calculate the nth Fibonacci number

My Firefox will go up to F[1,510,300], after which the BigInt integer is too large to allocate.

My Chromium takes 43 seconds to calculate F[1,546,639,205], but crashes trying to write over about 97 MB/97,000,000 digits to the page.

As you enter n values, the expected number of digits and the memory requirement for the output string are displayed (one byte per UTF-8 digit). To prevent a crash, you may select how many digits to display, and navigate through the digits in blocks.

The conversion from integer to string takes much longer than the calculation itself, 246 seconds for my F[1,546,639,205]. (It is possible to do it in blocks recursively so the progress can be displayed, but then it takes a lot longer.)

To avoid the long-running script notification in Firefox, go to about:config, search for dom.max_script_run_time, and set the time to a greater number of seconds. For Chromium or Chrome, launch the browser with the --disable-hang-monitor flag.

The fast doubling algorithm turns a pair of Fibonacci numbers (F[k], F[k+1]) into (F[2k], F[2k+1]) or (F[2k+1], F[2k+2]), which then become (F[k], F[k+1]) for the next step:

F[2k] = F[k](2*F[k+1] - F[k])
F[2k+1] = F[k]² + F[k+1]²
F[2k+2] = F[2k] + F[2k+1] = F[k+1](2*F[k] + F[k+1])

Starting from (F[1], F[2]), any Fibonacci number F[n] may be arrived at by successive doubling, as illustrated for F[105] below; but at each step, the algorithm must know which path to follow, (F[2k], F[2k+1]) or (F[2k+1], F[2k+2]).

Tracing k from the top down, it becomes 2k for the pair below it when it is even; but when it is odd, it cannot be 2k, so it becomes 2k+1.

For example: taking 26 and 27 to be 2k and 2k+1, the next step down (k, k+1) is (13, 14).

But 13, being odd, cannot be 2k for the next step, so 13 and 14 become 2k+1 and 2k+2, and the next step down (k, k+1) is (6, 7).

The even/odd state of k at each step downward is thus a map for the algorithm to follow on the way up:
if k was even on the way down, it becomes 2k on the way up;
if k was odd on the way down, it becomes 2k+1 on the way up.

And the map turns out to be the binary digits of n, 0 for even and 1 for odd, read from left to right starting with the second.

For n = 105 = (1101001)₂, the map is 101001:

       k values | map          the actual numbers
-----------------------      -----------------------------------------------------------
            105 | 1                                    3928413764606871165730 = F[105]
         52  53 | 0                       32951280099             53316291173
         26  27 | 0                            121393                  196418
         13  14 | 1                               233                     377
      6   7     | 0                        8       13
      3   4     | 1                        2        3
-----------------------      -----------------------------------------------------------
  1   2                           1        1

So, the algorithm in a nutshell: starting from (F[1], F[2]), the number pair (F[k], F[k+1]) progresses “straight up” (F[2k], F[2k+1]) when the next map digit is 0, but “up and to the right” (F[2k+1], F[2k+2]) when the next map digit is 1, stopping at F[n]. That’s it.

There is no redundancy; each number is calculated and used only once.

The only numbers that remain in memory are the previous pair.

The algorithm:


function getFibonacci(n) {

  var map = n.toString(2); // the binary digits

  var fk = 1n;  // F[1]
  var fk1 = 1n; // F[2]
  var f2k, f2k1;

  if (map[1])
    doIt(1);

  function doIt(i) {

    if (map[i] == "0") {
      f2k = fk*(2n*fk1 - fk);   // F[2*k]
      if (i < map.length - 1)
        f2k1 = fk*fk + fk1*fk1; // F[2*k + 1]
    }

    else {
      f2k = fk*fk + fk1*fk1;      // F[2*k + 1]
      if (i < map.length - 1)
        f2k1 = fk1*(2n*fk + fk1); // F[2*k + 2]
    }

    fk = f2k;

    if (i < map.length - 1) {
      fk1 = f2k1;
      doIt(i + 1);
    }

  }

  return fk;

}