@Bharat: It can be proven that Newton's method for square root, x(n+1) = (x(n) + a / x(n))/2, always converges to sqrt(a) if a > 0 and x(0) > 0. It is not difficult, so let e(n) = x(n) - sqrt(a), the error in the n-th iteration, and find the recurrence for e(n+1) in terms of e(n) and a. You should get e(n+1) = e(n)^2 / (2*(e(n) + sqrt(a))). You can then observe that if x(0) > 0, then e(1) >= 0, and if e(n) > 0 then 0 < e(n+1) < e(n) / 2, proving convergence. You can further observe that if e(n) is "small," then convergence is quadratic: e(n+1) = O(e(n)^2). Dave
On Monday, January 14, 2013 2:09:22 AM UTC-6, bharat wrote: > @Don : But, newton's formulae doesn't always converge.. if our guess is > bad enough, it may diverge also. > > On Tue, Jan 8, 2013 at 8:30 PM, Don <dond...@gmail.com <javascript:>>wrote: > >> Sure, >> >> Let's try two examples: >> x=1,038,381,081 >> >> The last digit is 1, so continue >> Now start with y=10,000 because that is half as many digits as x. >> y0 = 10,000 >> y1 = 56919 >> y2 = 37581 >> y3 = 32605 >> y4 = 32226 >> y5 = 32226 >> y6 = 32223 >> y7 = 32223 >> >> Y6=Y7 so you are done. Now square y7 giving 1,038,321,729. That is not >> equal to x, so x is not a perfect square. >> >> >> Second case >> x=1,038,579,529 >> Last digit is 9, so continue. >> y1 = 10000 >> y2 = 56928 >> y3 = 37585 >> y4 = 32608 >> y5 = 32229 >> y6 = 32227 >> y7 = 32227 >> >> 32227^2 = x, so x is a perfect square. >> >> Don >> >> >> On Jan 5, 8:08 am, bala bharath <bagop...@gmail.com> wrote: >> > @Don, >> > Can u explain with an Example...? >> > >> > With regards, >> > >> > Balasubramanian Naagarajan, >> > >> > Chettinad >> > College of Engg & Tech. >> > >> > >> > >> > >> > >> > >> > >> > On Sat, Jan 5, 2013 at 1:48 PM, Malathi <malu....@gmail.com> wrote: >> > > Check this. It might help. >> > >> > >http://www.johndcook.com/blog/2008/11/17/fast-way-to-test-whether-a-n. >> .. >> > >> > > On Sat, Jan 5, 2013 at 1:47 AM, Don <dondod...@gmail.com> wrote: >> > >> > >> start with a guess y. If you can arrange for y to be about half the >> > >> > > -- >> > >> > > With Regards, >> > > Malathi >> > >> > > -- >> >> -- >> >> >> > --
