Talk:Methods of computing square roots/Archive 1

Archive 1

Ibn al-Banna

• Surprising that the user user:pgk removed the section on Ibn al-Banna method of computing square roots. Its good if a reason is also provided for the edit done on the page. (LATER: the user has emailed me giving the reason for his edit: bad formatting)

Actually, this method appears already in the article, under the section "Babylonian Method". Do you have any reference that it is Ibn al-Banna who invented the method? This seems questionable. Also, notice that the first time you edited the article, a large portion of it was deleted - See this diff. My guess is that you have used an external text editing program, and something went bad with the copying back and forth. You should also use edit summaries when editing articles. -- Meni Rosenfeld (talk) 13:50, 21 June 2006 (UTC)

• I agree that something definitely went wrong while editing the article first time. As for the reference, it is mentioned in the book 'A History of Algorithms: from the Pebble to the Microchip' by Barbin and Borowczyk. Maybe we should change the heading title of the Babylonian Method to the Ibn-Al Banna Method? Chem1

No, "Babylonian method" is a very well known name for this, and Ibn-Al Banna came much, much later. You might want to add a reference to him in the Babylonian section (and remove the redundant information). I am wondering why he is notable for discovering something that had already been discovered. Could you provide a quote from your source? - Rainwarrior 15:38, 21 June 2006 (UTC)

I've had a look in said book at Amazon reader, and what you are probably referring to is from page 202 (in the edition I looked at), which says "The method was described in the 13th century by the mathematician Ibn al-Banna". But the method mentioned is not the x := (x + r/x) / 2 method, which is clearly described in the text as being known much before al-Banna (for example, it was known to Theon of Alexandria around 370 AD). So, please remove the irrelevant content from the Ibn al-Banna article, and be more careful when making edits in the future. -- Meni Rosenfeld (talk) 19:19, 21 June 2006 (UTC)

• I have removed the mentioning of this method from the Ibn al-Banna article. Also, I have removed the section from the Methods of computing square roots article and have added a line to the Babylonian section about al-Banna describing a similar method.

I would say based on the descriptions given that it is the same method, not merely similar. But, this isn't important. Do you know any more about Ibn al-Banna? His biography page has very little information so far... - Rainwarrior 01:23, 22 June 2006 (UTC)

• I have found some stuff on the Internet here and here. Is it OK to mention this?

Yes, it is okay to add this information to the Ibn al-Banna article, as long as you don't copy it word for word (otherwise it's a copyright violation) and provide links to these sources, so that the information can be checked. About al-Banna's method: It is difficult to say for sure, according to the text in the book, what exactly is the algorithm - It gives an equation which should be solved, but doesn't specify the way to solve it - but my impression is that this is not the Babylonian method, but rather something that is reminiscent of the long division-like method. -- Meni Rosenfeld (talk) 14:23, 22 June 2006 (UTC)

I am currently trying to understand the method given in the book and attributed to al-Banna. Hopefully I will come up with a 'layman' explanation for this method.

al-Banna's method seems to be the same as the "long-division-like algorithm" already described in this article, not the 0.5(x+r/x) one. I think, in the course of editing, his section got moved around or otherwise mis-associated. --Jay (Histrion) (talk • contribs) 20:59, 22 June 2006 (UTC)

• Have a look here. This is the algorithm for the method used by al-Banna. NOTE: this link opens up search results in the Amazon Reader. Click Next at the bottom of the page and click link # 12 on the resulting page. Pages 206-207 describe in detail what the 'root, not a root' method is. Cheers!

Duplication?

A lot of the algorithms in this article are variations on each other; for instance, the N + d/2N method is just the first iteration of Newton's algorithm; and the section listed under "Finding square roots using mental arithmetic" is really just the long-division-like algorithm without writing it out in a long division format. Can we either remove some of the redundancy, or, perhaps more usefully, tie the related algorithms together better? --Jay (Histrion) (talk • contribs) 16:27, 22 June 2006 (UTC)

i agree, at least the section under "Quadratic equation method" can be deleted completely, because it's explanation is way to complicated and the result basically boils down to the babylonian formula. It's obvious if you look closely at the given formula sqrt(r)=N+d/(N+sqrt(r)), which will be iterated to approximate sqrt(r). N is an initial guess (the same as x0 in the babylonian method) and d=r-N^2. if you substitute sqrt(r) with x (just another name) and N with x (since N is an approximation of x), the formula reads x=x+(r-x^2)/(x+x), which reduces to x=(x+r/x)/2, the babylonian formula. Besides the formula - due to the usage of constant N & d - converges slower. If nobody objects, i'll remove the section Catskineater 19:44, 1 September 2006 (UTC)

I think you could delete any or all of this article, except the Babylonian method which is the only method worth using. In any case, the article is much too long. JRSpriggs 05:32, 2 September 2006 (UTC)

Spring cleaning!

Yes, the article has been in a bad state for too long. I am currently in the middle of some major changes to the article, mostly trimming down some irrelevant information. I hope to be finished by tomorrow. Feedback welcome. -- Meni Rosenfeld (talk) 15:42, 8 September 2006 (UTC)

The article seems to be using "r" for the number whose square root is desired. Since "root" begins with "r", this is counter-intuitive. I suggest we pick another symbol for that number! And perhaps we could use "r" for the root itself? JRSpriggs 07:22, 9 September 2006 (UTC)

I'm not sure this is necessary, but I won't object to it. Which letter do you have in mind? As for using "r" for the root, I'm rather against it - It will be clearer if we explicitly write ${\sqrt {number}}$ every time. -- Meni Rosenfeld (talk) 08:53, 9 September 2006 (UTC)

How about using S for the square whose root is desired? Do we need a consistent convention for the iterative approximations to the root? JRSpriggs 09:52, 10 September 2006 (UTC)

Fine with me. The article currently uses x_n for the iterations wherever it is applicable. -- Meni Rosenfeld (talk) 10:55, 10 September 2006 (UTC)

Continued fractions

JRSpriggs, perhaps you can explain:

1. What made you modify the equation for $a_{n+1}$? It is now more cumbersome and less correct, since what we know is $a_{0}$,not ${\sqrt {S}}$.
2. What were you trying to accomplish with the example? Is it to demonstrate why the method works? In this case, it would be better to provide an actual proof. Is it to show how to use the method? In this case, don't you think it should be kept as simple as possible - sticking to the actual method given, which doesn't use any square roots except for intsqrt at the very beginning?

-- Meni Rosenfeld (talk) 18:07, 5 December 2006 (UTC)

I could not understand the method given (before my example) until I ignored it and worked out the continued fractions for several square roots from scratch. The given method is completely un-intuitive and no hint of justification or proof is given. "Simplicity" is less important than allowing people to understand what the method is and why it works. One does not normally remember exactly most of the mathematical formulas or facts which one studies. One just remembers the general approach and then figures it out again as needed. That would be impossible for the given method without an example, such as mine, or some other kind of proof. If you compare the formula which I enhanced with my example, you will see that the floor (integer part) of the expression containing the square root is actually what one uses in the example. The fact that one can replace the square root with its floor within that expression is very useful, but not immediately obvious. So the intermediate expression which I added is necessary to make it clear. JRSpriggs 05:04, 6 December 2006 (UTC)

Again, when you say you didn't understand, did you not understand how to use the method, or why it works? In the former case, the method was really as simple as it gets, I don't know what else to say. In the latter case, perhaps an explanation of how to use the method simply and efficiently should be separated from an explanation of why it works and how to perform the calculation without having the formulae readily available? -- Meni Rosenfeld (talk) 07:07, 6 December 2006 (UTC)

Digit by digit method is not fully explained.

As explained in the current article, it doesn't provide enough details of the method so one could apply it.

You could find a more detailed explanation: http://www.mathpath.org/Algor/squareroot/algor.square.root.htm —Preceding unsigned comment added by Muttley.meen (talk • contribs)

Care to explain which detail was missing? Often, providing excessive details makes it harder to apply the method. That's what examples are for. -- Meni Rosenfeld (talk) 11:29, 16 September 2006 (UTC)

I hope the edit which I did on 15 Sept 2006 made it clearer. Is there still a problem? JRSpriggs 03:09, 18 September 2006 (UTC)

Sory for the late reply. Now looks better. As for the example, yes, most of the time is better but the definition of the algorithm is also needed. -- Muttley.meen (talk)

I just found this page. I read of the DUPLEX METHOD of finding the square root in a book on Vedic mathematics. It is a precise algorithm. Geniuses can do it mentally. It is written like a long division problem with a subtraction of the duplex from the dividend prior to subtracting the product of the root digit times the divisor (double the first digit-groups square root). More later. A cube root algorithm is also given! Vedic Mathematics, by Jagadguru Swami Sri Bharati Krishna Tirthaji Maharaja Sankaracarya (1884-1960), 1965, 1978. Larry R. Holmgren 06:02, 26 February 2007 (UTC)

