使用整数乘法的布尔卷积
Boolean convolution using integer multiplication
在 Bringmann16 文章中介绍的算法中，建议使用 布尔卷积 来获取两组正整数的总和集。
在上面的工作中，两个集合都表示为位掩码 - indicator vectors。如果将它们表示为 1 + bit(0) * x + bit(1) * x^2 + ... + bit(i) * x^(i + 1) + ... + bit(n - 1) * x^n 形式的多项式，那么它们的乘积实际上仅包含那些单项式，其幂为第一组、第二组或总和中的数字。乘积的系数对于子集和问题无关紧要。它们的值仅表示有多少种方法可以将数字（相应单项式的度数）作为第一组和第二组元素的总和，或者可能为 0。任何系数的值都受两组的更大尺寸限制（s）。
要将多项式乘法问题转换为大整数（指标向量）乘法问题，需要在指标向量的每一位之后附加 log(s) 零位。如果product bitset中的bits(log(s) + 1) * i ... (log(s) + 1) * (i + 1) - 1没有全部清除，那么对应的sum=i是可以实现的。
对于大整数乘法算法（类似 Karatsuba 或基于 FFT 的算法），它为问题大小提供了额外的对数因子。我想消除对数填充。
我觉得用简单的教科书ijk算法来两个整数相乘是可行的。我只需要使用逻辑 OR 而不是 ADD 进行求和。但是该算法具有二次运行时复杂度。
在基于 FFT 的算法中，是否可以用 ORing 代替求和，例如 Schönhage–Strassen algorithm？
很遗憾没有。 FFT-或NTT-based乘法是基于卷积定理(https://en.wikipedia.org/wiki/Convolution_theorem)
卷积定理之所以有效，是因为 FFT/NTT 将长度为 N 的输入向量线性表示为 N 的总和独立指数序列。
要使 N 个不同的线性独立指数序列，您至少需要 N 个不同的元素用作基数，这意味着元素的大小必须至少为 log N 位。
+和*所用的元素类型和运算也必须成环(https://en.wikipedia.org/wiki/Ring_(mathematics))，OR不满足
在 Bringmann16 文章中介绍的算法中，建议使用 布尔卷积 来获取两组正整数的总和集。
在上面的工作中，两个集合都表示为位掩码 - indicator vectors。如果将它们表示为 1 + bit(0) * x + bit(1) * x^2 + ... + bit(i) * x^(i + 1) + ... + bit(n - 1) * x^n 形式的多项式，那么它们的乘积实际上仅包含那些单项式，其幂为第一组、第二组或总和中的数字。乘积的系数对于子集和问题无关紧要。它们的值仅表示有多少种方法可以将数字（相应单项式的度数）作为第一组和第二组元素的总和，或者可能为 0。任何系数的值都受两组的更大尺寸限制（s）。
要将多项式乘法问题转换为大整数（指标向量）乘法问题，需要在指标向量的每一位之后附加 log(s) 零位。如果product bitset中的bits(log(s) + 1) * i ... (log(s) + 1) * (i + 1) - 1没有全部清除，那么对应的sum=i是可以实现的。
对于大整数乘法算法（类似 Karatsuba 或基于 FFT 的算法），它为问题大小提供了额外的对数因子。我想消除对数填充。
我觉得用简单的教科书ijk算法来两个整数相乘是可行的。我只需要使用逻辑 OR 而不是 ADD 进行求和。但是该算法具有二次运行时复杂度。
在基于 FFT 的算法中，是否可以用 ORing 代替求和，例如 Schönhage–Strassen algorithm？
很遗憾没有。 FFT-或NTT-based乘法是基于卷积定理(https://en.wikipedia.org/wiki/Convolution_theorem)
卷积定理之所以有效，是因为 FFT/NTT 将长度为 N 的输入向量线性表示为 N 的总和独立指数序列。
要使 N 个不同的线性独立指数序列，您至少需要 N 个不同的元素用作基数，这意味着元素的大小必须至少为 log N 位。
+和*所用的元素类型和运算也必须成环(https://en.wikipedia.org/wiki/Ring_(mathematics))，OR不满足