Computing Fibonacci Numbers

Binary Exponentiation

You might have already seen that, with 1 → 2 → 4 → 8 → 16 as our chain, 16 + 4 will give us 20. But how would we do this in a way that a computer can do when we have hundreds of numbers in our chain?

Well, representing a number as a sum of powers of two is the very definition of binary:

$\begin{aligned} 20 &&=\ &10100_2 \\ &&=\ &1&&0&&1&&0&&0 \\ &&=\ &1 \times 2^4 + &&0 \times 2^3 + &&1 \times 2^2 + &&0 \times 2^1 + &&0 \times 2^0 \\ &&=\ &2^4 + 2^2 \\ \end{aligned}$

We just add up all of the powers of two that correspond to ones in binary. The number of ones, called the Hamming weight, will determine how efficient this becomes. Numbers right below a power of 2, like $15 = 1111_2$ , require the most additions: powers of two require the fewest relative to their size.

The algorithm ends up as follows. To find $b^n$ :

Compute $b^1, b^2, b^4$ , up until the last power of 2 before $b^n$ , computing each new term by squaring the previous term.. Store these powers in a list, call it l.
Set a working variable product = 1
For each bit of n: if it's a one, set product = product * l[i] where 2^i is the place of the bit.
Return product

Binary Exponentiation

Well, representing a number as a sum of powers of two is the very definition of binary:

$\begin{aligned} 20 &&=\ &10100_2 \\ &&=\ &1&&0&&1&&0&&0 \\ &&=\ &1 \times 2^4 + &&0 \times 2^3 + &&1 \times 2^2 + &&0 \times 2^1 + &&0 \times 2^0 \\ &&=\ &2^4 + 2^2 \\ \end{aligned}$

The algorithm ends up as follows. To find $b^n$ :

Compute $b^1, b^2, b^4$ , up until the last power of 2 before $b^n$ , computing each new term by squaring the previous term.. Store these powers in a list, call it l.
Set a working variable product = 1
For each bit of n: if it's a one, set product = product * l[i] where 2^i is the place of the bit.
Return product