DivisionAlgorithm と EuclideanAlgorithm

0771061J 森島聖

平成 10 年 7 月 6 日 (4 年セミナー)

1. Mathematica で、 DivisionAlgorithm のプログラムを作ってみました。

Div[f_,g_]:=Div[f,g]=Module[{q,r,if,k},
        q=0;r=f;
        if[q1_,r1_]:=if[q1,r1]=
        If[r1=!=0&&Exponent[g,x]<=Exponent[r1,x],
        k=x^Exponent[r1,x]*Coefficient[r1,x,Exponent[r1,x]]/
          (x^Exponent[g,x]*Coefficient[g,x,Exponent[g,x]]);
        q=q1+k; r=r1-k*g;if[q,r],
        {q1,Expand[r1]}];
        if[q,r]]

(プログラムの大まかな説明)

まず、 2 段目で、 q と r の初期値を、 q = 0、 r = f と定義します。次に、 3 段目から 8 段目までで、 if[q1,r1] という新しい関数を定義します。最後に、 9 段目で、今定義した関数に q1 = q、 r1 = r を代入します。 (初期値として q = 0、 r = f とおいたので、ここでは q1 = 0、 r1 = f ) この関数が出力する結果が、このプログラムが出力する結果になっています。それでは、この if という関数がどのように働くか見てみましょう。 Mathematica に最初から組み込まれている If[condition,true,false] という関数は、 condition という条件を与えた時に、この条件が、真ならば true を、偽ならば false を行うので、新しく定義した if という関数は、 q1 と r1 を変数として、その変数に対して、

          r1=!=0&&Exponent[g,x]<=Exponent[r1,x]

という条件 ( 意味は、 r1 ≠ 0 かつ deg(g) ≤ deg(r1) ) が偽ならば、

          {q1,Expand[r1]}

を、行います。つまり、リストとして、 q1 と Expand[r1] を出力します。 (Expand[expr] は、 expr を展開する組み込み関数) もし、条件が真ならば、

          k=x^Exponent[r1,x]*Coefficient[r1,x,Exponent[r1,x]]/
           (x^Exponent[g,x]*Coefficient[g,x,Exponent[g,x]]);
          q=q1+k; r=r1-k*g;
          if[q,r]

を、行います。これは、 k を k=LT(r1)/LT(g) とおいて、 q と r を q = q1+k、 r = r1−kg と、新しく定義し直して、さらにその新しい q と r を関数 if に q1 = q、 r1 = r として、代入します。あとは、関数 if の説明のくり返しです。このことから、関数 if は、条件 ( r1 ≠ 0 かつ deg(g) ≤ deg(r1) ) が、偽になるまで、 qと rを、新しく定義し続けて、条件が偽になった時の qと r、つまり商と余りをリストとして出力することがわかります。以上のことから、このプログラムは、テキストの pseudocode と対応していることがわかります。

(Example-1)

x^{3} + 2x^{2} + x + 1 を 2x + 1 で割ってみました。

In[1]:= Div[x^3+2x^2+x+1,2x+1]

Out[1]:=\{ \frac{1}{8} + \frac{3x}{4} + \frac{x^{2}}{2} , \frac{7}{8}\}

出力結果より、商が\frac{1}{2}x^{2} + \frac{3}{4}x + \frac{1}{8} 余りが\frac{7}{8} 。

2. Mathematica で、 EuclideanAlgorithm のプログラムを作ってみました。

PolyGCD[f_,g_]:=PolyGCD[f,g]=Module[{h,s,if2,rem},
            h=f;s=g;
            if2[h1_,s1_]:=if2[h1,s1]=
            If[s1=!=0,
            rem=Div[h1,s1][[2]];h=s1;s=rem;if2[h,s]
            ,h1];
            if2[h,s]]

(プログラムの大まかな説明)

まず、 2 段目で、 h と s の初期値を、 h = f、 s = g と定義します。次に、 3 段目から 6 段目までで、 if2[h1,s1] という新しい関数を定義します。最後に、 7 段目で、今定義した関数に h1 = h、 s1 = s を代入します。 (初期値として h = f、 s = g とおいたので、ここでは h1 = f、 s1 = g ) この関数が出力する結果が、このプログラムが出力する結果になっています。それでは、この if2 という関数がどのように働くか見てみましょう。この関数は、 h1 と s1 を変数として、その変数に対して、

          s1=!=0

という条件 ( 意味は、 s1 ≠ 0 ) が偽ならば、

          h1

を、出力します。もし、条件が真ならば、

          rem=Div[h1,s1][[2]];h=s1;s=rem;if2[h,s]

を、行います。これは、 rem を、 h1 を s1 で割ったときの余りとおいて (1 で作った DivisionAlgorithm を使います。 [[2]] というのは、 Div[f,g] が出力したリストの第 2 成分を出力するということです。つまり、余りを出力します。 )、 h と s を h = s1、 s = rem と、新しく定義し直して、さらにその新しい h と s を関数 if2 に h1 = h、 s1 = s として、代入します。あとは、関数 if2 の説明のくり返しです。このことから、関数 if2 は、条件 ( s1 ≠ 0 ) が、偽になるまで、 h と s を、新しく定義し続けて、条件が偽になった時の h、つまり最大公約数を出力することがわかります。以上のことから、このプログラムは、テキストの pseudocode と対応していることがわかります。

