为非常大的'n'找出第n个斐波纳契数

Question

我想知道怎样才能找到第n个斐波那契序列的n个非常大的n值1000000.使用等级 - 学校递推方程fib(n)=fib(n-1)+fib(n-2),找到第50个学期需要2-3分钟!

谷歌搜索后,我开始了解Binet的公式,但它不适合n> 79的值,因为这里说的

有没有算法这样做就像我们找到素数一样？

Answer 1

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

我不认为有更好的方法可以做到这一点.

Answer 2

您可以通过使用memoization节省大量时间.例如,比较以下两个版本(在JavaScript中):

版本1:正常递归

var fib = function(n) {
  return n < 2 ? n : fib(n - 1) + fib(n - 2);
};

版本2:记忆

A.使用下划线库

var fib2 = _.memoize(function(n) {
  return n < 2 ? n : fib2(n - 1) + fib2(n - 2);
});

B.无图书馆

var fib3 = (function(){
    var memo = {};
    return function(n) {
        if (memo[n]) {return memo[n];}
        return memo[n] = (n <= 2) ? 1 : fib3(n-2) + fib3(n-1);
    };
})();

对于n = 50(在Chrome上),第一个版本需要3分钟,而第二个版本只需要不到5毫秒!你可以在jsFiddle中查看这个.

如果我们知道版本1的时间复杂度是指数(O(2 ^N/2)),而版本2是线性的(O(N)),那就不足为奇了.

版本3:矩阵乘法

此外,我们甚至可以通过计算N个矩阵的乘法将时间复杂度降低到O(log(N)).

其中F _n表示Fibonacci序列的第n项.

Answer 3

我同意Wayne Rooney的答案,即最佳解决方案将在O(log n)步骤中完成,但总体运行时复杂性将取决于所使用的乘法算法的复杂性.例如,使用Karatsuba乘法,整体运行时复杂度将为O(n ^{log ₂ 3})≈O(n ^1.585).¹

但是,矩阵求幂不一定是最好的方法.正如Project Nayuki的开发人员所注意到的那样,矩阵取幂带有冗余计算,可以将其删除.从作者的描述:

给定F _k和F _{k + 1},我们可以计算出这些:

请注意,每次拆分只需要3次BigInt到BigInt的乘法运算,而不是8次矩阵取幂.

不过,我们仍然可以做得稍微好一些.最优雅的斐波那契身份之一与卢卡斯数字有关:

其中L _n是第n ^个 卢卡斯数.此身份可以进一步概括为:

有一些或多或少的等效方法可以递归地进行,但最合乎逻辑的似乎是F _n和L _n.下面的实现中使用的其他标识可以从Lucas序列列出的标识中找到或派生:

以这种方式进行每次拆分只需要两次BigInt-to-BigInt乘法,而最终结果只需要一次.这比Project Nayuki(测试脚本)提供的代码快20%左右.注意:原始来源已经过轻微修改(改进),以便进行公平比较.

def fibonacci(n):
  def fib_inner(n):
    '''Returns F[n] and L[n]'''
    if n == 0:
      return 0, 2
    u, v = fib_inner(n >> 1)
    q = (n & 2) - 1
    u, v = u * v, v * v + 2*q
    if (n & 1):
      u1 = (u + v) >> 1
      return u1, 2*u + u1
    return u, v

  u, v = fib_inner(n >> 1)
  if (n & 1):
    q = (n & 2) - 1
    u1 = (u + v) >> 1
    return v * u1 + q
  return u * v

更新

一个灰熊指出,上述结果已经由Takahashi(2000)^2改进,注意到BigInt平方通常(特别是Schönhage-Strassen算法)比BigInt乘法计算成本更低.作者建议迭代,使用以下标识拆分F _n和L _n:

以这种方式迭代将需要每次拆分两个BigInt方块,而不是如上所述的BigInt方形和BigInt乘法.正如预期的那样,对于非常大的n,运行时间明显快于上述实现,但对于小值(n <25000),运行时间稍慢.

