# Quickly obtaining sums of sets of numbers

We are given a set of $$n$$ bits, call them $$a_1$$, $$a_2$$,...,$$a_n$$. We are also given a set of $$m$$ sums, where the sums $$s_1$$, $$s_2$$,...,$$s_k$$,...,$$s_m$$ are given as sums of some of the bits. For example:

$$s_k = a_3 + a_5 + a_{17} + a_{22} + a_{35}$$

There is more structure to the sums, however. The sums are split into $$m / \alpha$$ groups, where each sum is in only one group. For example, and to make things easier, sums $$s_1$$, $$s_2$$,...,$$s_{\alpha}$$ are in group 1, sums $$s_{ \alpha + 1}$$,...,$$s_{2\alpha}$$ are in group 2, and so on. Then we know that each bit will occur exactly once in each group.

So for example, the bit $$a_1$$ will appear in each group, the bit $$a_2$$ will appear once in each group, and so on...

QUESTION

How fast can we calculate all of the sums?

MY IDEAS

If we assume that there are $$\alpha$$ sums in each group, then there are at most $$2^\alpha$$ combinations of bits. For example, if there are two sums, we know that there are four combinations of bits:

(0) Bits that are not in either sum

(1) Bits that are in sum 1 ($$s_1$$), but not in sum 2 ($$s_2$$)

(2) Bits that are not in sum 1 ($$s_1$$), but are in sum 2 ($$s_2$$)

(3) Bits that are in both sums.

Thus we need at most $$n$$ additions to calculate the sums of each of the $$m / \alpha$$ groups. So our total time is at most $$n(m/\alpha)$$ additions, since there are $$m/\alpha$$ groups.

However, I believe that we can do better! I'm guessing that we can also use subtraction and sums from different groups to arrive at a much better algorithm.

• – asds_asds Nov 23 '19 at 6:03

We split our list of bits $$a_1$$, $$a_2$$, $$\dots$$, $$a_n$$ into approximately $$n / \beta$$ collections (these could also be called groups, but I make the distinction so that we know that these are different from the groups above). Here we set $$\beta = \log{(m/(\log{(mn)})}$$ In other words, the first collection consists of the first $$\beta$$ bits $$a_1$$, $$a_2$$, $$\dots$$, $$a_{\beta}$$. The second collection consists of the second $$\beta$$ bits $$a_{\beta+1}$$, $$a_{\beta+2}$$, $$\dots$$, $$a_{2\beta}$$, and so on.
We find all possible sums for each collection, of which there are approximately $$2^{\log{(m/(\log{(mn)}))}} = m/(\log{(mn)})$$. We then calculate each of these sums exactly. If we're careful, we can calculate each sum in constant time by adding or subtracting one bit from a sum with all other bits the same.
Thus we use roughly $$m/(\log{(mn)})$$ space to store each solution, times $$\log{\log{(mn)}}$$ maximum bits per solution, times $$n / \log{(mn)}$$ different collections.
The running time should be approximately $$O \left( \frac{mn \log{ \log{ (mn)}}}{\log{(mn)})^2} \right)$$ if I did my calculations right.