# binary exponentiation

One way to calculate *x*^{25} would be to multiply *x* by itself 24 times. But if *x* is large (say one million digits), even just one
multiplication is time
consuming--so can we do it with fewer?

An ancient method which appeared about 200 BC in Pingala's
Hindu classic *Chandah-sutra* (and now called
**left-to-right binary exponentiation**) can be
described as follows. First
write the exponent 25 in binary: 11001. Remove the first
binary digit leaving 1001 and then replace each remaining
'1' with the pair of letters 'sx' and each '0'
with the letter 's' to get: `sx s s sx`

.
Now interpret 's' to mean square, and 'x' to mean
multiply by *x*, so we have:

square, multiply byx, square, square, square, multiply byx.

These are our instructions
to follow; so if we start with *x*, we then calculate
in turn *x*^{2}, *x*^{3},
*x*^{6}, *x*^{12},
*x*^{24}, and *x*^{25}. This
took 6, not 24, multiplications. For large exponents the
savings is dramatic! For example, using this method to
calculate: *x*^{1000000} takes 25
multiplications; *x*^{12345678901234567890}
takes 94 multiplications; and if
*n*=10^{1000}, then calculating *x ^{n}*
takes just 4483 multiplications. In
general, binary exponentiation will always take less than
2 log(

*n*)/log(2) multiplications.

Another method, suggested by
al-Kashi in 1427 (and similar to a method used by the
Egyptians to multiply around 2000 BC), is now called
**right-to-left binary exponentiation**. To calculate
*x*^{n} where *n* is a positive
integer we can do the following:

`Power(`

x,n) {r:= 1y:=xwhile (n> 1) { if odd(n) thenr:=r*yn:= floor(n/2)y:=y*y}r:=r*yreturn(r) }

This right-to-left method is easier to program, takes
the same number of multiplications as the left-to-right
method (2 less than the number of binary digits in *n*
plus the number of ones in this same binary expansion), but
requires slightly more storage. Also, in the special case
that *x* is small (e.g., we are calculating
3^{n} for a Fermat probable primality
test), the time to multiply by *x* may be
insignificant in comparison to the time
required to square, so the
left-to-right method *can be* significantly faster.

Binary exponentiation does not always gives the fewest
possible multiplications. For example, these
methods take 6 multiplications to find
*x*^{15}, but we can
find *x*^{3} in two and *x*^{5}
in three, so can get *x*^{15}=
(*x*^{3})^{5} in five
multiplications.

**References:**

- Knuth97 (section 4.6.3)
D. E. Knuth,Seminumerical algorithms, 3rd edition, The Art of Computer Programming Vol, 2, Addison-Wesley, 1997. Reading MA, [This book is an excellent reference for anyone interested in the basic aspects of programming the algorithms mentioned in these pages.]