binary exponentiation
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000: One way to calculate x25 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 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 x2, x3, x6, x12, x24, and x25. This took 6, not 24, multiplications. For large exponents the savings is dramatic! For example, using this method to calculate: x1000000 takes 25 multiplications; x12345678901234567890 takes 94 multiplications; and if n=101000, then calculating xn takes just 4483 multiplications. In general, binary exponentiation will always take less than 2log(n)/log(2) multiplications.

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


Power(x,n) {
  r := 1
  y := x
  while (n > 1) { 
    if odd(n) then r := r*y
    n := floor(n/2)
    y := y*y
  }
  r := r*y
  return(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 3n 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 x15, but we can find x3 in two and x5 in three, so can get x15= (x3)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, Reading MA, 1997. [This book is an excellent reference for anyone interested in the basic aspects of programming the algorithms mentioned in these pages.]



Chris K. Caldwell © 1999-2014 (all rights reserved)