找出非常大的“n"的第 n 个斐波那契数 [英] Finding out nth fibonacci number for very large 'n'

问题描述

我想知道如何找到一个非常大的 n 值的斐波那契数列的第 n 项，比如 1000000.使用小学递推方程 fib(n)=fib(n-1)+fib(n-2)，找到第50项需要2-3分钟！

I was wondering about how can one find the nth term of fibonacci sequence for a very large value of n say, 1000000. Using the grade-school recurrence equation fib(n)=fib(n-1)+fib(n-2), it takes 2-3 min to find the 50th term!

谷歌搜索后，我开始了解比奈的公式，但它不适用于 n>79 的值，因为据说 这里

After googling, I came to know about Binet's formula but it is not appropriate for values of n>79 as it is said here

有没有一种算法可以像我们寻找素数一样这样做?

Is there an algorithm to do so just like we have for finding prime numbers?

推荐答案

可以使用矩阵求幂方法(线性递推法).您可以在这篇博客中找到详细的说明和程序.运行时间为O(log n).

You can use the matrix exponentiation method (linear recurrence method). You can find detailed explanation and procedure in this blog. Run time is O(log n).

我认为没有比这更好的方法了.

I don't think there is a better way of doing this.

这篇关于找出非常大的“n"的第 n 个斐波那契数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！