Vintage work crew photos

[mklotz]

One thing computers do really well is iterating a simple arithmetic equation very fast. I don't know how it's done today but on at least one of the early breadboard computers I encountered capitalized on this by computing roots using Heron's method.

Heron's method for finding square roots is elegant and requires nothing more than the four basic arithmetic operations.

If x is less than the square root of N then N/x is greater than the square root so the average of the two will be closer to the true root. This leads to the iterative equation...

x[n+1] = (x[n] + N / x[n]) / 2

With even a poor starting guess of x[1] this will converge to the square root in a few iterations.

An example will demonstrate. Let's find the square root of 6 (for reference, my calculator says 2.44949). Six is between 4 (2 squared) and 9 (3 squared) so a reasonable guess for x1 might be 2.5. Then

x2 = (2.5 + 6/2.5)/2 = 2.45 (squared = 6.00250)

Very close but let's do one more iteration...

x3 = (2.45 + 6/2.45)/2 = 2.44949 (squared = 6.00000026)

which would be good enough for most purposes.

I can hear you saying, "Yeah, but you picked an initial guess that was very close to the actual value!" A valid objection so let's try it with an initial guess that's downright silly, 7. Remember, 7 squared is 49, and that's far enough from 6 that even a schoolkid would know it's not a good choice. In addition, the square root of a number can never be greater than the number so, since 7 is greater than 6, choosing it as a first guess is particularly dumb.

x2 = (7 + 6/7)/2 = 3.9286 (squared = 15.4339)

x3 = (3.9286 +6/3.9286)/2 = 2.7279 (squared = 7.4414)

x4 = (2.7279 + 6/2.7279)/2 = 2.4637 (squared = 6.0698)

x5 = (2.4637 + 6/2.4637)/2 = 2.4495 (squared = 6.00005)

close enough for the work I do. So, even with a laughable initial guess we got five significant figures in only four iterations. Clearly, one doesn't need to be a genius mathematician to make useful guesses.

[jdurand]

One thing computers do really well is iterating a simple arithmetic equation very fast. I don't know how it's done today but on at least one of the early breadboard computers I encountered capitalized on this by computing roots using Heron's method.

Heron's method for finding square roots is elegant and requires nothing more than the four basic arithmetic operations.

If x is less than the square root of N then N/x is greater than the square root so the average of the two will be closer to the true root. This leads to the iterative equation...

x[n+1] = (x[n] + N / x[n]) / 2

With even a poor starting guess of x[1] this will converge to the square root in a few iterations.

An example will demonstrate. Let's find the square root of 6 (for reference, my calculator says 2.44949). Six is between 4 (2 squared) and 9 (3 squared) so a reasonable guess for x1 might be 2.5. Then

x2 = (2.5 + 6/2.5)/2 = 2.45 (squared = 6.00250)

Very close but let's do one more iteration...

x3 = (2.45 + 6/2.45)/2 = 2.44949 (squared = 6.00000026)

which would be good enough for most purposes.

I can hear you saying, "Yeah, but you picked an initial guess that was very close to the actual value!" A valid objection so let's try it with an initial guess that's downright silly, 7. Remember, 7 squared is 49, and that's far enough from 6 that even a schoolkid would know it's not a good choice. In addition, the square root of a number can never be greater than the number so, since 7 is greater than 6, choosing it as a first guess is particularly dumb.

x2 = (7 + 6/7)/2 = 3.9286 (squared = 15.4339)

x3 = (3.9286 +6/3.9286)/2 = 2.7279 (squared = 7.4414)

x4 = (2.7279 + 6/2.7279)/2 = 2.4637 (squared = 6.0698)

x5 = (2.4637 + 6/2.4637)/2 = 2.4495 (squared = 6.00005)

close enough for the work I do. So, even with a laughable initial guess we got five significant figures in only four iterations. Clearly, one doesn't need to be a genius mathematician to make useful guesses.

That doesn't even require dividing by 2, that's just shift right by 1 bit so single cycle or free depending on your machine architecture.