Python：用较少的时间计算大型Fibonacci数的最后一位数

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

Answer 2

斐波那契数字repeats的最终数字序列，周期长度为60.因此，Nth斐波纳契数与(N % 60)th具有相同的最后一位数，这应该是非常快的计算。作为额外的优化，您只能保留每个术语的最后一位数：

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_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 4

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

披是你的朋友。