# Expressing sums of products in terms of sums of powers

I'm working on building some software that does machine learning. One of the problems I've come up against is that, I have an array of numbers:

$[{a, b, c, d}]$

And I want to compute the following efficiently:

$ab + ac + ad + bc + bd + cd$

Or:

$abc + abd + acd + bcd$

Where the number of variables in each group is specified arbitrarily. I have a method where I use:

$f(x) = a^x + b^x + c^x + d^x$

And then compute:

$f(1) = a + b + c + d$

$(f(1)^2-f(2))/2 = ab + ac + ad + bc + bd + cd$

$(f(1)^3 - 3f(2)f(1) + 2f(3))/6 = abc + abd + acd + bcd$

$(f(1)^4 - 6f(2)f(1)^2 + 3f(2)^2 + 8f(3)f(1) - 6f(4))/24 = abcd$

But I worked these out manually and I'm struggling to generalize it. The array will typically be much longer and I'll want to compute much higher orders.

Besides using the Newton's identities as mentioned in @Soarer's comment, you could also consider an algorithm to generate all combinations. E.g. to compute $$abc+abd+acd+bcd$$ you would generate 3-combinations out of 4 elements. Staying with this example, you have already an array of numbers $a = [a_0, a_1, a_2, a_3]$ so you would generate all possible triples of indexes $(i, j, k), i < j < k$ and then multiply and add $a_i * a_j * a_k$. This method could be numerically more robust then Newton's identities because only additions and no subtractions/divisions are used. The efficiency could also be favourable but this would require more analysis. There are perhaps still more efficient algoritms.
• Maybe I'm misunderstanding what you are saying. Say I have an array with 100 elements. If I understand you correctly, you want me to enumerate over ever possible combination that has n elements in it and sum the multiplication. If n is 4, that's 3921225 combinations. With the other method I can do it by creating 3 new arrays and summing each one, then applying the equations above which is O(nm). – dan_waterworth Sep 5 '11 at 13:44