1. xm, where m = 2⌊lg n⌋ is the highest power of 2 less than or equal to n.
2. Assume that x is input in register A, and n in location
NN; the output is in register X.
The running time is 21L + 16K + 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 14N – 7; it is faster than the previous program ...