1
$\begingroup$

Suppose wehave two sequences:

$$(a_0, a_1, a_2, \dots, a_{2^n-1})$$ $$(b_0, b_1, b_2, \dots, b_{2^n-1})$$

We also have the following sum:

$$\sum_{k=0}^{2^n-1}{a_k \cdot b_k}$$

I'd like to know the fastest way to get this sum:

$$\sum_{k=0}^{2^n-1}{(a_k+c) \cdot (b_k+d)}$$

MY THOUGHTS AND WORK

I thought that some statiscal information could be crucial. We can suppose that other statistics are handy - I will try to find a way to get them. I'm mainly interested in the fastest way to calculate this problem.

I figured that if we could get some kind of geometric mean and perhaps standard deviation for both sequences, we might somehow be able to add $c$ and $d$ to these values and simply multiply them together. I'm not very handy with statistics though, so I really don't know if this is possible.

WHAT I'D LIKE TO DO

I'm hoping that this could become a community wiki so that we could list all methods that might have a shot at being fast, and use feedback to find the best answer.

2 Answers 2

1

You probably have three meaningful choices: work out each term of $$\sum_{k=0}^{2^n-1}{(a_k+c) \cdot (b_k+d)}$$ and then take the sum, or work out the four terms $$\sum_{k=0}^{2^n-1}{a_k \cdot b_k}+d\sum_{k=0}^{2^n-1}{a_k}+c\sum_{k=0}^{2^n-1}{b_k}+c\cdot d \cdot 2^n ,$$ or the three terms $$\sum_{k=0}^{2^n-1}{a_k \cdot b_k}+ \sum_{k=0}^{2^n-1}(d \cdot a_k+c \cdot b_k) +c\cdot d \cdot 2^n. $$ My money would be on the second.

  • 2
    Both time and space complexity of the first one (equation #2 in your answer) are way better that the one you preferred. The first one requires $O(2^n)$ more additions. The second one requires order $O(2^n)$ more multiplications. Addition is always faster than multiplication, and requires less space to store intermediate results. In particular, if $a, b \in \mathbb{Z},$ and $\log \mid a \mid, \log \mid b \mid \in n,$ then computing $a+b$ takes $O(n)$ time, where computing $ab$ takes $O(n \log n \log \log n)$ time using FFT, and the result $ab$ needs $2n,$ bits of storage.2012-01-06
  • 0
    @J.D.: when I said "My money would be on the second" I meant the middle of three.2012-01-06
  • 0
    Oops. I'm sorry. I got confused2012-01-06
3

Since it is a finite sum you can multiply out the brackets and split up the sums, to give

$$\sum_{k=0}^{2^n-1} (a_k+c)(b_k+d) = \sum_{k=0}^{2^n-1} a_kb_k + d\sum_{k=0}^{2^n-1} a_k + c\sum_{k=0}^{2^n-1} b_k + 2^ncd$$

So we calculate $\sum a_k$ (which is $2^n$ times the arithmetic mean of the $a_k$s) and $\sum b_k$ (analogous), and then it's just simple arithmetic.

But I'm not sure what you mean about finding the "fastest way".


There is another perspective: you can define $$ \begin{align} \mathbf{a} &= (a_0, a_2, \dots, a_{2^n-1}) \\ \mathbf{b} &= (b_0, b_2, \dots, b_{2^n-1}) \end{align}$$

Then we have $$\sum_{k=0}^{2^n-1} a_kb_k = \mathbf{a} \cdot \mathbf{b}$$

If, further, we define $$\mathbf{1} = (\underbrace{1, 1, \dots, 1}_{2^n})$$ then we get $$\sum_{k=0}^{2^n-1} (a_k+c)(b_k+d) = (\mathbf{a}+c\mathbf{1}) \cdot (\mathbf{b} + d\mathbf{1})$$ I'm not sure if this geometric picture helps, but it's something you could investigate.

  • 0
    I can't tell if this answers your question. If not, please let me know here and I'll change or delete my response appropriately.2012-01-06
  • 0
    This answers my question. I think I can make the algorithm I have in mind work with this.2012-01-06