Re: Geometric average: how to compute it: best approach ?

pamela fluente a écrit :

This *seems* to me the same as Peter suggestion ("You could still do
it in blocks if "), if I am getting right (?). The remarks about the
bounds are quite useful.

At this point, if I do it using blocks and recursion, wouldn't it be,
in any case, better to use sum and logarithms?

I heard that exponentiation e multiplication are very costly for the
computer. So I could replace the products with the sums of
logarithms ? On the other hand, there are n logarithms to take and
probably that's also very costly.

So to recap, which is the final advice about the way to go?

-P


It will depend of the poster of course! :-)

The recursive method requires nearly n exponentiations (see Duncan's answer or my initial example with n=8) and is costly.

David Bernier's idea is interesting too and could be implemented with functions like frexp and/or _logb in visual .net (http://msdn2.microsoft.com/en-us/library/w1xfschh(VS.80).aspx) but this is a kind of logarithm again (in base 2) and the drawback could be that both the mantissa and the exponent will have to be multiplied and added (and compared!) in parallel.

I should have began with the simplest method : add all the logarithms without additional test (well... your Xn should be positive else take the absolute value!).

But my recommandation will be : collect the product of a fixed number of terms of the product (if you are sure that this will not overflow! I'll take for example 20) and only then take the logarithm (in C something like) :
Pr = X[0] * X[1] * .. * X[19];
S += log(Pr); // or log(fabs(Pr))
X += 20; // X is a pointer on the Xn array
and loop until less than 20 terms remaining
add the remaining logs
divide by n
take the exponential!

This should be quick (written this way!) since we will have only one logarithm for 19 products. The eventual absolute value will be applied before the log.

Should you be interested by the time cost of logarithms on a Pentium architecture here is a speedtest for a pentium 4 at 2.8 GHz where one finds that (for floating point operations) addition and multiplication are of the same order (148 Mflops), division slower (65 Mflops) and y*log_2(x) of order 23 Mflops (*) : http://www.obliquity.com/computer/speedtest.html

A product and a sqrt as I proposed (case n =2^m only...) should give with the datas provided something like 45 Mflops and looks much less interesting that the second alternative...

Anyway actual time should depend largely of your implementation (repeating the same instructions multiple times before looping, avoiding explicit and implicit tests could speed up all this!).

Hoping it helped more!
Raymond


(*) y is 1 for log_2 else the multiplication does the base conversion. The opcode for y*log_2(x) is fyl2x on intel pentium (description in page 473 of http://www.intel.com/design/processor/manuals/253666.pdf or here http://www.ray.masmcode.com/tutorial/fpuchap11.htm
the number of cycles are given here : http://www.agner.org/optimize/instruction_tables.pdf)
Some architectures implement a faster log2 function with reduced precision (perhaps ia64 I'm not sure...).
.

Relevant Pages

  • Re: Geometric average: how to compute it: best approach ?
    ... A more general recursion is derived as follows. ... better to use sum and logarithms? ... Multiplication and division are very quick; exponentiation is slow. ...
    (sci.math)
  • Re: Are logarithms still useful?
    ... Electronic calculators have made them unecessary for this ... In what ways are logarithms still useful in mathematics? ... with good computers, direct multiplication is faster. ... exponentiation is generally done by using logarithms ...
    (sci.math)