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

问题描述

我想知道一个人如何能找到Fibonacci序列的第n项为n个非常大的值说，1000000使用等级学校递推公式 FIB（N）= FIB（N- 1）+ FIB（N-2），它需要2-3分钟找到50术语！

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的值，因为它是说的here

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 dont think there is a better way of doing this.

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