使用整数乘法的布尔卷积 [英] Boolean convolution using integer multiplication
问题描述
在 Bringmann16 文章中介绍的算法中，建议使用布尔卷积用于获取两组正整数的和集.
在以上工作中，两个集合都表示为位掩码-指标向量.如果以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.
对于大型int乘法算法(类似于Karatsuba或基于FFT)，它为问题大小提供了额外的对数因子.我想消除对数填充.
如果使用简单的教科书ijk算法将两个整数相乘，我认为这是可行的.我只需要使用逻辑 OR 而不是 ADD 进行求和.但是该算法具有二次运行时复杂度.
如果基于FFT的算法(例如 Schönhage–Strassen算法?
不幸的是，没有.基于FFT或NTT的乘法基于卷积定理( https://en.wikipedia.org/wiki/Convolution_theorem )
卷积定理只能起作用，因为FFT/NTT将长度为 N 的输入向量表示为 N 个线性独立指数序列的总和.
要使 N 个不同的线性独立的指数序列，您至少需要 N 个不同的元素用作基础，这意味着您的元素大小必须为至少 log N 位.
+和*所用的元素类型和运算也必须形成一个环( https://en.wikipedia.org/wiki/Ring_(数学))，或不满足.
In algorithms presented in Bringmann16 article a Boolean convolution is suggested to use to get sumset for two sets of positive integers.
In above work both sets are represented as bitmasks - indicator vectors. If represent them as polynomials in form 1 + bit(0) * x + bit(1) * x^2 + ... + bit(i) * x^(i + 1) + ... + bit(n - 1) * x^n, then indeed their product contains only those monomials, whose power is number either in first set, or in second set or in sumset. The coefficients of product does not matter for subset sum problem. Their values just indicate how many ways to get the number (degree of corresponding monomial) as a sum of elements from first and second set or maybe 0. Value of any coefficient limited by greater size of both sets (s).
To convert the problem of polynomials multiplication to problem of big integers (indicator vectors) multiplication there is need to append log(s) zero bits after each bit of indicator vector. If bits (log(s) + 1) * i ... (log(s) + 1) * (i + 1) - 1 are not all clear in product bitset, then corresponding sum=i is realizable.
For big int multiplication algorithms (Karatsuba-like or FFT-based) it gives extra logarithmic factor to problem size. I want to eliminate logarithmic padding.
I think it feasible if I use simple textbook ijk algorithm to multiply two integers. I just need to use logical OR instead of ADD for summation. But this algorithm has quadratic runtime complexity.
Is it possible to replace summation with ORing in case of FFT-based algorithms, like Schönhage–Strassen algorithm?
Unfortunately no. FFT- or NTT-based multiplication is based on the convolution theorem (https://en.wikipedia.org/wiki/Convolution_theorem)
The convolution theorem only works because the FFT/NTT expresses your input vector of length N as the sum of N linearly independent exponential sequences.
To make N distinct linearly independent exponential sequences, you need at least N different elements to use as bases, and that means that the size of your elements must be at least log N bits.
The type of elements and the operations used for + and * must also form a ring (https://en.wikipedia.org/wiki/Ring_(mathematics)), which OR does not satisfy.
这篇关于使用整数乘法的布尔卷积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
