algorithm - 使用整数乘法的 bool 卷积

Question

在 Bringmann16 中介绍的算法中文章建议使用 bool 卷积来获取两组正整数的总和。

在上面的工作中，两个集合都表示为位掩码 - indicator vectors .如果将它们表示为 1 + bit(0) * x + bit(1) * x^2 + ... + bit(i) * x^(i + 1) + ... + bit 形式的多项式(n - 1) * x^n，那么他们的乘积确实只包含那些单项式，其幂是第一组、第二组或总和中的数字。乘积的系数对于子集和问题无关紧要。它们的值仅表示有多少种方法可以将数字(相应单项式的次数)作为第一组和第二组元素的总和，或者可能为 0。任何系数的值都受两个集合的更大大小限制(s).

要将多项式乘法问题转换为大整数(指标向量)乘法问题，需要在指标向量的每一位之后附加 log(s) 零位。如果位 (log(s) + 1) * i ... (log(s) + 1) * (i + 1) - 1 在乘积位集中不是全部清除，则相应的 sum= i 是可实现的。

对于大整数乘法算法(类似 Karatsuba 或基于 FFT 的算法)，它为问题大小提供了额外的对数因子。我想消除对数填充。

我觉得用简单的教科书ijk算法来两个整数相乘是可行的。我只需要使用逻辑 OR 而不是 ADD 进行求和。但该算法具有二次运行时复杂度。

在基于 FFT 的算法中，是否可以用 ORing 代替求和，例如 Schönhage–Strassen algorithm ？

Answer 1

不幸的是没有。基于 FFT 或 NTT 的乘法基于卷积定理 (https://en.wikipedia.org/wiki/Convolution_theorem)

卷积定理之所以有效，是因为 FFT/NTT 将长度为 N 的输入向量表示为 N 线性独立指数序列的总和。

要制作 N 个不同的线性无关指数序列，您至少需要 N 个不同的元素作为基数，这意味着您的元素的大小必须为最少 log N 位。

元素的类型和用于+和*的操作也必须形成一个环(https://en.wikipedia.org/wiki/Ring_(mathematics))，OR不满足。