Re: Vector Rotation

On Mon, 27 Feb 2006 13:39:50 -0500, Carlos Moreno
<moreno_at_mochima_dot_com@xxxxxxxxxxxxxx> wrote:

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)

It's pretty intuitive. As long as the function used for N-R has no
inflection points near the zero crossing, and the initial estimate is
well away from any local minimum or maximum, it will converge. For the
square root I would use x² - K = 0, which is well-behaved.

After posting, I thought of a similar method based on the same
idea -- instead of the dot product, use the vector product (cross
product)

I also experimented with a similar idea. From what I've seen, though,
it looks like CORDIC will be at least as simple. The nice thing about
CORDIC is that it only uses shifts and adds, with multiplication by a
gain constant applied after all of the other processing is complete.
CORDIC can also compute arctan(y/x) directly. So now I'm thinking maybe
use the fact that tan(Ø) = |A x B|/(A · B) to allow CORDIC to rotate the
vector.

Another point about a binary search, which occurred to me after my last
message, is that it is so very similar to a one-bit divide iteration
that I might as well just do the division.

Anyway, I kind of doubt that either one of these two approaches
for binary search may be more efficient than N-R for the sqrt
and the inverse;

Yeah, it's looking that way.

Many thanks again for your input.

Greg Berchin
.