1

ウィンドウ乗算アルゴリズムを使用して、長い整数の乗算を使用して2つの多項式[係数inZ/nZと一部のrの多項式mod全体x^r-1]を乗算する場合、ウィンドウにどのサイズを指定する必要がありますか？

ここで、「ウィンドウ」とは、長整数の乗算の結果に結果の正しい係数が含まれるように、係数が最初の長整数で使用するビット長を意味します[係数の合計は重複しません"]。

ceil(log(n**2,2)) + 1最初はそれで十分だと思いました。なぜなら、各係数はせいぜいn-1であり、これらの係数の積はせいぜい(n-1)**2です。次に、長整数の乗算を行う場合、これらの係数の合計が存在する可能性があるため、ウィンドウはである必要があることに気付きましたceil(log(number-of-additions * n**2,2)) + 1。

せいぜい2つの多項式の加算の次数の合計があると思いましたが、ceil(log((deg_a + deg_b + 1) * n**2,2)) +1しばらくの間は動作しますが、最終的には係数が重複し、間違った結果が得られます。

では、この「ウィンドウ」はどのくらいの大きさにする必要がありますか？

ちなみに、現在の（python）コードは次のとおりです。

def __mul__(self, other):
    new = ModPolynomial(self._mod_r, self._mod_n)
    #new = x mod self._mod_n,x^(self._mod_r -1)
    try:
        new_deg = self._degree + other.degree
        new_coefs = []
        # i've also tried with (new_deg + 1) ** 2 * ...
        window = int(math.ceil(math.log((new_deg + 1) * self._mod_n**2,2))) + 1
        A = 0
        for i,k in enumerate(self._coefs):
            A += k << (window * i)
        B = 0
        for i,k in enumerate(other.coefficients):
            B += k << (window * i)

        res = A * B
        mask = 2**window - 1
        while res:
            new_coefs.append((res & mask) % self._mod_n)
            res >>= window
        new._coefs = new_coefs
        new._degree = self._finddegree(new_coefs)
    except AttributeError:
        new._coefs = [(c * other) % self._mod_n for c in self._coefs]
        new._degree = self._finddegree(new._coefs)
    new._mod()
    return new

編集1： ウィンドウサイズは問題ではないかもしれないと思い始めています。私はそれを最大に増やしてみましたがceil(log2((new_deg+1)**3 * self._mod_n ** 5))+1、これはを使用した場合と同じ結果ceil(log2((new_deg+1) * self._mod_n**2))+1になります。これら2つのサイズの違いは非常に大きいため、[私のテストでは約55〜60ビットの違いです。 ]、これは、すでに問題がない場合はおそらくこれらのサイズの最小値を意味しますが、どこかに他の問題があります。

編集2： 間違った結果の例は次のとおりです。

#ModPolynomial(r,n) = x mod n, x^r-1
>>> pol = polys.ModPolynomial(20,100)      # uses integer-multiplication
>>> pol += 2
>>> pol2 = polynomials.ModPolynomial(20,100)   #uses the naive algorithm
>>> pol2 += 2
>>> (pol2**52).coefficients      #should be the correct result[first is coef of x^0]
(76, 76, 44, 0, 0, 16, 16, 4, 0, 0, 24, 24, 81, 0, 0, 80, 80, 20)
>>> (pol**52).coefficients       #the wrong result
(12L, 52L, 8L, 20L, 60L, 12L, 92L, 28L, 60L, 80L, 68L, 48L, 22L, 0L, 0L, 20L, 20L, 80L)

手作業で確認できるように、もっと小さな例を見つけてみます。

編集3： さて、学位に問題があることがわかりました。程度が負になる例を見つけましたが、明らかにそうすべきではありません。だから私は、この予期しない方法で次数がいつ、なぜ変わるのかをもっと調べてみようと思います。

編集4： バグを見つけました。整数を作成するとき、私はすべてのシーケンスを反復していました_coefsが、私の実装は、多項式の次数の次数に対応するすべての係数が0であることを保証しません。これで問題が修正されます。

編集5： この実装をテストして得たパフォーマンス結果のほんの一部。

1）係数がintよりも大きい場合は、long -integer乗算を使用する方が使用するよりも高速です。それ以外の場合は高速です。numpy.convolve numpy.convolve

2）時間の約80％は、係数のリストを整数に変換し、整数を係数のリストに変換するために費やされます。これらの操作はO（n）であるため、これについてできることはあまりありません。

ここで、長い整数のみを使用して「mod x ^ r-1」操作を効率的な方法で実装する方法があるかどうか疑問に思っています...これにより、おそらく大幅なスピードアップが得られる可能性があります。もう変換を行う必要はありません。

4

1 に答える 1

1

正しい計算は

window = int(math.ceil(math.log((max(self._degree, other.degree) + 1) *
                                (self._mod_n - 1)**2, 2)))

ただし、これは間違いなく計算したウィンドウよりも小さいため、誤った結果が得られる理由は他にもあるはずです。度数が正しく計算されていますか？正しく計算されていない多項式の例を挙げていただけますか？

長整数の乗算を使用する特に正当な理由がない限り、NumPyを使用することをお勧めします。

new.coeffs = np.convolve(self.coeffs, other.coeffs) % self.mod

これは通常、少なくとも長整数の乗算（とにかく畳み込みの形式です）と同じくらい効率的であり、心配するPythonコードがはるかに少なくなります。実際、NumPyには多項式ライブラリがあります。浮動小数点係数用に設計されていますが、コードを効率的に実装する方法を理解するためにそれを見ることができます。

于 2012-08-21T18:53:30.123 に答える