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

On Jul 17, 7:16 am, Raymond Manzoni <raym...@xxxxxxx> wrote:
pamela fluente a écrit :





I want to write a very little computer program in which computes the
geometric mean of a large amount n of numbers Xi read from some data
source.Say for istance n = 1,000,000,000,000 numbers.

GM = (X1 * X2 * ... * Xn ) ^ 1/n

GM has the dimension of any of the Xi.

I cannot do all the multiplications first, because the computer will
not hold the result.

Also I guess I cannot apply the exponent to each single Xi before
multiplication because of the large n,
with consequent imprecision and extreme slowness...

How can proceed, say in an incremental way, to compute GM. What is the
best approach.?
Can anyone propose some pseudocode?

-P

Another idea (should you fear for the time 'cost' of a logarithm) :

Let's suppose that n= 2^m then you could decompose your product
recursively (preferably without using recursivity! :-)) in square roots
of the products of two consecutive variables or square roots.

Example for n= 2^3 :
GM= sqrt(sqrt(sqrt(X1*X2)*sqrt(X3*X4))*sqrt(sqrt(X5*X6)*sqrt(X7*X8)))

Hoping one these answers will help,
Raymond- Hide quoted text -

- Show quoted text -

But if n is not a power of two, then the formula cannot be applied.

A more general recursion is derived as follows. Let g() be the
function that returns the geometric mean of its arguments. Then

g(x_1, x_2, ..., x_n) = (x_1 * x_2 * ... * x_n)^(1/n)
= (x_1 * x_2 * ... * x_m)^(1/n) * (x_(m+1) * x_(m+2) * ... * x_n)^(1/
n)
= g(x_1, x_2, ..., x_m)^(m/n) * g(x_(m+1), g_(m+2), ..., x_n)^((n-m)/
n)

We can apply the formula above recursively to find the g.m. while
multiplying only two numbers together at each step. Furthermore,
without loss of generality, we can assume that

x_1 <= x_2 <= ... <= x_n

Then

x_1 <= g(...) <= x_n,

where g(...) represents any of the intermediate g.m.'s. Thus the
formula, applied recursively, never has to deal with a result larger
than (x_n)^2 and the number of exponents n_e that must be found lies
between log_2(n) and 2*log_2(n), which is much less than n.

- MO


.

Relevant Pages

  • Re: Geometric average: how to compute it: best approach ?
    ... recursively (preferably without using recursivity! ... of the products of two consecutive variables or square roots. ... But if n is not a power of two, then the formula cannot be applied. ... The first 2 are quite slow, but, on the other hand, the logarithm has ...
    (sci.math)
  • Re: Geometric average: how to compute it: best approach ?
    ... geometric mean of a large amount n of numbers Xi read from some data ... source.Say for istance n = 1,000,000,000,000 numbers. ... I cannot do all the multiplications first, ... :-)) in square roots of the products of two consecutive variables or square roots. ...
    (sci.math)
Loading