但是,这也可以略微改善.作者声称,"众所周知,卢卡斯数的乘积算法使用最少的比特运算来计算斐波纳契数F _n".然后,作者选择调整Lucas Numbers算法的产品,该算法在当时是最快的已知的,在F _n和L _n上分裂.但是请注意,L _n仅用于计算F _{n + 1}.如果考虑以下身份,这似乎有点浪费:

其中第一个是直接来自Takahashi,第二个是矩阵求幂方法的结果(也由Nayuki指出),第三个是加上前两个的结果.这允许在F _n和F _{n + 1}上进行明显的分割.结果需要少一个BigInt添加,并且重要的是,偶数n减少一个除以2 ; 对于奇数n,利益加倍.在实践中,这显着快于Takahashi提出的小n(快10-15%)的方法,对于非常大的n(测试脚本)略快.

def fibonacci(n):
  def fib_inner(n):
    '''Returns F[n] and F[n+1]'''
    if n == 0:
      return 0, 1
    u, v = fib_inner(n >> 1)
    q = (n & 2) - 1
    u *= u
    v *= v
    if (n & 1):
      return u + v, 3*v - 2*(u - q)
    return 2*(v + q) - 3*u, u + v

  u, v = fib_inner(n >> 1)
  # L[m]
  l = 2*v - u
  if (n & 1):
    q = (n & 2) - 1
    return v * l + q
  return u * l

更新2

自从最初发布以来,我也略微改进了之前的结果.除了两个BigInt正方形之外,在F _n和F _{n + 1}上的分裂也有三个BigInt加法的开销和每个分裂的两个小的常数乘法.这种开销几乎可以完全通过分裂L _n和L _{n + 1}来消除:

以这种方式拆分需要像以前一样使用两个BigInt方块,但只需添加一个BigInt.但是,这些值需要与相应的斐波纳契数相关联.幸运的是,这可以通过单个除以5来实现:

因为已知商是整数,mpz_divexact_ui所以可以使用诸如GMP的精确除法方法.展开最外层的分割允许我们使用单个乘法计算最终值:

正如在Python中实现的那样,对于非常大的n(测试脚本)来说,这比前面的小n快(快5-10%)并且稍微快一些.

def fibonacci(n):
  def fib_inner(n):
    '''Returns L[n] and L[n+1]'''
    if n == 0:
      return mpz(2), mpz(1)
    m = n >> 1
    u, v = fib_inner(m)
    q = (2, -2)[m & 1]
    u = u * u - q
    v = v * v + q
    if (n & 1):
      return v - u, v
    return u, v - u

  m = n >> 1
  u, v = fib_inner(m)
  # F[m]
  f = (2*v - u) / 5
  if (n & 1):
    q = (n & 2) - 1
    return v * f - q
  return u * f

¹可以看出F _n ~ O(n)的位数(或位)为:

使用Karatsuba乘法的运行时复杂度可以计算为:

² Takahashi,D.(2000)," 用于计算大型斐波纳契数的快速算法 "(PDF),信息处理快报75,第243-246页.

Answer 4

使用重复身份http://en.wikipedia.org/wiki/Fibonacci_number#Other_identities以步骤查找n-th数字log(n).你必须使用任意精度整数.或者,您可以通过在每个步骤使用模运算来计算模拟某些因子的精确答案.

注意到3n+3 == 3(n+1),我们可以设计一个单递归函数,在每一步计算两个连续的Fibonacci数,除以n3并根据余数值选择合适的公式.如果它在一步中@(3n+r,3n+r+1), r=0,1,2从一对@(n,n+1)中计算一对,所以没有双递归并且不需要记忆.

Haskell代码就在这里.

更新:

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 

似乎导致更快的代码.使用 "Lucas序列标识"可能是最快的(这是由于用户:primo,他引用了这个实现).

Answer 5

大多数人已经给你链接解释了Nth Fibonacci数的发现,顺便说一下,Power算法的工作方式与微小变化相同.

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

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));
    }
}