?

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.

Comments

( 8 comments — Leave a comment )
drplokta
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....

drplokta
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.
smhwpf
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.
andrewsherman
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





andrewsherman
Nov. 30th, 2007 10:48 pm (UTC)
Bah, beaten to the punch by writing stupid ascii equations
akicif
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....

blackinkedwords
Dec. 1st, 2007 04:37 pm (UTC)
I'm showing my math-geek, but I <3 this post and the comments. :)
nickbarnes
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

March 2019
S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930
31      

Tags

Powered by LiveJournal.com
Designed by yoksel