Carry-free multiplication operation

Question

In long-multiplication, you shift and add, once for each $1$ bit in the lower number.

Let $r = p \otimes q$ be an operation similar to multiplication, but slightly simpler: when expressed via long-multiplication, the addition does not carry. Essentially you bitwise-xor the shifted numbers.

Like so:

$$ \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} &&{\Huge{\oplus}} \\ \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.

---

Followup: Shift-and-or multiplication operation

Answer 1

Your operation is multiplication of polynomials over $GF(2)$, i.e., multiplication in the polynomial ring $GF(2)[x]$.

For instance, if $p=101$ and $q=1101$, you can represent them as $p(x)=x^2+1$, $q(x)=x^3+x^2+1$, and their product as polynomials is $p(x) \times q(x) = x^5+x^4+x^3+1$, so $p \otimes q = 111001$.

If $p,q$ are $r$ bits long, this polynomial multiplication operation can be computed in $O(r \lg r)$ time using FFT techniques, but in practice this may not be a win unless your polynomial is extremely large. There is also a Karatsuba-style algorithm, whose complexity is something like $O(r^{1.6})$, as well as other options. The situation is somewhat analogous to integer multiplication, in that many of the same fast algorithms can be applied, but not identical.

See, e.g.,

• Wikipedia on Fast multiplication algorithms for large inputs. These methods are described in terms of multiplying two integers, but they can be transposed to apply to polynomial multiplication.

• Polynomial Multiplication, Karatsuba and Fast Fourier Transform

• When is FFT multiplication of arbitrary-precision polynomials practical?. Richard Fateman, March 14, 2006.

• Can you save time in multiplying polynomials by encoding them as integers?. Richard Fateman, January 15, 2005.

Answer 2

here is a nice/comprehensive survey of standard/best techniques in the area esp from the pov of implementation in logic gates, which shows basic optimizations including Schonhage and Strassen, but there is also an issue of practicality in the implementation.

Schonhage and Strassen [302] have described a circuit to multiply integers represented in binary that is asymptotically small and shallow. Their algorithm for the multiplication of n-bit binary numbers uses $O(n \log n \log \log n)$ gates and depth $O(\log n)$. It illustrates the point that a circuit can be devised for this problem that has depth $O(\log n)$ and uses a number of gates considerably less than quadratic in $n$. Although the coefficients on the size and depth bounds are so large that their circuit is not practical, their result is interesting...

• Savage, models of computation, binary multiplication

• powerful algorithms too complex to implement, tcs.se