Последовательность Fibonacci приводит к бесконечности, затем NaN

Я играл с написанием последовательности Fibonacci по javascript, так как я никогда не пытался это сделать, придумал простую итеративную формулу для ее вычисления. Затем я решил протестировать его, выполнив 10000 итераций, чтобы увидеть результаты. к моему удивлению, он работал до 1476-й итерации, а затем сломался. 1477 и 1478 оба дали результат «Бесконечность». Я пробовал разные браузеры, меняя методы отображения, но получал те же результаты.Последовательность Fibonacci приводит к бесконечности, затем NaN

1475i - 1.3069892237633983e + 308 1476i - Бесконечность 1477i - Бесконечность 1478i - NaN

код используется:

<!DOCTYPE html><html><head><script> 
function fibonacci(){ 
var x = 1; 
var y = 0; 
    for(i=0;i<1478;i++){ 
    var box = document.createElement('div'); 
    box.setAttribute('id','box'+i); 
    document.body.appendChild(box); 
    document.getElementById('box'+i).innerHTML = [i] + 'i - ' + x; 
     x = x + y; 
    y = x - y; 
    } 
} 
</script></head><body onLoad="fibonacci();"><div id="output"></div></body></html>

Я не уверен, что если бы тогда функция сломал в некоторой точке, или что я, возможно, не принял во внимание в последовательности. И да, я понимаю, что я пропустил первое целое число, но это не должно влиять на функцию.

источник

2013-12-13 Thomas Cheney

JavaScript использует 64-битные целые числа. Смысл, JavaScript может содержать только значение, равное 2^64 - 1. Однако я не уверен на 100%, если это проблема, с которой вы сталкиваетесь. –

Это было сделано без просмотра каких-либо других образцов, которые при этом выглядят так, как будто большинство из них используют гораздо более сложные способы получения одного и того же результата.Я думаю, что это вопрос слишком большого числа. Благодарю. –

@JustinWood Это неправда. JavaScript использует 64-битную * плавающую точку * с 52-битной мантиссой. Один из способов увидеть это - заметить, что первое целое число, которое JavaScript не может содержать как число, равно 2^53 + 1. – Matt

1477-е число Фибоначчи слишком велико, чтобы быть представленным Javascript. «Переполнение» приводит к тому, что ваш номер становится Infinity.

Infinity - 1476thFibonacciNumber по-прежнему Infinity в следующем y расчет.

Затем на следующей итерации у вас есть Infinity - Infinity, что составляет NaN в JavaScript. С этого момента это NaN до конца.

источник

2013-12-13 22:25:15 Vache

Наибольшее значение Javascript может обрабатывать 1.7976931348623157e + 308. Если ваш код генерирует нечто большее, чем это, он сломается.

источник

2013-12-13 22:22:55

Для больших значений N, то ряд Фибоначчи может быть аппроксимирована

F(N) = math.pow(phi, N)/math.sqrt(5)

(Ref: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#fibround)

Где phi это золотое сечение: (SQRT (5) + 1)/2

Теперь вы можете выяснить, что наибольшее число Фибоначчи, который можно рассчитать следующим:

phi = (math.sqrt(5)+1)/2 
fibMax = math.floor(log(1.79769)/log(phi) + math.log(math.sqrt(5)))

И ответ из вышеизложенного ... 1475 - это самое большое число, которое вы смогли вычислить без переполнения.

Нижняя линия - после того, как ваш расчет переполнится, он будет продолжать делать это. Infinity + anything = Infinity, и интересно Infinity - anything = still infinity. И infinity + infinity = NaN. Поэтому, даже если вы вычтете последний номер снова, вы не вернетесь к «реальному» числу. Именно так обрабатывается переполнение.

источник

2013-12-13 22:32:02 Floris

Это путь выше моей головы, а не математик, но определенно очень интересный. Спасибо за информацию и ссылку. –

Не стоит беспокоиться - вы вычисляете серию Фибоначчи «вручную», что ставит вас в категорию «больше математиков, чем не». Я просто показывал, что место, где ваши расчеты перевернуты, было «как и ожидалось», а именно, где аппроксимация F (N) при больших N становится больше, чем наибольшее число, которое вы можете представить в Javascript. Так что все хорошо с миром. Счастливый взлом! – Floris

О теме последовательности Фибоначчи в JavaScript. MDN имеет хороший пример с использованием генераторов:

// Declare generator 
function* fibonacci() { 
    let n0; 
    let n1 = 0 
    let n2 = 1 
    while (true) { 
     n0 = n1 
     n1 = n2 
     n2 = n0 + n1 
     yield n0 
    } 
} 

// Create generator 
var y = fibonacci() 

// Print them out 
for (let x = 0; x < 1477; x++) { 
    console.log(x + 1, " ", y.next().value) 
}

источник

2017-07-10 07:39:18

Последовательность Fibonacci приводит к бесконечности, затем NaN

ответ

Смежные вопросы