使用整数乘法的布尔卷积
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不满足