How can I optimize vector normalization in a Molecular Modeling program?

Mike Percy mpercy at scires.com
Wed Nov 10 18:20:39 EST 1999


Xiaohui Xue wrote:
> 
> Instead of l^2 norm, use l^1 norm in your normalization and relevant
> computation.
> 
> For vector {x_n},
> 
> l^2 norm of {x_n} = sqrt( x(1)^2 + x(2)^2 + .... + x(n)^2 ), which
> involves multi and sqrt in the computation.
> 
> l^1 norm of {x_n} = (abs(x(1)) + abs(x(2)) + ... + abs(x(n))), the
> computation of which is simplified.
> 
> In addition, l^1 norm is equivalent to l^2 norm in a strong sense.
> 
> Please let me know if it helps.
> 
> Xiaohui

Use a different sqrt() routine.  The one provided in most C libraries is coded
similarly to one in Plauger's Standard C Library book.  Instead, use a 1/sqrt()
function, which is often much quicker to compute and often has hardware
assists.  Plus, the result is often in the form you want anyway, that is, you
usually are doing {x_n} / norm.  By using a 1/sqrt() function, you can write
{x_n} * one_over_norm.  Avoiding the division can be a big benefit (you also
avoid division in the 1/sqrt() computation).

The "normal" (pardon the pun) way of computing sqrt() is a Newton's method with
3 iterations, but each iteration requires division.  Newton's method for
computing 1/sqrt(x) needs more iterations (5 seems to work well for me) and a
good initial estimate (I have hardware assist in PowerPC frsqrte instruction!),
but uses only addition and multiplication so comes out way ahead.  The standard
sqrt that came with my compiler runs in about 1500ns; my sqrt_r() routine runs
in about 600ns, although part of that speedup might be that I do not check for
NaN/Inf (do check for 0).

Just in case you might be doing it, do not use pow() to square the numbers...

-- 
"I don't know about your brain, but mine is really...bossy."
Mike Percy, Senior Computer Scientist, Scientific Research Corp.




More information about the Molmodel mailing list