Question 302455 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Compute arithmetic-geometric mean of arbitrary array length in JS

The arithmetic-geometric mean of two numbers is defined as the limit of a sequence of arithmetic and geometric means.

Here is what I have for one iteration with two numbers:

function agm2(n)
{
    /**
     * @param {Float64Array(2)} n
     */
    var x0 = n[0], x1 = n[1];

    var a0 = (x0 + x1) / 2;
    var a1 = Math.sqrt(x0 * x1);

    return new Float64Array([a0, a1]);
}

Per this thread on MathOverflowDotNet, we can generalise this function to get the iteration-by-iteration function for an arbitrary number using elementary symmetic polynomials and binomial coefficients.

For three variables:

function agm3(n)
{
    /**
     * @param {Float64Array(3)} n
     */
    var x0 = n[0], x1 = n[1], x2 = n[2];

    var a0 = (x0 + x1 + x2) / 3;
    var a1 = Math.sqrt((x0 * x1 + x1 * x2 + x0 * x2) / 3);
    var a2 = Math.pow(x0 * x1 * x2, 1 / 3);

    return new Float64Array([a0, a1, a2]);
}

Four variables:

function agm4(n)
{
    /**
     * @param {Float64Array(4)} n
     */
    var x0 = n[0], x1 = n[1], x2 = n[2], x3 = n[3];

    var a0 = (x0 + x1 + x2 + x3) / 4;
    var a1 = Math.sqrt((
                      x0 * x1
                    + x0 * x2
                    + x0 * x3
                    + x1 * x2
                    + x1 * x3
                    + x2 * x3
        ) / 6);
    var a2 = Math.pow((
                      x0 * x1 * x2
                    + x0 * x1 * x3
                    + x0 * x2 * x3
                    + x1 * x2 * x3
        ) / 4, 1 / 3);
    var a3 = Math.pow(x0 * x1 * x2 * x3, 1 / 4);

    return new Float64Array([a0, a1, a2, a3]);
}

And five variables:

function agm5(n)
{
    /**
     * @param {Float64Array(5)} n
     */
    var x0 = n[0], x1 = n[1], x2 = n[2], x3 = n[3], x4 = n[4];

    var a0 = (x0 + x1 + x2 + x3 + x4) / 5;
    var a1 = Math.sqrt((
                      x0 * x1
                    + x0 * x2
                    + x0 * x3
                    + x0 * x4
                    + x1 * x2
                    + x1 * x3
                    + x1 * x4
                    + x2 * x3
                    + x2 * x4
                    + x3 * x4
        ) / 10);
    var a2 = Math.pow((
                      x0 * x1 * x2
                    + x0 * x1 * x3
                    + x0 * x1 * x4
                    + x0 * x2 * x3
                    + x0 * x2 * x4
                    + x0 * x3 * x4
                    + x1 * x2 * x3
                    + x1 * x2 * x4
                    + x1 * x3 * x4
                    + x2 * x3 * x4
        ) / 10, 1 / 3);
    var a3 = Math.pow((
                      x0 * x1 * x2 * x3
                    + x0 * x1 * x2 * x4
                    + x0 * x1 * x3 * x4
                    + x0 * x2 * x3 * x4
                    + x1 * x2 * x3 * x4
        ) / 5, 1 / 4);
    var a4 = Math.pow(x0 * x1 * x2 * x3 * x4, 1 / 5);

    return new Float64Array([a0, a1, a2, a3, a4]);
}

And six variables:

