Fibonacci非常大的n个数的六个最高有效位（最右边）

Question

我试图有效地计算第n个斐波那契值，这个值可以非常大，只保留最右边的6个数字。例如，fib（1000000）只返回546875。你知道吗

我知道一些递归矩阵求幂算法，我一直在测试一个O（logn）实现，如下所示-

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万、1亿等匹配的部分原因；1000万-900万=100万，但900万=6*150万。你知道吗

所以，为了回答你的问题，你需要在你的代码中实现的就是先将模n乘以1500000，然后计算你的答案，例如：

answer = fib(n%1500000)

我提供了用于查找模何时重复（find\u repeating\u length）的代码，以及检查模是否按预期工作的函数（check）。你知道吗

希望有帮助！你知道吗

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