Python:用更少的时间计算一个大的斐波那契数的最后一位

Question

# Uses python3
# Compute the Last Digit of a Large Fibonacci Number
def Fib_Last_Digit(n):
    if n == 0 : return 0
    elif n == 1: return 1
    else:
        a,b = 0,1
        for i in range(1,n):
            c = a + b;
            a = b;
            b = c;
        # Calculate the last digit of the final number 
        lastdigit = int(repr(c)[-1]);
        print(lastdigit);
n = int(input(""));
Fib_Last_Digit(n);

这段代码效果很好。但是，我想修改算法以节省更多时间和内存。顺便说一下，输入和输出应与以前的版本保持一致。

Answer 1

在计算过程中只保留最后一个数字可以节省大量时间：

def fib_last_digit(n):
    if n < 2: return n
    else:
        a, b = 0, 1
        for i in range(1,n):
            a, b = b, (a+b) % 10
        print(b)
n = int(input())
fib_last_digit(n)

处理适合更少字节的数字可以节省时间。

当您处理大量数字时，使用此处描述的答案可以节省大量时间，稍作修改以仅跟踪最后一位数字：

def fib_last_digit(n):
    v1, v2, v3 = 1, 1, 0    # initialise a matrix [[1,1],[1,0]]
    for rec in bin(n)[3:]:  # perform fast exponentiation of the matrix (quickly raise it to the nth power)
        calc = (v2*v2) % 10
        v1, v2, v3 = (v1*v1+calc) % 10, ((v1+v3)*v2) % 10, (calc+v3*v3) % 10
        if rec == '1': v1, v2, v3 = (v1+v2) % 10, v1, v2
    return v2

最后，基于Eugene Yarmash的答案中描述的概念(最后一位数字每60步重复一次(，我们可以做出一个更快的解决方案(O(1((：

def fib_last_digit(n):
    return (
        [1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0]
        [n % 60 - 1]
    )

Answer 2

斐

波那契数的最后一个数字系列以 60 的周期长度重复。因此，第 N 个斐波那契数与第 (N % 60) 个具有相同的最后一个数字，计算起来应该很快。作为额外的优化，您可以只保留每个术语的最后一位数字：

def fib_last_digit(n):
    a, b = 0, 1
    for i in range(n % 60):
        a, b = b, (a + b) % 10
    return a    
print([fib_last_digit(n) for n in range(1, 11)])

输出：

[1, 1, 2, 3, 5, 8, 3, 1, 4, 5]

Answer 3

def fib(n): 
    phi = (1 + 5 ** 0.5) / 2
    fib_n = round(((phi** n) - (phi**-n) )/(5 ** .5))
    return fib_n % 10

皮是你的朋友。

Answer 4

def fib_digit(n):
    f=[1,1]
    for i in range(2,n):
        f.append((f[i-1]+f[i-2])  % 10 ) 
    return f[-1]
n = int(input())
print(fib_digit(n))

这是最简单的答案之一，我敢肯定，有一种更快的算法。

这是我发现的：

f1, f2 = 0, 1
for i in range(int(input())-1):
    f1, f2 = f2, (f1+f2)%10
print(f2)

Answer 5

只需

--- 0.002832174301147461 秒---即可完成代码。

import time
n = 100000000000000000000000000000000000000000

def printfib(previous, latest, n):
    if(latest > n):
        return
    print(', ', latest, end='')
    printfib(latest, previous + latest, n)

start_time = time.time()
print(0, end='')
printfib(0, 1, n)
print(" ")
print("--- %s seconds ---" % (time.time() - start_time))