The author earned these titles and accolades. He traveled from India to New York to take seven Masters Degrees by examination. He passed with highest honors.

I shall need help in setting up the long division bracket for examples of roots of perfect squares and irrational roots. Larry R. Holmgren 07:27, 26 February 2007 (UTC)

I added duplex examples and a 5-digit root example. Would another example be of value? The square root of a non-perfect square or of Pi, in two treatments? Larry R. Holmgren 03:55, 27 February 2007 (UTC)

To Larry: There is no reason to put "~~~~" into your edit summaries. Please use either "·" or "×" to indicate multiplication rather than "x". Please use "²" to indicate a square rather than "*2" (or "**2" which would be more conventional). JRSpriggs 06:47, 27 February 2007 (UTC)

Credit for Quake3 InvSqrt() algorithm

Why did a someone with IP "69.181.250.222" (on December 21st, 2006 at 02:34) say that Greg Walsh created the InSqrt() algorithm from Quake3? Not only should this be cited, but from what I hear, no one knows who created it. Read that external link about the Quake3 algorithm to see what I mean. I think this either needs to be cited or removed. 65.110.239.80

Ok, to answer my own question, after the (main) Quake3 article (that is in the external links) was published, Greg Walsh contacted the author and owned up to creating that algorithm. I added the link to the follow up story in the external links section, but I still believe this fact needs to be cited. I don't know if this link then belongs in both the references or just the external links or both, so I would like someone else to make that decision with the information I have found. 65.110.239.80

Just make sure it is there. If you put it in the wrong section, someone will move it to the right one. JRSpriggs 13:19, 28 January 2007 (UTC)

Me again with a different IP. I added the link to the external links section. 129.186.16.56 21:07, 29 January 2007 (UTC)

It seems like the external links are 404ed. 66.59.156.141 13:57, 13 April 2007 (UTC)

I'd always thought John Carmack invented that inverse square root approximation. A good analysis of the algorithm can be found here: [1]. AlphaPyro 18:02, 17 May 2007 (UTC)

Citations of source code used?

Does anyone have the place where the different more complex snippets in this page were taken from? E.g. Mul/Div-Free Algorithm.

The "faster" mul/div-free algorithm is C.C.Woo's book "The Fundamental Operations in Bead Arithmetic", China Lace Co, Hong Kong, adapted to binary. See [2]. A google search for "integer square root algorithm" will turn up a lot of stuff. Martinwguy 09:16, 7 September 2007 (UTC)

Separate article for integer Square Root algorithms

Would a separate article be appropriate for integer square root algorithms? There seem to be many of them out there, all very different. Martinwguy 09:15, 7 September 2007 (UTC)

I think they are better placed here. -- Meni Rosenfeld (talk) 11:18, 7 September 2007 (UTC)

Pell's equation

In this section, it's stated that:

• In either case, ${\frac {p_{n}}{q_{n}}}$ is a rational approximation satisfying

$\left|{\frac {p_{n}}{q_{n}}}-{\sqrt {S}}\right|<{\frac {1}{q_{n}^{2}\cdot {\sqrt {S}}}}.$

In article Liouville number it's said that:

• In number theory, a Liouville number is a real number x with the property that, for any positive integer n, there exist integers p and q with q > 1 and such that

$0<\vert x-{\frac {p}{q}}\vert <{\frac {1}{q^{n}}}.$

I think it should be stated that ${\sqrt {S}}\,$ is not a Liouville number, because it satisfies that property for n = 2 but not for all n (does it fail for n = 3?). Albmont (talk) 18:29, 5 August 2008 (UTC)

Hmm, it doesn't have much to do with methods of computing square roots, so the article on square root seems a more natural notation. However, the fact that ${\sqrt {S}}$ is an algebraic number (which is a bit hidden in that article; perhaps that could be improved) and Liouville numbers cannot be algebraic implies that square roots are not Liouville numbers, so I'm not sure it should be mentioned at that article either.

The square root of 6 is 2.44949… so

$0<\left|{\sqrt {6}}-{\frac {5}{2}}\right|=0.05051<0.0625={\frac {1}{2^{4}}}.$

However, what is true is that there are only finitely many pairs (p, q) such that

$0<\left|{\sqrt {S}}-{\frac {p}{q}}\right|<{\frac {1}{q^{2}}}$

(the irrationality measure is 2). On the other hand, a Liouville number has infinitely many such pairs. -- Jitse Niesen (talk) 20:17, 5 August 2008 (UTC)#

"Inverse square root" eh?

Why does inverse square root redirect here? —Preceding unsigned comment added by 75.177.191.14 (talk • contribs)

Because of the section Methods of computing square roots#Iterative methods for reciprocal square roots. "Inverse square root" is the same as "reciprocal square root". JRSpriggs 10:45, 4 December 2006 (UTC)

whilest it is unstable surely if you just start from a very small number then it will always converge? (155.198.115.46 (talk) 16:25, 27 November 2008 (UTC))

If by small, you mean "close to zero", then yes it will converge, but very slowly. JRSpriggs (talk) 07:49, 28 November 2008 (UTC)

Finished, more or less

The one section I don't know what to make of is Approximations that depend on IEEE representation (the last one). It looks like a useful section; But it looks like it can be written better, and I don't have the knowledge to do it. If anyone with better understanding of IEEE can take a look at it, it would be great. Also, adding references would be good, though I don't know of any good sources. -- Meni Rosenfeld (talk) 14:45, 9 September 2006 (UTC)

