Recursion - Data Structures and Problem Solving Using Java - page 313

and if N is odd, then

= XX N 1

⋅ = XXX ⋅ ( ⋅ )

- N 2 ⁄

X N

(Recall that is the largest integer that is smaller than or equal to X .) As before,
to perform modular exponentiation, we apply a % after every multiplication.
The recursive algorithm shown in Figure 7.16 represents a direct imple-
mentation of this strategy. Lines 8 and 9 handle the base case: X 0 is 1, by def-
inition. 4 At line 11, we make a recursive call based on the identity stated in the
preceding paragraph. If N is even, this call computes the desired answer; if N
is odd, we need to multiply by an extra X (and use operator% ).

X

This algorithm is faster than the simple algorithm proposed earlier. If
M ( N ) is the number of multiplications used by power , we have M ( N )

Exponentiation can
be done in logarith-
mic number of
multiplications.

≤
M ( ⎣ N /2 ⎦ ) + 2. The reason is that if N is even, we perform one multiplica-
tion, plus those done recursively, and that if N is odd, we perform two mul-
tiplications, plus those done recursively. Because M (0) = 0, we can show
that M ( N ) < 2 log N . The logarithmic factor can be obtained without direct
calculation by application of the halving principle (see Section 5.5), which
tells us the number of recursive invocations of power . Moreover, an average
value of M ( N ) is (3/2)log N , as in each recursive step N is equally likely to
be even or odd. If N is a 100-digit number, in the worst case only about 665
multiplications (and typically only 500 on average) are needed.

1 /**
2 * Return x^n (mod p)
3 * Assumes x, n >= 0, p > 0, x < p, 0^0 = 1
4 * Overflow may occur if p > 31 bits.
5 */
6 public static long power( long x, long n, long p )
7 {
8 if( n == 0 )
9 return 1;
10
11 long tmp = power( ( x * x ) % p, n / 2, p );
12
13 if( n % 2 != 0 )
14 tmp = ( tmp * x ) % p;
15
16 return tmp;
17 }

figure 7.16
Modular
exponentiation routine

4. We define 0 0 = 1 for the purposes of this algorithm. We also assume that N is nonnegative
and P is positive.