'how to calculate XOR (dyadic) convolution with time complexity O(n log n)

enter image description here

“⊕” is the bitwise XOR operation.

I think Karatsuba’s algorithm may be used to solve the problem, but when I try to use XOR instead of "+" in the Karatsuba’s algorithm, it is tough to get the sub-problem.

algorithmdivide-and-conquer


Solution 1:[1]

The convolution theorem gives you

F(C) = F(A) . F(B)

where F is a Fourier-related transform, in this case the Hadamard transform, and . is point-wise multiplication. Using the fast Walsh–Hadamard transform, you can compute F(A), F(B), and finally C (using the inverse), in O(n log n) operations. The point-wise multiplication is simply O(n).

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Nelfeal

Related Questions