为什么这个斐波那契数函数在第4000个值时返回无穷大
Why does this Fibonacci number function return infinity for the 4000th value?
考虑：
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();
它不起作用，显示出无穷大。为什么？
简单：因为它太大了。
第300个术语是222232244629420445529973989346109967206666939096499764990979600，所以你可以想象第4000个术语有多大。你不能在JavaScript变量中保存这样的值。
如果你真的想计算它，可以使用任意精度的库，如果你想快速计算，可以使用JavaScript以外的东西。
检查GNU多精度算术库-GMP。很好地与C一起使用，它甚至有特殊的Fibonacci函数。
这里有一个小的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纤维c-lgmp
并运行：-(
时间/a.out399094734350044227920812480949609126007925709820252785262887632652305181864137343354913676942413244229396930653752011827387962802544323537036225095543565417159289667908648144582231419142725908974684721803706396953344496626503128747355609262982644041683090642143510444509777749425236777608092260951518520527813529754494825658383698091837717874396608251408243431319117112963924571386748659392354417789373542860223821224916463145250765860340001200368532298848384889623514926325777553544529049241294565662519417235020049873878602731379207893212335423484873469083055632989416726281869259981520958251727796505906823554313945937502827685122143581595737427314442290941639537517873926854436812689424097913532217600737478099801065771077567525856041594078495411724236560242597759185543824798332467919613598667003025993715274875实际0m0.005s用户0m0.001s系统0m0.002s
为了完整起见，这里有一个纯JavaScript解决方案。它使用了几个库。
您将需要大整数和树懒。该解决方案还需要JavaScript 1.7生成器。
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((调用：(
一个更简单的解决方案：只需将数字存储在数组中，每个元素一位，然后像在小学时那样执行加法-"在列中"；。它是这样的：
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("");
}
这似乎完全无效，但在2.3 GHz的MacBook上只需要几分之一秒就可以获得fib(4000)。
因为Number.MAX_VALUE + Number.MAX_VALUE === Infinity
问题是sum超过了JavaScript存储数值的能力。
调用
fibonacci(4000)
结果(836位(
3990947343500442279208124809496091260079257098202527852628876326523051818641373433549136769424132442293969306537520118273879628025443235370362250955435654171592896679086481445822314191427259089746847218037063969533444966265031287473556092629826440416830906421435104445097777494252367776080922609515185205278135297544948256583836980918377178743966082514082434313191171129639245713867486593923544177893735428602238212249156564631452507658603400012003685322988483848896235149263257775535445290492412945656625194172350200498738786027313792078932123354234848734690830554556329894167262818692599815209582517277965059068235543139459375028276851221435815957374273143824422909416395378739268544368126889424097913532217600737478099801065771077562556041594078495411724236560242597759185543824798332467919613598667003025993715274875
代码
<!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
// Internet Explorer version (if any) determines the 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= ize; 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>
这只是函数中的一个轻微变化，以获得JavaScript可能计算的最大位置。
是的，使用的每种浏览器和体系结构的结果都会有所不同。
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计算的最大斐波那契位置。
BigInt对象可用于增加JavaScript允许的最大整数值，而不限于计算机体系结构。
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]); }, []);
}
您可以使用WebWorkers和BigInt来计算Fibonacci序列的巨大值：
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>在无穷大之前实际上有1475个数字。这个号码是1.3068992237633987e+308。
相关文章：
- 如何使用url加载程序在webpack中导入多个图像
- 多个单选按钮组相互干扰
- 下拉选择可自动更改第二个下拉选择
- onkeyup无法动态创建多个文本区域
- JQuery合并了keyup和focusout两个函数
- 正在验证8个真/假复选框或复选框中的2个
- 借助asp.net验证或java脚本对多个文本进行验证
- 如何使用 node.js 比较两个 json 数组
- 为复选框javascript指定两个值
- Phonegap-(安卓/iphone）多个图像的图像库出现问题
- jQuery自定义验证比较多个输入的序列
- Html页面上的多个Base64图像和平滑加载
- 节点是否需要模块传递带有方括号的arg?这是个错误吗
- 使用javascript检查多个输入值，并在1次检查中标记多个输入框
- KnockoutJS-组件-多个实例
- 用每小时的差值填充数组/列表-从下拉列表中给定两个时间值
- 科尔多瓦页面类应用程序中的多个谷歌地图
- 使用数据上的角度更改设置集合的第一个元素的动画
- 为什么grunt contrib connect的中间件选项的第三个参数是未定义的
- 为什么这个斐波那契数函数在第4000个值时返回无穷大
