October 21, 2008

Geek entry of the day

Another from the PG archives because I've got nuthin' today. As for those of you who think that that makes this day no different from any other, well, you have a point.
============================================

Have you ever been caught off guard when someone walks up to you and asks, "What's the square root of X?" Me, too. Usually, I can remember approximations for most square roots up through, uh, maybe I won't finish that statement. Anyway, sometimes the numbers are just too damn big or I need more digits after the decimal place than I can comfortably work out. It's times like that when you really need Newton's formula:

Newtons sqrt.jpg

b represents the number for which you're seeking the square root and x is your first guess. Wanna see how it all works? Of course you do! Observe:

Let's say that you need the square root of 13 and we want to be within 0.00001 of the actual value. For simplicity, we'll make x the same as b, the number we're taking the square root of.

Iterations
-----------
x=13, b=13
NewX=7, difference is 6

x=7, b=13
NewX=4.428571, difference is 2.571429

x=4.428571,b=13
NewX=3.682028, difference is 0.746544

x=3.682028, b=13
NewX=3.606345, difference is 0.075682

x=3.606345, b=13
NewX=3.6055514, difference is 0.000794

x=3.6055514,b=13
NewX=3.605551, difference <0.000001

There you have it: the square root of 13 is approximately 3.605551.

I feel better already.

Posted by Physics Geek at October 21, 2008 08:44 AM | TrackBack StumbleUpon Toolbar Stumble It!
Comments

Newton's Algorithm

(Dunno if named after Sir Isaac or not.) Useful for other things as well. The old big round Cray machines of the 80's supposedly used a variant to improve the precision of their floating divide op. If you fool around with it you can get cube roots and higher integer roots as well. Just lots of arithmetic. But arithmetic is cheaper now than it was.

The trick is finding a good pre-algo to get x-sub-zero, but this is handy when working in an environment with no square root operator. After that, the number of bits of precision in x-sub-n+1 approximately doubles with each iteration.

No, I didn't learn that in high school math.

Posted by: no, not THAT Glenn at October 21, 2008 10:49 AM