Talk:Square root algorithms

Reciprocal of the square root

This piece of code is a composite of a quirky square root starting estimate and Newton's method iterations. Newton's method is covered elsewhere; there's a section on Rough estimate already - the estimation code should go there. Also, I first saw this trick in Burroughs B6700 system intrinsics about 1979, and it predated my tenure there, so it's been around a long time. That's well before the drafting of IEEE 754 in 1985. Since the trick is based on linear approximation of an arc seqment of x² which in the end, is how all estimates must be made, I'm certain that the method has been reinvented a number of times.

There're numerous issues with this code:

• the result of type punning via pointer dereferencing in C/C++ is undefined
• the result of bit-twiddling floating point numbers, bypassing the API, is undefined
• we don't know whether values like zero, infinity and unnormalized floating point numbers, and big/little endian formats are correctly handled.
• It definitely won't work on architectures like Unisys mainframes which are 48/96 bit, or 64-bit IEEE floats. Restructuring the expression to make it work in those cases is non-trivial.
• since I can readily find, by testing incremental offsets from the original, a constant which reduces the maximum error, the original constant isn't optimal, probably resulting from trial and error. How does one verify something that's basically a plausible random number? That it works for a range of typical values is cold comfort. (Because its only use is as an estimate, maybe we don't actually care that enumerable cases aren't handled(?)... they'll just converge slowly.)
• because it requires a multiply to get back a square root, on architectures without fast multiply, it won't be such a quick estimate relative to others (if multiply and divide are roughly comparable, it'll be no faster than a random seed plus a Newton iteration).

I think we should include at least an outline of the derivation of the estimate expression, thus: a normalized floating point number is basically some power of the base multiplied by 1+k, where 0 <= k < 1. The '1' is not represented in the mantissa, but is implicit. The square root of a number around 1, i.e. 1+k, is (as a linear approximation) 1+k/2. Shifting the fp number represented as an integer down by 1 effectively divides k by 2, since the '1' is not represented. Subtracting that from a constant fixes up the 'smeared' mantissa and exponent, and leaves the sign bit flipped, so the result is an estimate of the reciprocal square root, which requires a multiply to re-vert back to the square root. It's just a quick way of guessing that gives you 1+ digits of precision, not an algorithm.

That cryptic constant is actually a composite of three bitfields, and twiddling it requires some understanding of what those fields are. It would be clearer, but a few more operations, to do that line as a pair of bitfield extract/inserts. But we're saving divides in the subsequent iterations, so the extra 1-cycle operations are a wash.

Continued fraction expansion

This section is the longest in the article, and most laden with awkward symbolism. It might in large part, be the reason for the "Too Technical" maintenance tag. I do a lot of my work on a cell phone or tablet, and it's gobbledegook. I first question whether the section belongs in the presentation at all - any number, even irrational and transcendental ones (including the square root of any number), can be represented as a Continued fraction, and there's a lead article on that topic, as well as Generalized continued fraction and Periodic continued fraction. There's nothing unique about the procedure with respect to the square root of a number. It's sometimes convenient, for mathematical foundations as well as estimating, to have a continued fraction representation of frequently used numbers like √2, √10, $e$, $\pi$, $\phi$. It's tedious to work out one of these; unless there's some motive besides obtaining a final numerical approximation, we do it by looking up the expansion in a table, and it's usually for some mathematics-related number like the above enumerated ones. The worked eample has a better place in one of the aforementioned articles. If we're going to give an example here, it's more useful to use a number like √2. I'd like to see the section merged into one of the other articles, and replaced with a much shorter useful presentation, rather than a derivation-based one.Sbalfour (talk) 18:27, 30 November 2019 (UTC)

I'm moving all the text associated with the √114 to Periodic continued fraction, for a number of reasons: 1) it's an unwieldy large example; 2) it's not actually very useful, not as useful as say a similar example for √3; 3) it's more about how-to (i.e. how to expand the fraction and find the repetend) rather than using a fraction to compute a value; 4) such extreme precision as 7 denominators will almost never in practice be done; 5) all those radicals are intimidating to much of an amateur non-mathematical audience. I note that this example was once before deleted from the article, and for related reasons. Expanding a continued fraction is mostly the province of mathematicians; using one, i.e. to compute a value, is actually rather straight forward. But neither reducing a continued fraction to a rational fraction, nor computing an actual value from it is covered in that text. Finally, by my so doing, we're not actually losing any information from the encyclopedia - it's a matter of locating the example in the most generally applicable article. Sbalfour (talk) 18:03, 13 December 2019 (UTC)

