Обнаружение энного числа Фибоначчи для очень большого 'n'
Я задавался вопросом о том, как можно найти, что энный термин последовательности fibonacci для очень большого значения n говорит, 1000000. Используя уравнение повторения начальной школы fib(n)=fib(n-1)+fib(n-2), требуется 2-3 минуты для нахождения 50-го срока!
После поиска с помощью Google я узнал о формуле Бине, но это не подходит для значений n> 79, как это сказано здесь
Существует ли алгоритм, чтобы сделать так точно так же, как мы имеем для нахождения простых чисел?
1 ответ
Только для получения информации :
следующая формула кажется хорошо работающей, но зависит от точности используемого числа -
[((1+в€љ5)/2) вЃї-((1-в€љ5)/2) вЃї]/в€љ5
Примечание: не округляют числа для большей точности.
пример кода JS:
let n = 74,
const sqrt5 = Math.sqrt(5);
fibNum = Math.round((Math.pow(((1+sqrt5)/2),n)- Math.pow(((1-sqrt5)/2),n))/sqrt5) ;
Согласно Точность Числа , это будет хорошо работать на хромовой консоли [до 1 130] n=74
, Открытый для любого предложения!
Другое решение
Следует, шаги -
- делают ряд индекса и значения и доступного значения fibonacci ряда в определенных интервалах. например, каждый 50 или каждый 100.
- Находят ближайший более низкий индекс желаемого номера
nот набора неродной 1 . - Продолжаются традиционным способом путем добавления предыдущего значения в каждом последующий.
Примечание: Это не делает кажется хорошим, но если Вы действительно касаетесь о временной сложности, это решение имеет успех. Макс. повторения будут равны интервалу согласно неродной 1 .
Заключение:
- Числа Фибоначчи сильно связаны с золотое сечение : формула Бине выражает энное Число Фибоначчи с точки зрения n и золотого сечения, и подразумевает, что отношение двух последовательных Чисел Фибоначчи склоняется к золотому сечению как n увеличения.
- В формуле Бине чистой математики даст Вам точный результат каждый раз. В реальном мире, вычисляющем будут ошибки, поскольку необходимая точность превышает используемую точность. Каждое действительное решение имеет ту же проблему с чрезмерной точностью в какой-то момент.