Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Continuing in the same vein as Carry-free multiplication operation, a followup question is as follows (differences in bold):

Let $r = p \oplus q$ be an operation similar to multiplication, but slightly simpler: when expressed via long-multiplication the columns aren't summed up, but rather or'd (not xor) together. Nothing is carried.

$$ \left[\begin{matrix} &&p_n & ... & p_i & ... & p_2 & p_1 \\ &&q_n & ... & q_i & ... & q_2 & q_1 & \otimes\\ \hline\\ &&q_1 \cdot p_n & ... & q_1 \cdot p_i & ... & q_1 \cdot p_2 & q_1 \cdot p_1\\ &q_2 \cdot p_n & ... & q_2 \cdot p_i & ... & q_2 \cdot p_2 & q_2 \cdot p_1\\ &&&&&&&...\\ q_i \cdot p_n & ... & q_i \cdot p_i & ... & q_i \cdot p_2 & q_i \cdot p_1 & \stackrel{i}{\leftarrow} &&{\bigvee} \\ \hline \\ \\r_{2n}& ... & r_i & ... &r_4& r_3 & r_2 &r_1 & = \end{matrix} \right] $$

Using the long-multiplication-style formulation, this takes $\mathcal O\left(\max\left(\left|p\right|,\left|q\right|\right)^2\right)=\mathcal O\left(\left|r\right|^2\right)$ time. Can we do better? Perhaps we can reuse some existing multiplication algorithms, or even better.

share|cite|improve this question
this is very similar to a problem known as "boolean convolution" in savages models of computation book.... – vzn Oct 30 '13 at 17:41
@vzn can you link it here again? – Realz Slaw Oct 30 '13 at 17:42
Have you done any thinking about whether Karatsuba, FFT, etc. methods apply to this operation as well? That'd be the first thing I would try. – D.W. Oct 30 '13 at 17:51

This is equivalent to an operation known as boolean convolution. See Models of Computation page 419 defn 9.6.3.

Dunne states (p5):

Weiss 1984 and Blum 1984b obtained lower bounds for the n-point boolean convolution function which is closely related to integer multiplication.

share|cite|improve this answer

Your Answer


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.