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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum