Velocity Reviews > C++ > How to Solve a Root...

# How to Solve a Root...

Mark
Guest
Posts: n/a

 12-02-2005
always wondered how a computer might go about doing this...
i'm taking calculus at university... and we went over newton's method.
i found this interesting...

------------------------------
#include <cstdlib>
#include <iostream>
#include <cmath>

using namespace std;

double f1(double x);
double f2(double x, double y);

int main(int argc, char *argv[])
{
double x = 5;
cout << f1(x) << endl;
cout << sqrt(x) << endl;

system("PAUSE");
return EXIT_SUCCESS;
}

double f1(double x)
{
return f2(x,x/2);
}

double f2(double x, double y)
{
double z = y - (y*y-x)/(2*x);
if( y == z ) return z;
else return f2(x,z);
}
---------------------------

will work for cube roots and others if you just tweak the formula.

Mark
Guest
Posts: n/a

 12-02-2005
(just thought i'd share. no question involved)

int2str@gmail.com
Guest
Posts: n/a

 12-02-2005

Mark wrote:
> always wondered how a computer might go about doing this...
> i'm taking calculus at university... and we went over newton's method.
> i found this interesting...
>
> ------------------------------
> #include <cstdlib>
> #include <iostream>
> #include <cmath>
>
> using namespace std;
>
> double f1(double x);
> double f2(double x, double y);
>
> int main(int argc, char *argv[])
> {
> double x = 5;
> cout << f1(x) << endl;
> cout << sqrt(x) << endl;
>
> system("PAUSE");
> return EXIT_SUCCESS;
> }
>
> double f1(double x)
> {
> return f2(x,x/2);
> }
>
> double f2(double x, double y)
> {
> double z = y - (y*y-x)/(2*x);
> if( y == z ) return z;

I thought it was bad to directly compare floats?

> else return f2(x,z);
> }
> ---------------------------
>
> will work for cube roots and others if you just tweak the formula.

I love recursion as much as the next guy, but in this mathematical case
I see huge potential for a stack overflow. Maybe this should be rolled
into a loop instead. Might actually look cleaner.

Cheers,
Andre

gottlobfrege@gmail.com
Guest
Posts: n/a

 12-02-2005

Mark wrote:
> always wondered how a computer might go about doing this...
> i'm taking calculus at university... and we went over newton's method.

> will work for cube roots and others if you just tweak the formula.

You might want to look into the Runge-Kutta method. Quite robust. I
coded it up once many years ago...

Mark
Guest
Posts: n/a

 12-02-2005
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:

> I thought it was bad to directly compare floats?

i have no idea... never heard that before.

> I love recursion as much as the next guy, but in this mathematical case
> I see huge potential for a stack overflow. Maybe this should be rolled
> into a loop instead. Might actually look cleaner.

well. when i've worked these out on paper... they only took about 6 or
8 "loops" to get it accurate to about 8 decimal places.... it really
shouldn't stack that much at all. *i think*

but yes, maybe a for loop would be more efficient...but... oh well.

(E-Mail Removed) wrote:
> You might want to look into the Runge-Kutta method. Quite robust. I
> coded it up once many years ago...

Runge-kutta eh? perhaps i shall look into it. you wouldnt happen to
know what method cmath uses, would you?

i suppose i could open the library and check myself.... if i can
understand it.

Mark P
Guest
Posts: n/a

 12-02-2005
Mark wrote:
> (E-Mail Removed) wrote:
>
>
>>I thought it was bad to directly compare floats?

>
>
> i have no idea... never heard that before.
>

"Bad" may be too strong, but it should be done with care. A computer
will compare 2.0 and 1.999999 as unequal; sometimes this is undesirable.
Often rather than comparing for equality it makes more sense to see if
the absolute value of the difference is less than some small number (say
0.0001).

>
> (E-Mail Removed) wrote:
>
>>You might want to look into the Runge-Kutta method. Quite robust. I
>>coded it up once many years ago...

>

Runge-Kutta is a numerical method for solving differential equations.
Quite different from root finding.

-Mark

=?ISO-8859-15?Q?Juli=E1n?= Albo
Guest
Posts: n/a

 12-02-2005
Mark wrote:

> well. when i've worked these out on paper... they only took about 6 or
> 8 "loops" to get it accurate to about 8 decimal places.... it really
> shouldn't stack that much at all. *i think*

Seems not fast enough. Some years ago, talking about fixed point
calculations for writing graphics demos, I recommended to try the Hero
method (a Newton's variant specific for square roots), and the result was
that just 4 iterations were enough for 3-d calculus.

programming.

--
Salu2

Michiel.Salters@tomtom.com
Guest
Posts: n/a

 12-02-2005

Mark P wrote:

> Runge-Kutta is a numerical method for solving differential equations.
> Quite different from root finding.

Not really. Often these forms can be converted into each other,
certainly
for the trivial forms used here. And sqr(x)=y implies y*y-x = 0, which
is
truly trivial. Runga-Kutta takes three points, IIRC, which means it's a
single iteration for second-degree functions like that. Newton uses two
points, which means it's only a single iteration for first-degree
functions
(lines).

HTH,
Michiel.

int2str@gmail.com
Guest
Posts: n/a

 12-02-2005

Mark wrote:
> (E-Mail Removed) wrote:
> > I love recursion as much as the next guy, but in this mathematical case
> > I see huge potential for a stack overflow. Maybe this should be rolled
> > into a loop instead. Might actually look cleaner.

>
> well. when i've worked these out on paper... they only took about 6 or
> 8 "loops" to get it accurate to about 8 decimal places.... it really
> shouldn't stack that much at all. *i think*

I've measured it with a non-trivial number like '12345.6789' and it
took 3669 iterations. That's quite a bit of stack pressure.

>
> but yes, maybe a for loop would be more efficient...but... oh well.
>

Here's my entry (based on your formula):

double my_sqrt( const double & x )
{
double y = 0;
double z = 1;

while ( y != z )
{
z = y;
y = y - (y * y - x) / (2 * x);
}

return y;
}

Cheers,
Andre

mlimber
Guest
Posts: n/a

 12-02-2005
Mark P wrote:
> Mark wrote:
> > (E-Mail Removed) wrote:
> >
> >
> >>I thought it was bad to directly compare floats?

> >
> >
> > i have no idea... never heard that before.
> >

>
> "Bad" may be too strong, but it should be done with care. A computer
> will compare 2.0 and 1.999999 as unequal; sometimes this is undesirable.
> Often rather than comparing for equality it makes more sense to see if
> the absolute value of the difference is less than some small number (say
> 0.0001).

See the FAQ:

http://www.parashift.com/c++-faq-lit...html#faq-29.17

Cheers! --M