This is some work I did for a paper, but later decided to exclude. It might still be of interest to someone so I choose to publicize it here. This problem is about summing vectors in a space of dimension . We are only allowed to use exactly vectors from a box containing vectors. Assume that an addition operation of vectors of dimension requires work. If we are going to sum over all possible such vectors, we will hit the same point in space several times because it does not matter in what order we sum the vectors together. This is done by giving the vectors some order in which the should occur in the sum. For instance, adding is ok, but is not. Removing the redundant ones, gives us unique entries. This will take operations to compute all possible points in space that is reachable by addition of exactly vectors. However, one can do better than this. The idea is to reuse already computed values. How? We perform addition between once and then generate all possible weight vectors containing . This is performed recursively, thus, we perform the addition only once and so forth. The recursive algorithm is pretty straightforward (but also pretty inefficient):
function f(sum, this, left) for all i in interval (this, p] if left == 0: do something with sum + vectors[i] else f(sum + vectors[i], i, left-1)
In order to make it efficient, one has to consider the divide-and-conquer version. This will be omitted, because it is a technical aspect. The important question is: how much does it help?
What is the gain of this? POW! Here’s a lemma…
The improvement factor is given by
Proof. First, we make a choice of all possible pairs. Since the vector has weight we cannot choose among the last . This gives possible pairs. In the next step we check all possible triples, i.e. as we are not allowed to pick from the last positions. Since we have performed additions with all pairs, the addition . Repeating this idea, we end up with total summations.
The asymptotic improvement factor is
Proof. We have that
which directly gives the Corollary. Well… so what? The impact of this is that one can perform the additions in operations. The interesting thing to note here is that if is big, we will practically never sum together more than two vectors in order to produce something that actually is sum of vectors. In other words, the summation procedure becomes independent of the number of vectors (say constant complexity ) that are being summed together. Only the number of weight vectors depends on .