Problem Detail: 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 Oleft(maxleft(left|pright|,left|qright|right)^2right)=mathcal Oleft(left|rright|^2right)$ time. Can we do better? Perhaps we can reuse some existing multiplication algorithms, or even better.
Followup: Shift-and-or multiplication operation
Asked By : Realz Slaw
Answered By : D.W.
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/16578