I've been trying to find a source for it for a while to no avail. I understand IEEE but I'd have to take a close look at it to understand what's going on (it's kind of a reverse engineering problem). What we have now describes how to do it (maybe, I haven't been able to verify that it works), but not why it works. I think it's probably a valid technique, and is certainly of use to graphics programmers who may need a quick way to normalize a vector, but I haven't taken the time to look at it yet. - Rainwarrior 23:28, 9 September 2006 (UTC)

If you are referring to fastsqrt, it is better to motivate the discussion without referring to log2. The explanation about computing the biased exponent for the square root needs clarification, especially because the right-shifting of the LSB of the exponent into the MSB of the trailing significand is important when motivating why the resulting significand approximates that for sqrt(x). The basic idea is let x = 1.t*2^e, where e is the unbiased exponent and t is the trailing significand. If e is even, say, e = 2*p, then sqrt(x) = sqrt(1.t)*2^p. The number 1.t represents 1+t and sqrt(1+t) is approximately 1+t/2 (use first two terms of Taylor series). The biased exponent is odd, so the subtraction of 1 produces an even number and bit 23 is a zero. The right-shift takes trailing significand t[22]..t[0] and makes it 0t[22]...t[1], so the significand is (approximately) 1.0t which represents 1+t/2. If e is odd, say, e = 2*p+1, then sqrt(x) = sqrt(2(1.t))*2^p. The number 2(1.t) represents 2+2*t and sqrt(2+2*t) is approximately 3/2+t/2. The biased exponents is even, so the subtraction of 1 produces an odd number and bit 23 is a 1. The right-shift takes trailing significand t[22]...t[0] and makes it 1t[22]...t[1], so the significand is (approximately) 1.1t which represents 3/2+t/2. If instead you are referring to the inverse square root, the Wikipedia page for the inverse square root has a history of the algorithm that is more detailed than on the square root page (and the two pages are not quite in agreement).Daveeberly (talk) 06:15, 14 July 2010 (UTC)

About A two-variable iterative method

It is not clear where the pair of equations come from, although reverse engineering them is not too difficult. However, it is simple enough to show that a[n+1] = (3*S*a[n] - a[n]^3)/(2*S), which makes the algorithm equivalent to applying Newton's method to F(y) = 1/y^2 - 1/S (the a[i] are the iterates with a[0] = S).Daveeberly (talk) 06:15, 14 July 2010 (UTC)

Babylonian method

Repeat steps 2 and 3 until the desired accuracy is achieved

Let's say I want the iteration to stop when the relative (or absolute) error is below some required value. Is there an easy test I can perform?--Malcohol 13:36, 30 November 2007 (UTC)

The true root will lie between $x_{n}\!$ and ${\frac {S}{x_{n}}}$. So when their absolute difference is less than the required value, then $x_{n}\!$ (or better still $x_{n+1}\!$) is close enough. JRSpriggs 20:45, 30 November 2007 (UTC)

Convergence: The Babylonian method only converges for $S\geq 0$. For $S<0$ the series is chaotic, never converges, and is highly sensitive to both $S$ and $x_{0}$. If you guess $x_{0}<0$, the series will converge to the negative root $-{\sqrt {S}}$ [3]. Pulu (talk) 11:10, 8 March 2011 (UTC)

I modified the lead to make it clear that this article only deals with the principal square root of nonnegative real number. JRSpriggs (talk) 20:03, 8 March 2011 (UTC)

Last edits

In the hope of collaboration, the current version means nothing to laymen. Wikipedia is written for the general publix, not professionals. I believe the current explanation given is absolutely nonsensical to the common reader, and a much simpler explanation is easily possible. If I have confused one variable, that variable can be changed. The useful technical information (geometric mean vs arithmetic mean) is best nested into the prose, as most people will not understand what either is. - ʄɭoʏɗiaɲ ^τ _¢ 02:27, 8 August 2010 (UTC)

The established text contains this point:

2. Let x_n+1 be the average of x_n and S / x_n (using the arithmetic mean to approximate the geometric mean).

One large problem with that is the typography relating to the '/' which requires a fair bit of confidence to be interpreted as "divides". The following may be more accessible:

2. Let x_n+1 be the average of x_n and the result from dividing S by x_n (this uses the arithmetic mean to approximate the geometric mean).

Johnuniq (talk) 04:40, 8 August 2010 (UTC)

Regarding Floydian's remark about Wikipedia being written for the general public and not professionals, I do think one has to be a little careful about making quite such sweeping statements. For example Wikipedia quite properly has a very useful article on Lie groups but it's certainly not written for the general public. Realistically we have to expect that the target audience varies with the nature of the article. Computing square roots (by implication to arbitrary precision) strikes me as an essentially technical matter and in this case, beyond providing the customary lead designed to instruct the widest possible audience, one really isn't at pains to address the general public. The Square root article is a different matter but again we can overstate the case even there. FightingMac (talk) 04:13, 17 April 2011 (UTC)

Fast inverse square root attribution

The main article states "no conclusive proof of authorship exists", while this one attributes it without a doubt to Gary Tarolli. I'd be inclined to believe the main article, but either one or the other is definitely wrong, since they contradict each other. --Lohoris (talk) 12:23, 20 March 2012 (UTC)

The supporting references (for Tarolli) are external links to a website which does not appear to me to be a reliable source. So the information should probably be removed from this article. JRSpriggs (talk) 13:55, 20 March 2012 (UTC)

Vedic Mathematics Claims Need Much Better Sources

I see the article as a whole is already flagged for lacking reliable sources. The specific claim that the "Vedic mathematics" method described in the article is "ancient" is not backed up by a reliable source. Many claims like this are found in many articles on mathematical topics in Wikipedia, and all either need better sourcing or to be edited out. -- WeijiBaikeBianji (talk, how I edit) 03:37, 1 February 2013 (UTC)

I#m fine with removing it and/or moving it temporarily to the article's talk page (here) until sufficient sourcing is provided. Vedic math is unfortunately a POV prone subject with a lot of dubious claims from questionable sources, hence I suggest to remove it wherever it shows up without appropriate sourcing. That's the only way to discourage the POV warriors and to keep our articles in a proper state.--Kmhkmh (talk) 02:40, 4 February 2013 (UTC)

Complexity ?

I'm disappointed but almost even more surprised that the word "complexity" does not occur a single time on that page... On Computational_complexity_of_mathematical_operations it is written that the complexity of sqrt is that of multiplication, but that's IMO far from obvious. Some details here would have been nice. — MFH:Talk 19:34, 11 November 2012 (UTC)

I compare Methods of computing square roots#Iterative methods for reciprocal square roots with Division algorithm#Newton–Raphson division:

$x_{n+1}={\frac {x_{n}}{2}}\cdot (3-S\cdot x_{n}^{2})\,$

$X_{i+1}=X_{i}(2-DX_{i})\,$

and conclude that the complexity of extracting a square-root is only slightly greater than the complexity of division. But division is significantly harder than multiplication since it requires repeated multiplication of the order of the logarithm of the number of digits times. JRSpriggs (talk) 07:16, 12 November 2012 (UTC)

Not true, because when performing Newton-Raphson approximation, we do not have to use the final desired precision. Instead we can use just enough precision at each iteration, and since the precision roughly doubles on each iteration, the total time complexity is asymptotically bounded by that of the final iteration. Therefore all arithmetic operations that can be reduced by Newton-Raphson approximation to addition and multiplication will have the same time complexity as multiplication. Lim Wei Quan (talk) 06:50, 13 April 2013 (UTC)

To Lim Wei Quan: Thank you for pointing that out.

If we just look at the final stage of division, then it would be about three multiplications: (1) D by X_i, (2) X_i by (2 - D X_i), and (3) the reciprocal of the denominator by the numerator.

If we just look at the final stage of extracting a square-root, then it would be about four multiplications: (1) square x_n, (2) S by that square, (3) x_n/2 by (3 - S x_n^2), and (4) S by the square-root of its reciprocal.

Is that correct? JRSpriggs (talk) 19:57, 13 April 2013 (UTC)

Or would we be better off going back to the Babylonian method and just using the three multiplications of the final division of S by X_n? JRSpriggs (talk) 20:01, 13 April 2013 (UTC)

Regarding the section "Rough estimation"

With $S$ expressed in scientific notation as $S=a\times 10^{2n}$ where $1\leq a<100$, an estimate for ${\sqrt {S}}={\sqrt {a}}\times 10^{n}$ is ${\sqrt {S}}\approx 3\times 10^{n}$. The factor three is used because it approximates the geometric mean of the lowest and highest possible values with the given number of digits: ${\sqrt {{\sqrt {1}}\cdot {\sqrt {100}}}}={\sqrt[{4}]{100}}\approx 3$.

Expressed as a binary number, we have $S=a\times 10_{b}^{2n}$ where $1\leq a<100_{b}$, an estimate for ${\sqrt {S}}={\sqrt {a}}\times 2^{n}$ is ${\sqrt {S}}\approx 2^{n}$, since the geometric mean of the lowest and highest possible values with the given number of digits is ${\sqrt {{\sqrt {1}}\cdot {\sqrt {100_{b}}}}}={\sqrt[{4}]{4}}={\sqrt {2}}\approx 1.4$, which is close to one.

Slightly improved estimates can be obtained by expressing $S$ in normalized scientific notation as $S=a\times 10^{b}$ where $1\leq a<10$, and treating the cases $b=2n$ (even) and $b=2n+1$ (odd) differently. Then the estimates are

${\sqrt {S}}\approx {\begin{cases}2\cdot 10^{n}&{\text{if }}b=2n,\\6\cdot 10^{n}&{\text{if }}b=2n+1.\\\end{cases}}$

In the binary case we obtain

${\sqrt {S}}\approx {\begin{cases}1\cdot 2^{n}&{\text{if }}b=2n,\\2\cdot 2^{n}&{\text{if }}b=2n+1.\\\end{cases}}$

To discuss: Is it relevant in practice to treat the odd and even cases differently? Is the difference more relevant in the decimal case than for binary numbers? Isheden (talk) 14:13, 13 July 2013 (UTC)

Since $2\cdot 2^{n}=2^{n+1}$, I think your odd and even cases give the same end result as the binary estimate described in the article. Gandalf61 (talk) 15:22, 13 July 2013 (UTC)

In the example in the article, S has $17=2\cdot 8+1$ binary digits, so the odd case above yields $2\cdot 2^{8}=512$ if I'm not mistaken. It also seems reasonable that 512 should be a better initial guess than 256 if 600 is supposed to be better than 300. Isheden (talk) 15:59, 13 July 2013 (UTC)

b is one less than the number of digits. S has 17 binary digits because it lies between 2^16 and 2^17 so b = 16 and your method gives an estimate of 2^8 = 256, the same as the method in the article. The actual square root of S is about 354. Gandalf61 (talk) 16:19, 13 July 2013 (UTC)

OK, so then we actually have the even case which is equivalent to the formula above. Sorry for the confusion. Isheden (talk) 16:45, 13 July 2013 (UTC)

What I was actually mainly thinking of is the relevance of treating even and odd number of digits separately in the decimal case. For the example given, starting with 300 instead of 600 actually yields the answer to six significant figures in one iteration less. While this is surely just a coincidence, the question is if the extra effort is justified? Isheden (talk) 17:03, 13 July 2013 (UTC)

The idea of the rough estimate is to get an estimate of the square root of S using a method which is significantly easier than doing even merely one iteration of the Babylonian method. This means that the calculation can depend only on the order of magnitude of S, i.e. the number of digits to the left of the decimal point (when S≥1) or the number of zeroes immediately to the right of the decimal point (when S<1).

The estimates chosen were the ones which minimized the absolute value of the relative error (see Methods of computing square roots#Convergence) in the worst cases while preserving the simplicity of the method by limiting the estimate to less than one significant digit. If we used $1\cdot 10^{n}$ for the entire range $10^{2n-1}..10^{2n+1}$ instead of breaking it into two parts, then the relative error in the worst case would be 2.16 rather than 1.0 for the method with 2 or 6. This would require roughly one extra iteration of the Babylonian method to fix.

One should not expect the estimates used with binary to be the same as those used with decimal since the ranges being approximated are not the same ranges. JRSpriggs (talk) 08:26, 14 July 2013 (UTC)

I have reworked the decimal and binary cases, skipping the coarse estimate over the entire range based on your comment. Now it should be clear to the reader how the estimates are calculated and how they can be modified if required. By the way, why is the absolute value not contained in the relative error formula? Isheden (talk) 21:48, 14 July 2013 (UTC)

Your most recent changes have made the section more consistent and clear. Thank you.

I did not put an absolute value into my version of the definition because if I had, then x_n could not be expressed as a function of ε_n (unless we assume that x_n≥√S) which would interfere with deriving the formula for ε_n+1.

Also, $\vert {\frac {x_{n}}{\sqrt {S}}}-1\vert$ is the wrong way to equate over-estimates with under-estimates. Better would be $\vert \ln {\frac {x_{n}}{\sqrt {S}}}\vert$, but I did not want to use the transcendental function ln in an article targeted to a middle school audience. Notice that if y=S/x, then (y+(S/y))/2=(x+(S/x))/2. So, if x were an under-estimate of √S, then the equivalent over-estimate is S/x. If we replace that in the formula for relative error, we get $\varepsilon _{n}={\frac {\frac {S}{x_{n}}}{\sqrt {S}}}-1={\frac {\sqrt {S}}{x_{n}}}-1$. So we could use $\varepsilon _{n}=\max \left({\frac {x_{n}}{\sqrt {S}}},{\frac {\sqrt {S}}{x_{n}}}\right)-1$ except for the fact that this function is not invertible. JRSpriggs (talk) 08:54, 15 July 2013 (UTC)

Regarding Vedic Method

Is it just me, or are there others who think that the Vedic method can be bettered by some exposition. While the algorithmic side is substantial, I am at loss on why it even works. (Manoguru (talk) 03:56, 17 December 2013 (UTC))

I am of the opinion less would be better as it isn't very notable, it is just someones idea in a book. Dmcq (talk) 10:29, 17 December 2013 (UTC)

Your idea of notability is quite strange, since every algorithm is from someone's book or paper. I myself think that it is a remarkably easier algorithm for digit-by-digit calculation compared to the usual long division method. My elementary school math would have been much easier if this method had been taught. It exploits the fact that it is easier to multiply two single digit numbers than multiple digit numbers. Today I read up a few external links related to this method, and here is my summary of it. We proceed as with the digit-by-digit calculation by assuming that we want to express a number N as a square of the sum of n positive numbers as

$N=(a_{0}+a_{1}+\ldots +a_{n-1})^{2}.$

The right side of this expression can be expanded as

$N=a_{0}^{2}+2a_{0}\sum _{i=1}^{n-1}a_{i}+a_{1}^{2}+2a_{1}\sum _{i=2}^{n-1}a_{i}+\ldots +a_{n-1}^{2}.$

Define divisor as $q=2a_{0}$ and the duplex for a sequence of m numbers as

$d_{m}={\begin{cases}a_{\lceil m/2\rceil }^{2}+\sum _{i=1}^{\lfloor m/2\rfloor }2a_{i}a_{m-i}&{\mbox{for}}\;m\;{\mbox{odd}}\\\sum _{i=1}^{m/2}2a_{i}a_{m-i}&{\mbox{for}}\;m\;{\mbox{even}}.\\\end{cases}}$

Now the computation can proceed by recursively guessing the values of $a_{m}$ so as that

$X_{m}=X_{m-1}-qa_{m}-d_{m},$

such that $X_{m}\geq 0$ for all $1\leq m\leq n-1$, with initialization $X_{0}=N-a_{0}^{2}.$ Here the $X_{m}$ is the dividend. When $X_{m}=0$ the algorithm terminates and the sum of $a_{i}$s give the square root.(Manoguru (talk) 12:43, 18 December 2013 (UTC))

Notability is determined by third party sources, not by the source book or paper. Have a look at Vedic Mathematics (book), it seems to be mostly controversy about 'Vedic' and people pushing it as that and the use in schools has been under the impression it helps nationalism rather than anything to do with its merits as maths. It doesn't have much in the way of notability as maths. Dmcq (talk) 15:00, 18 December 2013 (UTC)

I agree with your sentiments. I too think that the title of Vedic is a misnomer and it is best to label the method simply as the duplex method.(Manoguru (talk) 04:16, 19 December 2013 (UTC))

Personally I see very little point in going into the system in detail. I mean why do you want to learn off by heart a quicker way of doing square roots by hand? Does it confer greater understanding? You said you didn't find it obvious. Is it useful? I think it is worth showing students how to do things by hand but learning a more complicated algorithm which is faster is not a real gain when they'd use calculators if they really needed to know the result without error. I think it should just be described in the sort of detail given for the other methods, this isn't a how to manual. Dmcq (talk) 15:12, 18 December 2013 (UTC)

The flaw in this argument is that all the algorithms are done by hand before people can trust it for machine implementation. If hand computation yields faster results, then so will the machine implementation. For instance, the digit-by-digit square root method for binary strings is often implemented in computers. Also for much of history, the Babylonian method was done by hand. That being said, I agree with the last point that you make. A concise description of the duplex method is not given and one example would have been sufficient. But I don't dare make the edits myself, lest I incite edit wars. (Manoguru (talk) 04:16, 19 December 2013 (UTC))

Mainly it is the amount of space that is given to it that I feel is undue. And even at that it has very little about the method, just examples. If a couple of the examples were replaced by a better explanation that would be an overall gain I think. An encyclopaedia should tell about things, not train you in doing them. Dmcq (talk) 12:53, 19 December 2013 (UTC)

I have chopped out all the examples except the first. One properly explained example of the square root of a 6 digit number might be okay instead, but three long examples without proper explanation are not. Dmcq (talk) 09:11, 22 December 2013 (UTC)

Another algorithm

There is another algorithm which runs very fast using only shifts, increments, decrements, additions and subtractions, and works with any base. This algorithm has been in use successfully for almost 40 years in nuclear instrumentation. The algorithm and an example are published at http://www.king-cart.com/square-root.html

Marshall Dudley2602:306:BC45:8A30:290E:C082:979:2365 (talk) 16:58, 25 February 2015 (UTC)

So, how does this compare to the Odd-integer methods? As used by operators of hand-cranked decimal calculators or even electrically-cranked ones such as Friden.NickyMcLean (talk) 04:12, 26 February 2015 (UTC)

Note: 20p + x is simply twice p, with the digit x appended to the right).

Is 20p twice p? I'm not sure if this is a typo or a profound insight that I fail to grasp. Fotoguzzi (talk) 21:16, 16 February 2016 (UTC)

Merging proposal

It seems to me that the scope of this article is methods for numerical calculuation of square roots, and that the sections on continued fractions and Pell's equation do not belong here. On the other hand, the example ${\sqrt {114}}$ expressed as a periodic continued fraction would be good in the article periodic continued fraction. Any opposite views? Isheden (talk) 20:52, 7 December 2011 (UTC)

None from me. In fact, I just made Pell's equation a subsection of the Continued fractions group (it was a separate section) to simplify merging the the whole thing if appropriate. I have also removed one GCF for ${\sqrt {114}}$ that after more careful analysis proved inappropriate. — Glenn L (talk) 02:05, 18 January 2012 (UTC)

I see that the Pell's equation section has been separated from the Continued fractions section; no problem there. However, I restored the GCF subsection since I don't see it as redundant, as the example of ${\sqrt {114}}$ appears unique to Wikipedia. — Glenn L (talk) 04:28, 16 June 2016 (UTC)

Are We Going to Add This to the Main Page?

While playing around with numbers, I discovered this, but if you're reading this, feel free to check this method: To approximate the square root of a positive integer n, start with a fraction that has 1 as the numerator and 0 as the denominator. For each subsequent fraction, the numerator is the numerator of the previous fraction + n*the denominator of the previous fraction, and the denominator is the sum of the numerator and denominator of the fraction before it. Although the fraction will never exactly reach the square root of n, it will keep coming closer. ---- — Preceding unsigned comment added by 2601:2C1:C003:EF7A:58A9:3D2:9198:302A (talk) 01:22, 13 February 2016 (UTC)

I noticed that your contribution was removed from the article because wikipedia is not meant for publishing own research. In any case, if for some n your method converges, it will indeed converge to the square root of n. Bye, Bob.v.R (talk) 22:07, 13 February 2016 (UTC)

Sounds a lot like continued fraction expansion. Manoguru (talk) 01:38, 4 October 2016 (UTC)

No mention of complexity?

I'm really surprised that there is no mention of the computational complexity of the various methods. The rate of convergence per iteration is meaningless without information about the amount of work that each iteration takes. NathanZook (talk) 20:12, 22 February 2017 (UTC)

If you have a reliable source for any of those complexities, we invite you to add that information. JRSpriggs (talk) 02:02, 24 February 2017 (UTC)

Original research

This article seems to largely ignore several common algorithms used in numerical analysis, instead presenting original research stuff like the high/low method. This article should be checked against standard references in numerical analysis, as well as the Wikipedia articles numerical analysis and root-finding algorithm, in this case for solving the equation x² - r = 0, where r is the radicand. Methods that cannot be found in the literature in this field comprise original research and should be removed. Isheden (talk) 10:17, 15 January 2012 (UTC)

I would not mind if someone took out the section Methods of computing square roots#High/low method. I refrain from taking it out myself for fear of inciting an edit-war (with its author) unnecessarily. Similarly for Methods of computing square roots#A two-variable iterative method and some of the others. However, I think we need to keep at least the sections: Rough estimation, Babylonian method, Digit-by-digit calculation, Iterative methods for reciprocal square roots, and Negative or complex square. JRSpriggs (talk) 06:01, 16 January 2012 (UTC)

First, regarding the High/low method, I don't know who was the original author. However, I think it's safe to replace it with the bisection method, which has known convergence properties. With the high/low method, in principle you need to calculate nine intermediate points (e.g. 4.41, 4.42, 4.43, 4.44, 4.45, 4.46, 4.47, 4.48, 4.49) to determine which ones are too high/too low, and which ones are "close". With the bisection method, you just evaluate one intermediate point and there is a clear rule for discarding one interval. Isheden (talk) 11:29, 16 January 2012 (UTC)

The bisection method would be better (when using a calculator) than the high/low method, but it is dominated by the Babylonian method which is the best method for calculators which have addition and division.

Digit-by-digit is the best method for low precision calculations by hand.

Using the reciprocal square-root is best when your calculator has subtraction and multiplication, but not division.

Rough estimation is necessary to initialize the other methods in an efficient way.

Simply applying various root-finding algorithms in the case of the square-root does not (to my way of thinking) add anything not already in those articles. At most, we could mention that they can be so applied. JRSpriggs (talk) 14:58, 17 January 2012 (UTC)

It's hard to know what's OR and what isn't as the article is so lacking in references. The digit-by-digit method given is perhaps a fairly well-known one (taught to me long before WP existed), so clearly isn't OR, but there's no indication of its name or origin, and no references have been given for the method. I would imagine that whoever added it to WP was recalling it from memory. I'll see what I can find for this one when I've a bit more time. — Smjg (talk) 11:22, 28 July 2017 (UTC)

Trigonometric Solutions

http://math.exeter.edu/rparris/peanut/cordic.pdf (page 16) gives a very weird way of computing square roots using trig functions -- anonymous

The exeter link seems dead.

The cordic cited method, I think (and will check), actually gives twice the square root and the error is copied from Table IV in the cited paper that is wrong. When Cordic is run in hyperbolic vectoring mode it computes sqrt(x^2 - y^2), so for x=s+1 and y=s-1 we get sqrt(s^2 + 2s + 1 - s^2 + 2s - 1) = sqrt(4s). David.J.Greaves (talk) 19:33, 22 August 2017 (UTC).

We do have an article about CORDIC, which mentions computing square roots but does not give further details. I added a sentence to this article with a link to CORDIC. I don't have an idea whether CORDIC is still used (or was ever used) to compute square roots, but it would be good to have some more details. -- Jitse Niesen (talk) 14:42, 8 December 2008 (UTC)

There are several methods of computing a square root using trigonometry. For example:

root = cos( asin( (n-1)/(n+1) ) ) * (n+1)/2

or

root = tan( acos( (n-1)/(n+1) ) ) * (n-1)/2

Should these methods be added to the article and/or to Square root? RareEntity (talk) 03:14, 28 January 2016 (UTC)

Do you have a reliable source? We don't usually bother including ideas from every amateur web page. And is this really a method of computing? Or just a cute identity? Dicklyon (talk) 05:14, 28 January 2016 (UTC)

Using transcendental functions to calculate a much simpler algebraic function, √n, seems like burning diamonds to conserve coal. It is not efficient.

Also these formulas would not work unless n > 1. And it would not work well unless n ≈ 3+2√2 ≈ 5.8 . JRSpriggs (talk) 04:43, 29 January 2016 (UTC)

The first one I listed is an identity derived from Euclid's Elements Book 2, Prop 14. RareEntity (talk) 06:24, 17 February 2016 (UTC)

References

Suggested change to the first digit-by-digit method example

The root chosen, 12.34, may be a poor choice. As p is initially 0, this pattern can create unnecessary confusion for people new to this algorithm, such as that the later values of x, 1, 2, 3, and 4 somehow are related to counting from that initial 0. Consider changing.

Also, if there are going to be these examples, it may be prudent to make them as clear as possible, explicitly noting the values of p, 20p, x, and y in each line of guessing/calculation.

Also, mentioning that the '20' in '20p' is the product of the base, 10, and the root being sought, 2, may be another effective link to the related article, https://en.wikipedia.org/wiki/Shifting_nth_root_algorithm — Preceding unsigned comment added by 137.118.149.208 (talk) 21:22, 24 May 2018 (UTC)

Your suggestion in the first paragraph of your message seems to me to be a good one. Why don't you go ahead and replaced the example with a better one? I'm not so sure about "explicitly noting the values..." That may be a good idea, or it may just add more clutter and make the whole thing more confusing. I suppose to some extent it depends on how it is done. The editor who uses the pseudonym "JamesBWatson" (talk) 15:58, 25 May 2018 (UTC)

Double bubble method

My grandmother, who was a math teacher, taught me the digit by digit calculation method in the 1970s. She referred to it as the double bubble method, since to gain an additional digit of accuracy, you need to add two zeroes to the end of your remainder (assuming that you are taking the square root of a decimal that is terminating). Has anyone else heard this method called by that name? Google searches bring up nothing. Jdlawlis (talk) 02:56, 17 June 2018 (UTC)

No. I suspect that she was creating or using a neologism. JRSpriggs (talk) 04:28, 17 June 2018 (UTC)

Or a neoneologism. - DVdm (talk) 08:20, 17 June 2018 (UTC)

If it was Jdlawlis's grandmother, it was perhaps more likely to be a veteroneologism than a neoneologism. In any case, even if it was a neoneologism in the 1970s, it's probably a veteroneologism by now. The editor who uses the pseudonym "JamesBWatson" (talk) 20:12, 19 June 2018 (UTC)

-8.1648465955514287168521180122928e-39

Why sqrt(4) - 2 in Windows calculator gives -8.1648465955514287168521180122928e-39? Barellor (talk) 05:01, 9 June 2019 (UTC)

On my computer, it gives 0. Perhaps on yours, it has a round off error which is not hidden? See Catastrophic cancelation. In any case, this is the wrong place to ask such a question. We are not responsible for the functioning of Windows. JRSpriggs (talk) 05:33, 9 June 2019 (UTC)

Recent rewrite of lede

Imho, the rewrite of the lede per 02:37, 19 August 2016‎ by Esquivalience is no improvement, but just adds imprecision.
I am prepared to discuss this, but did not want to go through manual revert. Purgy (talk) 05:54, 19 August 2016 (UTC)

This matter is settled since 19 August 2016. -Purgy (talk) 05:51, 4 October 2016 (UTC)

Settled by whom? In what way? Sbalfour (talk) 23:12, 14 November 2019 (UTC)

so which method is the FASTEST!

so which method is the FASTEST!

It would seem like that information should be on this page!

2601:14F:8006:2580:1948:BAF5:8A41:1D72 (talk) 13:23, 4 May 2017 (UTC)

Fastest in terms of what? The time taken by a human to compute mentally, to compute with paper and pencil, or the time taken by a machine to print the result? If the latter, it depends on the programming language, the efficiency of the programming, the optimization level of the compiler, and the features of the target architecture. In short, which method is fastest depends on what fastest means. Sbalfour (talk) 03:42, 15 November 2019 (UTC)

simple argument for sqrt(S) = average(S/x, x)

A simple argument for the iteration of sqrt(S) would be that the correct answer with a good guess x_n would lie between x_n and S/x_n. So why not choose the average as x_{n+1} and repeat?

(this method might also converge for many other functions)

This is just Newton's method for estimating roots of the function F(x)=X^2.Sbalfour (talk) 03:49, 15 November 2019 (UTC)

Off-topic

The text says: In numerical analysis, a branch of mathematics, there are several square root algorithms or methods of computing the principal square root of a non-negative real number. For the square roots of a negative or complex number, see below. That's a direct contradiction: either the article is about finding the principal square root or it is not. Then there's the sections Reciprocal of the square root and Iterative methods for reciprocal square roots which are also tangentially off-topic (and for which there are separate articles). Considering the already excessive length of this article (maintenance tag), I think we ought to delimit the topic as stated in the opening sentence. Maybe square roots of negative numbers needs its own article, but there's much to say that isn't said here, nor should it be.Sbalfour (talk) 16:38, 15 November 2019 (UTC)

chop

The text contains way too much detail for a concise, scholarly article. Scholars don't need elaboration of grade school arithmetic, nor compilable and runnable program code. Those things are for textbooks, not the encyclopedia. Not to mention that most of the examples are uncited and appear to be WP:OR. My first inclination is to delete all examples, cited or not, to give the article a fresh appearance and concise presentation. We need a focus on exposition, not a tutorial. Then there's the cryptically concise section CORDIC (CORDIC what - is that an acronym? If so, it needs expansion in the text) containing hyperbolic coordinate system in vectoring mode,... that implies a WHOLE lot that isn't developed here. The whole section needs to go. Vedic duplex method for extracting a square root is single sourced, by a primary source, and a dubious and discredited one at that. The Vedic stuff is almost like a mythology, and shouldn't be included here... it's just way out there. The whole section needs to go. I'd like to see the article shrunk by a factor of at least 3; if any examples are added, keeping them extremely terse, or placing them in footnotes, to keep the text readable. What's happened here is a "Me, too!" thing, everyone has to regurgitate their mostly WP:OR cute wrinkle on some well-worn algorithm. And like another editor noted, what's actually done in system numerical libraries doesn't look anything like what's presented here. Sbalfour (talk) 16:51, 15 November 2019 (UTC)

First sentence of the lead

The first sentence presently reads "In numerical analysis, a branch of mathematics, there are several methods for calculating the principal square root of a nonnegative real number". This is in my view really awkward and seems to originate in an attempt to make the article title "Methods of computing square roots" the subject of the first sentence. The real subject of this article is square root algorithms, and "methods for calculating the principal square root of a nonnegative real number" is just a description/definition of this subject. Thus, since "square root algorithm" is a widely accepted name for the subject, a more logical way of structuring the first sentence would be "square root algorithms are methods for calculating the principal square root of a nonnegative real number", or even better in singular. Further information on how to write the first sentence can be found in WP:LEAD, particularly WP:FIRSTSENTENCE. Isheden (talk) 12:13, 28 March 2013 (UTC)

The first sentence of the lead is pretty strictly proforma, and it goes like this: A foo is a bar, baz, quux. foo is the title of the article, and bar, baz, quux are qualities or properties of foo (the commas are virtual placeholders - they may or may not be syntactically required or permitted). For example: "An elephant is a large pachyderm mammal. Hence, "Methods of computing square roots are numerical analysis algorithms for finding principal square roots of non-negative real numbers." If you want to use something else in place of 'Methods of computing square roots', like 'Square root algorithms', it will be necessary to rename the article to that first (and I'm not opposed, but others are, so there needs to be consensus before you do that, and there is not such at this moment).Sbalfour (talk) 17:11, 15 November 2019 (UTC)

The lead

Considering the extraordinary length of text here, the lead can and should support 5 solid paragraphs, as a feature-length article might have. It should be encompassing overview - what these algorithms consist of, what they have in common, what distinguishes them from each other. We mention Newton's method and the Babylonian method without even minimally describing what makes them notable - the reader will have to go read two other articles to understand the significance of those two terms. The methods encompass at least mental, paper-and-pencil, and programmatic algorithms; and arithmetic, algebraic and geometric construction modes of computation. The lead should lay out the scope of the article and introduces each of its major ideas, so readers know whether what they're looking for may reasonably be found here, or that they need to look elsewhere. As it stands, the first sentence is hackneyed phraseology and the whole lead is threadbare and moribund. Sbalfour (talk) 18:01, 15 November 2019 (UTC)

Requested move

I think the title "Methods of computing square roots" makes it unnecessarily difficult to find this page, since someone interested in computation of square roots would not expect that the page title begins with a general term such as "methods". A more natural title would be "Square root computation". Are there any objections to moving this page to Square root computation? Isheden (talk) 08:40, 27 March 2012 (UTC)

"Square root computation" is ambiguous. It could mean the same thing as "Methods of computing square roots", but it could also mean a computation which uses square roots in some way. For that reason and because of the very many existing mental and textual links to the article by its current title, I would strongly oppose a change in its name. I have made your suggested title into a redirect to make it easier for people who think like you to find this article. JRSpriggs (talk) 12:24, 27 March 2012 (UTC)

Then I would suggest "Square root computation methods". Of course all links to the present article name would be taken care of with a redirect to the new article name. I can't see that anyone would think of typing "methods" as the first word if they're looking for an article like this. Isheden (talk) 21:51, 31 March 2012 (UTC)

I sort of agree that 'Methods' is not a good first (and most important) word of the title. And that 'Square root computation methods' is better. There is an analogous article titled Root-finding algorithm, hence 'Square root-finding algorithm' (or 'algorithms'). But that seems overly elaborate. Why not just 'Square root algorithm'? It's open to the objection that it may refer to algorithms that use square root, but we could place a hatnote

For algorithms that use square root, see other article.

if 'other article' exists, or if it doesn't, a hatnote

This page is about finding square roots. For other uses, see Square root.

.That's completely accepted and transparent when there's ambiguity, like there is here.Sbalfour (talk) 18:47, 15 November 2019 (UTC)

Digit-by-digit calculation

This is substantially the longest section in the article, and very tutorial in tone, though Basic method subsection is more like Proof- this part belongs in a textbook, not here. Though there's no citations, and probably WP:OR, it certainly isn't original to the editor - I learned it junior high as the way to do paper-and-pencil square root. He probably regurgitated it from memory. The level 2 section is obviously a keeper, but needs to be way shorter (like a factor of 3 or 4) and accessible to a junior high student (because like me, that's who's going to be taught it).Sbalfour (talk) 21:20, 15 November 2019 (UTC)

Numerical analysis

None of the techniques detailed here can directly be used to program a math library quality sqrt routine. Having written such libraries and routines, I have some idea what they do. Library routines are highly polished, and highly idiosyncratic with respect to the target platform. I once saw an Algol intrinsic for sqrt in about 5 single-cycle bit operations followed by 8 floating point operations produce a full 40-bit precision fp sqrt. It depended on the format of the operand, but something similar could be done on IEEE operands and 32/64-bit targets. The Sun/SPARC sqrt routine was written in assembly (I gather), and it was so obtuse I couldn't understand it. I think it depended on things like OoO execution and register aliasing. It, too, was very short, and very fast. We could include at least one example like this, say for a modern Intel 64-bit IEEE post-SSE2 SoC, for somebody who wants to know how the pros do it.Sbalfour (talk) 21:42, 15 November 2019 (UTC)

Newton's method / Babylonian method

Newton's method is the more general and most well known name for the tangent/intercept method of root finding, whether square root or roots of other functions. That it devolves to an ancient method in this case is an interesting historical footnote, but that is all it is. We needn't have duplicate presentations, and the Babylonian section can be subsumed under Newton's method, and the rest of the detail moved into a historical footnote. If I were looking for a square root approximation method, I'd look first for Newton's method, and expect to find a full presentation of it in an encyclopedia. We don't want to elaborate excessively, because there's a separate article for it.Sbalfour (talk) 23:17, 15 November 2019 (UTC)

Why is it called the "Babylonian method"?

I added three notes related to the Babylonian method for computing square roots. Is the ancient Babylonian method essentially the same as the method that is now called the "Babylonian method"? --Jtir 20:20, 12 October 2006 (UTC)

Basically, it is not known how the Babylonians computed square roots, although there are informed conjectures. I still haven't discovered the origin of the term "Babylonian method" in modern usage. I put my conclusions in a note here: Square root of 2#Notes and simplified the note in this article. --Jtir 18:58, 15 October 2006 (UTC)

There is not a shred of archaeological evidence that the Babylonians used this method. 'Informed conjecture' is what we call wild speculations made by otherwise informed persons. Consider that square root can be by geometrical construction, then measured. The earliest historical record of the method is in the Hellenic period. I suggest we rename the section to Heron's method (which redirects to there), and drop the reference to 'Babylonian' altogether, or move it into a historical footnote with a comment that it's speculation, not fact.Sbalfour (talk) 19:21, 16 November 2019 (UTC)

Mass undo

Recently, editor JRSpriggs engaged in a mass undo or reversion (rollback?) of dozens of edits comprising a couple hundred lines, of my work on this article, which I have been a couple of weeks in researching, analyzing and preparing. His edit summary merely stated that I deleted much useful stuff and added duplicate stuff.

Back when, JRSpriggs himself wrote:

"I think you could delete any or all of this article, except the Babylonian method which is the only method worth using. In any case, the article is much too long. JRSpriggs 05:32, 2 September 2006 (UTC)

but now objects when I take his advice, without recourse, by undoing me? What's the real issue?

Among my edits, I deleted an unsourced section. I also deleted a dubious primary source (self-published, more or less), which was the only source supporting another section, so I eventually deleted that section as well, since it was now unsourced. I'm entitled to challenge and delete unsourced text, even whole sections.

I redrafted the lead of this quite large article, adding 5 nice overview paragraphs. I also added a section on Newton's method, which was not covered in the article, though it had a one-line mention at the bottom of another section. I don't see how either of these duplicated anything. I also made various other minor edits comprising diction, typos, formatting, etc.

I've given substantive explanations of my work and intended work here, on the talk page, before starting work (though only a day or two before). Nonetheless, I'm not fly-by editing, this is a substantive effort, and I want others to understand what I do and why.

If JRSpriggs has suggestions on improvements to what I've done, or objects to things I've done, I invite him or other editors to comment here, item by item, edit by edit, or section by section, so we we can arrive at consensus on those items. I feel free to continue editing because there's a lot yet I intend to do.

Wholsesale undo of the work of another editor smacks of WP:OWN, and is almost never acceptable - It's likely to invite an edit war. At WP:OWN, I see this under Examples of ownership behavior:

An editor reverts a good-faith change without providing an edit summary that refers to relevant Wikipedia policies and guidelines, previous reviews and discussions, reliable sources, or specific grammar or prose problems introduced by the edit.

That's exactly what happened here; not just one time, but dozens.

Only in cases of addition of large amounts of unsourced or dubious material would wholesale reversion be warranted, and even then, it would be proper procedure to notify the editor first, and give him or her an opportunity to source the material. I have added a sparing amount of text to this article in the Newton's method section, which was among the last things I did before retiring that day, and did not yet source it, because I was still composing it. If that is the objection, I can source it forthwith, though I'm still adding text, and may need additional sources.

I've restored my work for now. It just can't be that I'm prohibited from working on the article because one editor objects. Time to come to the table.Sbalfour (talk) 18:44, 16 November 2019 (UTC)

You quoted me above. Look at the date, that was thirteen years ago. The article has improved a lot in that time. But it seems to me that you are ripping it apart without consideration for the efforts of other editors. I suggest that you make a small localized change and then wait a few days to see how other editors react before proceeding to change the article again.

In particular, I object to your taking out the error bounds from the Babylonian method. They give the reader an idea of how fast the method converges.

I also object to your taking out the formula for the square root of a complex number. While this does appear elsewhere in Wikipedia, it is not easy to find it there. And the formula is far from obvious.

I also think that adding a section on Newton's method is pointless since the article already made clear that the Babylonian method is the same as a certain version of Newton's method.

Also, I find it unhelpful for you to scatter your comments among the many sections of this talk page. JRSpriggs (talk) 05:08, 17 November 2019 (UTC)

Ok, this gives me something to work with. But your objections then are still valid now: the article is even longer, and most of it is still OR. Hardly any of the examples are cited, as well as part of the methods.

I'm aware, after drafting the Newton's section, that the result, and example are analogous to the Babylonian method, in the case of square root. Considering the wide usage and recognition of that name, I think we need a parallel level 2 section. Instead of an analytical approach, which just devolves to the same computation, a geometric approach showing how the derivative intercept approaches the root would give a better picture. I'm working on it. I'll restore the parts you want retained. I'd like to know what pieces of the article you don't want... how to we make this article plausibly concise and readable? Split it? Delete what? I'm trying to read the continued fraction example on a smartphone, and it's just jibberish. Even on my 10" tablet, it's still indecipherable.

The inverse sqrt is very cute - there's a GA article on it. But it's one line estimate is good only to about 6%, that's just 4 bits of precision; the final result is ~9 bit precision. If multiply or divide were that inaccurate, the chip would be recalled. The reason is, that routine was application-specific, and the application vector values were internally stored as 8-bit quantities, so essentially they only needed 8-bit arithmetic. We don't say that, and readers won't know it isn't a full precision square root routine. It's actually very easy to make a 4-bit guess (a 16-byte lookup table is the obvious way, but ~five 1-cycle instructions are sufficient to yield a 6-7 bit estimate), no tricky stuff required. The code also does type-punning whose result is undefined, meaning specific implementations may invalidate the method now or later. I just don't think we want to play this up. Maybe it should be a footnote that refers back to the main article? This page is presumtively valid methods of computing square root.Sbalfour (talk) 16:24, 18 November 2019 (UTC)

I've answered all of your principal objections, so you'll be happy to work with me. I'm not going to try reorganizing the talk page... it's a stream of consciousness; most of my comments are in contiguous section by topic, at the bottom of the current page.Sbalfour (talk) 15:48, 21 November 2019 (UTC)

Rough estimate

The existing Rough Estimate section for square root is untenable. It's uncited, and I can't find anything like it in my polynomial approximation, arithmetic, linear algebra or computer algorithm texts. It returns 2 as the square root of 1, an implausible result, and an error of 100%. It also returns 2 as the square root of 2. If it were a black box (and it might be, if it were implemented as a computer routine), and the black box returned 2 as the square root estimate for 2, I'd presume the box was broke, because it didn't do anything. And it's not useably close to the right answer either.

It's so very easy to estimate the square root of a number to two or even three significant digits, after factoring out powers of 10 until a number less than 100 is left. There can only be 9 possible first digits (it can't be 0)... surely that's a trivial interpolation. Just a few examples of the mental approach (brackets are the result from my calculator):

