98 Part 2 The instruction-set processor: main-line computers

could be formed in 6 multiplication times, and hence a quotient b/a in 7 multiplication times. Accordingly we see that the question of building a divider s really a function of how fast it can be made to operate compared to the iterative method sketched above: In order to justify its existence, a divider must perform a division in a good deal less than 7 multiplication times. We have, however, conceived a divider which is much faster than these 7 multiplication times and therefore feel justified in building it, especially since the amount of equipment needed above the requirements of the multiplier is not important.

It is, of course, also possible to handle square roots by iterative techniques. In fact, if X is our estimate of a^1/2, then X' = 1/2(X + a/X) is a better estimate. We se that this scheme involves one division per iteration. As will be seen below in our more detailed examination of the arithmetic organ we do not include a square- rooter in our plans because such a device would involve more equipment than we feel is desirable in a first model. (Concerning the iterative method of square-rooting, cf. 8.10 in Part II)

55. The first part of our arithmetic organ requires little discussion at this point. It should be a parallel storage organ which can receive a number and add it to the one already in it, which is also able to clear its contents and which can transmit what it contains. We will call such an organ an Accumulator. It is quite conventional in principle in past and present computing machines of the most varied types, e.g. desk multipliers, standard IBM counters, more modem relay machines, the ENIAC. There are of, course, numerous ways to build such a binary accumulator. We distinguish two broad types of such devices: static, and dynamic or pulse-type accumulators. These will be discussed in 5.11, but it is first necessary to make a few remarks concerning the arithmetic of binary addition. In a parallel accumulator, the first step in an addition is to add each digit of the addend to the corresponding digit of the augend. The second step is to perform the carries, and this must be done in sequence since a carry may produce a carry. In the worst case, 39 carries will occur. Clearly it is inefficient to allow 39 times as much time for the second step (performing the carries) as for the first step (adding the digits). Hence either the carries must be accelerated, or use must be made of the average number of carries or both.

5.6. We shall show that for a sum of binary words, each of length n, the length of the largest carry sequence is on the average not in excess of ²log n. Let p_n(v) designate the probability that a carry sequence is of length v or greater in the sum of two binary words of length n. Then clearly p_n(v) - p_n(v + 1) is the probability that the largest carry sequence is of length exactly v and the weighted average

Indeed, p_n(v) is the probability that the sum of two n-digit numbers contains a carry sequence of length ³ v. This probability obtains by adding the probabilities of two mutually exclusive alternatives: First: Either the n - 1 first digits of the two numbers by themselves contain a carry sequence of length ³ v. This has the probability p_n-1(v). Second: The n - 1 first digits of the two numbers by themselves do not contain a carry sequence of length ³ v. In this case any carry sequence of length ³ v in the total numbers (of length n) must end with the last digits of the total sequence. Hence these must form the combination 1, 1. The next v - 1 digits must propagate the carry, hence each of these must form the combination 1, 0 or 0, 1. (The combinations 1, 1 and 0, 0 do not propagate a carry.) The probability of the combination 1, 1 is 1/4, that one of the alternative combinations 1, 0 or 0, 1 is 1/2 . The total probability of this sequence is therefore 1/4(1/2)^v-1 = (1/2)^v+1. The remaining n - v digits must not contain a carry sequence of length ³ v. This has the probability 1 - p_n-v(v). Thus the probability of the second case is [1 - p_n-v(v)]/2 ^v+l. Combining these two cases, the desired relation

obtains. The observation that p_n(v) = 0 if v >n is trivial.

We see with the help of the formulas proved above that p_n(v) - p_n-1(v) is always £ 1/2 ^v+1, and hence that the sum