        Next: Binary Search Up: Divide and Conquer Previous: Divide and Conquer

## Fast Exponentiation

Suppose that we need to compute the value of for some reasonably large n. Such problems occur in primality testing for cryptography, as discussed in Section .

The simplest algorithm performs n-1 multiplications, by computing . However, we can do better by observing that . If n is even, then . If n is odd, then . In either case, we have halved the size of our exponent at the cost of at most two multiplications, so multiplications suffice to compute the final value.

```

function power(a,n)

if (n = 0) return(1)

x = power( )

if (n is even) then return( )

else return( )

```

This simple algorithm illustrates an important principle of divide and conquer. It always pays to divide a job as evenly as possible. This principle applies to real life as well. When n is not a power of two, the problem cannot always be divided perfectly evenly, but a difference of one element between the two sides cannot cause any serious imbalance.

Algorithms
Mon Jun 2 23:33:50 EDT 1997