3 is between 1 (1^2) and 4 (2^2), so the square root of 3 must be between 1 and 2, a bit more than half way, because 3 is a bit more than half way from 1 to 4, so I'd guess the root is 1.7, maybe 1.75 [the square root of 3 is 1.73 to 3 significant digits, an error of only 2 parts in 1000].

The square root of 37 is the square root of 36 (6) plus 1/13 or .08, because 37 is 1/13 of of the way to 7^2, which is 49. So I'd guess the root is 6.08 [the square root of 37 is 6.08 to 3 significant digits]

The square root of 75 is 8 point something because 8*8 is 64, but 9*9 is 81, too big. But 75 is a little less than 2/3s of the way to 81, so I'd guess the root is 8 + a little less than .67, maybe .66, so 8.66 [the square root of 75 is indeed 8.66 to 3 significant digits]

The square root of 47 is a little less than 7 because 7^2 is 49, that's 2/13 of the way to 36 which is 6^2, and 2/13 is about 15%, so 7 - .15 = 6.85 is the guess. [the square root of 47 to 4 significant digits is 6.856, an error of only 6 parts in 10000].

The square root of 91 is 9 something, because 9^2 is 81, but 10^2 is 100, too big. But it's just over half way to 100, so guess .55, and the estimate is 9.55. [The square root of 91 is 9.54 to 3 significant digits, an error of 1 part in 1000].

