To find sqrt(a), this is equivalent to Newton's Method with
f(x)=x^2 - a.
Newton is:
x_{i+1} = x_i + f'(x_i) / f'(x_i).
So you have
x_{i+1} = x_i + (x_i^2 - a) / (2 x_i) = (x + a/x) / 2,
which is just what the Babylonian method says to do.
Newton's method roughly doubles the number of significant bits in the
answer with every iteration _when it converges_. The problem is that
though it works fine for sqrt(), it won't converge for arbitrary f.
There's
a huge literature on this, which I'll let you find yourself.
On Jan 15, 4:22 pm, Ankur Garg <ankurga...@gmail.com> wrote:
> Hello
>
> I was going through this link
>
> http://www.geeksforgeeks.org/archives/3187
>
> Wonder what is the time complexity for this..?Can anyone explain >
>
> Regards
> Ankur
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
