числа Фибоначчи 1 кк итерация

Question

Я функцию для вычисления чисел Фибоначчи

function fib(n) { 
    var a = 1, 
    b = 1; 
    for (var i = 3; i <= n; i++) { 
    var c = a + b; 
    a = b; 
    b = c; 
    } 
    return b; 
} 

alert(fib(3)); // 2 
alert(fib(7)); // 13 
alert(fib(77)); // 5527939700884757 

Но с n > 10000 я получаю Infiniti заявление.

Как рассчитать числа Фибоначчи над (n > 1kk) в JavaScript?

Answer 1

Вам нужна библиотека с большим целым числом. Либо бросьте самостоятельно (это не так сложно), либо используйте библиотеки js-bigint, плавающие в сети (позвольте мне включить бесстыдный self-plug здесь).

Но для чисел числа Ларег Фибоначчи вы должны использовать другой алгоритм и делать это путем экспоненциальной матрицы. Если вы используете мою BigInt-библиотеку вы можете использовать следующий скрипт

function smallfibonacci(n) { 
    var i = 1, 
     j = 0, 
     k, l; 
    for (k = 1; k <= n; k++) { 
     l = i + j; 
     i = j; 
     j = l; 
    } 
    return j; 
} 

function fibonacci(n) { 
    var i = n - 1, 
     r; 
    var a, b, c, d, t, t1, t2, t3; 
    var e; 

    if (n <= 76) { 
     return smallfibonacci(n).toBigint(); 
    } 

    a = new Bigint(1); 
    b = new Bigint(0); 
    c = new Bigint(0); 
    d = new Bigint(1); 

    while (i > 0) { 
     if (i & 0x1) { 
      //t = d*(a + b) + c*b; 
      t1 = c.mul(b); 
      t2 = a.add(b); 
      t3 = d.mul(t2); 
      t = t3.add(t1); 

      //a = d*b + c*a; 
      t1 = d.mul(b); 
      t2 = c.mul(a); 
      a = t1.add(t2); 
      //b = t; 
      b = t.copy(); 
     } 
     //t = d*(2*c + d); 
     t1 = c.lShift(1); 
     t2 = t1.add(d); 
     t = d.mul(t2); 

     //c = c*c + d*d; 
     t1 = c.sqr(); 
     t2 = d.sqr(); 
     c = t1.add(t2); 
     //d = t; 
     d = t.copy(); 
     i >>>= 1; 
    } 
    r = a.add(b); 
    return r; 
} 

fibonacci(10000).toString(); 

Преобразование в строку еще не оптимизирован и нуждается в большей части выполнения здесь. Вычисление (но не печать!) F (1,000,000) требуется около 24 секунд на этой машине с питанием от среднего уровня.

Answer 2

Максимальное целое число в JavaScript составляет 2^53. 1000-й член последовательности Фибоначчи значительно превышает этот предел в ~ 4.35 * 10^208, поэтому вам нужно будет использовать библиотеку большого числа, чтобы вычислять числа на этом высоком уровне. Вот пример использования big.js, чтобы легко решить эту проблему.

function fib(n) { 
    var a = new Big(1), 
     b = new Big(1); 
    for (var i = 3; i <= n; i++) { 
     var c = a.plus(b); 
     a = b; 
     b = c; 
    } 
    return b; 
} 

alert(fib(3)); // 2 
alert(fib(7)); // 13 
alert(fib(77)); // 5527939700884757 
alert(fib(1000)); // 4.346655768...e+208