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

On Tue, 17 Jul 2007 05:03:44 -0700, beeworks wrote:

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


<snip>
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
I don't understand the last part. It seems to me that the number of
exponentiations will be of the same order as the number of data.
If E(n) is the number of exponentiations then if the recursion is
g(x_1, x_2, ..., x_n) =
g(x_1, x_2, ..., x_m)^(m/n) * g(x_(m+1), g_(m+2), ..., x_n)^((n-m)/n
then we get E(n) = E(m) + E(n-m) + 2
with E(1) = 0 we get E(2^n) = 2^(n+1)-2

Even in the ideal case where n is a power of 2 and the recursion is
g(x_1, x_2, ..., x_2n) =
sqrt( g(x_1, x_2, ..., x_n) * g(x_(n+1), g_(m+2), ..., x_2n))
we have E(2n) = 2*E(n)+1
and we get E(2^n) = 2^n-1


.

Relevant Pages

  • Re: Prime Buddies
    ... The first cross section is all 1's. ... Next,how do you determine if the integer is a power or not. ... You've introduced recursion into the stepping ... what is so special about recursion that it allows us to ...
    (sci.math)
  • Re: Another way to do x^n
    ... \ raise float to positive integer power ... Recursion unnecessarily obfuscates the algorithm. ... # conditionally multiply stack top by x, ...
    (comp.lang.forth)
  • Re: Prime Buddies
    ... The first cross section is all 1's. ... Next,how do you determine if the integer is a power or not. ... You've introduced recursion into the stepping ... what is so special about recursion that it allows us to ...
    (sci.math)
  • Re: Grammatical Recursion
    ... Miguel> equivalent to iteration. ... recursion has higher expressive power than ... be expressed as a form of recursion. ... My claim implies that there are cases in which recursion can ...
    (sci.lang)
  • Re: Signal Handling
    ... Jose Pina Coelho writes: ... > It allows an application to cleanup correctly before the power runs out. ... is called frequenctly to interrupt ... In order to understand recursion you must first understand recursion. ...
    (comp.unix.aix)