462 ARITHMETIC 4.6.3 sink exchange roles, and we (Web design programs)
462 ARITHMETIC 4.6.3 sink exchange roles, and we obtain another directed graph corresponding to a set of addition chains for the same n; these addition chains have the same length (53) as the chain we started with. For example, if we make the arrows in (52) run from right to left, and if we relabel the vertices according to the number of paths from the right-hand vertex, we get (54) One of the star chains corresponding to this reduced directed graph is 1, 2, 4, 6, 12, 24, 26, 52, 78, 79; we may call this a dual of the original addition chain. Exercises 39 and 40 discuss important consequences of this graphical repre- sentation and the duality principle. EXERCISES 1. [IS] What is the value of 2 when Algorithm A terminates? 2. [%$I Write a MIX program for Algorithm A, to calculate xn mod w given integers n and x, where w is the word size. Assume that MIX has the binary operations SRB, JAE, etc., that are described in Section 4.5.2. Write another program that computes xn mod w in a serial manner (multiplying repeatedly by x), and compare the running times of these programs. b 3. [22] How is xg75 calculated by (a) the binary method? (b) the ternary method? (c) the quaternary method? (d) the factor method? 4. [M.%I] Find a number n for which the octal (23-ary) method gives ten fewer multiplications than the binary method. b 5. [24] Figure 13 shows the first eight levels of the power tree. The (Ic + 1)-st level of this tree is defined as follows, assuming that the first k levels have been constructed: Take each node n of the lath level, from left to right in turn, and attach below it the nodes n + 1, n + al, n + us, . . . , 72 + uk-1 = 2n (in this order), where 1, al, uz, . . . , ok-1 is the path from the root of the tree to n; but discard any node that duplicates a number that has already appeared in the tree. Design an efficient algorithm that constructs the first r + 1 levels of the power tree. [Hint: Make use of two sets of variables LINKU[j], LINKR[j] for 0 5 j 5 2 ; these point upwards and to the right, respectively, if j is a number in the tree.]