Яваскрипт Фибоначчи

Question

function fibo() {
var first,second,add;
for(var i=0;i<4000;i++){
    if(i === 0){
        first = 1;
        second = 2;
    }
    add = first + second;
    first = second;
    second = add;

}

alert(add);

}

fibo();

не работает показывает бесконечность почему?

Answer 1

Простой: потому что он слишком большой.

300-й член - 222232244629420445529739893461909967206666939096499764990979600, так что вы можете представить, насколько велик 4000-й. Вы не можете хранить такое значение в переменной JavaScript.

Если вы действительно хотите рассчитать его, используйте библиотеку произвольной точности и, возможно, что-то отличное от JavaScript, если вы хотите быстро рассчитать ее.

Проверка Библиотека многократной точности GNU - GMP . Приятно использовать с C, и он даже имеет специальные функции Фибоначчи .

---

Вот небольшая программа на C для выполнения этой работы:

#include <gmp.h>

int main()
{
    mpz_t num;
    mpz_init(num);

    mpz_fib_ui(num, 4000);
    gmp_printf("%Zd\n", num);

    return 0;
}

Компилировать с:

cc fib.c -lgmp

И беги: -)

time ./a.out
39909473435004422792081248094960912600792570982820257852628876326523051818641373433549136769424132442293969306537520118273879628025443235370362250955435654171592897966790864814458223141914272590897468472180370639695334449662650312874735560926298246249404168309064214351044459077749425236777660809226095151852052781352975449482565838369809183771787439660825140502824343131911711296392457138867486593923544177893735428602238212249156564631452507658603400012003685322984838488962351492632577755354452904049241294565662519417235020049873873878602731379207893212335423484873469083054556329894167262818692599815209582517277965059068235543139459375028276851221435815957374273143824422909416395375178739268544368126894240979135322176080374780998010657710775625856041594078495411724236560242597759185543824798332467919613598667003025993715274875

real    0m0.005s
user    0m0.001s
sys     0m0.002s

Answer 2

Хорошо, это крайне поздно для вечеринки, но просто для полноты, вот чистое решение javascript. Он использует пару библиотек.

Вам потребуется biginteger (http://silentmatt.com/biginteger/) и лень (https://github.com/rfw/sloth.js).) Для решения также требуются генераторы Javascript 1.7 (см. https://developer.mozilla.org/en-US/docs/JavaScript/Guide/Iterators_and_Generators).

var window = {};
load('biginteger.js');
load('sloth.js');
var sloth = window.sloth;


function fibonacci(){
  var fn1 = new BigInteger(1);
  var fn2 = new BigInteger(1);

  while (1){
    var current = fn2;
    fn2 = fn1;
    fn1 = fn1.add(current);
    yield current;
  }
}

var iter = sloth.iter(fibonacci());
var some = sloth.ify(iter).take(4000).force();
print(some[299]); 
print(some[3999]);

Код немного эксцентричный (использование load () и window), потому что я хотел протестировать его в Rhino, не добавляя поддержку npm. Если это вас смущает, просто представьте, что вы видите вызов require ():)

Answer 3

Хотя это уже принято, я думаю, что могу предложить более простое решение.Просто храните числа в массивах, по одной цифре на элемент, и выполняйте сложение, как в начальной школе - «в столбцах».Это выглядит так:

function add(a, b) {
    while (a.length < b.length) a.unshift(0);
    while (a.length > b.length) b.unshift(0);
    var carry = 0, sum = []
    for (var i = a.length - 1; i >= 0; i--) {
        var s = a[i] + b[i] + carry;
        if (s >= 10) {
            s = s - 10;
            carry = 1;
        } else {
            carry = 0;
        }
        sum.unshift(s);
    }
    if (carry)
        sum.unshift(carry);
    return sum;
}

И функция Фибоначчи выглядит следующим образом:

function fib(n) {
    var f1 = [0];
    var f2 = [1];

    while (n--) {
        var f3 = add(f1, f2)
        f1 = f2;
        f2 = f3;
    }
    return f1.join("");
}

Кажется совершенно неэффективным, но занимает всего доли секунды, чтобы получить fib(4000) на 2,3 ГГцMacbook.

Answer 4

Фибоначчи (4000) [836 цифр]

39909473435004422792081248094960912600792570982820257852628876326523051818641373433549136769424132442293969306537520118273879628025443235370362250955435654171592897966790864814458223141914272590897468472180370639695334449662650312874735560926298246249404168309064214351044459077749425236777660809226095151852052781352975449482565838369809183771787439660825140502824343131911711296392457138867486593923544177893735428602238212249156564631452507658603400012003685322984838488962351492632577755354452904049241294565662519417235020049873873878602731379207893212335423484873469083054556329894167262818692599815209582517277965059068235543139459375028276851221435815957374273143824422909416395375178739268544368126894240979135322176080374780998010657710775625856041594078495411724236560242597759185543824798332467919613598667003025993715274875

