12921


以前した質問（[（バイナリ法を用いた）多項式の累乗計算について](https://ja.stackoverflow.com/questions/12910/%E3%83%90%E3%82%A4%E3%83%8A%E3%83%AA%E6%B3%95%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F-%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%81%AE%E7%B4%AF%E4%B9%97%E8%A8%88%E7%AE%97%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6/12917#12917)）の続きの質問です。

１変数の多項式の累乗計算をしていたのですが、  
ある次数以下の結果のみ知りたかったので、  
次のようなコードを書きました。

[code]

    # -*- coding: cp932 -*-
    import numpy
    
    # m次以下のみにする
    def mth_degree_poly(p, m):
        return numpy.poly1d(list(p)[- m - 1:])
    
    def power(f, n, m):
        p = numpy.poly1d(numpy.array([1], dtype = numpy.int64))
        for i in format (n, 'b'):
            p *= p
            p = mth_degree_poly(p, m)
            if i == '1':
                p *= f
                p = mth_degree_poly(p, m)
        return p
    
    f0 = numpy.poly1d(numpy.array([4, 3, 2, 1], dtype = numpy.int64))
    print list(reversed((power(f0, 15, 45)).c))
    print list(reversed((power(f0, 15, 4)).c))
    
[/code]

出力結果  
[1, 30, 465, 4960, 40845, 276066, 1590085, 8003580, 35839245, 144672190,
5318000  
61, 1794232440, 5591221545, 16174660530, 43617158385, 110012216516,
260248759395  
, 578739992010, 1212052994915, 2394073568880, 4465009918551, 7869335811350,
1311  
3723590175, 20668736021700, 30811909487775, 43435666238874, 57874992919695,
7283  
2798011960, 86477359352115, 96744251753430, 101799552129259, 100538923462140,
92  
949580044720, 80183958662080, 64289991816960, 47677224152064, 32507254108160,
20  
224232570880, 11370846289920, 5704957296640, 2510929526784, 946423726080,
294691  
799040, 71470940160, 12079595520, 1073741824]  
[1, 30, 465, 4960, 40845]

上記において、  
「多項式のかけ算を行なった後でm次以下のみにする」  
ということを行なっていますが、  
この無駄を解消する方法はあるのでしょうか？  
（ただし、数学的解決法を用いない方法でお願いします。）


CC BY-SA 3.0
2015-08-01T11:29:04.773
12920
2015-08-02T05:30:54.790
2017-04-13T12:52:38.920
-1
5363
question
python
Numpyを使った多項式の累乗計算について


ま、ベタな方法ですが以下の様に書いてみました。

[code]

    import itertools as iter
    
    poly = [4, 3, 2, 1]
    npower = 10
    m = 5
    
    l = range(len(poly))
    poly.reverse()
    fac = [0] * m
    
    for lst in iter.product(*([l]*npower)):
      s = sum(lst)
      if s < m:
        fac[s] += reduce(lambda x, y: x*y, [poly[i] for i in lst])
    
    print fac
    
[/code]

numpy は使っていません。ただし、itertools.product が **とても遅い** ので、高次係数の計算を省略しても numpy
より遅くなってしまいます。

そこで、numpy で itertools.product と同等の処理を以下の様に書いてみたのですが、

[code]

    print np.array(l)[np.rollaxis(
            np.indices((len(l),) * npower), 0, npower + 1)
                      .reshape(-1, npower)]
    
[/code]

`npower = 15` では `ValueError: array is too big.` と表示されて異常終了してしまいます。


CC BY-SA 3.0
2015-08-01T15:03:28.633
12921
2015-08-01T15:03:28.633
12920
answer