Associated Topics || Dr. Math Home || Search Dr. Math

### 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

more, or if you have any other questions.

- Doctor Jubal, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Exponents

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search