There are four different types of notation in this section:

${\sqrt {S}}\Rightarrow 1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2+...}}}}}}\equiv 1+{\frac {1|}{|2}}+{\frac {1|}{|2}}+{\frac {1|}{|2}}+\cdots \equiv [1;2,2,2...]\equiv [1;{\overline {2}}]$

But then, we make the incredible leap $[1;2,2,2]=17/12$. I gave the problem to a neighbor's son who's a math whiz in high school, and he was unable to demonstrate to me how to compute 17/12 from the given expression. He didn't recognize any of the 4 expressions for continued fractions, and was unable to correctly compute anything. The mathematical brevity here is inscrutable. I didn't get continued fractions until a second course in calculus, as a college math major. A non-math major will never see any of this notation. Only applied mathematicians use that kind of notation (and they don't source wikipedia for it), and only for computing reference continued fractions. The rest of us look up the fraction, and use it to compute with. And how do you do that? Hmmmm.... Sbalfour (talk) 19:08, 13 December 2019 (UTC)

I'm going to move all the dense mathematical formalisms into a mathematical sidebar or footnote; that'll shrink the section substantially. Then, add at least one sequence showing the progressive reduction of the continued fraction to a rational (numerical) fraction, and finally, computation of the value of the root from it. That should leave the section accessible at the high school level. Sbalfour (talk) 19:32, 13 December 2019 (UTC)

Pell's equation?

Pell's equation is a Diophantine equation, meaning it has integer coefficients, and requires an integer solution. So $S$ in this case must be an integer (not zero and not a perfect square). Most of the time, we're not computing square roots of integers, because we can look them up. But let's just suppose we want the square root of 1361, First we come up against: Find positive integers p1 and q1... This is the hard part; It can be done either by guessing, or by using fairly sophisticated techniques. Guess?? This isn't the same kind of guessing we do in the Initial estimate section, because a bad guess there just means more work. No, a bad guess here is utterly worthless. There's no guessable solution to p² - 1361 · q²=1. (Yes, 1361 is prime, and has a few other properties that make it a particularly irascible number, but in the end, it's just an arbitrary number). The standard method of solving Diophantine equations is by continued fractions (one must find the period of the repetend); the problem is that the repetend may be long, extremely long, and it can be that long for seemingly innocuous choices of $S$. We don't elaborate that in the section.

Pell's equation is a recursive relationship that allows one to generate infinitely many solutions after finding one. It's finding one that's the hump, as it is with any Diophantine equation. And in the usual case, while there may be infinitely many solutions, none of them are small, small enough to make trial and error a useable approach. I don't think this section ought to be in the article, unless we greatly expand it to demonstrate how actually to solve the equation. Solving a Diophantine equation is a LOT more work than an arithmetic computation of square root. Sbalfour (talk) 22:09, 14 December 2019 (UTC)

I agree. JRSpriggs (talk) 09:29, 15 December 2019 (UTC)

What's the programming language used here?

Which languages have been used to desribe the algorothms?

2003:E0:5F1B:749A:DC42:9B8D:E639:24FC (talk) 22:09, 7 January 2020 (UTC)

In general, at Wikipedia we try to avoid using any specific programming language in the articles. If an example is necessary, it is generally done in pseudocode.

Obviously, articles about a particular language are an exception.

In this article, it appears that the three examples are in C (programming language). But we do not guarantee that they will work as written. JRSpriggs (talk) 00:38, 8 January 2020 (UTC)

"nearest perfect square" in Bakhshali method?

The example in the Bakhshali method has me published. The initial guess is said to be "x₀² be the initial approximation to S." The example uses $S=125348$, and chooses $x_{0}=600$. How can that be? $600^{2}=360000$ and there are many perfect squares closer to S, like 400 or 350.

How is the initial guess really meant to be chosen? Unfortunately, the material here (in particular, this example) isn't well-referenced enough to explain how 600 meets the criteria given in the article. -- Mikeblas (talk) 21:06, 26 February 2020 (UTC)

The method does not require the initial guess to be the closest perfect square. This was only used to obtain a bound on the error. The 600 value is obtained in the above section on scalar estimates and was used as the initial guess in the previous example. --Bill Cherowitzo (talk) 23:27, 26 February 2020 (UTC)