function agm6(n)
{
    /**
     * @param {Float64Array(5)} n
     */
    var x0 = n[0], x1 = n[1], x2 = n[2], x3 = n[3], x4 = n[4], x5 = n[5];

    var a0 = (x0 + x1 + x2 + x3 + x4 + x5) / 6;
    var a1 = Math.sqrt((
                      x0 * x1
                    + x0 * x2
                    + x0 * x3
                    + x0 * x4
                    + x0 * x5
                    + x1 * x2
                    + x1 * x3
                    + x1 * x4
                    + x1 * x5
                    + x2 * x3
                    + x2 * x4
                    + x2 * x5
                    + x3 * x4
                    + x3 * x5
                    + x4 * x5
        ) / 15);
    var a2 = Math.pow((
                      x0 * x1 * x2
                    + x0 * x1 * x3
                    + x0 * x1 * x4
                    + x0 * x1 * x5
                    + x0 * x2 * x3
                    + x0 * x2 * x4
                    + x0 * x2 * x5
                    + x0 * x3 * x4
                    + x0 * x3 * x5
                    + x0 * x4 * x5
                    + x1 * x2 * x3
                    + x1 * x2 * x4
                    + x1 * x2 * x5
                    + x1 * x3 * x4
                    + x1 * x3 * x5
                    + x1 * x4 * x5
                    + x2 * x3 * x4
                    + x2 * x3 * x5
                    + x2 * x4 * x5
                    + x3 * x4 * x5
        ) / 20, 1 / 3);
    var a3 = Math.pow((
                      x0 * x1 * x2 * x3
                    + x0 * x1 * x2 * x4
                    + x0 * x1 * x2 * x5
                    + x0 * x1 * x3 * x4
                    + x0 * x1 * x3 * x5
                    + x0 * x1 * x4 * x5
                    + x0 * x2 * x3 * x4
                    + x0 * x2 * x3 * x5
                    + x0 * x2 * x4 * x5
                    + x0 * x3 * x4 * x5
                    + x1 * x2 * x3 * x4
                    + x1 * x2 * x3 * x5
                    + x1 * x2 * x4 * x5
                    + x1 * x3 * x4 * x5
                    + x2 * x3 * x4 * x5
        ) / 15, 1 / 4);
    var a4 = Math.pow((
                      x0 * x1 * x2 * x3 * x4
                    + x0 * x1 * x2 * x3 * x5
                    + x0 * x1 * x2 * x4 * x5
                    + x0 * x1 * x3 * x4 * x5
                    + x0 * x2 * x3 * x4 * x5
                    + x1 * x2 * x3 * x4 * x5
        ) / 6, 1 / 5);
    var a5 = Math.pow(x0 * x1 * x2 * x3 * x4 * x5, 1 / 6);

    return new Float64Array([a0, a1, a2, a3, a4, a5]);
}

If you run this over and over again for any set of strictly positive real numbers, eventually all of the coefficients will tend towards a single value.

My question is, how can I generalise this so that I don’t have to define separate functions for each length?

The agm function should take a Float64Array of arbitrary length, and then output a Float64Array with the correct values for one iteration.

Implementing binomial coefficients is no problem since I know how to write the factorial function for non-negative whole numbers, but how do I properly implement the elementary symmetric polynomials for an arbitrary array length beyond the first and last terms?

Tags:

2

Answers


  1. Chosen as BEST ANSWER
    0

    First, we define the binomial coefficient over non-negative whole numbers:

    function binom(n, r)
{
    var range = function(from, to) {
        var ar = [];
        for (var i = from; i <= to; i++)
        {
            ar.push(i);
        }
        return ar;
    };

    n = Math.round(Math.abs(n));
    r = Math.round(Math.abs(r));

    return ((n < r) ? 0 : range(n - r + 1, n).reduce((x, y) => {
        return x * y;
    }) / range(1, r).reduce((x, y) => {
        return x * y;
    }));
}

    Then, using the code that gog kindly provided, I got:

    function agm(vars)
{
    /**
     * @param {Float64Array} vars
     */
    var size = vars.length;
    var sums = {}, output = new Float64Array(size);

    for (let i = 1; i < (1 << size); i++)
    {
        let product = 1, len = 0;

        for (let j = 0; j < size; j++)
        {
            if (i & (1 << j))
            {
                product *= vars[j];
                len++;
            }
        }
        (sums[len] = sums[len] ?? []).push(product);
    }

    for (let i = 1; i <= size; i++)
    {
        let s = sums[i], o = 0;
        for (let j = 0; j < s.length; j++)
        {
            o += s[j];
        }
        output[i - 1] = Math.pow(o / binom(size, i), 1 / i);
    }

    return output;
}

  2. 0

    I’m not sure I’ve got the math right, but it appears you can proceed like this:

    Generate all integers from 1 to 2^n. For each integer, check which bits are set, multiply corresponding elements and place the result into the k-th bin, where k is the number of set bits (basically, you’re generating a powerset here).

    Once complete, compute an average of each bin.

    Example (using string concatenation instead of multiplication for clarity):

    let sums = {}
let vars = [1, 2, 3, 4]
let size = vars.length


for (let i = 1; i < (1 << size); i++) {
    let product = '', len = 0

    for (let b = 0; b < size; b++) {
        if (i & (1 << b)) {
            product += String(vars[b])
            len += 1
        }
    }
    (sums[len] = sums[len] ?? []).push(product)
}

console.log(sums)

// now just compute an average of each `sum`
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search