3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ in binary multiplication. isnt it true that matrix multiplication methods, which have been well studied, are all applicable as binary multiplication methods? dont recall seeing this pointed out anywhere.... you might like Savage Models of Computation which treats this problem specifically.... $\endgroup$ – vzn Oct 30 '13 at 16:51
  • $\begingroup$ @vzn binary multiplication ... as opposed to what? I am pretty sure you can easily extend this to other bases. $\endgroup$ – Realz Slaw Oct 30 '13 at 16:56
  • $\begingroup$ @vzn wrt. matrix multiplication, how can that help here though? Sure matrix multiplication can help for 0-1 matrices, but I don't see how they are directly applicable to integer-multiplication; aside from some similarity to the recursive integer multiplication algorithms, from which matrix multiplication can be compared, I don't know of any results that say that advances in matrix multiplication help for integer multiplication. Also, though perhaps unrelated, AFAIK, 0-1 matrix multiplication has the same bounds as regular matrix multiplication; except perhaps that it bounds the element sizes. $\endgroup$ – Realz Slaw Oct 30 '13 at 16:59
  • $\begingroup$ not sure exactly except that shonhage/strassen are cited [below] as having one of the faster algorithms & theyve done work on matrix multiplication also, think there is some connection in the techniques... $\endgroup$ – vzn Oct 30 '13 at 17:22
5
$\begingroup$

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.,

$\endgroup$
-1
$\begingroup$

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...

$\endgroup$
  • 1
    $\begingroup$ This is for regular multiplication, and I am aware of fast multiplication algorithms. My question was about a modified form of multiplication. $\endgroup$ – Realz Slaw Oct 30 '13 at 17:22
  • $\begingroup$ it answers your question "can we do better?" ... maybe you need to clarify better how what you are looking for is not satisfied by fast multiplication algorithms. $\endgroup$ – vzn Oct 30 '13 at 17:25
  • $\begingroup$ It only answers the question "can we do better" if you first show how you can modify FFT/Schönhage–Strassen algorithms can actually do this type of multiplication. $\endgroup$ – Realz Slaw Oct 30 '13 at 17:27
  • $\begingroup$ ok, oops misunderstood the exact question. $\endgroup$ – vzn Oct 30 '13 at 17:40
  • 1
    $\begingroup$ This answer doesn't answer the question. This answer talks about integer multiplication. The question is not about integer multiplication. It is about a different sort of multiplication operation (which I show in my answer is polynomial multiplication). $\endgroup$ – D.W. Oct 30 '13 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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