Binary Exponentiation

Date: 09/13/2001 at 16:34:56
From: Abe
Subject: Fast exponentiation

Hi,

Show how to compute 5^21 using 6 multiplications.
How many multiplications are needed to compute 7^7024 ?

Date: 09/13/2001 at 17:57:24
From: Doctor Jubal
Subject: Re: Fast exponentiation

Hi Abe,

Thanks for writing Dr. Math.

The fastest exponentiations to perform are exponentiations of the type
a^(2^n), that is, where the exponent is a power of two. This is 
because you can find these powers by repeatedly squaring the number.

So I can find 5^2 with only one multiplication, 5^4 = (5^2)^2 with 
only two, 5^8 = ((5^2)^2)^2 in three, and so forth.

This leads to the method of binary exponentiation:

1) Write the exponent as a sum of powers of two.
2) Find the base to each of the powers of two that appear in the  
   exponent.
3) Multiply those powers together.

To illustrate with 5^21:

1) 21 = 16 + 4 + 1
2) 5^1 = 5    
   5^2 = 5*5 = 25
   5^4 = 25 * 25 = 625
   5^8 = 625 * 625 = 390625
   5^16 = 390625 * 390625 = 152587890625
3) 5^21 = 5^16 * 5^4 * 5 = 476837158203125

All told, step 1 required no multiplication, step 2 required four
multiplications to get up to 5^16, and step 3 required two 
multiplications for a total of six multiplications.

In general, once you write out the exponent as a sum of powers of two, 
you can figure out how many multiplications you'll need.  If the 
highest power of two in the sum is 2^m, step 2 above will require 
m multiplications to calculate all the powers you'll need for step 
three. If there are n powers of two in the sum, step three requires 
n-1 multiplications.

So all told, binary exponentiation requires m+n-1 multiplications, 
where n is the number of powers of two needed to write the exponent as 
a sum of powers of two, and m is the largest power of two in the sum.  
I'll leave it to you to use that to figure out the second half of your 
question.

If you want to look into it further, there are a couple of ways to
streamline the algorithm.  Here's a link:

  Binary Exponentiation (from the Prime Pages)
  http://www.utm.edu/research/primes/glossary/BinaryExponentiation.html    

Does this help?  Write back if you'd like to talk about this some
more, or if you have any other questions.

- Doctor Jubal, The Math Forum
  http://mathforum.org/dr.math/