用高精度算法求斐波那契

高精度算法用于处理大数计算，特别是在计算斐波那契数列时尤其重要，因为随着序列项的增加，数字会变得非常大。常规的递归或线性计算方法可能会遇到溢出的问题。下面是一个简单的高精度斐波那契数列计算方法：

1. **基于字符串或数组存储**：将每个数字作为一个字符或整数数组来操作，避免直接处理整数可能导致的溢出。

def fibonacci_memory(n, memo={}):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        if n not in memo:
            memo[n] = fibonacci_memory(n - 1) + fibonacci_memory(n - 2)
        return memo[n]

# 示例
n = 50
fib = fibonacci_memory(n)

2. **矩阵快速幂法**：利用斐波那契数列的矩阵形式和快速幂算法，可以显著减少计算次数。这种方法的时间复杂度为O(log n)，比朴素的递归更高效。

def matrix_multiply(a, b):
    x = a[0][0]*b[0][0] + a[0][1]*b[1][0]
    y = a[0][0]*b[0][1] + a[0][1]*b[1][1]
    z = a[1][0]*b[0][0] + a[1][1]*b[1][0]
    w = a[1][0]*b[0][1] + a[1][1]*b[1][1]

    return [[x, y], [z, w]]

def matrix_power(matrix, n):
    if n == 1:
        return matrix
    half = matrix_power(matrix, n // 2)
    if n % 2 == 0:
        return matrix_multiply(half, half)
    else:
        return matrix_multiply(matrix_multiply(half, half), matrix)

def fibonacci_matrix(n):
    fib_matrix = [[1, 1], [1, 0]]
    result = matrix_power(fib_matrix, n - 1)
    return result[0][0]

# 示例
n = 50
fib = fibonacci_matrix(n)