
Glossary: Prime Pages: Top 5000: 
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
consumingso can we do it with fewer?
An ancient method which appeared about 200 BC in Pingala's
Hindu classic Chandahsutra (and now called
lefttoright 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: square, multiply by x, square, square, square, multiply by x.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 2log(n)/log(2) multiplications. Another method, suggested by alKashi in 1427 (and similar to a method used by the Egyptians to multiply around 2000BC), is now called righttoleft binary exponentiation. To calculate x^{n} where n is a positive integer we can do the following:
This righttoleft method is easier to program, takes the same number of multiplications as the lefttoright 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 lefttoright 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:
Chris K. Caldwell © 19992015 (all rights reserved)
