answer to this post has not yet been answered ...i.e abt complexity.
seems log(n) to me..
correct me if i am wrong.
On Mon, Jan 16, 2012 at 8:53 AM, Gene gene.ress...@gmail.com wrote:
I'm sorry for not being specific. I meant it doesn't converge for all
roots, e.g. cube root.
On Jan 15,
@atul:
on the first look, even I thought the same.. O(log N).. and this is may be
true for the given precision.
*[-- the following may not be related to given qn.] -- but.. can u comment
on this view point..*
but.. I am thinking that, the complexity is dependent on the level of
precision
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
@Gene: Actually, Newton's Method for sqrt(a), where a 0, also
sometimes called Heron's Method, converges for every initial guess x_0
0. This is not true generally for Newton's Method, but it is true
for Newton's Method applied to f(x) = x^2 - a.
Dave
On Jan 15, 5:39 pm, Gene
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
I'm sorry for not being specific. I meant it doesn't converge for all
roots, e.g. cube root.
On Jan 15, 10:18 pm, Dave dave_and_da...@juno.com wrote:
@Gene: Actually, Newton's Method for sqrt(a), where a 0, also
sometimes called Heron's Method, converges for every initial guess x_0 0.
This