Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $S$ be a set of integers. $|S|=n$.

Can we find the product $\prod_{a,b\in S} a+b$ faster than naively add all pairs then multiply them one by one? By faster, I mean use less than $O(n^2)$ arithmetic operations.

If it's possible, can that algorithm work for any commutative semiring?

share|cite|improve this question
You might be better off at or . If you do cross-post, add a link here too. – user55085 Feb 15 '13 at 11:25
up vote 1 down vote accepted

Well, a repeated product is best done by recursively splitting the set of terms in half*, computing the products in each half, then multiplying the result, but only if the products become big enough that fast multiplication algorithms become relevant.

Of course, this is the same number of arithmetic operations either way. But it is still computational work overall.

*: half is best computed by total size of the numbers rather than simply how many

We could construct the polynomial

$$ f(x) = \prod_{s \in S} (x + s) $$

(keep in mind my advice about repeated products when computing this product!)

Now, the product you seek to compute is

$$ \prod_{s \in S} f(s) $$

The set of values $\{ f(s) | s \in S \}$ could be computed by a fast "multipoint evaluation" algorithm.

Recall that the resultant $\mathop{\text{Res}}(g(x),h(x))$ of two monic polynomials is the product

$$ \prod (\alpha - \beta) $$

where $\alpha$ and $\beta$ range over the roots of $g(x)$ and $h(x)$ respectively. So we could also compute the product by

$$ \mathop{\text{Res}}(f(x), f(-x)) $$

I haven't attempted to compute the time complexity of these algorithms. I expect the resultant to be the best of the methods I describe both in terms of time complexity and number of arithmetic operations.

All of these techniques can be adapted directly, I think, to any commutative ring. I know very little about computational algebra in semirings, but I find it very plausible the middle algorithm would only require a little bit of adaptation (although I'd be worried about the existence of fast polynomial multiplication algorithms), and a little bit plausible that there is a variation on resultants that would work.

share|cite|improve this answer
If I'm not mistaken, the middle one would use $O(n \log n)$ arithmetic operations. I can't find anything on how many arithmetic operations are required to find the resultant of a polynomial. I'm not familiar with computational algebra, but it seems it's quite difficult to find time complexity analysis of algorithms and express it in a way so CS people would understand... – Chao Xu Feb 15 '13 at 9:17

Couldn't you count the exponents for each of the elements of S? Assuming the different cases where the pairwise sums are symmetric a + b and b + a being counted twice or once, you could calculate the exponents for each of the elements of s, and then using fast exponentiation for each of the elements, and construct the sum of the terms.

You might also get extra mileage out of factoring the elements into powers of generators, if that is possible in the objects you describe.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.