# Did Newton Crack Square Roots For Us??? **URL:** \ **Category:** Factual Questions\ **Created:** [May 21, 2003, 4:19am UTC](https://boards.straightdope.com/t/did-newton-crack-square-roots-for-us/176499 "2003-05-21T04:19:39Z")\ **Posts on this page:** 11\ **Page:** 2
**Author:** ![Orbifold](https://avatars.discourse-cdn.com/v4/letter/o/779978/32.png) [@Orbifold](https://boards.straightdope.com/u/Orbifold)\ **Post date:** [May 21, 2003, 3:44pm UTC](https://boards.straightdope.com/t/did-newton-crack-square-roots-for-us/176499/21 "2003-05-21T15:44:30Z")
> [@](#): > > \*Originally posted by Engywook \* > \*\*I’ve a feeling I’ll be smacking my head in a mere moments, but how does this method give you the square root of anything? > > Let _y_ be length of diagonal. > Let _x_ be length of side of square. > > 2x[sup]2[/sup] = y[sup]2[/sup] > From this, I don’t see a way to get to the square root of either _x_ or _y_ being equal to anything but something times the square root of _y_ or _x_. \*\* Well, this method gives you the square root of two, if x = 1. But you’re right, for arbitrary square roots you need a more general construction. For example: suppose AB is a line segment of length n. Extend AB to a line segment AC with length n+1. Construct a circle with diameter AC, and let P be one of the points where the perpendicular to AC at B intersects the circle. Then the length of PB will be exactly the square root of n. ---
**Author:** ![sailor](https://avatars.discourse-cdn.com/v4/letter/s/a587f6/32.png) [@sailor](https://boards.straightdope.com/u/sailor)\ **Post date:** [May 21, 2003, 3:55pm UTC](https://boards.straightdope.com/t/did-newton-crack-square-roots-for-us/176499/22 "2003-05-21T15:55:51Z")
> [@](#): > > \*Originally posted by Desmostylus \* > \*\*Right shift the exponent field. > > “sufficiently close to the solution” has a precise meaning in terms of the convergence of Newton’s method. Look it up. :rolleyes: \*\* I guess rolleyes were on sale and you got quite a few you can give away. Still you have not answered my question of how to program an algorithm which is simpler and more efficient than the one I proposed. Please post one that is simpler and will converge in fewer steps. Thank you. ---
**Author:** ![sailor](https://avatars.discourse-cdn.com/v4/letter/s/a587f6/32.png) [@sailor](https://boards.straightdope.com/u/sailor)\ **Post date:** [May 21, 2003, 4:10pm UTC](https://boards.straightdope.com/t/did-newton-crack-square-roots-for-us/176499/23 "2003-05-21T16:10:50Z")
Another point I do not quite understand. “Guessing a number M” or doing M=(1 + n/2) or whatever method you use to get a first M serves to give you the first pair to work with, the pair being M and M/N. The next step is to make M=(M+M/N)/2 and reiterate. If you "right shift the exponent field"as you propose, you are effectively dividing by 2 so that your first M is N/2 and your next step is to make M= (M + M/2)/2 which always equals !.5_M = 3_N which can be got without so much hassle. Your next step will yield M= (N/2 + 3\*N)/2 etc. Unless I am missing something this does not seem to converge. Can I get an explanation of how this works? (preferably without a rolleyes) ---
**Author:** ![sailor](https://avatars.discourse-cdn.com/v4/letter/s/a587f6/32.png) [@sailor](https://boards.straightdope.com/u/sailor)\ **Post date:** [May 21, 2003, 4:23pm UTC](https://boards.straightdope.com/t/did-newton-crack-square-roots-for-us/176499/24 "2003-05-21T16:23:19Z")
I have implemented both algorithms, strating out with M=N/2 and M=(1+N/2) and they both converge to six figures in about the same number of steps although sometimes M=(1+N/2) will do it in one or two less but I guess that is not a huge difference. I had always used M=(1+N/2) because that is what I was taught somewhere and never really thought about it. I still don’t get the rolleyes though. Maybe someone else can explain it to me? ---
**Author:** ![Newton\_meter](https://avatars.discourse-cdn.com/v4/letter/n/57b2e6/32.png) [@Newton\_meter](https://boards.straightdope.com/u/Newton_meter)\ **Post date:** [May 21, 2003, 6:37pm UTC](https://boards.straightdope.com/t/did-newton-crack-square-roots-for-us/176499/25 "2003-05-21T18:37:58Z")
> [@](#): > > \*Originally posted by sailor \* > **If you "right shift the exponent field"as you propose, you are effectively dividing by 2…** Right shift the **exponent**. That’s an approximation of the square root, not division by two. ---
**Author:** ![sailor](https://avatars.discourse-cdn.com/v4/letter/s/a587f6/32.png) [@sailor](https://boards.straightdope.com/u/sailor)\ **Post date:** [May 21, 2003, 6:52pm UTC](https://boards.straightdope.com/t/did-newton-crack-square-roots-for-us/176499/26 "2003-05-21T18:52:34Z")
> [@](#): > > \*Originally posted by Newton meter \* > \*\*Right shift the **exponent**. That’s an approximation of the square root, not division by two. \*\* Thanks, now I see it. I was not thinking right. ---
**Author:** ![Newton\_meter](https://avatars.discourse-cdn.com/v4/letter/n/57b2e6/32.png) [@Newton\_meter](https://boards.straightdope.com/u/Newton_meter)\ **Post date:** [May 21, 2003, 7:17pm UTC](https://boards.straightdope.com/t/did-newton-crack-square-roots-for-us/176499/27 "2003-05-21T19:17:12Z")
S’okay. If you have the ability to just right shift the exponent (of, say, and IEEE 754 single precision float) then I don’t think you’d bother with Newton’s method, anyway. ---
**Author:** ![raygirvan](https://avatars.discourse-cdn.com/v4/letter/r/ac91a4/32.png) [@raygirvan](https://boards.straightdope.com/u/raygirvan)\ **Post date:** [May 21, 2003, 9:46pm UTC](https://boards.straightdope.com/t/did-newton-crack-square-roots-for-us/176499/28 "2003-05-21T21:46:50Z")
**Engywook** :smack: Sorry, my brain is going, as others have noticed. I was groping for the construction described by **Orbifold** , which is Proposition 13 from Book VI of Euclid’s Elements. ---
**Author:** ![bonzer](https://avatars.discourse-cdn.com/v4/letter/b/45deac/32.png) [@bonzer](https://boards.straightdope.com/u/bonzer)\ **Post date:** [May 21, 2003, 9:47pm UTC](https://boards.straightdope.com/t/did-newton-crack-square-roots-for-us/176499/29 "2003-05-21T21:47:56Z")
> [@](#): > > \*Originally posted by Jinx \* > If you want the square root of 18, for example, your first number in the solution will be the root of the closest square…I forget the exact method after this obvious step. I’ll see if I can locate it in a reference book. In any sense, I was taught it was developed by Newton. I suspect you may be thinking of [this method](http://home.attbi.com/~rthamper/html/body_squareroot2.htm). However, it predates Newton and is, I suspect, also ancient. As may be the equivalent method for cubics roots, which Fibonacci published in 1202. There’s also a generalisation to arbitrary roots given by Stifel in 1544 - see A.W.F. Edwards, _Pascal’s Arithmetical Triangle_ (1987; Johns Hopkins, 2002, 5-7). Aside from Newton-Raphson, the other method Newton invented for extracting roots was the binomial expansion, which can express roots as the sum of an infinite series. You approximate by truncating the series at some finite number of terms. [This page](http://www.mathpages.com/home/kmath190.htm) has more information on classical methods for the extraction of roots. ---
**Author:** ![raygirvan](https://avatars.discourse-cdn.com/v4/letter/r/ac91a4/32.png) [@raygirvan](https://boards.straightdope.com/u/raygirvan)\ **Post date:** [May 21, 2003, 10:00pm UTC](https://boards.straightdope.com/t/did-newton-crack-square-roots-for-us/176499/30 "2003-05-21T22:00:35Z")
More on sources here at [Big Square Roots](http://www.merriampark.com/bigsqrt.htm); it mentions evidence that the ‘long division’ method goes back at least to the 13th century Arab mathematician Ibn al-Banna. ---
**Author:** ![Desmostylus](https://avatars.discourse-cdn.com/v4/letter/d/c57346/32.png) [@Desmostylus](https://boards.straightdope.com/u/Desmostylus)\ **Post date:** [May 22, 2003, 2:12pm UTC](https://boards.straightdope.com/t/did-newton-crack-square-roots-for-us/176499/31 "2003-05-22T14:12:11Z")
> [@](#): > > \*Originally posted by Newton meter \* > \*\*S’okay. If you have the ability to just right shift the exponent (of, say, and IEEE 754 single precision float) then I don’t think you’d bother with Newton’s method, anyway. \*\* This problem has to be addressed whenever you’re porting a compiler to a machine that doesn’t have hardware floating point support. And Newton’s method is a very easy way to do it. The implementation depends on what floating point representation you’re using, of course. The basic steps are: 1. separate the mantissa and exponent. 2. the mantissa will be in a narrow range, e.g. 0.5 to 1, so use a linear interpolation to guess the mantissa of the root. e.g. root mantissa = 0.42 + 0.59 \* mantissa. 3. right shift the exponent, and take note of whether it’s odd or even. 4. reassemble the root’s mantissa and exponent, and if the exponent was odd, multiply the result by 1.4142. 5. you now have a root accurate to about 3 decimal places. Iterate through Newton’s method 3 times, and that’s it. [Previous page](https://boards.straightdope.com/t/did-newton-crack-square-roots-for-us/176499.md?page=1)