計算効率

前節の関数 g_c_d で, $f=(2x^3+4x^2+3)(3x^3+4x^2+5)^{10}$, $g=(2x^3+4x^2+3)(4x^3+5x^2+6)^{10}$ の GCD を計算してみよう.

[151] F=(2*x^3+4*x^2+3)*(3*x^3+4*x^2+5)^10$
[152] G=(2*x^3+4*x^2+3)*(4*x^3+5*x^2+6)^30$
[153] H=g_c_d(F,G)$
6.511sec + gc : 0.06728sec(6.647sec)

使用する計算機にもよるが, 数秒程度で巨大な係数を持つ多項式が得られる. 実はこの多項式は $2x^3+4x^2+3$ の定数倍である. これを組み込み関数 ptozp(F) で確かめてみよう. ptozp(F) は, F に適当な 有理数をかけて, 係数を GCD が 1 であるような整数にした多項式を返す関数 である.

[154] ptozp(H);
2*x^3+4*x^2+3

この例からわかるように, 前節の g_c_d では, 互除法の途中および 結果の多項式に分母分子が巨大な分数が現れてしまう. 人間と同様, 計算機 も分数の計算は苦手である. そこで, 分数の計算が現れないように工夫して みよう. まず, 剰余を定数倍しても, GCD は定数倍の影響を受けるだけという ことに注意して, 次のような関数を考える.

def remainder(F,G) {
   Q = 0; R = F;
   HCG = coef(G,deg(G,x));
   while ((R != 0) && (deg(R,x) >= deg(G,x)))
      R = HCG*R-coef(R,deg(R,x))*x^(deg(R,x)-deg(G,x))*G;
   return R;
}

この関数は, 適当な自然数 $k$ に対し

$${\rm lc}(g)^k f = q g + r , \quad {\rm deg}(r) < {\rm deg}(g)$$

(${\rm lc}(g)$ は $g$ の最高次の係数) なる $r \in {\bf Z}[x]$ を求めていることになる. この関数で, 前節の division を置き換えてみよう.

def g_c_d_1(F,G) {
   if (deg(F,x) > deg(G,x)) {
     S = F; T = G;
   }else {
     S = G; T = F;
   }
   while (T != 0) {
     R = pseudo_remainder(S,T);
     S = T;
     T = R;
   }
   return(S);
}

[207] g_c_d_1(F,G);
Needed to allocate blacklisted block at 0x988d000
Needed to allocate blacklisted block at 0x9899000

どうしたことか, 妙なメッセージは出るものの結果は出そうもない. 実は, pseudo_remainder でかけた ${\rm lc}(g)^k$ のせいで, 途中の多項式の係数が大きくなりすぎているのである. そこで, pseudo_remainder の結果を ptozp で簡単化 してみよう.

def g_c_d_2(F,G) {
   if (deg(F,x) > deg(G,x)) {
     S = F; T = G;
   }else {
     S = G; T = F;
   }
   while (T != 0) {
     R = pseudo_remainder(S,T);
     R = ptozp(R);
     S = T;
     T = R;
   }
   return(S);
}

[237] g_c_d_2(F,G);
2*x^3+4*x^2+3
0.057sec(0.06886sec)

今度はずいぶん速く計算できた. ptozp では, 実際に係数の整数 GCD を計算することで 簡単化を行っているが, より詳しく調べると, GCD を計算しなくても, GCD のかなりの部分は あらかじめ知ることができる. この話題にはこれ以上立ち入らない. [3] Section 4.6.1 または [2] 5.4 節 を参照して欲しい.

ここで見たように, 互除法のような単純なアルゴリズムでも, 実現方法によっ てはずいぶん効率に差が出る場合がある. 特に, 分数が現れないようなアルゴ リズムを考えることは重要である.

問題 14.4   g_c_d も ptozp を用いることで高速化できる. その改良版 g_c_d と g_c_d_2 をさまざまな例で比較してみて, 分数が現れる演算が効率低下を招くこと を確認せよ.