The Museum of HP CalculatorsThe 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 you 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.
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.:
12 = 1 22 = 1 + 3 32 = 1 + 3 + 5 42 = 1 + 3 + 5 + 7 n2 = 1 + 3 + ... + (2n-1)
Here's a picture of how this series works:
12 = 1
22 = 1 3
3 3
32 = 1 3 5
3 3 5
5 5 5
42 = 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×(12) = 5×(1) = 5 5×(22) = 5×(1 + 3) = 5 + 15 5×(32) = 5×(1 + 3 + 5) = 5 + 15 + 25 5×(42) = 5×(1 + 3 + 5 + 7) = 5 + 15 + 25 + 35 5×(n2) = 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-s2)
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[-100s2 + 100s2 + 20sd + d2]
= 5[20sd+d2]
= 100sd + 5d2
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.
To take the square root of 625, the calculator would multiply by 5 to yield: 3125. Then it would start subtracting 100s+5 100s+15... from the leftmost digits: (s started at 0)
3125
500-
1500- : 2 subtractions
leaving 1125
so first digit is 2 (s is set to 2)
Then it subtracted 100s+5, 100s+15... (s = 2)
1125
205-
215-
225-
235-
245- : 5 subtractions
leaving 0
(so d is 5 which is appended to s yielding 25)
So, the root of 625 is 25.
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.
12500
500-
1500-
2500-
3500-
4500- : s is 5
Placing the decimal yields 5 or 50 respectively.
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.
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.
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