binary exponentiation

One way to calculate x²⁵ 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 x², x³, x⁶, x¹², x²⁴, and x²⁵. 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¹⁰⁰⁰, then calculating xⁿ 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ⁿ 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 3ⁿ 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¹⁵, but we can find x³ in two and x⁵ in three, so can get x¹⁵= (x³)⁵ 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.]