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?

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)² <=  m < n².  Letting a equal the n^th 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/(26+171) = 0.1319 so 85.13 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 100² (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 = n²*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)²*100 <= m < n²*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

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

Even better, since a little algebra shows (n-1) = (N - 100)/200  and 20(n-1) = N/10 - 10

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

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 100^k is a square and that if N is any odd multiple of 100^k, it can be written as a sum of ten odd multiples of 100^k-1. These results are stated formally below,

Result #1:

For k >= 0 the sum of the first n odd multiples of 100^k is a square.

Thus we can calculate the square root of m to the nearest 10^k by finding the smallest integer n such that m - (1*100^k + 3*100^k + ... + (2n-1)*100^k) < 0 which implies (n-1)²*100^k <= m < n²*100^k. If we let N = (2n-1)*100^k then solving the double inequality obtains a range for twice the root

Observe that this is not a very good estimate!

Result #2

Any odd multiple of 100^k can be written as the sum of ten consecutive odd multiples of 100^k-1. Specifically if N is an odd multiple of 100^k, 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

1. To find the square root of m, start with 100^k and subtract the increasing sequence of odd multiples of 100^k until the result is negative. If N is the last odd multiple subtracted then N is the sum of ten consecutive odd multiples of 100^k-1.

 
2. N/10 + 9*100^k-1 was largest (last) odd multiple of 100^k-1 subtracted. Starting with this value add back the decreasing sequence of odd multiples of 100^k-1 until a positive result is obtained.

Replace k-1 with k and let N be the last odd multiple of 100^k 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 100^k-1 so continue on to step 3.
 
3. N/10 - 9*100^k-1 was the smallest (last) odd multiple of 100^k-1 added back. Starting with this value subtract the increasing sequence of odd multiples of 100^k-1 until a negative result is obtained.

Replace k-1 with k and let N be the last odd multiple of 100^k 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 100^k-1  so go back to step 2.
 
4. N is largest odd integer such that m - (1 + 3 + 5 + ...+ N) < 0. Hence

The ENIAC used N for twice the square root

Example: Find the square root of 72,510,000.

1.    Starting with 100³ subtract the increasing sequence of odd multiples of 100³ until a negative result is obtained

Therefore the last odd multiple of 100² subtracted was 17*100³/10 + 9*100² = 179*100²

2.    Starting with 179*100² add back the decreasing sequence of odd multiples of 100² until a positive result is obtained.

Therefore the last odd multiple of 100 added back was 171*100²/10 - 900 = 1701*100.

3.    Starting with 1701*100 subtract the increasing sequence of odd multiples of 100 until a negative result is obtained

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

Therefore 17031 is the smallest odd integer such that 72,510,000 - (1 + 3 + 5 + ... + 17031) < 0. Therefore

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 10⁸ (100⁴) 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 10⁸ (100⁴) 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*100⁴ < 0 and if N = 1*100⁴ then N/10 + 9*100³ was the last odd multiple of 100³ subtracted. Therefore starting with N/10 + 9*100³ = 019,000,000, add back the decreasing sequence of odd multiples of 100³ 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

    Numerator: -0,274,900,000            Denominator:  0,300,000,000
                                         Denominator:  0,190,000,000    after subtracting 11

Aside: If N = (2n-1)*100⁴ is the largest odd multiple of 100⁴ (10⁸)  such that m - (1*100⁴ + 3*100⁴  + ...+ (2n-1)*100⁴) < 0 , then the denominator contains N + 2*10⁸  instead of N. Subtracting 11*10⁷ yields N + 9*10⁷ 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).

    Numerator: -0,274,900,000            Denominator:  0,190,000,000
               -0,084,900,000                          0,170,000,000
                0,085,100,000                          0,150,000,000

If N = (2n-1)*100^k was the last odd multiple of 100^k added back, then N/10 - 9*100^k-1 was the last (smallest) odd multiple of 100^k-1 added back. Thus beginning with N/10 - 9*100^k-1 subtract the increasing sequence of odd multiples of 100^k-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.

    Numerator:  0,851,000,000            Denominator:  0,161,000,000
 

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

    Numerator:  0,851,000,000            Denominator:  0,161,000,000
                 ...                                    ...
               -0,145,000,000                          0,173,000,000