It took me only a few seconds to make each of those estimates, thinking out loud, but I completed them far faster than I can speak or write. I didn't know any of those square roots, I had to go punch them into my calculator. The point is, how very accurate they are, just by interpolative guessing. With a slight modification to the process, I think I could make get 4 digits of precision in most cases. It could probably be quantified into an algorithm, but it's most suited for mental reckoning; computers don't guess, they calculate. The estimates aren't 'rough' at all - they're very good for the effort spent. That's what people actually do, and what should be presented here.

For paper-and-pencil doodling, I think the usual method is a linear regression line, because it's more predictable and reliable as per error bounds, It's also very easy to formulate... the secant line or tangent line somewhere along the arc [1.100] for y=x^2 is a good approximation. Push it a little bit to the right or left, and viola! you have the regression line without needing to do any integration. I can also do that mentally, but writing it out helps to visualize it.

Sbalfour (talk) 21:11, 20 November 2019 (UTC)

It is only a rough estimate. That is, it is limited to one decimal place and no calculation other than looking at the order of magnitude of the square. If you put any more effort into getting it, then you would be better off expending the additional effort on doing additional iterations of the Babylonian method.

It was chosen as the one-digit value of x₀ which minimizes the maximum possible value of $\epsilon _{1}$ over the required (factor of ten) interval. It does that.

