Фибоначчи 1000 ... 10 000 ... 100 000
Некоторые ответы сталкиваются с проблемами при попытке вычислить большие числа Фибоначчи.Другие являются приблизительными числами, используя фи.Этот ответ покажет вам, как вычислить точную серию больших чисел Фибоначчи без ограничений, установленных реализацией с плавающей запятой в JavaScript.
Ниже мы сгенерируем первые 1000 чисел Фибоначчи за несколькомиллисекунды.Позже мы сделаем 100 000!
const { fromInt, toString, add } =
Bignum
const bigfib = function* (n = 0)
{
let a = fromInt (0)
let b = fromInt (1)
let _
while (n >= 0) {
yield toString (a)
_ = a
a = b
b = add (b, _)
n = n - 1
}
}
console.time ('bigfib')
const seq = Array.from (bigfib (1000))
console.timeEnd ('bigfib')
// 25 ms
console.log (seq.length)
// 1001
console.log (seq)
// [ 0, 1, 1, 2, 3, ... 995 more elements ]
Давайте посмотрим тысячное число Фибоначчи
console.log (seq [1000])
// 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
10000
Это решение масштабируется довольномило.Мы можем вычислить первые 10000 чисел Фибоначчи менее чем за 2 секунды.На данном этапе последовательности числа превышают 2000 цифр, что намного превышает возможности чисел с плавающей запятой в JavaScript.Тем не менее, наш результат включает точные значения без аппроксимаций.
console.time ('bigfib')
const seq = Array.from (bigfib (10000))
console.timeEnd ('bigfib')
// 1877 ms
console.log (seq.length)
// 10001
console.log (seq [10000] .length)
// 2090
console.log (seq [10000])
// 3364476487 ... 2070 more digits ... 9947366875
Конечно, вся эта магия происходит в Bignum, которым мы сейчас поделимся.Чтобы понять, как мы будем проектировать Bignum, вспомните, как вы добавили большие числа, используя перо и бумагу в детстве ...
1259601512351095520986368
+ 50695640938240596831104
---------------------------
?
Вы добавляете каждый столбец справа налево, и когдастолбец переполняется до двух цифр, не забывая перенести 1 в следующий столбец ...
... <-<b>001</b>
1259601512351095520986368
+ 50695640938240596831104
---------------------------
... <-<b>472</b>
Выше мы можем видеть, что если бы у нас было два 10-значных числа, потребовалось бы приблизительно 30 простыхдополнения (3 на столбец), чтобы вычислить ответ.Вот как мы настроим Bignum на работу
const Bignum =
{ fromInt: (n = 0) =>
n < 10
? [ n ]
: [ n % 10, ...Bignum.fromInt (n / 10 >> 0) ]
, fromString: (s = "0") =>
Array.from (s, Number) .reverse ()
, toString: (b) =>
Array.from (b) .reverse () .join ('')
, add: (b1, b2) =>
{
const len = Math.max (b1.length, b2.length)
let answer = []
let carry = 0
for (let i = 0; i < len; i = i + 1) {
const x = b1[i] || 0
const y = b2[i] || 0
const sum = x + y + carry
answer.push (sum % 10)
carry = sum / 10 >> 0
}
if (carry > 0) answer.push (carry)
return answer
}
}
Мы запустим быстрый тест для проверки нашего примера выше
const x =
fromString ('1259601512351095520986368')
const y =
fromString ('50695640938240596831104')
console.log (toString (add (x,y)))
// 1310297153289336117817472
А теперь полная демонстрация программы.Разверните его, чтобы вычислить точное 10 000-е число Фибоначчи в вашем собственном браузере!Обратите внимание, что результат совпадает с ответом, предоставленным wolfram alpha
const Bignum =
{ fromInt: (n = 0) =>
n < 10
? [ n ]
: [ n % 10, ...Bignum.fromInt (n / 10 >> 0) ]
, fromString: (s = "0") =>
Array.from (s, Number) .reverse ()
, toString: (b) =>
Array.from (b) .reverse () .join ('')
, add: (b1, b2) =>
{
const len = Math.max (b1.length, b2.length)
let answer = []
let carry = 0
for (let i = 0; i < len; i = i + 1) {
const x = b1[i] || 0
const y = b2[i] || 0
const sum = x + y + carry
answer.push (sum % 10)
carry = sum / 10 >> 0
}
if (carry > 0) answer.push (carry)
return answer
}
}
const { fromInt, toString, add } =
Bignum
const bigfib = function* (n = 0)
{
let a = fromInt (0)
let b = fromInt (1)
let _
while (n >= 0) {
yield toString (a)
_ = a
a = b
b = add (b, _)
n = n - 1
}
}
console.time ('bigfib')
const seq = Array.from (bigfib (10000))
console.timeEnd ('bigfib')
// 1877 ms
console.log (seq.length)
// 10001
console.log (seq [10000] .length)
// 2090
console.log (seq [10000])
// 3364476487 ... 2070 more digits ... 9947366875
100,000
Мне было просто любопытно, как далеко может зайти этот маленький сценарий.Кажется, что единственное ограничение - это просто время и память.Ниже мы вычисляем первые 100 000 чисел Фибоначчи без аппроксимации.Числа в этой точке в последовательности более 20000 цифр, вау!Требуется 3,18 минуты, но результат все равно соответствует ответу wolfram alpha
console.time ('bigfib')
const seq = Array.from (bigfib (100000))
console.timeEnd ('bigfib')
// 191078 ms
console.log (seq .length)
// 100001
console.log (seq [100000] .length)
// 20899
console.log (seq [100000])
// 2597406934 ... 20879 more digits ... 3428746875