Talk:Square root algorithms
 | Mathematics Start‑class Low‑priority | |||||||||
| ||||||||||
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)
- 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 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 xn for the iterations wherever it is applicable. -- Meni Rosenfeld (talk) 10:55, 10 September 2006 (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)
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 "<sup>2</sup>" to indicate a square rather than "*2" (or "**2" which would be more conventional). JRSpriggs 06:47, 27 February 2007 (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)
"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)
Continued fractions
JRSpriggs, perhaps you can explain:
- What made you modify the equation for ? It is now more cumbersome and less correct, since what we know is ,not .
- 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)
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)
- 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)
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)
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 and . So when their absolute difference is less than the required value, then (or better still ) is close enough. JRSpriggs 20:45, 30 November 2007 (UTC)
Convergence: The Babylonian method only converges for . For the series is chaotic, never converges, and is highly sensitive to both and . If you guess , the series will converge to the negative root [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)
Pell's equation
In this section, it's stated that:
- In either case, is a rational approximation satisfying
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
I think it should be stated that 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 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
- However, what is true is that there are only finitely many pairs (p, q) such that
- (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)#
new method
http://math.exeter.edu/rparris/peanut/cordic.pdf (page 16) gives a very weird way of computing square roots using trig functions -- anonymous
- 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)
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)
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 xn+1 be the average of xn and S / xn (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 xn+1 be the average of xn and the result from dividing S by xn (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)
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 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 that after more careful analysis proved inappropriate. — Glenn L (talk) 02:05, 18 January 2012 (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 x2 - 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)
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)
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)
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:
- 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)