(Example-2)

x^{3} + 2x^{2} − 5x − 6 と x^{2} + 2x − 8 の最大公約数を求めてみました。

In[2]:= PolyGCD[x^3+2x^2-5x-6,x^2+2x-8]
Out[2]:= −6 + 3x

出力結果より、最大公約数は、 3x − 6 。 (最大公約数は、 0 でない定数倍を除いて一意に表せたので、見やすくするには、 3 で割って x − 2 。 )

3. DivisionAlgorithm と EuclideanAlgorithm のプログラムの応用例を紹介します。まず、 EuclideanAlgorithm の 3 変数 version(多項式としての 3 変数ではなく、プログラムとしての 3 変数ということです。 ) を、テキスト 43 ページの Prop.8 (iii) を使って作りました。

Poly3GCD[f_,g_,h_]:=Poly3GCD[f,g,h]=PolyGCD[f,PolyGCD[g,h]]

次に、 f_{red}(f の square-free part) を求めるプログラムを作ってみました。 (定義等は、 Exercise 12 〜 15 を参照して下さい。 )

Red[f_]:=Red[f]=Simplify[f/PolyGCD[f,D[f,x]]]

(Example-3) テキストの Exercise 8 (a) x^{4} + x^{2} + 1、 x^{4} − x^{2} − 2x − 1、 x^{3} − 1 の最大公約数を求めてみました。

In[3]:= Poly3GCD[x^4+x^2+1,x^4-x^2-2x-1,x^3-1]
Out[3]:= −1 − x − x^{2}

出力結果より、最大公約数は x^{2} + x + 1 。 (見やすくするために−1 をかけました。 )

(b) x^{3} + 2x^{2} − x − 2、 x^{3} − 2x^{2} − x + 2、 x^{3} − x^{2} − 4x + 4 の最大公約数を求めてみました。

In[4]:= Poly3GCD[x^3+2x^2-x-2,x^3-2x^2-x+2,x^3-x^2-4x+4]
Out[4]:= −12 + 12x

出力結果より、最大公約数は x − 1 。 (見やすくするために 12 で割りました。 )

(Example-4) テキストの Exercise 9 x^{2} − 4 が、 < x^{3} + x^{2} − 4x − 4, x^{3} − x^{2} − 4x + 4, x^{3} − 2x^{2} − x + 2 > の元であるかどうかを調べました。まず、

In[5]:= h=Poly3GCD[x^3+x^2-4x-4,x^3-x^2-4x+4,x^3-2x^2-x+2]
Out[5]:= −12 + 6x

より、 < x^{3} + x^{2} − 4x − 4, x^{3} − x^{2} − 4x + 4, x^{3} − 2x^{2} − x + 2 >=< h > がいえます。次に、

In[6]:= Div[x^2-4,h]

Out[6]:= \{ \frac{1}{3} + \frac{x}{6}, 0 \}

より、 x^{2} − 4 が h で割り切れるので、

x^{2} − 4 ∈< x^{3} + x^{2} − 4x − 4, x^{3} − x^{2} − 4x + 4, x^{3} − 2x^{2} − x + 2 >

がいえます。

(Example-5) テキストの Exercise 15.(b)

x^{11} − x^{10} + 2x^{8} − 4x^{7} + 3x^{5} − 3x^{4} + x^{3} + 3x^{2} − x − 1 の square-free part を求めてみました。

In[7]:= Red[x^11-x^10+2x^8-4x^7+3x^5-3x^4+x^3+3x^2-x-1]

Out[7]:= −\frac{87025(−1 − x + x^{2} + x^{5})}{405108}

出力結果より、 square-free part は、 x^{5} + x^{2} − x − 1 。

4. (考察) プログラムの説明といくつかの例を、 LaTEX(文書整形システム) を使用してまとめてみました。私は、家庭教師用の簡単な教材作成にしか LaTEX を使用したことがなく、今回のレポート形式では大変苦労しました。ちなみに、 enumerate 環境 (項目を使用する時の環境) の中での改行後に 1 文字あけるやり方がわからなかったので、ちょっと読みずらい文章になってしまいました。プログラムの方ですが、いくつかの修正を加えてそれなりに機能するものが出来ました (プログラムの組み方は別として)。しかし、問題点として、最大公約数と square-free part の出力する結果が、入力する多項式が複雑な程、係数が複雑なものになるということです。これを、今後の課題にしようと思います。また、木村先生から提案していただいた、多項式を係数のリストとして表した場合 ( 例えば、 x^{3} − 2x + 3 は、 {1, 0, −2, 3} ) のプログラムについても挑戦してみたいと思います。