Martin Kirk (mlk@asu.edu) wrote:

>I would like to normalize a vector as follows:
>
>        X = x(1)*i + x(2)*j
>
>                         x(1)*i                  x(2)*j
>        X(norm) = --------------------- + ---------------------
>                  sqrt[x(1)^2 + x(2)^2]   sqrt[x(1)^2 + x(2)^2]
>
>That is to say that I normalize by dividing each vector component by the
>magnitude of the original vector.
>
>        What I need here is either a good approach to doing the square
>root function on a pic or some other approximation for finding vector
>magnitudes which is efficiently calculated.

Martin:

The first thing you need to do is decide whether you really DO need to
normalize the vector in the first place.  For instance, if your ultimate
objective were to draw lines from one point to another, or to calculate PWM
duty-cycles (hard to believe that those two are equivalent problems, but they
are), you could simply use the Bresenham algorithm, which requires no
multiplications or divisions, let alone square-roots.

Assuming that you DO need to perform the calculation as you've described,
there are a number of ways to determine square roots.  Last year, Klaus
Borchers sent me a very clever 16-bit square-root finder that executes in 127
cycles and requires only 35-or-so instructions; so far, this is the best I've
seen, although I don't think Klaus wants it publicized.

The "I'll Buy You a Beer at the Embedded Systems Conference If You Can Figure
Out How This Works" challenge I posted on the Microchip BBS last year
computed square roots using just one 16-bit subtract (with a test for
negative results), an 8-bit increment, and an "add 2".  The program makes an
average of 60 passes (maximum of 127 passes) through this 3-operation loop,
so it's pretty fast.

Walter Banks, who wrote the MPC C-compiler, came up with a method that's a
little slower, but which gives more-precise non-integer results.  C source
code for his square-root routine is available on his BBS (519 888-7626), but
it may be overkill for your application.

Unless you're REALLY hurting for clock cycles, you should probably just use
the implementation of the Newton-Raphson method that's included in
Microchip's Embedded Control Handbook.  As written, it sorta sucks, but you
can improve it substantially by:

    Allowing up to 11 iterations through its loop.  It only uses 10... Not
    enough to guarantee covergence.

    Adding a check for convergence.  It doesn't know when it's found the
    answer, so it does all 10 iterations anyway.

    Seeding it with a good initial guess, like 181 (I THINK that's the
    most-optimum number... It's CERTAINLY better than x/2, which is what the
    routine currently uses.

Oh, by the way... You realize, of course, that your equation is equivalent
to:

                     x(1)*i + x(2)*j
        X(norm) = ---------------------,
                  sqrt[x(1)^2 + x(2)^2]

so you only have to compute the square-root once... Right?

-Andy

P.s.  I just thought of a REALLY fast way to do square-roots, but it needs a
      512-byte lookup table.  If such a large table wouldn't be a problem for
      you, let me know and I'll give you the details.

--
Andrew Warren - fastfwd@ix.netcom.com
Fast Forward Engineering, Vista, California