The Museum of HP Calculators

How The Friden Extracted Square Roots

It's Basically What You Learned In School

The reader will probably (vaguely) remember being taught to extract square roots in school by a method that looked a lot like "long division". At each iteration your were probably told to "find some next digit d for which ("the root so far" * 20+d) multiplied by d could be subtracted from the remainder. The Friden's square root extraction was based on essentially the same "long division" algorithm but unlike poor human calculators, the Friden could extract the root of a 10 digit number in an amazing 9 seconds.

Adjusted For A Machine

Since a calculating machine would be hard pressed to deal with an algorithm with involved "finding some d such that...", it used the odd integer series in which the square of a number n can be computed by the sum of the odd integers from 1 to 2n-1 i.e.:

1^2 = 1
2^2 = 1 + 3
3^2 = 1 + 3 + 5
4^2 = 1 + 3 + 5 + 7 
n^2 = 1 + 3 + ... + (2n-1)

Here's a picture of how this series works:

1^2  = 1

2^2  = 1 3
       3 3

3^2  = 1 3 5
       3 3 5
       5 5 5

4^2  = 1 3 5 7
       3 3 5 7
       5 5 5 7
       7 7 7 7

and so on... Each squared number is the previous square with one more layer which is always two more than the one before it.

To make the following algorithm work well on a calculating machine, Friden used the same series multiplied by 5:

5*(1^2) = 5*(1) = 5
5*(2^2) = 5*(1 + 3) = 5 + 15
5*(3^2) = 5*(1 + 3 + 5) = 5 + 15 + 25
5*(4^2) = 5*(1 + 3 + 5 + 7) = 5 + 15 + 25 + 35
5*(n^2) = 5*(1 + 3 + ... + (2n-1)) = 5 + 15 + ... + (10n-5)

This was more efficient for the machine because it turned multiplications by 20 into multiplications by 100 which can be done by shifting the carriage.

The above is all you need to start brute-forcing square roots by subtracting 1, 3, ... but that would take a very long time for large numbers. Thus you want to proceed from left to right as you did in school.

Begin by assuming we have already found the square root of some of the leading digits of the number n. Call this "root so far" s. (At the first step set s to zero.)

If we square s and subtract it from the original number n, we are left with some remainder r. (i.e. r = n-s^2)

So given an s (root so far), we need to find the next digit d. Appending the next digit would cause a change in the remainder which could be expressed (scaled by 5) as:

5[r1-r2] = 5[n-(10s)^2 - (n-(10s+d)^2)]
         = 5[-100s^2 + 100s^2 + 20sd + d^2]
         = 5[20sd+d^2]
         = 100sd + 5d^2

Note that this is also the sum of a (scaled by 5) odd digits series:

100s+5 + 100s+15 ... + 100s+(10d-5)

(For example for d=3 we have 100s*3+5*9 = 100s+5 + 100s+15 + 100s+25)

Thus the calculator could compute d by successively subtracting 100s+5, 100s+15 until a negative number would result.

Example: Square Root of 625

To take the square root of 625, the calculator would multiply by 5 to yield:

Then it would start subtracting 100s+5 100s+15... from the leftmost digits: (s started at 0)

3125
 500-
1500-   : 2 subtractions so first digit is 2 (so s is now 2)
leaving 1125

Then it subtracted 100s+5, 100s+15... (s = 2)

1125
 205-
 215-
 225-
 235-
 245- : 5 subtractions (so d is 5 which is appended to s yielding 25)
        leaving 0

So the root of 625 is 25.

Decimal Positions

The above example uses integers but the algorithm works just as well for fractional numbers and roots. It does require some care with the decimal points however, since the roots of 25 and 2500 have the same digits as do 250 and 25000, but the digits in the square roots of 25 and 250 are different.

Example: Square Roots of 25, and 2500

With 25 and 2500 you start with:

12500 
  500-
 1500-
 2500-
 3500-
 4500- : s is 5  Placing the decimal yields 5 or 50 respectively.

Example: Square Roots of 250 and 25000

But with 250 or 25000 you start with:

1250
 500- : d is 1, s is now 1

750
105-
115-
125-
135-
145- d is 5, s is now 15

12500
 1505-
 1515-
 1525-
 1535-
 1545-
 1555-
 1565-
 1575- : d is 8, s is now 158
 
18000
15805- : d is 1, s is now 1581

219500
158105- : d is 1, s is now 15811

6139500
1581105-
1581115-
1581125- : d is 3, s is now 158113

And so on... Placing the decimal in the result yields 15.8113 for 250 or 158.113 for 25000. The bottom row of keys on the Friden keyboard indicated the decimal position in the number and started the square root process.

Further Refinement: Computing The Next S Directly

Notice an interesting property of the terms being subtracted:

Count  Term:       Term:
       Odd Digits  Scaled By    
       Form        Five Form
1      01          05
2      03          15
3      05          25
4      07          35
5      09          45
6      11          55
7      13          65
8      15          75
9      17          85
10     19          95

In the scaled by 5 case, if the 5 in the term is cleared, the digit left in the term is the count minus 1. This was very handy because, instead of doing the shift/add on each iteration to build the new s from the old s and d, the calculator could produce the new s' directly by simply subtracting until the negative number appeared (an overdraft) and then adding that last term back into the remainder.

It then kept this last term (which is one beyond the last term that could be subtracted and thus contained the correct count) and cleared the 5. Since it was much easier for the calculator to detect an actual overdraft than to detect that an overdraft would occur, this algorithm was more efficient all around.

Example: Square Root of 191844 Friden-style

For example, to extract the square root of 191844, start by multiplying by 5:

959220
 50000- : Now staring with s=0, subtract 05, 15...
150000-
250000-
350000-
450000- : Overdraft so add this last term (450000) back.  Clear the 5 keeping
          400000 as the root so far.  

          Now start adding 05, 15 to the term (shifted one place to the right)

1592200
 405000- : s=4, subtract s05, s15...
 415000-
 425000-
 435000- : Overdraft so add this term (435000) back.  Clear the 5 keeping
           430000 as the root so far.  Add 05, 15 in the next place to
           the right.

3472000
 430500- : s=43, subtract s05, s15...
 431500-
 432500-
 433500-
 434500-
 435500-
 436500-
 437500- : equals 0 but no overdraft so continue
 438500- : Overdraft so add this term back (leaving 0.)  Clear the 5.

Since the result is 0, the root is 438000 (438.000) Because of the scaled-by-five algorithm, no adding of d's to s' was required. (The Friden would continue attempting to subtract until it ran out of digits, but we'll stop here since we know we're done.)

Back to early models contents
Back to the Friden SRW