Notes

The Square-Root Algorithm
Similar to division, the process of square-rooting involves repeated subtractions, additions and shifts. The
square-root algorithm is based on the fact that the square of the integer a is the sum of the first a odd integers:
This method was often used in electric or manual desk computing machines at the time of the ENIAC. To find a
rough estimate of the square root of M, one can subtract progressively larger odd numbers until a negative result
is produced. The last odd number used is (2a – 1) where a2 is the first perfect square greater than M. Adding
one and dividing by two provides an estimate of ÖM that is no more than one greater than the actual value.
However, for a ten-digit number, the process of subtracting larger and larger odd numbers is prohibitively timeconsuming.
Moreover, it is useful to refine this estimate using decimal places rather than just integers since
more often than not, square-root calculations do not involve perfect squares.
Using the above equation, it is apparent that 100 is the sum of the first ten odd integers, 1 through 19. Adding
20 to each of these provides the next ten odd integers, i.e. 21 through 39. The sum of these 10 odd integers is
100 + 10(20) = 300. Continuing in this way, it becomes obvious that the sum of the (10n – 9)th through 10nth
odd integers is (2n – l)×100, and the values of these integers are 20(n – 1)+1 through 20×(n – 1) + 19, or 20n –
19 through the value 20n – 1.
This leads to a method of making a very rough estimate of the square root. First, subtract successively
increasing odd hundreds (100, 300, 500, . . . (2n–1)×100 . . .) until a sign change is achieved. At this point, it
has been determined that M is greater than (or equal to) the sum of the first 10×(n- 1) odd integers, but less than
the sum of the first 10n odd integers (the last of which is 20n – 1). Hence, 10×(n – 1) £ ÖM < 10n.
Since the last number used to subtract is N = 200n – 100, and the last of the 10n integers is l =(20n–1), l can be
calculated to be, l = N /10 + 9. The rough estimate can be refined by "un-subtracting" (i.e., adding) successively
smaller odd numbers from the overdraft starting with l until a sign change. If the last odd integer added is b, it is
now known from Eq. (1) that b – 1< 2Ö M £ b + 1. A good estimate is, therefore, b » 2Ö M . The same
algorithm can be expanded by noting that 104 is the sum of the first 102 odd integers, 106 is the sum of the first
103 odd integers, and so on.
The ENIAC begins with 108 in the denominator ("two-root") accumulator (i.e., a I in the ninth decade) with the
radicand stored in the numerator accumulator. The contents of the denominator accumulator are subtracted from
the numerator accumulator, after which the denominator is incremented by 2 in the ninth place. This subtraction
and increment is repeated until the sign changes. At this point, the denominator accumulator has already been
incremented beyond the last number subtracted. The division by 10 is accomplished by shifting the numerator
one place to the left. Then, instead of adding nine in the next place down in the denominator accumulator, an
effective 20 has already been added, so 11 is subtracted.
The new number is added to the numerator, and the quotient is decremented by two in that next place down.
After a sign change, the numerator is shifted, and the correction factor of 11 is added one more place down.
Then, the process continues, alternating subtraction and incrementing with subtraction and decrementing at
every sign-change, until the desired accuracy is achieved.
Rounding off in square-rooting is an approximate method. As in division, the residue of the numerator is shifted
to the left again, and the denominator is subtracted from this five times. If no overdraft results, the last place of
the doubled root will be incremented or decremented by two.
Again, because of shifting, significant figures in the numerator accumulator can potentially be lost. Since the
denominator is initially incremented in the ninth place, any radicand greater than or equal to 25 × 108 will cause
the tenth place of the denominator accumulator to be non-zero, and thus cause shift errors. To ensure that no
such shift errors can occur, the general rule is to keep at least one zero preceding the radicand in the numerator
accumulator.