Efficient algorithm for taking powers of binary numbers?

Question

Is there any efficient algorithm for taking powers of binary numbers? Or even just squaring one?

Thanks ahead of time.

Answer 1

Here's a reference that I found:

http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

The most intuitive algorithm that I can think of for squaring binary numbers involves appending zeros and adding. As an example, say you want to square $101101$. To do so, note the position of each $1$ in the number (this can be done algorithmically by right-shifting and doing an AND with $1$. In our example, we have $1$'s in the 1st, 3rd, 4th, and 6th positions. So we would add

$$ 101101 + 10110100 + 101101000 + 10110100000$$

where for each addend you append the position of the corresponding $1$ minus one. Since you have $1$'s in the 1st, 3rd, 4th, and 6th positions you would append $ 1- 1 = 0$, $3 - 1 = 2$, $4 - 1 = 3$, and $6 - 1 = 5$ zeros to each of the four addends respectively.

Answer 2

And if you want to square (or multiply) very large numbers, there is the Karatsuba algorithm:

http://en.wikipedia.org/wiki/Karatsuba_algorithm

Answer 3

Reducing exponentiation to squaring and occasional multiplication seems to be fast, see Exponentiation by Squaring. It uses $$ x^n = \begin{cases} x \, ( x^{2})^{(n - 1)/2}, & \mbox{if } n \mbox{ is odd} \\ (x^{2})^{n/2} , & \mbox{if } n \mbox{ is even}. \end{cases} $$ The squaring is done by $x^2 = x * x$.

In Henry S. Warren's "Hacker's Delight", chapter 11-3, a method called „Computing $x^n$ by Binary Decomposition of $n$“ is presented, but it seems to be the same idea at first glance (please check this). $$ x^{13} = x^{(1101)_2} = x^{8+4+1} = x^8*x^4*x = \underbrace{(\underbrace{(\underbrace{(\underbrace{1^2 * x}_1)^2}_0 * x}_1)^2)^2 * x}_1 $$ One starts with initial value $1$ and the exponent representation is read right to left and either a "square and multiply" (if $1$) or "square" step (if $0$) is taken, see example above.

The other idea that comes to mind, but depends on how large your numbers are, in this case rather be small, is using some kind of lookup table.