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
.