Talk:Methods of computing square roots

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class Low Priority  Field: Analysis

Contents

[edit] 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!

[edit] 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)

[edit] 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 xn for the iterations wherever it is applicable. -- Meni Rosenfeld (talk) 10:55, 10 September 2006 (UTC)

[edit] 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)

[edit] 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 "&middot;" or "&times;" 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)

[edit] 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)

[edit] "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)

[edit] Continued fractions

JRSpriggs, perhaps you can explain:

  1. What made you modify the equation for an + 1? It is now more cumbersome and less correct, since what we know is a0,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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)