This would have been apparent if you had not deleted the section showing he maximum possible values of $\epsilon _{n}$.

Compare your calculations with the result of doing one or two iterations of the Babylonian method after applying the rough estimate. JRSpriggs (talk) 02:01, 21 November 2019 (UTC)

Not all iterations are as simple as Newton-Raphson, and Newton-Raphson has division complexity. On most current processors, division is microprogrammed, hence very expensive. For example, on Intel's Coffee Lake, it's 29 cycles for single precision. That means that one would rather spend up to 29 bit/arithmetic instructions to save an iteration. A linear approximation won't need divide, and is only 2 operations, multiply+add. A 2-piece piece-wise linear approximation would reduce maximum error by a factor of about 10, and cost 5-6 operations. Linear approximation is the standard approach to polynomial approximation. It should certainly be presented here.Sbalfour (talk) 17:33, 22 November 2019 (UTC)

The rough estimate given may be appropriate for hand-calculation. But for machine calculation, you have a point. It would probably be better to combine the rough estimate with the first iteration of the Babylonian method and then precalculate and optimize the constants. If S is presented in decimal, this would give

$1\leq S<10\to x_{1}={\frac {\sqrt[{4}]{10}}{2}}+{\frac {1}{2{\sqrt[{4}]{10}}}}\cdot S=0.889140+0.281171\cdot S$

