Re: Programming question : Newton's method

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.

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
> ------------------------------------------------------------------
>
>
Received on Fri Oct 29 09:32:38 1999