プロジェクトオイラー
http://projecteuler.net/index.php?section=problems&id=258
この問題では、結局2000項の多項式の掛け算に時間がかかる。単純に計算すると、N=2000として、N2回の掛け算が必要となる。実際には自乗の計算なので半分くらいで済む。しかし、世の中には掛け算の速いアルゴリズムがあるらしいので、それを利用すればよい。Pythonの長整数はなんらかの速いアルゴリズムを使っていると思われる。そこで、多項式を配列ではなく一つの長整数で表して掛け算を行ってみた。
def square(a):
b = [ 0 ] * (N * 2 - 1)
for k in xrange(N):
b[k*2] += a[k] * a[k]
for l in xrange(k + 1, N):
b[k+l] += a[k] * a[l] * 2
return b
def square(a):
n = 0
for e in a:
n = (n << 64) | e
n *= n
b = [ 0 ] * (N * 2 - 1)
for k in xrange(N * 2 - 2, -1, -1):
e = n & ((1 << 64) - 1)
b[k] = e
n >>= 64
return b
これで、2分が22秒になった。ここ以外も長整数にすると、もう少し速くなると思われる。
