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 (

nis 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.

Mon Jun 2 23:33:50 EDT 1997