This reminds me that the rounded square root of an integer can be derived using only a truncating square root algorithm, and without conditionals or guess-then-test. That is, t := sqrtFloor(4n). answer := floor(t/2) + (t mod 2) If the calculations are performed with arbitrary precision integers, rounding is always correct. On 6/10/18 18:55 , Lucas, Stephen K - lucassk wrote:
The Friden square root algorithm (the calculator was released in 1965) is a thing of beauty, and completely different from square root algorithms that are more common these days. The starting point is the sum of odd integers is successive squares, but it is far more sophisticated. Knowing that if 1+3+5+..+k=n^2 then 1+3+5+…+(10k_9)=100n^2, you can use a shift and subtract algorithm to find digits very quickly. It is very closely related to the ENIAC square root algorithm, and surprisingly, turns out to be equivalent to an algorithm Frazer Jarvis published in 2005, but with a completely different proof.
It turns out that the same trick works in any base, not just ten, and is particularly nice base two. And is not the same as the digit by digit approach, even digit by digit, that we were taught in high school back in the day.