**1.** *x ^{m}*, where

**2.** Assume that *x* is input in register A, and *n* in location `NN`

; the output is in register X.

The running time is 21*L* + 16*K* + 8, where *L* = λ(*n*) is one less than the number of bits in the binary representation of *n*, and *K* = ν(*n*) is the number of 1-bits in that representation.

For the serial program, we may assume that *n* is small enough to fit in an index register; otherwise serial exponentiation is out of the question. The following program leaves the output in register A:

The running time for this program is 14*N* – 7; it is faster than the previous program ...

Start Free Trial

No credit card required