$10\leq S<100\to x_{1}={\frac {\sqrt[{4}]{1000}}{2}}+{\frac {1}{2{\sqrt[{4}]{1000}}}}\cdot S=2.81171+0.0889140\cdot S$.

But more likely, it would be in binary, and that subsection would apply.

$0.5\leq S<2\to x_{1}=0.5+0.5\cdot S$.

OK? JRSpriggs (talk) 07:21, 24 November 2019 (UTC)

Hmmmm... I don't immediately follow your logic, but give me a little time, and I'll try to work it in.Sbalfour (talk) 17:13, 26 November 2019 (UTC)

This section (now called "Methods of computing square roots#Initial estimate") is becoming bloated. Please cut it back to just the best method for each application! JRSpriggs (talk) 01:02, 25 November 2019 (UTC)

Agreed; it's too-tutorial; people just want to grab a formula and run.Sbalfour (talk) 17:13, 26 November 2019 (UTC)

@Sbalfour: The last linear estimate you give has relative errors greater than that of the formula in my second previous comment (which is not more than 17%). JRSpriggs (talk) 09:23, 26 November 2019 (UTC)

Did I make a computation error? I'll take another look. However, least-squares methods that minimize average differences are based on the integral (area between the curves). That often leaves an anomalously high relative error at one end of the range or other, for a small portion of the range. Arrrrrgh! We can't simultaneously minimize maximum and average error, or relative and absolute error. Maybe we need two formulas.Sbalfour (talk) 17:13, 26 November 2019 (UTC)

