Log in

No account? Create an account

Previous Entry | Next Entry

Random musing

If x is an approximation to the square root of n, then (x/2 + n/2x) is a closer approximation.


( 8 comments — Leave a comment )
Nov. 30th, 2007 10:19 pm (UTC)
Clearly untrue. Zero is a (poor) approximation of root 2, and 0/2 + 2/0 is not a closer one.

I suspect it fails in all cases where x < 1. If we take 0.1 as an approximation of root 2, 0.1/2 + 2/0.2 is 10.05, which is considerably further from 1.414....

Nov. 30th, 2007 10:23 pm (UTC)
Thinking about it, I now suspect that your formula gives a result that is closer on a log scale rather than a linear one. Neither of my counter-examples would disprove this.
Nov. 30th, 2007 10:45 pm (UTC)
Indeed. 'tis the Newton-Raphson method!

Re previous comments, it only fails if you choose zero as your first approximation, as then you end up dividing by 0. But you'd have to be very silly to do that.

Sorry, it only completely fails if you choose x=0. If you choose x very small as drplotka discusses, it will initially go wrong, but will then start converging when you iterate.
Nov. 30th, 2007 10:47 pm (UTC)
This is the Newton–Raphson method, I think.

f(x) = x^^2 - n = 0

f'(x) = 2x

f(x)/f'(x) = x/2 -n/2x

next approx = x - f(x)/f'(x) = x/2 + n/2x

Nov. 30th, 2007 10:48 pm (UTC)
Bah, beaten to the punch by writing stupid ascii equations
Dec. 1st, 2007 12:27 pm (UTC)
In general
If x is an approximation to the kth root of n then ((k-1)x + n/x^(k-1))/k is better....

Dec. 1st, 2007 04:37 pm (UTC)
I'm showing my math-geek, but I <3 this post and the comments. :)
Dec. 3rd, 2007 12:51 am (UTC)
As others have pointed out, this is Newton-Raphson, which means that when it's good it's very very good and when it's bad it's awful. It's no good as a basis for extracting decimal square roots in one's head (a restful motorway driving exercise for some), although for finding rational approximations it's quite pleasing.

e.g. n=2: 1 -> 3/2 -> 17/12 -> (17/24 + 12/17), which is, hmm, 577/408? And the next step would take me a good 20 miles down the M6.
( 8 comments — Leave a comment )

Latest Month


Powered by LiveJournal.com
Designed by yoksel