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.