3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ this is very similar to a problem known as "boolean convolution" in savages models of computation book.... $\endgroup$
    – vzn
    Oct 30, 2013 at 17:41
  • $\begingroup$ @vzn can you link it here again? $\endgroup$
    – Realz Slaw
    Oct 30, 2013 at 17:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Oct 30, 2013 at 17:51

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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