<!doctype html>
<html lang= "en">
<head>
<meta charset= "utf-8">
<title> Javascript Big Integers</title>

<style>
body{margin: 0 1em;width: auto;font-size: 125%}
p{max-width: 800px;margin: 1ex 1em;}
div{margin: 1em;}
input, textarea, label{
    font-size: 1em;line-height: 1.2;font-family: arial, sans-serif;
    font-weight: 600;padding: 0 2px;
}
textarea{
    background-color: white;    color: black;   width: 90%; 
    border: 2px ridge silver;position: absolute;z-index: 5;overflow-y: scroll;height: 500px;
}
#fibInp{text-align: right;}
#calcfibBtn, #stopFibBtn{color:navy;cursor:pointer}
#calcfibBtn:focus, #stopFibBtn:focus, #calcfibBtn:hover, #stopFibBtn:hover{color:red}

</style>

<script>
//utilities
//ie version (if any) determines initial loop size
/*@cc_on
    @if(@_jscript_version> 5.5){
    navigator.IEmod= document.documentMode? document.documentMode: 
    window.XMLHttpRequest? 7: 6;
    }
    @end
@*/

function mr(hoo){
    if(hoo){
        if(typeof hoo== 'string') return document.getElementById(hoo);
        if(hoo.nodeType=== 1) return hoo;
    }
    return null;
}
if(!Array.prototype.map){
    Array.prototype.map= function(fun, scope){
        var L= this.length, A= Array(this.length), i= 0, val;
        if(typeof fun== 'function'){
            while(i< L){
                if(i in this){
                    A[i]= fun.call(scope, this[i], i, this);
                }
                ++i;
            }
            return A;
        }
    }
}
//Big Integer Object
function BigInt(n, sign){
    if(this.constructor!= BigInt){
        if(n.constructor== BigInt) return n;
        n= n.toString();
        if(/^\d+$/.test(n)){
            var digits= n.split('').map(Number);
            return new BigInt(digits.reverse(), sign);
        }
        else{
            throw Error('base 10 integer input only');
        }
    }
    while(n.length && !n[n.length - 1]){
        --n.length;
    }
    this.digits= n;
    this.length= n.length;
    if(sign== -1) this.sign= sign;
}
BigInt.prototype.toString= function(){
    var s= this.digits.slice().reverse().join('');
    if(this.sign== -1) s= '-'+s;
    return s;
}
BigInt.prototype.plus= function(n){
    n= BigInt(n);
    var n1= this.digits, n2= n.digits,
    len1= n1.length, len2= n2.length,
    hoo= Array(Math.max(len1, len2)+ 1),
    size= Math.min(len1, len2), temp= 0, dig;
    for(var i= 0; i < size; i++){
        dig= n1[i]+ n2[i]+ temp;
        hoo[i]= dig%10;
        temp= (dig/10)|0;
    }
    if(len2> len1){
        n1= n2;
        len1= len2;
    }
    for(var i= size; temp && i < len1; i++){
        dig= n1[i]+ temp;
        hoo[i]= dig%10;
        temp= (dig/10)|0;
    }
    if(temp) hoo[i]= temp;
    while(i < len1){
        hoo[i]= n1[i];
        ++i;
    }
    return new BigInt(hoo);
}
// Math.fibonacci methods
Math.fibonacci= function(n){
    var n1= 0, n2= 1, t= 1, fib= [], i= 0;
    var limit= 9007199254740992;
    while(n1< limit){
        fib[i++]= n1;
        if(i== n) return fib;
        n2= t;
        t= n1+n2;
        n1= n2;
    }
    if(n){
        t= fib.pop(), n1= fib.pop(), i= fib.length;
        while(i<n){
            fib[i++]= n1;
            n2= BigInt(t);
            t= n2.plus(n1);
            n1= n2.toString();
        }
    }
    return fib;
}
Math.nthFibonacci= function(n, ret){
    var fibs= [0, 1], i= 78;
    while(n && --i){
        fibs[2]= fibs[0]+ fibs[1];
        fibs.shift();
        n--;
    }
    if(n){
        fibs= [BigInt(fibs[0]), BigInt(fibs[1])];
        while(n--){
            fibs[2]= fibs[0].plus(fibs[1]);
            fibs.shift();
        }
    }
    return ret? fibs: fibs[0];
}
// demonstration code
Fib={
    clear: function(){
        mr('yw_fib_tex').value= '';
        Fib.wait= false;
        mr('fibInp').value= '';
    },
    counter: 1,
    demo: function(){
        mr('calcfibBtn').onclick= Fib.getFib;
        mr('stopFibBtn').onclick= Fib.quitFib;
        mr('fibInp').onkeypress= Fib.keycheck;
        mr('fibInp').focus();
    },
    discomma: !!window.opera,
    getFib: function(){
        mr('yw_fib_tex').value= '';
        var d, c, n= mr('fibInp').value;
        n= parseInt(mr('fibInp').value);
        if(!n || n<2){
            mr('fibInp').value= '';
            mr('fibInp').focus();
            return true;
        }
        if(n<= 1100){
            d= Math.nthFibonacci(n).toString();
            var fibs= ['', n, d.length, d];
            Fib.report(fibs);
            return true;
        }
        if(n> 10000){
            d= Fib;
            c= d.counter;
            if(c> 2000){
                Fib.reach(d.low, d.high, n, c, Fib.report);
                return true;
            }
        }
        d= Math.nthFibonacci(1000, 1);
        Fib.reach(d[0], d[1], n, 1000, Fib.report);
        return true;
    },
    high: 1,
    keycheck: function(e){
        e= e || window.event;
        var k= e.charCode || e.keyCode;
        if(k== 13) Fib.getFib();
        return true;
    },
    low: 0,
    quitFib: function(){
        Fib.wait= true;
        mr('yw_fib_tex').focus();
    },
    reach: function(n1, n2, n, i, cb){
        var d, q, who, mf= Fib, F= Fib.reach;
        if(F.time=== undefined){
            F.top= n;
            F.count= i+1;
            F.time= new Date().getTime();
            F.cb= cb;
            F.tik= false;
        }
        q= n2.toString().length;
        who= mr('yw_fib_tex');
        if(who){
            if(q<2100) who.value= n2;
            else who.value= q+ ' digits...thinking...';
        }
        if(q> 20000) q= q> 100000? 10: 20;
        else if(q> 5000) q= q> 10000? 50: 100;
        else q= q> 1000? 200: 1000;
        if(navigator.IEmod) q/= 4;
        q= Math.min(q, F.top-F.count);
        while(q> 0){
            d= BigInt(n1).plus(n2);
            F.count++;
            n1= n2;
            n2= d;
            --q;
        }
        if(F.count>= F.top || Fib.wait){
            var t= (new Date()-F.time)/1000;
            d= d.toString();
            var fibs= [t, F.count, d.length, d, n1];
            F.time= undefined;
            if(typeof F.cb== 'function') return F.cb(fibs);
        }
        else{
            setTimeout(function(){
                F(n1, d)
            },
            0);
        }
    },
    report: function(fb){
        var mf= Fib, s, fibz, f1= fb[1], t= fb[0] || '', fN= fb[3];
        if(t){
            t+= mf.time;
            if(mf.wait) Fib.time+= t;
            else Fib.time= 0;
            t= t.toFixed(3)+' seconds to calculate ';
        }
        fibz= t+'fibonacci('+f1+') ['+fb[2]+' digits]';
        if(fb[4] && fN> mf.counter){
            mf.counter= f1;
            mf.low= fb[4];
            mf.high= fN;
        }
        fN= fN.toString();
        if(window.opera){
            fN= fN.replace(/(\d{10})/g, '$1 ');
        }
        fibz= fibz+'\n\n'+fN;
        mr('yw_fib_tex').value= fibz;
        Fib.wait= false;
        mr('yw_fib_tex').focus();
        return true;
    },
    time: 0,
    wait: false
}
window.onload= function(){
    Fib.demo();
}
</script>
</head>

