Hey, i was trying to implement the sqrt function in c, and this was what i came across, and it works abs fine.
But i dont get this , is this a standard logic based on Taylor, Maclaurin or something ?
Is this more of a programming question or a Math formula(which has proof) and has just been put into code.
g2=n/2;
do
{
g1=g2;
g2=(g1+n/g1)/2;
}
while((g1-g2)!=0);
printf("The root of %f is ",n);
printf("%f",g2);
}It is a standard logic based on a Newton-Raphson method. Here is how it works:
We are trying to solve an equation
x^2 - n = 0
Given an iteration X0, the next iteration X1 is an x-intercept of a tangential at X0. In a general form the tangential is
(y - Y0)/(x - X0) = f'(X0)
In our case Y0 is X0^2 - n and f' is 2*X0, that is
(y - X0^2 + n)/(x - X0) = 2*X0
For x-intercept, y is 0:
(-X0^2 + n)/(x - X0) = 2 * X0
or
n - X0^2 = 2*x*X0 - 2*X0^2
or
x = (X0 + n/X0)/2
which is your formula.
hey nezachem thanks a lot for that.
I did find about the Newton-Raphsson method after posting, but none of those explanations were as precise and clear as urs. Thanks a lot for that.
Is there a method to find the log of a number like this ?
I mean, i want to be able to write code to find the log of a number.
On a lighter note , there is a reference to the Newton-Raphsson method in the movie 21
Yes and no. Of course there is a N-R formula for a logarithm, but it involves calculating an exponent at each iteration; that makes it way less attractive than a square root one.
A log n is a solution of exp(x) = n. Applying the same logic as above, you'd arrive to X1 = X0 + n/exp(X0) - 1 If you have a good exponentiator, you're all right. Otherwise, it may become tricky.
hey nezachem, thanks for that. Yes , i followed ur advice and was able to reach ur answer along the same lines.
I also tried for cube root of x and got the solution as
x=(n/x0^2 + 2x0)/3; :)
I tried for y=sinx and got the sol as
x=-tanx0 + x0
I dont get it,
1)does this method work for every function in the world ?
2)What are the cons of this method ?
Is it that, you have to keep on doing iteratively to get a better answer all the time ?
3)Can u probably give me a couple of examples where this doesnt work ?
I mean, i am able to find the answer to literally everything using this that, i really cant understand why you would need anoter method to approximate functions
N-R is a very powerful method. It is easy to implement, it converges fast, it doesn't even need a closed form: it is possible to work directly from the initial equation
X1 = X0 - Y0/f'(X0)
and approximate the derivative numerically.
The problem with N-R is that sometimes it doesn't converge at all. This chapter of a Wiki gives some good examples. A proof of convergence in a given case could be very hard and painful.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.