快速倍增和斐波那契算法讲解

Question

在研究矩阵求幂时，我遇到了快速加倍和下面的实现。我有以下问题：

为什么for循环会从31向下迭代到0？
在条件语句中用 i 屏蔽 n 的目的是什么？

    private static BigInteger Fibonacci(int n) {
        BigInteger a = BigInteger.Zero;
        BigInteger b = BigInteger.One;
        for (int i = 31; i >= 0; i--) {
            BigInteger d = a * (b * 2 - a);
            BigInteger e = a * a + b * b;
            a = d;
            b = e;
            if ((((uint)n >> i) & 1) != 0) {
                BigInteger c = a + b;
                a = b;
                b = c;
            }
        }
        return a;
    }

请 link 任何可以帮助我深入理解该主题的参考资料或文献。

干杯！

Answer 1

你代码中循环的不变量是：

a = Fib(n/2^i)
b = Fib(n/2^i + 1)

（这里的^是求幂而不是异或）。

您可以使用快速倍增公式检查这些不变量是否随着 i 的变化而保持不变：

Fib(2k) = 2Fib(k)*Fib(k+1) - Fib(k)*Fib(k)
Fib(2k+1) = Fib(k+1)*Fib(k+1) + Fib(k)*Fib(k)

当 n/2^i 为奇数时，if 语句应用公式：

Fib(2k+1), Fib(2k+2) = Fib(2k+1), Fib(2k) + Fib(2k+1)

（这只是普通的斐波那契公式）。

将代码视为此递归代码的自上而下（而不是自下而上）版本可能会有所帮助：

def fib2(n):
    if n == 0:
        return 0, 1
    a, b = fib2(n//2)
    a, b = a*(b*2 - a), a*a + b*b
    if n % 2 != 0:
        a, b = b, a+b
    return a, b

唯一显着的区别是，虽然此代码递归直到 n 为 0，但自上而下的代码始终迭代 32 次。

Answer 2

为什么迭代器从 31 向下循环到 0？

回答。因为程序员存储的数据是32位的（从0到31）。 range from 31 to 0 的意义是从最低有效位迭代到最高有效位。

在条件语句中用 i 屏蔽 n 的目的是什么？

回答。这实际上不是掩蔽。它是一个左移运算符。整体表达式 if ((((uint)n >> i) & 1) != 0) 检查数字 n 是否有奇偶校验位要添加到下一个有效位。

您要学习的主题称为位操作。以下是我第一次自学位操作的一些资源。

快速倍增和斐波那契算法讲解

Fast doubling and fibonacci algorithm explanation

algorithm

bit-manipulation

fibonacci