4.3.3 HOW FAST CAN (Geocities web hosting) WE MULTIPLY? 289 The
4.3.3 HOW FAST CAN WE MULTIPLY? 289 The above observations leave us with the following problem to solve: Given positive integers e < f and a nonnegative integer u < 2f, compute the value of (cu)mod(2f-1), w h ere c is the number such that (ae - l)c -1 (modulo 2f -1); and the computation must be done in O(flogf) cycles. The result of exercise 4.3.2-6 gives a formula for c that suggests a suitable procedure. First we find the least positive integer b such that be - 1 (modulo f). (28) This can be done using Euclid s algorithm in O((logf)3) cycles, since Euclid s algorithm applied to e and f requires O(logf) iterations, and each iteration requires O((logf)2) c es; alternatively, we could be very sloppy here without cy 1 violating the total time constraint, by simply trying b = 1, 2, etc., until (28) is satisfied, since such a process would take O(flogf) cycles in all. Once b has been found, exercise 4.3.2-6 tells us that c=c[b]=(0~~2~ )mod(2f-i). (29) - A brute-force multiplication of (cu) mod (2f -1) would not be good enough to solve the problem, since we do not know how to multiply general f-bit numbers in O(flogf) cycles. But the special form of c provides a clue: The binary representation of c is composed of bits in a regular pattern, and Eq. (29) shows that the number c[2b] can be obtained in a simple way from c[b]. This suggests that we can rapidly multiply a number u by c[b] if we build c[b]u up in lg b steps in a suitably clever manner, such as the following: Let the binary notation for b be b = (b, . . . bAh)2; we may calculate the sequences ak, dk, uk, ?& defined by the rUleS a0 = e, ak = 2ak-l mod f; do = hoe, dk = (h-1 + h ak) mod f; uo = u, uk = (U&l + 2ak-1uk-l) mod (af -1); (30) v. = bou, vk = (vk-1 + bk 2dkp1uk) mod (2f -1). It is easy to prove by induction on Ic that ak = (2 e)mod f; uk = (c[2k]U)mod(2f -1); dk = ((bk.. blbo)z e)mod f; vk = (c[(bk . . blbo)2]u) mod (af -1). (31) Hence the desired result, (c[b]u) mod (2f -l), is 21,. The calculation of ak, dk, uk, vk from ak-11 dk-1, uk-1, vk-1 takes o(l% f )+o(h? f )+o(f )+0(f) = o(f) cycles, and therefore the entire calculation can be done in s O(f) = 0( f log f) cycles as desired.