javascript 为什么这个斐波那契数函数对于第 4000 个值返回无穷大？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/8331492/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Why does this Fibonacci number function return infinity for the 4000th value?
提问by vetri02
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();
not working shows infinity why?
不工作显示无穷大为什么？
回答by sidyll
Simple: because it's too big.
很简单：因为它太大了。
The 300th term is 222232244629420445529739893461909967206666939096499764990979600, so you might imagine how big the 4000th is. You can't hold such value in a JavaScript variable.
第 300 项是 222232244629420445529739893461909967206666939096499764990979600，所以你可以想象第 4000 项有多大。你不能在 JavaScript 变量中保存这样的值。
If you really want to calculate it, use an arbitrary precision library, and maybe something other than JavaScript if you want to calculate it fast.
如果您真的想计算它，请使用任意精度的库，如果您想快速计算，可以使用 JavaScript 以外的其他库。
Check GNU Multiple Precision Arithmetic Library - GMP. Nice to use with C, and it even has special Fibonacci functions.
检查GNU 多精度算术库 - GMP。很适合与 C 一起使用，它甚至具有特殊的 Fibonacci 函数。
Here's a little C program to do the job:
这是一个小 C 程序来完成这项工作：
#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 39909473435004422792081248094960912600792570982820257852628876326523051818641373433549136769424132442293969306537520118273879628025443235370362250955435654171592897966790864814458223141914272590897468472180370639695334449662650312874735560926298246249404168309064214351044459077749425236777660809226095151852052781352975449482565838369809183771787439660825140502824343131911711296392457138867486593923544177893735428602238212249156564631452507658603400012003685322984838488962351492632577755354452904049241294565662519417235020049873873878602731379207893212335423484873469083054556329894167262818692599815209582517277965059068235543139459375028276851221435815957374273143824422909416395375178739268544368126894240979135322176080374780998010657710775625856041594078495411724236560242597759185543824798332467919613598667003025993715274875 real 0m0.005s user 0m0.001s sys 0m0.002s
回答by Mike Hogan
Ok, this is extremelylate to the party, but just for the sake of completeness, here is a pure javascript solution. It uses a couple of libraries.
好吧，这是非常迟到了，但只是为了完整起见，这里是一个纯JavaScript解决方案。它使用了几个库。
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).
您将需要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]);
The code is a little eccentric (the use of load() and window) because I wanted to test it in rhino, without adding npm support. If that confuses you, just pretend you're seeing a require() call :)
代码有点古怪（使用 load() 和 window），因为我想在 rhino 中测试它，而不添加 npm 支持。如果这让您感到困惑，请假装您看到的是 require() 调用 :)
回答by georg
Although already accepted, I think I can offer a simpler solution. Just store numbers in arrays, one digit per element, and perform addition like you did in elementary school - "in columns". It goes like this:
虽然已经被接受，但我想我可以提供一个更简单的解决方案。只需将数字存储在数组中，每个元素一个数字，然后像在小学时一样执行加法 - “按列”。它是这样的：
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 like this:
而斐波那契函数是这样的：
function fib(n) {
var f1 = [0];
var f2 = [1];
while (n--) {
var f3 = add(f1, f2)
f1 = f2;
f2 = f3;
}
return f1.join("");
}
Seems totally ineffective, but only takes fractions of second to get fib(4000)on a 2.3GHz macbook.
似乎完全无效，但只需要几分之一秒就可以fib(4000)使用 2.3GHz macbook。
回答by kennebec
fibonacci(4000) [836 digits]
斐波那契(4000) [836 位]
39909473435004422792081248094960912600792570982820257852628876326523051818641373433549136769424132442293969306537520118273879628025443235370362250955435654171592897966790864814458223141914272590897468472180370639695334449662650312874735560926298246249404168309064214351044459077749425236777660809226095151852052781352975449482565838369809183771787439660825140502824343131911711296392457138867486593923544177893735428602238212249156564631452507658603400012003685322984838488962351492632577755354452904049241294565662519417235020049873873878602731379207893212335423484873469083054556329894167262818692599815209582517277965059068235543139459375028276851221435815957374273143824422909416395375178739268544368126894240979135322176080374780998010657710775625856041594078495411724236560242597759185543824798332467919613598667003025993715274875
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, ' ');
}
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>
回答by zzzzBov
Because Number.MAX_VALUE + Number.MAX_VALUE === Infinity
因为 Number.MAX_VALUE + Number.MAX_VALUE === Infinity
The issue is that sumexceeds JavaScripts capabilities for storing numeric values.
问题是sum超出了 JavaScript 存储数值的能力。
回答by Gabriel Gartz
For better results you can use the jsperf.com: http://jsperf.com/fib-vs-fib-loga/
为了获得更好的效果，你可以使用jsperf.com：http://jsperf.com/fib-vs-fib-loga/
Just a lite change in the function to get the max position possible to calculate by javascript.
只需在函数中稍作更改即可获得 javascript 可能计算的最大位置。
Yes, the result will be diferent on each browser and arch bean used.
是的，在每个浏览器和使用的 arch 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();
The result is: 14738.077637632156222e+3071.3069892237633987e+308Where 1473 is the maximum fibonacci position possible to calculate with javascript.
结果是：14738.077637632156222e+3071.3069892237633987e+308其中 1473 是可以使用 javascript 计算的最大斐波那契位置。
回答by tonyland
PubNub's Ariya Hidayat taught us this last night:
PubNub 的 Ariya Hidayat 昨晚告诉我们：
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]); }, []);
}
回答by rafaelcastrocouto
You can use WebWorkersand BigIntto calculate huge values of the fibonacci sequence:
您可以使用WebWorkers和BigInt来计算斐波那契数列的巨大值：
var input = document.querySelector('input');
var output = document.querySelector('#output');
var fulloutput = document.querySelector('#fulloutput');
var time = document.querySelector('#time');
var start, end;
var worker;
var createWorker = function () {
if (worker) worker.terminate();
var workerContent = "self.onmessage = " + workerFunction.toString();
var blob = new Blob([workerContent], {type: 'application/javascript'});
worker = new Worker(URL.createObjectURL(blob));
worker.onmessage = receive;
};
var workerFunction = function(event) {
var total = BigInt(event.data);
var fib = function(index) {
var temp;
var last = BigInt(0);
var sum = BigInt(1);
for (; index >= BigInt(2); index--) {
if (index % BigInt(1000) === BigInt(0))
self.postMessage({
total: total,
calculating: index
});
temp = last;
last = sum;
sum += temp;
}
return sum;
};
if (total > BigInt(0)) self.postMessage({done: fib(total)});
else self.postMessage({error: 'Input error'});
};
window.addEventListener('load', function () {
if (!window.Worker ||
!window.Blob ||
!window.URL ||
!window.BigInt) {
output.textContent = 'Browser not supported';
} else {
start = performance.now();
createWorker();
output.textContent = 'Worker created, starting calculations';
worker.postMessage(input.value);
input.addEventListener('change', function () {
createWorker();
start = performance.now();
output.textContent = 'Calculating';
worker.postMessage(input.value);
});
}
});
var receive = function(event) {
if (event.data.error) {
output.textContent = event.data.error;
}
if (event.data.calculating) {
var total = BigInt(event.data.total);
var index = BigInt(event.data.calculating);
var progress = (BigInt(100) * (total - index) / total);
output.textContent = 'Calculating ' + progress + '%';
}
if (event.data.done) {
var formatter = new Intl.NumberFormat('en', {
notation: 'scientific'
});
output.textContent = formatter.format(event.data.done);
fulloutput.textContent = event.data.done;
end = performance.now();
time.textContent = 'It took ' + ((end - start) / 1000) + ' seconds';
}
};body {
display: grid;
place-content: center;
min-height: 100vh;
}
p, pre {
text-align: center;
width: 80vw;
white-space:normal;
word-wrap: break-word;
}<p>N: <input type="number" value="4000"></p>
<pre id="output"></pre>
<pre id="fulloutput"></pre>
<pre id="time"></pre>