誰かが私をさらに改善するのを手伝ってくれることを願っていますが、コンバージョンを最適化する方法を見つけました。うまくいけば、他の賢いアイデアを見つけることができます。
基本的に、これらの関数の問題点は、整数をパックするとき、またはアンパックするときに、ある種の2次メモリ割り当ての動作をすることです。（この種の動作の他の例については、Guido van Rossumのこの投稿を参照してください）。
これに気付いた後、分割統治の原則を試してみることにしました。いくつかの結果が得られました。配列を2つの部分に分割し、それらを別々に変換して、最終的に結果を結合します（後でf5、Rossumの投稿[編集：それほど速くはないようです]にあるような反復バージョンを使用しようとします）。
変更された機能：
def _coefs_to_long(coefs, window):
"""Given a sequence of coefficients *coefs* and the *window* size return a
long-integer representation of these coefficients.
"""
length = len(coefs)
if length < 100:
res = 0
adder = 0
for k in coefs:
res += k << adder
adder += window
return res
else:
half_index = length // 2
big_window = window * half_index
low = _coefs_to_long(coefs[:half_index], window)
high = _coefs_to_long(coefs[half_index:], window)
return low + (high << big_window)
def _long_to_coefs(long_repr, window, n):
"""Given a long-integer representing coefficients of size *window*, return
the list of coefficients modulo *n*.
"""
win_length = long_repr.bit_length() // window
if win_length < 256:
mask = 2**window - 1
coefs = [0] * (long_repr.bit_length() // window + 1)
for i in xrange(len(coefs)):
coefs[i] = (long_repr & mask) % n
long_repr >>= window
# assure that the returned list is never empty, and hasn't got an extra 0.
if not coefs:
coefs.append(0)
elif not coefs[-1] and len(coefs) > 1:
coefs.pop()
return coefs
else:
half_len = win_length // 2
low = long_repr & (((2**window) ** half_len) - 1)
high = long_repr >> (window * half_len)
return _long_to_coefs(low, window, n) + _long_to_coefs(high, window, n)
そして結果：
>>> import timeit
>>> def coefs_to_long2(coefs, window):
... if len(coefs) < 100:
... return coefs_to_long(coefs, window)
... else:
... half_index = len(coefs) // 2
... big_window = window * half_index
... least = coefs_to_long2(coefs[:half_index], window)
... up = coefs_to_long2(coefs[half_index:], window)
... return least + (up << big_window)
...
>>> coefs = [1, 2, 3, 1024, 256] * 567
>>> # original function
>>> timeit.timeit('coefs_to_long(coefs, 11)', 'from __main__ import coefs_to_long, coefs',
... number=1000)/1000
0.003283214092254639
>>> timeit.timeit('coefs_to_long2(coefs, 11)', 'from __main__ import coefs_to_long2, coefs',
... number=1000)/1000
0.0007998988628387451
>>> 0.003283214092254639 / _
4.104536516782767
>>> coefs = [2**64, 2**31, 10, 107] * 567
>>> timeit.timeit('coefs_to_long(coefs, 66)', 'from __main__ import coefs_to_long, coefs',... number=1000)/1000
0.009775240898132325
>>>
>>> timeit.timeit('coefs_to_long2(coefs, 66)', 'from __main__ import coefs_to_long2, coefs',
... number=1000)/1000
0.0012255229949951173
>>>
>>> 0.009775240898132325 / _
7.97638309362875
ご覧のとおり、このバージョンでは、変換までの速度がかなり4速く8なります（入力が大きいほど、速度が速くなります）。2番目の関数でも同様の結果が得られます。
>>> import timeit
>>> def long_to_coefs2(long_repr, window, n):
... win_length = long_repr.bit_length() // window
... if win_length < 256:
... return long_to_coefs(long_repr, window, n)
... else:
... half_len = win_length // 2
... least = long_repr & (((2**window) ** half_len) - 1)
... up = long_repr >> (window * half_len)
... return long_to_coefs2(least, window, n) + long_to_coefs2(up, window, n)
...
>>> long_repr = coefs_to_long([1,2,3,1024,512, 0, 3] * 456, 13)
>>> # original function
>>> timeit.timeit('long_to_coefs(long_repr, 13, 1025)', 'from __main__ import long_to_coefs, long_repr', number=1000)/1000
0.005114212036132813
>>> timeit.timeit('long_to_coefs2(long_repr, 13, 1025)', 'from __main__ import long_to_coefs2, long_repr', number=1000)/1000
0.001701267957687378
>>> 0.005114212036132813 / _
3.006117885794327
>>> long_repr = coefs_to_long([1,2**33,3**17,1024,512, 0, 3] * 456, 40)
>>> timeit.timeit('long_to_coefs(long_repr, 13, 1025)', 'from __main__ import long_to_coefs, long_repr', number=1000)/1000
0.04037192392349243
>>> timeit.timeit('long_to_coefs2(long_repr, 13, 1025)', 'from __main__ import long_to_coefs2, long_repr', number=1000)/1000
0.005722791910171509
>>> 0.04037192392349243 / _
7.0545853417694
最初の関数で開始インデックスと終了インデックスを渡し、スライスを回避することで、より多くのメモリの再割り当てを回避しようとしましたが、これにより、入力が小さい場合は関数の速度が大幅に低下し、実際の場合は少し遅くなります。入力。あまり良い結果が得られないとは思いますが、それらを混ぜてみることができるかもしれません。
私は前の期間に私の質問を編集したので、何人かの人々は私が最近必要としたものとは異なる目的で私にいくつかのアドバイスをくれました。コメントと回答でさまざまな情報源から指摘された結果を少し明確にして、高速多項式やAKSテストの実装を検討している他の人々に役立つようにすることが重要だと思います。
- JF Sebastianが指摘したように、AKSアルゴリズムには多くの改善が加えられているため、古いバージョンのアルゴリズムを実装しようとすると、プログラムが非常に遅くなります。これは、AKSの適切な実装がすでにある場合は、多項式の改善を高速化できるという事実を排除するものではありません。
- 小さい係数
n（ワードサイズの数値を読み取る）に関心があり、外部の依存関係を気にしない場合は、乗算numpyを使用するnumpy.convolveかscipy.fftconvolve、乗算を使用します。それはあなたが書くことができる何よりもはるかに速くなります。残念ながら、nワードサイズでない場合はまったく使用できずscipy.fftconvolve、numpy.convolve地獄のように遅くなります。
- モジュロ演算（係数と多項式）を実行する必要がない場合は、素晴らしい結果を約束していなくても（haroldが指摘しているように）、おそらくZBDDを使用することをお勧めします[本当におもしろいので、湊の論文を読んでください]。
- 係数に対してモジュロ演算を実行する必要がない場合は、Originで述べられているように、おそらくRNS表現を使用することをお勧めします。
numpy次に、複数のアレイを組み合わせて効率的に動作させることができます。
- 係数モジュロが大きい多項式の純粋なPython実装が必要な場合は
n、私のソリューションが最速のようです。私はPythonで係数の配列間にfft乗算を実装しようとしませんでしたが（これはより速いかもしれません）。