我正在尝试优化我的多项式实现。特别是我正在处理系数模的多项式n（可能>2^64) 并对以下形式的多项式取模x^r - 1(r is < 2^64）。目前，我将系数表示为整数列表（*），并且我已经以最直接的方式实现了所有基本操作。
我希望求幂和乘法尽可能快，为了实现这一点，我已经尝试了不同的方法。我当前的方法是将系数列表转换为大整数，将整数相乘并解压缩系数。
问题是装箱和拆箱需要花费大量时间。
那么，有没有办法改进我的“打包/解包”功能呢？
def _coefs_to_long(coefs, window):
'''Given a sequence of coefficients *coefs* and the *window* size return a
long-integer representation of these coefficients.
'''
res = 0
adder = 0
for k in coefs:
res += k << adder
adder += window
return res
#for k in reversed(coefs): res = (res << window) + k is slower
def _long_to_coefs(long_repr, window, n):
'''Given a long-integer representing coefficients of size *window*, return
the list of coefficients modulo *n*.
'''
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
请注意，我这样做not choose n，它是来自用户的输入，我的程序想要证明它的素数（使用AKS测试），所以我不能分解它。
(*)我尝试了几种方法：
- Using a
numpy数组而不是列表并使用相乘numpy.convolve。速度很快n < 2^64但非常慢n > 2^64[我也想避免使用外部库]
- Using
scipy.fftconvolve。根本不起作用n > 2^64.
- 从一开始就将系数表示为整数（无需每次都进行转换）。问题是我不知道有什么简单的方法可以做到这一点
mod x^r -1操作而不将整数转换为系数列表（这违背了使用这种表示形式的原因）。
除非你这样做是为了学习，否则为什么要重新发明轮子呢？另一种方法是为其他多项式库或程序编写一个 Python 包装器（如果这样的包装器尚不存在）。
尝试 PARI/GP。速度快得惊人。我最近编写了一个自定义 C 代码，花了我两天的时间来编写，结果只比两行 PARI/GP 脚本快 3 倍。我敢打赌，调用 PARI 的 Python 代码最终会比单独用 Python 实现的任何代码都要快。甚至还有一个用于从 python 调用 PARI 的模块：https://code.google.com/p/pari-python/ https://code.google.com/p/pari-python/
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
