如何计算具有时间复杂度O(n log n)的XOR(二进)卷积 [英] how to calculate XOR (dyadic) convolution with time complexity O(n log n)
问题描述
⊕"是按位XOR运算.
"⊕" is the bitwise XOR operation.
我认为Karatsuba的算法可以用来解决问题，但是当我尝试使用XOR而不是"+"时，在唐津算法中，很难找到子问题.
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.
推荐答案
卷积定理给你
F(C) = F(A) . F(B)
其中 F 是与傅立叶相关的变换，在本例中为Hadamard变换，而.是逐点乘法.使用快速Walsh–Hadamard变换，您可以计算F(A)， F(B)，最后是 C (使用反码)，以 O(n log n)操作.逐点乘法就是 O(n).
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).
这篇关于如何计算具有时间复杂度O(n log n)的XOR(二进)卷积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
