math - 大整数的 OR 乘法

Question

两个 n 位数字 A 和 B 的乘法可以理解为移位的总和:

 (A << i1) + (A << i2) + ... 

其中 i1, i2, ... 是 B 中设置为 1 的位数。

现在让我们用 OR 替换 PLUS 以获得我实际需要的新操作:

 (A << i1) | (A << i2) | ... 

此操作与存在许多更快算法(例如 Schönhage-Strassen)的常规乘法非常相似。
我在这里介绍的操作算法是否类似？

数字的大小为 6000 位。

编辑:
出于某种原因，我没有发表评论的链接/按钮(知道为什么吗？)所以我将编辑我的问题。
我确实为上面定义的操作寻找比 O(n^2) 更快的算法。
是的，我知道这不是普通的乘法。

Answer 1

有没有类似的算法？我想可能不是。

有什么方法可以加快速度超过 O(n^2) 吗？可能。如果你认为一个数 A 是 A(x) = Σanxn 的类似物，其中 an 是 A 的二进制数字，那么你的按位或运算(我们称之为 A ⊕ B )可以表示如下，其中“⇔” "模拟"是什么意思

A ⇔ A(x) = Σanxn

B ⇔ B(x) = Σbnxn

C = A ⊕ B ⇔ C(x) = f(A(x)B(x)) = f(V(x)) 其中 f(V(x)) = f(Σvnxn) = Σu(vn)xn 其中如果 vn = 0，则 u(vn) = 0，否则 u(vn) = 1。

基本上，您所做的相当于将两个多项式相乘，然后识别所有非零项。从位串的角度来看，这意味着将位串视为零或一的样本数组，convolving两个数组，并折叠非零的结果样本。有 O(n log n) 的快速卷积算法，例如使用 FFT，这里的“折叠”步骤是 O(n) ......但不知何故我想知道快速卷积的 O(n log n) 评估将某些东西(如大整数的乘法)视为 O(1)，因此您实际上不会获得更快的算法。要么是这样，要么是增长阶数的常数太大，以至于您必须拥有数千位才能获得任何速度优势。 ORing 就是这么简单。

编辑:似乎有一种叫做“二进制卷积”的东西(例如，参见 this book)在这里听起来非常相关，但我找不到任何与其背后理论的良好链接以及是否有快速算法。

编辑 2:也许该术语是“逻辑卷积”或“按位卷积”...这里是 page from CPAN (废话!)与 Walsh 和 Hadamard 变换一起谈论它，它们有点相当于傅立叶变换的按位……嗯，不，这似乎是 XOR 而不是 OR 的模拟。