Web site design and hosting - 4.3.1 ANSWERSTOEXERCISES 581 8. ENNl N 1 2H
4.3.1 ANSWERSTOEXERCISES 581 8. ENNl N 1 2H LDA W+N+l,2 K JOV OFLO 1 INCA 1 K STZ W 1 STA W+N+1,2 K IH LDA U+N+l,l N DEC2 1 K ADD V+N+l,l iV JOV 2B K STA W+N+i,i N 3H INC2 1 N JNOV 3F N J2N 1B N ENT2 -1,l L I The running time depends on L, the number of positions in which uj + v3 2 b; and on K, the total number of carries. It is not difficult to see that K is the same quantity that appears in Program A. The analysis in the text shows that L has the average value N((b -1)/2b), and K has the average value +(N -b-l -b- -. . . -b- ). So if we ignore terms of order l/b, the running time is 9N + L + i K + 3 z 13N + 3 cycles. Note: Since a carry occurs almost half of the time, it would be more efficient to delay storing the result by one step. This leads to a somewhat longer program whose running time is approximately 12N + 5 cycles, based on the somewhat more detailed information calculated in exercise 7. 9. Replace b by bnp3 everywhere in step A2. 10. If lines 06 and 07 were interchanged, we would almost always have overflow, but register A might have a negative value at line 08, so this would not work. If the instructions on lines 05 and 06 were interchanged, the sequence of overflows occurring in the program would be slightly different in some cases, but the program would still be right. 11. (a) Set j + 1; (b) if 2~~ < vi, terminate [u < v]; if ZL~ = v~j and j = n, terminate [u=v];ifu3=v3andj