ENIAC took a Square Root
Abstract: The ENIAC (Electronic Numerical Integrator and Computer) is the world's first electronic computer. However it could only store twenty 10-digit decimal numbers and was programmed by wiring the computational units together. These limitations made it very unlike today's stored-program computers. The ENIAC had hardware to add, subtract, multiply, divide and take a square root. This last operation is interesting since computers normally don't do square roots in hardware. So given the limited capabilities of the ENIAC, how did it take a square root? A slightly updated version of How the ENIAC took a Square Root (revised 2009) in .pdf format is also available.
History: The ENIAC was a war time effort by the University of Pennsylvania's Moore School of Electrical Engineering for the Army's Ballistics Research Lab at Aberdeen Maryland. Its purpose was to compute "firing tables" for artillery, information that gunners would use to properly aim and fire their guns. During World War II such computational work for firing tables was being done using the Moore School's Differential Analyzer, an analog device that could solve differential equations. 1942 John Mauchly, a physics professor working at the Moore School who had a long time interest in scientific computing, submitted a proposal for using vacuum tube devices for high speed computing. Discussions with J. Presper Eckert, graduate student at the Moore School, convinced him that such a devices was possible. In 1943 when the need for more firing tables became more acute, Mauchly's proposal was brought up with the result that the army awarded a contract to the Moore School to build what we know today as the ENIAC. Mauchy was the principal consultant and Eckert the chief engineer. Work on ENIAC began in the summer of 1943 but the ENIAC was not completed until the after the war ended; the ENIAC was officially unveiled in February 1946.
Overview of the ENIAC: The ENIAC was "build" around twenty 10 decimal digit Accumulators which could add and subtract at electronic speeds. To add or subtract two numbers, the contents of one accumulator was sent to a second. Accumulators could "receive" a number, transmit its contents "additively" (for addition) or transmit "subtractively" (for subtraction). The ENIAC was capable of performing 5000 additions/subtractions per second!
An accumulator contained ten decade counters. Each decade counter (designed by Eckert) was a ten state circuit that could store a single decimal digit much like a ten position "counter wheel" from a mechanical calculator. An electronic "pulse" (a "square wave" __|---|__ ) would advance the decade counter one position. Digits were sent as a "train of pulses" so if a decade counter was in the "4" state, upon receiving a train of 3 pulses ( __|---|_|---|_|---|__ ) it would advance to the "7" state. If it received a train of 8 pulses it would advance with "wrap-around" to the "2" state and while generating a "carry- pulse" to the next decade. Subtraction was done by using 9 complement digits (i.e. -7 was sent as 9 - 7 = 2 pulses) with an extra pulse added to the units digit (essentially tens-complement notation). The ten digit "pulse trains" plus a sign "pulse" were sent over eleven parallel wires. An eleventh two-state plus-minus counter was used for the sign.
The ENIAC also had a high-speed Multiplier unit for multiplication. The Multiplier contained the logic to multiply a ten digit number by a single digit to obtain a partial product. The partial products were then added together (using accumulators) to obtain the final product. The Multiplier made use of four accumulators to multiply (six for a 20 digit product).
The final computational unit was a Divider/Square Rooter. Division and taking a square root was orchestrated as a series of subtractions/additions and shifts which like the Multiplier made use of a number of accumulators but unlike the Multiplier contained no special computational hardware to do either; in other words it used accumulators to do the needed addition and subtraction. All work was done in decimal. Division was done by repeated subtractions followed by repeated additions etc. using a technique called "non-restoring division". As we shall see taking a square root used a similar technique which is probably why the two operations were combined in one unit.
Input Output was provided by a mechanical IBM card Reader and card Punch which were connected to an electronic Constant Transmitter used to stored constants. The Constant Transmitter provided the interface between the slow-speed mechanical I/O devices and the rest of the high-speed electronic ENIAC. There were also three Function Table units, essentially 100 by 10 digit ROM memories which were set by switches.
The units of the ENIAC were connected by two buses: a data bus used to transmit the "ten digits plus sign" over parallel wires and a control bus. Program control for the ENIAC was distributed, not centralized. Each accumulator contained control logic that would allow it to "work" with other accumulators to perform a sequence of calculations. Programming was accomplished by setting switches on the various units and wiring the connections between them using the control bus for control signals and the data bus for data. A Master Control unit was used to "loop" the various sequence of calculations set up between accumulators. A Cycling Unit synchronized the various units over a third cycle bus (not shown above). There was also an Initializing Unit.
The ENIAC did not use a "fetch-decode-execute" cycle to execute its program since there was no memory to store instructions. And the ENIAC was not "programmed" using paper tape unlike Zuse's Z3 (a device unknown to Mauchly and Eckert) or Aiken's Automatic Sequence Controlled Calculator (Harvard Mark I) completed in the summer of 1944, both of which read their instructions from paper tape readers. The reason for not using paper tape readers was the slow speed of such mechanical. devices. If the ENIAC was to be truly fast, both instructions and calculations had to be executed at electronic speeds. The only way to effectively do the former was to "wire" the program into the machine. The idea was not completely new; IBM punch card equipment could be programming in a limited way using plug boards.
All of this was packaged into 40 panels each 2 feet wide wide by 8 feet high arranged in a U shape in a 30 by 60 foot area. A diagram of the ENIAC from the "ENIAC Progress Report" of June 30, 1945 can be seen <click here>.
A Method for Taking a Square Root
The method used by the ENIAC Square Rooter to take a square root required only addition and subtraction. It was based on the formula that the sum of the first n odd integers is n squared.
To calculate the square root of m, find the smallest integer n such the sum of the first n odd integers exceeds m. This can be done by subtracting the consecutive odd integers from m until a negative result is obtained. If n is the smallest integer such that m - (1 + 3 + 5 + ...+ 2n-1) < 0 then (n - 1)2 <= m < n2. Letting a equal the nth odd integer 2n -1, solve the double inequality (n-1) <= sqrt(m) < n for
Example: To estimate the square root of 7251, subtract the consecutive odd integers until a negative result is obtained. Note that 7251 - (1 + 3 + 5 + ... + 169) = 26 and 7251 - (1 + 3 + + 5 + ... 169 + 171) = -145 so a = 171. Thus
Aside: By comparing the 26 and the -145 observe that 85 is the closer approximation. Using linear interpolation, 26/171 = 0.1520 so 85.152 is a better approximation. (compare with 85.1528). - End of Example
Additional precision is possible if you first multiply m by a power of 100, take the square root then divide by the same power of 10. For example if we multiply 7251 by 1002 (one hundred squared) to obtain 72,510,000 and take the square root using the above technique, then 72,510,000 - (1 + 3 + 5 + ... + 17031) = -12256. Thus
so 85.15 <= sqrt(7251) < 85.16 (after dividing by ten squared).
Reality Check: The ENIAC could do 5000 additions/subtractions per second. Therefore to do the twice 8516 additions/subtractions would take 3.4 seconds! Thi is not a very efficient way to find the square root.
A More Efficient Approach
The above algorithm can be made more efficient. It's a two step process.
First observe that the sum of the consecutive odd multiples of 100 is also a square. That is 100 + 300 + 500 + ... (2n-1)*100 = n2*100. Thus we can calculate the square root of m to the nearest tens by finding the smallest integer n such that m - (100 + 300 + ... + (2n-1)*100) < 0 which implies (n-1)2*100 <= m < n2*100. Again if we let a equal the odd integer 2n-1 then solving the double inequality yields
However every odd multiple N = (2n-1)*100 is the sum of ten consecutive odd integers. Let
N = (2n-1)*100 = 200(n-1) + 100
Now 200(n-1) can be rewritten as 10*20(n-1) and 100 can be expressed as the sum 1 + 3 + 5 + ... + 19. Hence N can be written as the sum of the ten consecutive odd integers
N = [20(n-1) + 1] + [20(n-1) + 3] + ... [20(n-1) + 19]
Even better, since a little algebra shows (n-1) = (N - 100)/200 and 20(n-1) = N/10 - 10
N = [N/10 - 9] + [N/10 - 7] + ... + [N/10 + 7] + [N/10 + 9]
Thus we can add back the odd integers starting with N/10 + 9 until the result is positive. If N/10 + j (where j is an odd integers between -9 and +9) was the last (smallest) odd integer added back, the N/10 + j is the smallest odd integer such that
m - (1 + 3 + 5 + ... + (N/10 + j)) < 0
Thus if a = N/10 + j then
Example: Find the square root of 72,5120,000
1. Subtract odd multiples of 100
72,150,000 - (100 + 300 + 500 + ... + 170100) = 89900
72,150,000 - (100 + 300 + 500 + ... + 170100 + 170300) = -80400
so N = 170300. The last (largest) odd integer subtracted was 170300/10 + 9 = 17039
2. Add back the decreasing sequence of odd integers starting with 17039
-80400 + (17039 + 17037 + ... + 17033) = -12256
-80400 + (17039 + 17037 + ... + 17033 + 17031) = 4775
so N = 17031 which agrees with the previous result (i.e. 8515 <= sqrt(72,510,000) < 8516).
End of Example
Thus by combining subtracting odd multiples of 100 then adding back the odd integers whose sum equals the last odd multiple of 100, we can reduce the number of calculations by an order of magnitude.
Reality Check: With a reduction of the number of additions/subtractions by a factor of 10, the ENIAC could now calculate the square root in approximately 0.34 seconds - which is still slow.
A Generalization of the More Efficient Approach
We can extend this technique to subtracting odd multiples of powers of 100 by observing that the sequence of odd multiples of 100k is a square and that if N is any odd multiple of 100k, it can be written as a sum of ten odd multiples of 100k-1. These results are stated formally below,
For k >= 0 the sum of the first n odd multiples of 100k is a square.
Thus we can calculate the square root of m to the nearest 10k by finding the smallest integer n such that m - (1*100k + 3*100k + ... + (2n-1)*100k) < 0 which implies (n-1)2*100k <= m < n2*100k. If we let N = (2n-1)*100k then solving the double inequality obtains a range for twice the root
Observe that this is not a very good estimate!
Any odd multiple of 100k can be written as the sum of ten consecutive odd multiples of 100k-1. Specifically if N is an odd multiple of 100k, then
Proof:: Simply do the algebra. The case k = 1 is the result that any odd multiple of 100 is the sum of ten consecutive odd integers.
Given these two results we present an algorithm (used by the ENIAC) to obtain a square root
Square Root Algorithm
Replace k-1 with k and let N be the last odd multiple of 100k added back (remember k-1 is now k). If k = 0 then you're done so go to step 4; otherwise N is the sum of ten consecutive odd multiples of 100k-1 so continue on to step 3.
Replace k-1 with k and let N be the last odd multiple of 100k subtracted (remember k-1 is now k). If k = 0 then you're done so go to step 4; otherwise N is the sum of the ten consecutive odd multiples of 100k-1 so go back to step 2.
The ENIAC used N for twice the square root
Example: Find the square root of 72,510,000.
1. Starting with 1003 subtract the increasing sequence of odd multiples of 1003 until a negative result is obtained
72,510,000 - (1*1003 + 3*1003 + ... + 15*1003 + 17*1003) = -8490000
Therefore the last odd multiple of 1002 subtracted was 17*1003/10 + 9*1002 = 179*1002
2. Starting with 179*1002 add back the decreasing sequence of odd multiples of 1002 until a positive result is obtained.
-8490000 + (179*1002 + 177*1002 + ...+ 173*1002 + 171*1002) = 260000
Therefore the last odd multiple of 100 added back was 171*1002/10 - 900 = 1701*100.
3. Starting with 1701*100 subtract the increasing sequence of odd multiples of 100 until a negative result is obtained
260000 - (1701*100 + 1703*100) = -80400
Therefore the last odd integer subtracted was 1703*100/10 + 9 = 17039
4. Starting with 17039 add back the decreasing sequence of odd integers until a positive result is obtained
-80400 + (17039 + 17037 + ... + 17033 + 17031) = 4775
Therefore 17031 is the smallest odd integer such that 72,510,000 - (1 + 3 + 5 + ... + 17031) < 0. Therefore
17030 <= 2*sqrt(72,510,000) < 17032
End of Example
How this Algorithm was Implemented on the ENIAC
On the ENIAC the hardware to take a square root was combined with the divider since the sequence of operations used is similar to those used to divide (a non-restoring division technique was used) . Taking a square root was done using a couple of accumulators to execute the series of subtractions and additions discussed. The divider/square rooter essentially orchestrated the sequence of steps needed; unlike the high-speed multiplier unit it contain no special circuits to perform arithmetic.
The square rooter actually performed calculations to obtain twice the square root. To obtain 2*sqrt(m), the value m was deposited to an accumulator which we shall call the numerator. Then a second accumulator, the denominator, was initialized to 108 (1004) by setting the 9th digit to 1.
For example, to calculate twice the square root of 72,510,000 two accumulators were initialized as follows
Numerator: 0,072,510,000 Denominator: 0,100,000,000
Step 1: Subtract increasing odd multiples of 108 (1004) from the numerator until a negative result is obtained.
The denominator was subtracted from the numerator and the denominator was incremented by 2 in the 9th digit. This was repeated until there was a sign change in the numerator. Note that the denominator is incremented after the subtraction but before the sign of the numerator is tested so that the denominator "overshoots" the "correct" value.
Numerator: -0,027,490,000 Denominator: 0,300,000,000
At this point we know that m - 1*1004 < 0 and if N = 1*1004 then N/10 + 9*1003 was the last odd multiple of 1003 subtracted. Therefore starting with N/10 + 9*1003 = 019,000,000, add back the decreasing sequence of odd multiples of 1003 until a sign change is obtained. The value to be added back could be obtained by right shifting the denominator and setting the 7th position to 9.
Numerator: -0,027,490,000 Denominator: 0,019,000,000
However, this was not done by the ENIAC square rooter!
To increase the precision of the final answer the ENIAC scaled its calculations by left shifting the numerator and not right shifting the denominator and setting the 8th digit to 9 instead of the 7th digit. This scaling trick would eventually add 4 digits of accuracy to the final answer.
Numerator: -0,274,900,000 Denominator: 0,190,000,000
But there was one further complication! The denominator contains the wrong value since it was incremented by 2 before the sign of the numerator was tested. So instead of setting the 8th digit to 9, it subtracts 11 from the 8th and 9th digits
Denominator: 0,190,000,000 after subtracting 11
Aside: If N = (2n-1)*1004 is the largest odd multiple of 1004 (108) such that m - (1*1004 + 3*1004 + ...+ (2n-1)*1004) < 0 , then the denominator contains N + 2*108 instead of N. Subtracting 11*107 yields N + 9*107 which is what the denominator should contain for the next iteration.
Step 2: Add back!
Add the denominator back into the numerator and decrement the denominator by 2 in the 8th digit until a sign change is obtained (numerator is positive).
If N = (2n-1)*100k was the last odd multiple of 100k added back, then N/10 - 9*100k-1 was the last (smallest) odd multiple of 100k-1 added back. Thus beginning with N/10 - 9*100k-1 subtract the increasing sequence of odd multiples of 100k-1 until a sign change is obtained (to negative). Again to increase precision the ENIAC scaled by left shifting the numerator and by not right shifting the denominator and adding 11 to the 7th and 8th digits.
At this point we repeat alternately subtracting/adding the denominator from/to the numerator and incrementing/decrementing the denominator by 2 in the pth position until a sign change is obtained. After the repeated subtraction/addition sequence terminates with a sign change, we left shift the numerator and subtract/add 11 to the p-1 position in the denominator.
Step 3: Subtract
Step 4: Add Back
Step 5: Subtract
Step 6: Add Back
Step 7: Subtract
Step 8: Add Back
Step 9: Subtract
The last odd integer subtracted was a = 170,305,607 which made the numerator negative, Thus after scaling we have
If you compare the magnitudes of the last two numerator values, 1412,243,192 and -29,062,416, the better approximation would be 17,030.5607. The ENIAC square rooter has an optional round off mechanism. It left shifted the numerator one more time and then subtracted the denominator 5 times from it. If there is no sign change the last position in the doubled root was incremented or decremented by 2 depending on whether the denominator was previously decremented or incremented by 2. Thus
Numerator: -0,290,624,160 Denominator: 0,170,305,609
Numerator: 0,560,903,885 <- sign change!
Since there is a sign change, 17,030.5607 is the best approximation for the doubled square root. The decimal point is between the 4th and 5th positions so the doubled root is approximately 17,030.5607.
This method also works for small numbers. Here we demonstrate how the ENIAC would take the square root of 2 an accuracy of 4 digits below the decimal point.
Step 1: Subtract increasing odd multiplies of 108 from the numerator until a negative result is obtained. Remember that the ENIAC always increments the denominator by 2 in the pth digit..
Step 2: Left shift the numerator and subtract 11*107 from the denominator. Add back decreasing odd multiples of 107 to the numerator until a positive result is obtained.
Step 3: Left shift the numerator and add 11*106 to the denominator. Subtract increasing odd multiples of 106 from the numerator until a negative result is obtained.
Step 4: Left shift the numerator and subtract 11*105 from the denominator. Add back decreasing odd multiples of 105 to the numerator until a positive result is obtained.
Step 5: Left shift the numerator and add 11*104 to the denominator. Subtract increasing odd multiples of 104 from the numerator until a negative result is obtained.
Step 6: Left shift the numerator and subtract 11*103 from the denominator. Add back decreasing odd multiples of 103 to the numerator until a positive result is obtained.
Step 7: Left shift the numerator and add 11*102 to the denominator. Subtract increasing odd multiples of 102 from the numerator until a negative result is obtained.
Step 8: Left shift the numerator and subtract 11*101 from the denominator. Add back decreasing odd multiples of 101 to the numerator until a positive result is obtained.
Step 9: Left shift the numerator and add 11 to the denominator. Subtract increasing odd integers from the numerator until a negative result is obtained.
Thus twice the square root of 2 is between 2.8284 and 2.8286. If we round off by adding 5 times the denominator to the numerator we get a sign change so we use 2.8285 as our best approximation. 2.8285/2 = 1.41425 agrees favorably with sqrt(2) = 1.4142135.
Summary: To my knowledge, only two of the "early" computers ever implemented a square root operation in hardware: Zuse's Z3 and the ENIAC both of which had limited memory and/or programming capabilities. In the "First Draft of the Report on the EDVAC" written in 1945, von Neumann incorporates the design for a square rooter (which von Neumann notes is similar to the "divider network"). Yet in his later 1946 paper "Preliminary discussion of the logical design of an electronic computing instrument" which von Neumann authored with Arthur Burks and Herman Goldstine, he leaves out the design of a square rooter "because such a device would involve more equipment than we feel desirable in first model". Hardware was expensive in the early computers and designs reflected a "keep it simple" philosophy. (I should point out that neither the EDVAC or the EDSAC, computers which were heavily influenced by the "First Draft" paper, had a square root operation. And neither did the IAS machine which was influenced by the "Preliminary discussion" paper). Besides, the increased memory capacity and the flexibility of programming found in later stored program computers allowed square roots to be easily done in software. The Z3 and ENIAC were not stored program computers.
So given that square roots are hard to compute (how many of us can take one by hand?), how did a relatively primitive computer like the ENIAC take a square root? The ENIAC implemented a well known square root algorithm that could be carried out by any one with desk calculator with addition, subtraction, and shift capabilities. Since the ENIAC was very good at addition and subtraction (it had 20 accumulators that could do both at electronic speeds), taking a square root turned out just to be a matter of sequencing their operations in the correct way.
1946 Technical Report on The ENIAC <http://ftp.arl.army.mil/~mike/comphist/45eniac_report>: This is the first four chapters of the the June 1, 1946 Report on the ENIAC. Excellent primary source material from the U.S. Army Research Laboratory at the Aberdeen Proving Grounds, MD.
History of Computing Information <http://ftp.arl.army.mil/~mile/comphist> : web page with other links to ENIAC materials also maintained at the ARL at Aberdeen
How the ENIAC took a Square Root (revised 2009) is a slightly updated version in .pdf format of this .html file.
ENIAC: The Triumphs and Tragedies of the World's First Computer; Scott McCartney : This is an excellent general history of the ENIAC
From ENIAC to UNIVAC: An Appraisal of the Early Eckert-Mauchly Computers, Nancy Stern: Another excellent general history of the ENIAC.
"The ENIAC: History, Operation, and Reconstruction in VLSI" by Jan Van der Spiegel, James F. Tau, Titiimaea F. Ala'ilima Lin Ping Ang; from The First Computers: History and Architectures edited by R. Rojas and U. Hashagen : This paper contains many of the technical details of the ENIAC. The square root algorithm was obtained from this source.
Return to Brian
Shelburne's Home Page