Re: Vector Rotation


"Carlos Moreno" <moreno_at_mochima_dot_com@xxxxxxxxxxxxxx> wrote in message
news:lGHMf.11242$rg2.537803@xxxxxxxxxxxxxxxxxxxxxx
Greg Berchin wrote:

Both square root and division can be done via Newton-Raphson
if you can do multiplications (for the division, use N-R to
find the inverse, then multiply).


A good suggestion. For some reason I seem to overlook Newton-Raphson as
one of the "obvious" choices; I guess I've never liked the fact that it
can diverge in some cases. Should be no such problems in this
situation.

I'm pretty certain that for the square root, N-R is guaranteed
to work (don't know of any proof, but I wouldn't be surprised
if it has been rigorously proven) -- if you start with an initial
estimate of x (for the sqrt(x)) if x > 1, and 1 if x < 1.


Hello Guys,

Actually the Newton - Raphson method is quadratically convergent in the
limit of the point of convergence. However, it can be painfully slow. For
example try using this for sqrt(x) with x near zero. Here the derivative
causes a real problem. The region of convergence is very small for x small.
And it is easy to have a seed fall outside of this region, hence your algo
diverges.

One alternative is to find 1/sqrt(x), another is using an algo for directly
finding the square root by pairing bits and using trial subtractions. I've
seen this actually done in hardware for a quick square root. Each iteration
yields one bit of the square root.

Clay



.

Relevant Pages

  • Re: Coding of ordered pairs
    ... actual facts (long ago I did analyse them with truncating arithmetic). ... truncating arithmetic and N-R for the calculation of the square root. ... N-R does not converge. ... their algorithm is slightly wrong. ...
    (sci.math)
  • Re: Coding of ordered pairs
    ... part of mathematics, but it is in the field of numerical mathematics. ... actual facts (long ago I did analyse them with truncating arithmetic). ... truncating arithmetic and N-R for the calculation of the square root. ... N-R does not converge. ...
    (sci.math)
  • Re: Vector Rotation
    ... Both square root and division can be done via Newton-Raphson ... you only need two multiplications and one addition -- no ... you do a binary search of the scaling factor f ... required precision, multiply each of B's coordinates times f. ...
    (comp.dsp)
  • Re: Vector Rotation
    ... Then iterating with N-R: ... so you trade-in the square root for another division. ...
    (comp.dsp)
  • Re: sqrt algo
    ... >> Can anyone shed light on an Algorithm for finding out the square root of a ... There is one to compute square roots "by hand", like multiplications and ...
    (comp.programming)