Fast doubling and fibonacci algorithm explanation

user_12407970 0
Viewed 206

While looking into matrix exponentiation, I came across fast doubling and the implementation below. I have the following questions:

  1. Why does the for loop iterate down from 31 to 0?

  2. What is the purpose of masking n by i in the conditional?

    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;
    }

Please link any references or literature that could help me understand the topic in depth.

Cheers!

fibonacci bit-manipulation algorithm
2 Answers

The invariant of the loop in your code is:

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

(here ^ is exponentiation rather than xor).

You can check that these invariants hold as i changes, by using the fast doubling formulae:

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

And for when n/2^i is odd, the if statement applies the formula:

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

(this is just the regular Fibonacci formula).

It may help to consider the code as a top-down (rather than bottom-up) version of this recursive code:

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

The only significant difference is that whereas this code recurses until n is 0, the top-down code always iterates 32 times.

user_14007930
  1. Why does the iterator loop down from 31 to 0?

Ans. Because the programmer stored data in 32 bits (ranging from 0 to 31). The sense of ranging from 31 to 0 is that iterating from the lowest significant bit to the highest significant bit.

  1. What is the purpose of masking n by i in the conditional?

Ans. That is not actually masking. It is a left-shift operator. The overall expression if ((((uint)n >> i) & 1) != 0) checks whether the number n has a parity bit to be added in the next significant bit.

The topic you want to learn is known as Bit Manipulation. Here are a few resources where I first taught myself about bit manipulations.

user_84584650
Related