python-3.x - python : Calculate the last digit of a large Fibonacci Number with less time

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)

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

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

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]
    )