在 Python 中计算一个巨大的斐波那契数模 m

Question

这道题的目标是计算F[n]modm。这里的输入是 n 和 m，其中 n 代表斐波那契数的索引，比如说F[0] = 0, F[1] = 1, F[2] = 1, F[3]= 2 and m 代表 F[n]会被除。约束是：

n >= 1 且 n <= 10^18
m >= 2 且 m <= 10^5

到目前为止我已经解决了这个问题并且能够生成这个问题的确切输出，除了当我给 100000 作为 m 的值时，它超过了时间限制。时间限制为 5 秒。如果 m 的值介于 2 到 99999 之间（含），我的程序会在时限内生成正确的输出。任何形式的帮助解决这个问题将不胜感激。

代码：

def fibonacci(n):
    if ( n == 0 ):
        return (0, 1)
    else:
        a, b = fibonacci(n/2)
        c = a * (2* b - a)
        d = a**2 + b**2
        if ( n % 2 ):
            return (d, c + d)
        else:
            return (c, d)


def findRemainders(m):
    remainderList = ["0", "1"]
    i = 2
    while(1):
        firstFib, secondFib = fibonacci(i)
        if ( (firstFib % m) == 0 and (secondFib % m) == 1 ):
            break
        remainderList.append( (firstFib % m) )
        remainderList.append( (secondFib % m) )
        i += 2

    return remainderList


def hugeFibonacciNumberModulo_m( n, m ):
    remainderList = findRemainders(m)
    length_of_period = len(remainderList)
    remainder = (n % length_of_period)
    out = remainderList[remainder]
    return out


inp = map(int, raw_input().split())
n, m = inp[0], inp[1]

if ( (n >= 1 and n <= 10**18) and (m >= 2 and m <= 10**5) ):
    out = hugeFibonacciNumberModulo_m( n, m )
print out

Answer 1

我不明白您在 findRemainders(m) 中尝试做什么或为什么需要它。您已经在使用 Fibonacci-by-doubling 算法，它类似于（并且通常派生自）矩阵求幂平方算法。求幂可以 mod 有效地处理 mod 平方求幂，本质上是在每一步 mod 计算你的部分结果。

def fibmod(n, m):
    assert 1 <= n <= 10**18, n
    assert 2 <= m <= 10**5, m

    def f(n):
        if n == 0:
            return 0, 1
        else:
            a, b = f(n // 2)
            c = a * (2*b - a) % m
            d = (a**2 + b**2) % m

            if n % 2 == 0:
                return c, d
            else:
                return d, (c + d) % m

    return f(n)[0]

您可以进一步分解 c 和 d 的表达式，并在每个中间乘法、加法和减法之后应用 % m 以防止溢出（但这不是Python 确实是个问题）。

Answer 2

您可以使用 mod 平方幂很快地完成此操作。

考虑以下矩阵乘法：

| 0  1 |     | a |     |  b  |
|      |  x  |   |  =  |     |
| 1  1 |     | b |     | a+b |

如果 a 和 b 是最后两项，您应该立即看到此乘法的结果是斐波那契数列的下一次迭代。要获得执行此乘法 n 次的结果，您需要计算 2x2 矩阵 (0,1;1,1) (mod m) 的 n-th 次方。这可以通过将该矩阵提高到 2 的连续幂来非常快速地完成。

例如计算这个矩阵的10次方：

                   | 0  1 |     | 0  1 |     | 1  1 |
A x A  =  A**2  =  |      |  x  |      |  =  |      |
                   | 1  1 |     | 1  1 |     | 1  2 |

                      | 1  1 |     | 1  1 |     | 2  3 |
A**4 =  (A**2)**2  =  |      |  x  |      |  =  |      |
                      | 1  2 |     | 1  2 |     | 3  5 |

                      | 2  3 |     | 2  3 |     | 13  21 |
A**8 =  (A**4)**2  =  |      |  x  |      |  =  |        |
                      | 3  5 |     | 3  5 |     | 21  34 |

对矩阵进行三次平方后，我们现在有 A**8 和 A**2 的值。将它们相乘得到 A**10:

          | 13  21 |     | 1  1 |     | 34  55 |
A**10  =  |        |  x  |      |  =  |        |
          | 21  34 |     | 1  2 |     | 55  89 |

这些数字在常规算术中会迅速变得巨大，但如果您执行所有乘法 modulo m，那么这不是问题。最后，将向量 (0; 1) 乘以结果矩阵得到你的答案（或者，等价地，只挑出矩阵顶行的第二个数字）。

需要的乘法次数是log(n)的数量级，所以需要的时间应该很小，即使m是一万亿或更多。

See Wikipedia for more information about modular exponentiation of matrices.

在 Python 中计算一个巨大的斐波那契数模 m

Calculating a huge fibonacci number modulo m in Python

algorithm

fibonacci

python-2.7

代码：