python - 斐波那契 - 非常大的 n 个数字的六个最高有效数字(最右边)

Question

我试图通过仅保留最右边的六位数字来有效地计算可能非常大的第 n 个斐波那契值。例如 fib(1000000) 将仅返回 546875。

我知道一些递归矩阵求幂算法，并且我一直在测试 O(log n) 实现，如下所示 -

def solution(n):
    fibs = {0: 0, 1: 1}

    def fib(n):
    # recursive helper function
        if n in fibs: 
            return fibs[n]
        if n % 2 == 0:
            fibs[n] = ((2 * fib((n / 2) - 1)) + fib(n / 2)) * fib(n / 2) % 1000000
            return fibs[n]
        else:
            fibs[n] = (fib((n - 1) / 2) ** 2) + (fib((n+1) / 2) ** 2) % 1000000
            return fibs[n]

    answer = fib(n)
    return answer % 1000000

所有答案似乎都有效，直到 n = 1000000。后面所有 10 的指数是否都应该返回相同的答案？ 10^k 其中 k = [7, 8, 9, 10...] 全部返回 546875(一百万的值)。我认为它们应该是这样的，因为当你对它们取模 10^6 时，这些值具有相同的余数为零。所以我想知道这个实现是否正确？

Answer 1

所以我做了一些简单的代码来证明/反驳你当前的定理，我偶然发现了这个特殊的模式:代码最后 6 位的斐波那契序列似乎每 150 万个序列重复一次。

这就是 100 万、1000 万、10000 万等值匹配的部分原因； 1000 万 - 900 万 = 100 万，但 900 万 = 6 * 150 万。

因此，要回答您的问题，您需要在代码中实现的就是首先将 n 乘以 1,500,000，然后计算您的答案，例如:

answer = fib(n%1500000)

我在下面提供了用于查找模数何时重复的代码 (find_repeating_length) 以及用于检查模数是否按预期工作(检查)的函数。

希望有帮助!

def solution(n):
    fibs = {0: 0, 1: 1}

    def fib(n):
        # simple linear-time fib function
        if n in fibs:
            return fibs[n]
        fibs[n] = (fibs[n-1]+fibs[n-2]) % 1000000
        return fibs[n]

    def find_repeating_length():
        find_number = [0, 1] # find these two numbers of the sequence
        for i in range(0, 10000001):
            n_0 = fib(i)
            if (n_0 in find_number):
                print(str(n_0) + ":" + str(i))

    def check(): # check that first 10,000,000 nums follow sequence
        for i in range(2, 10000001): 
            n_0 = fib(i)
            if (i >= 1500000):
                left = n_0
                right = fib(i - 1500000)
                # if (left == right):
                #    print("Success at " + str(i) + " Values: " +
                #          str(n_0))
                if (left != right):
                    return("Fail at " + str(i) + " Values: " +
                           str(n_0) + ":" + str(right))

            return "Success, repeats"
    find_repeating_length()
    print(check())


solution()

输出(稍微格式化，以值:序列格式输出):

0:0 1:1 1:2 0:750000 1:1499999

0:1500000 1:1500001 1:1500002 0:2250000 1:2999999

0:3000000 1:3000001 1:3000002 0:3750000 1:4499999

0:4500000 1:4500001 1:4500002 0:5250000 1:5999999

0:6000000 1:6000001 1:6000002 0:6750000 1:7499999

0:7500000 1:7500001 1:7500002 0:8250000 1:8999999

0:9000000 1:9000001 1:9000002 0:9750000

Success, repeats