Re: Programming question : Newton's method

On Fri, 29 Oct 1999, James Nelson wrote:

> It may not be called Newton's method strictly, but the same idea works. We
> used this on a 8051 to compute the square root of a 12 bit number. In three
> iterations, it was dead correct to one bit.

        No math book required. Just generally iterating is the oldest
trick in the book for calculating the value of functions like sqrt.

        Say you want to calculate the sqrt of 2. So, what you do is:

        Start with an initial guess, say 0.
        Check: Is 0^2 = 2 (Computing the square of a number is
easy.) Nope, it's too low, so increment the guess by some amount (since
sqrt is a monotonically increasing function) if you are too high, you
decrement your guess, and if you are too low, you increment your
guess.
        You keep doing this until the difference between your guess
squared and the number that you are trying to compute the sqrt of is
within some tolerance.

        Maybe this is what you were talking about, but it's not Newton's
method (also called Newton-Raphson iteration.) I'm not sure if it has any
"official name."

Joe

> > I can get the math book out if we need more specifics.
> -James
>
>
> ----- Original Message -----
> From: <jwelser@ccwf.cc.utexas.edu>
> To: <vectorlist@lists.cc.utexas.edu>
> Sent: Friday, October 29, 1999 10:12 AM
> Subject: Re: Programming question : Newton's method
>
>
> > On Fri, 29 Oct 1999, James Nelson wrote:
> >
> > > I noticed the conversation. Since nobody mentioned it. I will.
> > >
> > > I good method for solving many equations is "Newton's method". I can
> get a
> > > math book out on this, but it more or less involves this:
> > >
> > > Make a guess of the square root based on whatever simple criteria.
> > > square it
> > > what is the difference between that and the expected answer?
> > > adjust the number according to how far off you are
> > > square it
> > > what is the difference between that and the expected answer?
> > > adjust the number according to how far off you are
> > > square it
> > > what is the difference between that and the expected answer?
> > > adjust the number according to how far off you are
> > > square it
> > >
> > > Generally, if correctly implemented, it is accurate to several decimal
> > > places after 3 iterations.
> > > This is probably more code than a look up table, but you should be
> familiar
> > > with this technique for solving complex equations.
> >
> > Yeah, computing the first derivative of the function is generally
> > more complicated than a lookup table ;)
> >
> > Actually, for this example, Newton-Raphson approximation wouldn't
> > work. Newton-Raphson is generally used to find the roots of a function:
> >
> > i.e. For which values of x are <insert your nasty, but not too bad
> > to differentiate function here> = 0
> >
> > Joe
> >
> > >
> > >
> > > ----- Original Message -----
> > > From: jeff hendrix <jhendrix@Quark.Com>
> > > To: <vectorlist@lists.cc.utexas.edu>
> > > Sent: Thursday, October 28, 1999 5:14 PM
> > > Subject: RE: Programming question
> > >
> > >
> > > > Thanks for all the replies.
> > > > These posts have got some of the wheels turning in my brain.
> > > > Just a few comments.
> > > >
> > > > Previously I was think of using a "reverse" lookup table like Zonn
> > > > suggested, and I might go that route now after he suggested doing a
> binary
> > > > search on it. (binary search had slipped my mind and I was planning on
> > > > starting at one end and just moving through the table, which would
> have
> > > > averaged 128 loops) I'm actually currently doing lots of calculations
> with
> > > > data from lookup tables. I.E.- collision detection.
> > > >
> > > > I had considered using gravity in something like 16 steps, but I still
> > > need
> > > > the straight line distance to determine which ring I'm in. (as well as
> to
> > > > normalize the vectors)
> > > >
> > > > The problem with doing equations like this
> > > > if (distanceX < 10)
> > > > scaleX = 1;
> > > > if (distanceX < 20)
> > > > scaleX = 2;
> > > > if (distanceX < 30)
> > > > scaleX = 4;
> > > > ...etc...
> > > > speed.x += gravity_constant/scaleX;
> > > > is that it doesn't take into consideration the actual distance from
> the
> > > sun.
> > > > You could be 500 y units away and 10 x units and it will end up
> pulling
> > > > harder in the x direction. Both vectors must first be normalized to
> > > properly
> > > > divide the gravitational pull between them.
> > > >
> > > > Rodger, I also couldn't get this to properly work, but if you do find
> the
> > > > proper equation, it might be worth a try.
> > > > Take the smaller of xlength or ylength, multiply it time 3, divide
> > > > by 2, and add the result to the larger of xlength or ylength. The
> > > > result is a close approximation of the square root of the sum of
> > > > the squares.
> > > >
> > > > I have also toyed with the idea of doing linear gravity, I'm just
> afraid
> > > > that you won't be able to orbit properly. (I get upset in gravitar
> because
> > > > you can't quite orbit the planet that you can fly in circles around)
> > > >
> > > > Clay, I threw a few numbers into these equations
> > > > "real dist" = sqrt(x^2+y^2), "fake dist" = ((X*2)+(Y*2))/4
> > > > and in a circular obit, the gravity gets stronger when you have only
> an x
> > > or
> > > > y offset and weaker when your at one of the 45 degree angles from the
> sun.
> > > > (making the gravity rings a square turned 45 degrees). But this might
> be
> > > ok
> > > > consider how little time it takes to calculate.
> > > >
> > > >
> > > > thanks
> > > > -jeff
> > > >
> > > >
> > >
> >
> > ------------------------------------------------------------------
> > Joseph J. Welser jwelser@ccwf.cc.utexas.edu
> > Design Engineer -- Crystal Semiconductor Corporation
> > Ph.D. Student in E.E. -- University of Texas at Austin
> > Work: jwelser_at_crystal.cirrus.com http://www.crystal.com
> > P.O. Box 17847; Austin, TX 78760
> > ------------------------------------------------------------------
> >
> >
>

------------------------------------------------------------------
Joseph J. Welser jwelser@ccwf.cc.utexas.edu
Design Engineer -- Crystal Semiconductor Corporation
Ph.D. Student in E.E. -- University of Texas at Austin
Work: jwelser_at_crystal.cirrus.com http://www.crystal.com
P.O. Box 17847; Austin, TX 78760
------------------------------------------------------------------
Received on Fri Oct 29 11:07:14 1999