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.

  • 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
    This answers my question. I think I can make the algorithm I have in mind work with this.2012-01-06