O'Reilly logo

Art of Computer Programming, Volume 2, The: Seminumerical Algorithms by Donald E. Knuth

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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.

Image

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.

Start Free Trial

No credit card required