I was not sufficiently clear. I meant to say that your formula

${\sqrt {a\cdot 10^{2n}}}\approx (0.24a+1.04)\cdot 10^{n}{\text{ if }}1\leq a<10$

is inferior to my formula

${\sqrt {a\cdot 10^{2n}}}\approx (0.889140+0.281171\cdot a)\cdot 10^{n}{\text{ if }}1\leq a<10$

because yours has an error of 28% at a=1 and mine has an error of under 17.1% for any a in the interval. JRSpriggs (talk) 03:35, 27 November 2019 (UTC)

You are correct. I located the tangent lines at the arithmetic means of the intervals instead of the harmonic means, and later used the wrong bounds on the integral for the area between the curves. The formulas for the piece-wise linear estimates of square roots need to be adjusted. I vaguely thought that 28% was too high for the relative error, but didn't catch my mistake. Thanks for bringing this to my attention.Sbalfour (talk) 19:08, 27 November 2019 (UTC)

Binary estimates

This section essentially says to guess the square root of any number between 1/2 and 2, as 1. That's actually a bad guess... A good guess can't be had by ignoring the mantissa?!

A good guess is readily at hand: the square root of any number between .5 and 1 is between .707 and 1.0, so intuitively split the difference and guess 0.854, and similarly guess halfway between 1 and 1.414 or 1.21 for the square root of any number between 1 and 2. Again, that's a scalar estimate, and those are not very good. A linear estimate in both cases is (1+a)/2. Actually, what's happened is that Newton's (Babylonian, Heron's) method has collapsed to its own best estimate because the underlying mathematics is the same: this method is only very effective when the guess is already close to the root. And both 0.5 and 1.<something> are close to 1.

But we can do better than that: guessing the mean is always higher than the root, by a maximum of 0.086 for linear guesses between 1 & 2, and 0.043 for guesses between 0.5 and 1. So again split the difference and guess (1+a-.086)/2 for numbers between 1 & 2, and (1+a-.043)/2 for numbers between 0.5 & 1. This gives us an estimate with maximum absolute error of 0.043 for roots between 1 & 2, and 0.022 for roots between 0.5 & 1.

But we're not done yet; the 'correction factor' above was a scalar, and that's not very good, usually. If instead we use a fractional part of the mantissa, the final estimate is:

${\sqrt {S}}\approx (1+a-a/8)/2$ for a < 1

${\sqrt {S}}\approx (1+a-a/16)/2$ for a >= 1

So for √0.5, the estimate is 0.719 and √0.5 is .707, an error of 0.012, and for the √2, the estimate is 1.437 and √2 is 1.414, an error of .023. Since we're working in binary, subtracting a/16 or a/8 is a rshift + sub, not a divide. The relative error is 1.63%(0.0163) in both cases, larger than 1/64 = 0.0156, so they're not quite good to 6 bits.

These estimates are still too big, and there's a corollary worth noting. The linear correction factors are close to 3a/16 and 3a/32, to another bit of precision. That's again another rshift/sub. But this time, the relative error drops to .0077%, less than 1/128, which is .0078. That means the estimates would be good to 7 bits. To 7 bit precision, the normalized representation of √2 is 0b011011 (rounded, high bit of 1 not represented); the estimate is 0b011010 exactly. An IEEE single is 24 bits of precision (23 represented), so 2 Newton-Raphson iterations of 7 bits yields 28 bits, done. An IEEE double is 53 bits (52 bits represented), so 3 Newton-Raphson iterations yields 56 bits, done. Without this last dibble-dabble, we need an additional iteration for both. It's unlikely that it would pay off to try and extend the precision of the estimate to the required 12/13+ bits to save another iteration in both cases. It's a moot point anyway - most modern processors including mine, have a sqrt operator, and we're not going to beat that.

Sbalfour (talk) 20:54, 26 November 2019 (UTC)

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)

Square Root algorithm in 1965 Friden EC-132 Electronic Calculator

Early electronic calculator square root algorithms:

• https://www.oldcalculatormuseum.com/friden132.html
• https://www.oldcalculatormuseum.com/d-f132svcsqr.pdf
• https://docs.google.com/viewer?url=patentimages.storage.googleapis.com/pdfs/US3526760.pdf — Preceding unsigned comment added by 98.164.14.157 (talk) 15:16, 6 October 2020 (UTC)

"nearest perfect square" in Bakhshali method?

The example in the Bakhshali method has me confused. 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)

The article referenced here makes clear, by numerical example, that the initial guess does not need to be near the closest perfect square. — Preceding unsigned comment added by Sramakrishna123 (talk • contribs) 22:10, 19 December 2020 (UTC)

JSON or what?

Code language is not identified. It should. Is it JSON? All traces of JAVA should be exterminated from the planet to the seventh generation. It's on the bible. — Preceding unsigned comment added by 188.80.214.144 (talk) 23:54, 13 April 2021 (UTC)

JSON isn't a programming language, and isn't closely related to Java (although it is related to JavaScript, which is not the same but could be confused with Java).

The code appears to be in C, which is a bit similar to Java; I'll mark it as such. Xnft (talk) 15:48, 15 April 2021 (UTC)

Erroneous introduction

The first paragraph of the article is this:

"Methods of computing square roots are numerical analysis algorithms for finding the principal, or non-negative, square root (usually denoted √S, ²√S, or S^1/2) of a real number. Arithmetically, it means given S, a procedure for finding a number which when multiplied by itself, yields S; algebraically, it means a procedure for finding the non-negative root of the equation x² - S = 0; geometrically, it means given the area of a square, a procedure for constructing a side of the square."

I do not know much about numerical analysis. But I do know that this is totally misleading!

A "method for computing a square root" of a number does not mean a method for *finding* the square root of that number.

Instead, it means a method for approximating the square root of the number, usually to various degrees of accuracy.

The distinction is essential to understanding what a "method for computing a square root" means. So the article should not mislead readers with an erroneous first paragraph.66.37.241.35 (talk) 16:39, 7 October 2020 (UTC)

Is this not dealt with adequately in the second paragraph? JRSpriggs (talk) 17:05, 7 October 2020 (UTC)

I'd say no, it's not, because however well it is dealt with in the second paragraph, that's the SECOND paragraph, and it's the FIRST paragraph which should mention that it's an approximation, since that's what is being accomplished. Therefore I think the word 'finding' in the first paragraph should be changed to approximating. UnderEducatedGeezer (talk) 02:48, 8 December 2021 (UTC)

{=3 } =4

In procedure int32_t isqrt(int32_t n)

• 3 left curly brackets
• 4 right curly brackets Jumpow (talk) 20:37, 21 December 2021 (UTC)

I tried to fix it. Is it OK now? JRSpriggs (talk) 22:57, 22 December 2021 (UTC)

Yes, now OK Jumpow (talk) 21:33, 4 January 2022 (UTC)

binary method in c

I believe that the example that is given in C is what is referred to as the Chinese Abacus Method - confirmation from this article and code that appears to be the same algorithm. — Preceding unsigned comment added by 70.124.38.160 (talk) 15:55, 18 April 2022 (UTC)