next up previous contents index CD CD Algorithms
Next: Binary Search Up: Divide and Conquer Previous: Divide and Conquer

Fast Exponentiation

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

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

function power(a,n)

if (n = 0) return(1)

x = power( tex2html_wrap_inline24838 )

if (n is even) then return( tex2html_wrap_inline24840 )

else return( tex2html_wrap_inline24842 )

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