有人可以帮忙解释一下这种快速加倍算法吗?

问题描述 投票:0回答:2

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

  1. 为什么for循环从31迭代到0?

  2. 在条件中被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;
    }

请链接所有可以帮助我深入理解该主题的参考文献或文献。

干杯!

algorithm bit-manipulation fibonacci
2个回答
0
投票

代码中循环的不变性是:

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

(这里^是幂而不是xor)。

您可以使用快速倍增公式来检查这些不变式是否随我的变化而保持:

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次。


0
投票
  1. 为什么迭代器从31循环到0?

答案因为程序员将数据存储为32位(范围从0到31)。从31到0的含义是从最低有效位到最高有效位进行迭代。

  1. 在条件中被i屏蔽n的目的是什么?

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

您要学习的主题称为位操作。这里是我最初自学比特操作的一些资源。

© www.soinside.com 2019 - 2024. All rights reserved.