找出非常大的'n‘的第n个斐波那契数

Question

我想知道如何才能找到费波纳契数列的第n项，对于非常大的n值，比如1000000。使用小学递归方程fib(n)=fib(n-1)+fib(n-2)，需要2-3分钟才能找到第50个学期！

通过谷歌搜索，我知道了比奈的公式，但它不适合n>79的值，因为它说here

有没有像我们寻找质数一样的算法呢？

Answer 1

您可以使用矩阵求幂方法(线性递归法)。你可以在this博客中找到详细的解释和步骤。运行时间为O(log )。

我不认为有更好的方法来做这件事。

Answer 2

在log(n)步骤中使用recurrence http://en.wikipedia.org/wiki/Fibonacci_number#Other_identities查找n-th number。为此，您必须使用任意精度的整数。或者你可以通过在每一步中使用模运算来计算模数的精确答案。

​

​

​

​

​

​

注意到3n+3 == 3(n+1)，我们可以设计一个单递归函数，它在每一步计算两个序列斐波纳契数，将n除以3，并根据余数值选择适当的公式。它在一个步骤中从一对@(n,n+1)计算出一对@(3n+r,3n+r+1), r=0,1,2，所以没有双重递归，也不需要记忆。

哈斯克尔代码是here。

F(2n-1) =   F(n-1)^2    + F(n)^2   ===   a' = a^2 + b^2 
F(2n)   = 2 F(n-1) F(n) + F(n)^2   ===   b' = 2ab + b^2 

似乎导致了更快的代码。使用可能是最快的(this is due to user:primo，他引用了this implementation)。

Answer 3

大多数人已经给了你一个链接，解释第N个斐波那契数的发现，顺便说一下，Power算法的工作原理是相同的，但有很小的变化。

无论如何，这是我的O(log )解决方案。

package algFibonacci;

import java.math.BigInteger;

public class algFibonacci {
    // author Orel Eraki
    // Fibonacci algorithm
    // O(log2 n)
    public static BigInteger Fibonacci(int n) {

        int num = Math.abs(n);
        if (num == 0) {
            return BigInteger.ZERO;
        }
        else if (num <= 2) {
            return BigInteger.ONE;
        }

        BigInteger[][] number = { { BigInteger.ONE, BigInteger.ONE }, { BigInteger.ONE, BigInteger.ZERO } };
        BigInteger[][] result = { { BigInteger.ONE, BigInteger.ONE }, { BigInteger.ONE, BigInteger.ZERO } };

        while (num > 0) {
            if (num%2 == 1) result = MultiplyMatrix(result, number);
            number = MultiplyMatrix(number, number);
            num/= 2;
        }

        return result[1][1].multiply(BigInteger.valueOf(((n < 0) ? -1:1)));
    }

    public static BigInteger[][] MultiplyMatrix(BigInteger[][] mat1, BigInteger[][] mat2) {
        return new BigInteger[][] {
            {
                mat1[0][0].multiply(mat2[0][0]).add(mat1[0][1].multiply(mat2[1][0])), 
                mat1[0][0].multiply(mat2[0][1]).add(mat1[0][1].multiply(mat2[1][1]))
            },
            {
                mat1[1][0].multiply(mat2[0][0]).add(mat1[1][1].multiply(mat2[1][0])), 
                mat1[1][0].multiply(mat2[0][1]).add(mat1[1][1].multiply(mat2[1][1]))
            }
        };
    }

    public static void main(String[] args) {
        System.out.println(Fibonacci(8181));
    }
}