用幂乘代码实现Fibonacci数列

斐波那契数列是一种经典的递归序列，其中每个数字是前两个数字的和。通常，我们会用迭代的方式而非递归来提高效率，避免过多的函数调用开销。使用幂乘法（也称为矩阵快速幂算法），可以在较短的时间复杂度O(log n)内计算出较大的斐波那契数。这种方法基于矩阵乘法的性质。

下面是一个简单的Python代码示例：

def matrix_multiply(a, b):
    c = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                c[i][j] += a[i][k] * b[k][j]
    return c

def power_matrix(base, exponent):
    result = [[1, 0], [0, 1]]  # 初始化单位矩阵
    while exponent > 0:
        if exponent % 2 == 1:  # 如果指数奇数，则乘上base
            result = matrix_multiply(result, base)
        exponent //= 2  # 将指数右移一位
        base = matrix_multiply(base, base)  # 每次将base平方
    return result

def fibonacci(n):
    if n <= 0:
        return []
    elif n == 1 or n == 2:
        return [0, 1]

    # 定义Fibonacci矩阵 [[1, 1], [1, 0]]
    fib_matrix = [[1, 1], [1, 0]]
    
    # 计算第n次方，结果矩阵的对角线元素就是Fibonacci数列的值
    result = power_matrix(fib_matrix, n - 1)

    return result[0][0]  # 返回对角线上对应的值，即Fibonacci数列的第n项

# 测试
print(fibonacci(10))