Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
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. –  user2468 Jan 6 '12 at 0:53
    
@J.D.: when I said "My money would be on the second" I meant the middle of three. –  Henry Jan 6 '12 at 0:56
    
Oops. I'm sorry. I got confused –  user2468 Jan 6 '12 at 0:57
add comment

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.

share|improve this answer
    
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. –  Clive Newstead Jan 6 '12 at 0:34
    
This answers my question. I think I can make the algorithm I have in mind work with this. –  Matt Groff Jan 6 '12 at 0:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.