<body>
<h2 id= "yw_fib_head"> Fibonacci numbers in javascript</h2>
<p>
This is a demonstration of Big Integer Math in Javascript, handling numbers of arbitrary precision.
The time it takes to calculate a large Fibonacci number depends on your computer and browser.</p>
<div>
<label> fibonacci#<input size= "5" id= "fibInp" type= "text" value= "1000"> </label>
<input type= "button" id= "calcfibBtn" value= "Calculate">
<input type= "button" id= "stopFibBtn" value= "Stop">
<br>
<textarea readonly= "readonly" id= "yw_fib_tex">
</textarea>
</div>
</body>
</html>

Answer 5

Поскольку Number.MAX_VALUE + Number.MAX_VALUE === Infinity

Проблема в том, что sum превышает возможности JavaScripts для хранения числовых значений.

Answer 6

Для лучших результатов вы можете использовать jsperf.com : http://jsperf.com/fib-vs-fib-loga/

Просто облегченное изменение в функции, чтобы получить максимальную позицию, которую можно вычислить с помощью JavaScript.

Да, результат будет отличаться в зависимости от браузера и используемого bean-компонента.

function fibo() {
    var first,second,add;
    for(var i=0;i<4000;i++){
        if(i === 0){
            first = 1;
            second = 2;
        }
        if(first+second > Number.MAX_VALUE){
            console.debug(i, first, second);
            return;
        }
        add = first + second;
        first = second;
        second = add;
    }
    alert(add);
}
fibo();

Результат: 1473 8.077637632156222e+307 1.3069892237633987e+308 Где 1473 - максимальная позиция Фибоначчи, которую можно вычислить с помощью JavaScript.

Answer 7

Ария Хидаят из PubNub научила нас этой ночью:

function fibo(n) {
    return Array.apply(0, Array(n)). reduce(function(x, y, z){ return x.concat((z < 2) ? z : x[z-1] + x[z-2]); }, []);
     }