## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

#### Section 4.6.3

1. xm, where m = 2lg 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 ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required