Step 4:  Add Back

    Numerator: -1,450,000,000            Denominator:  0,171,900,000
                 ...                                    ...
                0,089,900,000                          0,170,100,000

Step 5: Subtract

    Numerator:  0,899,000,000            Denominator:  0,170,210,000
                 ...                                    ...
               -0,122,560,000                          0,170,330,000

Step 6: Add Back

    Numerator: -1,225,600,000            Denominator:  0,170,319,000
                 ...                                    ...
                0,136,896,000                          0,170,303,000

Step 7: Subtract

    Numerator:  1,368,960,000            Denominator:  0,170,304,100
                 ...                                    ...
               -0,163,784,100                          0,170,305,900

Step 8: Add Back

    Numerator: -1,637,841,000            Denominator:   0,170,305,790
                 ...                                     ...
                0,065,216,000                           0,170,305,590

Step 9: Subtract

    Numerator:  0,651,600,000            Denominator:   0,170,305,601
                0,481,854,399                           0,170,305,603
                0,311,548,796                           0,170,305,605
                0,141,243,191                           0,170,305,607
               -0,029,062,416                           0,170,305,609

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 10⁸ from the numerator until a negative result is obtained. Remember that the ENIAC always increments the denominator by 2 in the pth digit..

    Numerator:  0,000,000,002            Denominator:  0,100,000,000
               -0,099,999,998                          0,300,000,000

Step 2: Left shift the numerator and subtract 11*10⁷ from the denominator. Add back decreasing odd multiples of 10⁷ to the numerator until a positive result is obtained.

    Numerator: -0,999,999,980            Denominator:  0,190,000,000
                 ...                                    ...
                0,000,000,020                         -0,010,000,000

Step 3: Left shift the numerator and add 11*10⁶ to the denominator. Subtract increasing odd multiples of 10⁶ from the numerator until a negative result is obtained.

    Numerator:  0,000,000,200            Denominator: -0,001,000,000
               -0,000,999,800                          0,003,000,000

Step 4: Left shift the numerator and subtract 11*10⁵ from the denominator. Add back decreasing odd multiples of 10⁵ to the numerator until a positive result is obtained.

    Numerator: -0,009,998,000            Denominator:  0,001,900,000
                 ...                                    ...
                0,000,002,000                         -0,000,100,000

Step 5: Left shift the numerator and add 11*10⁴ to the denominator. Subtract increasing odd multiples of 10⁴ from the numerator until a negative result is obtained.

    Numerator:  0,000,020,000            Denominator:  0,000,010,000
                 ...                                    ...
               -0,000,020,000                          0,000,050,000

Step 6: Left shift the numerator and subtract 11*10³ from the denominator. Add back decreasing odd multiples of 10³ to the numerator until a positive result is obtained.

    Numerator: -0,000,200,000            Denominator:  0,000,039,000
                 ...                                    ...
                0,000,004,000                          0,000,027,000

Step 7: Left shift the numerator and add 11*10² to the denominator. Subtract increasing odd multiples of 10² from the numerator until a negative result is obtained.

    Numerator:  0,000,040,000            Denominator:  0,000,028,100
                 ...                                    ...
               -0,000,016,400                          0,000,028,500

Step 8: Left shift the numerator and subtract 11*10¹ from the denominator. Add back decreasing odd multiples of 10¹ to the numerator until a positive result is obtained.

    Numerator: -0,000,164,000            Denominator:  0,000,028,390
                 ...                                    ...
                0,000,006,040                          0,000,028,270

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.

    Numerator:  0,000,060,400            Denominator:  0,000,028,281
                0,000,032,119                          0,000,028,283
                0,000,003,836                          0,000,028,285
               -0,000,024,449                          0,000,028,287

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.

Additional Links

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

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