Re: Optimal square calculation?

On 1 Oct, 07:59, Chris Bore <chris.b...@xxxxxxxxx> wrote:
I have an application that involves many sums of squares. For
instance:

for (i = 0; i < N; i++
  sum += x[i]*x[i];

Is any clever optimization possible when doing sums of squares?

(The application is calculating statistics on very large 3D arrays of
16-bit integer data - typically 3 Gsamples. There are also many cases
of sums of 4th power, and squares of differences.)

It is close enough to classic MAC but I feel there may be some benefit
from the fact that only one input argument needs to be loaded, or a
trick that avoids the multiply?

At the moment this is implemented on PC workstation (multi-processor
with multi-threading) which is the required platform. Although at some
time it may be possible to review this.

Thanks,

Chris
===================
Chris Bore
ch...@xxxxxxxxxxxxxxxxxxxxxx

Thanks for the helpful replies.

The distance approximation seems to be about twice as fast as
calculating the sqrt of squares. That is:

magnitude = max(abs(I), abs(Q)) + 0.5 * min (abs(I), abs(Q));

which has an error up to 12%.

(This is based on changing the nature of the question, to 'how can I
efficiently estimate the magnitude of a vector whose cartesian
coordinates are I and Q?' That is, by avoiding the squares and square
roots and replacing them with a numerical approximation to the desired
end result.)

Can I extend the scope of the question? :-)

Many of these statistical calculations involve sums of squares etc.
They are standard operations like variance, second moments and so on.
Following the distance approximation, are there optimized routines (in
C..) that estimate things like variance, sum of squares, to some
desired (lack of) accuracy?

I have started looking at statistics libraries, but some seem far from
optimized in two senses. (1) they are actually slower than simply
writing out a simple looped expression for the desired calculation.
(2) they do not estimate, they calculate according to a formula - I
feel that there must be numerical methods to get close to these
standard measures.

To draw a parallel with DSP (with which I am more familiar than this
statistical operation) I would expect to find libraries optimized for
speed, memory, etc - as I do for instance for the FFT and derivate
transforms. The same need for very fast statistics must also exist, I
am hoping to find its products. :-)

Thanks,

Chris
===============
Chris Bore
BORES Signal Processing
www.bores.com
.

Relevant Pages

  • Re: Calculate Pearson Correlation
    ... >> I don't know much about statistics and pearson distance. ... sums of squares is called SWEEP. ...
    (sci.stat.math)
  • Re: Nonlinear Least-Squares curve-fitting
    ... containing the keyword "Portuguese Statistics" helped. ... Nonlinear Least-Squares and parameter estimation is a fairly ... the same residual sum of squares... ... a large number of data points; therefore, if the least squares function ...
    (sci.stat.math)
  • Re: Need help on combinatorial problem
    ... The basic idea is cut the 8x8 squares into 4 4x4 squares, ... In order to check whether a configuration meet ... of +1 matching the given row sums 'r', ...
    (sci.math)
  • Re: Need help on combinatorial problem
    ... The basic idea is cut the 8x8 squares into 4 4x4 squares, ... In order to check whether a configuration meet ... of +1 matching the given row sums 'r', ...
    (sci.math)
  • Re: Optimal square calculation?
    ... Is any clever optimization possible when doing sums of squares? ... the various SSE instruction sets. ...
    (comp.dsp)