All geek questions in one place

Javascript fibonacci

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();

doesn't work shows infinity why?

+4
source share
7 answers

Simple: because it is too big.

The 300th term is 222232244629420445529739893461909967206666939096499764990979600, so you can imagine how big the 4000th is. You cannot hold such a value in a JavaScript variable.

If you really want to compute it, use an arbitrary precision library and maybe something other than JavaScript if you want to quickly compute it.

Check out the GNU Multipoint Arithmetic Library - GMP . Nice to use with C, and even special Fibonacci features .

Here's a little C program to do the job:

 #include <gmp.h> int main() { mpz_t num; mpz_init(num); mpz_fib_ui(num, 4000); gmp_printf("%Zd\n", num); return 0; }

Compile with:

  cc fib.c -lgmp

And run :-)

  time ./a.out


 real 0m0.005s
 user 0m0.001s
 sys 0m0.002s
+17
source

Well, it's extremely late for a party, but just for the sake of completeness, here is a clean javascript solution. It uses several libraries.

You will need biginteger ( http://silentmatt.com/biginteger/ ) and sloth ( https://github.com/rfw/sloth.js ). The solution also requires Javascript 1.7 generators (see 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]);

The code is a bit eccentric (using load () and windows) because I wanted to test it in a rhino without adding npm support. If this bothers you, just pretend you see a call to require () :)

+12
source

Although I have already made a decision, I think I can offer a simpler solution. Just store the numbers in arrays, one digit per element and add, as in elementary school, “in columns”. This happens as follows:

 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; }

And the fibonacci function is this:

 function fib(n) { var f1 = [0]; var f2 = [1]; while (n--) { var f3 = add(f1, f2) f1 = f2; f2 = f3; } return f1.join(""); }

It seems completely inefficient, but it only takes a split second to get fib(4000) on a Macbook 2.3 GHz.

+3
source

Because Number.MAX_VALUE + Number.MAX_VALUE === Infinity

The problem is that sum superior to JavaScripts for storing numeric values.

+2
source

Fibonacci (4000) [836 digits]

 <!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>
+2
source

For best results, you can use jsperf.com : http://jsperf.com/fib-vs-fib-loga/

Just a small change in the function to get the maximum position that can be calculated by javascript.

Yes, the result will be different for each browser and bean arch.

 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();

Result: 1473 8.077637632156222e+307 1.3069892237633987e+308 Where 1473 is the maximum fibonacci position that can be calculated using javascript.

+1
source

PubNub Aria Hidayat taught us last night:

 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]); }, []); }
0
source

Source: https://habr.com/ru/post/1383960/

More articles:


All Articles