Euclidean Algorithm(1変数リストversion改訂版)のプログラム


In[1]:=ListGCD[f_,g_]:=ListGCD[f,g]=Module[{h,s,rem、h1},
                       h=f;s=g;
		       While[s=!={0},rem=ListDiv[h,s][[2]];h=s;s=rem];
		       h/h([[-1]])]
		       
		       
	     但し、ListDiv[f_,g_]:=ListDiv[f,g]=Module[{q,r,deg,coe},
                        q=Table[0,{Max[Length[f]-Length[g]+1,1]}];r=f;
                        While[r=!={0}&&Length[g]<=Length[r],
		        deg=Length[r]-Length[g]; coe=r[[-1]]/g[[-1]];
		        q=ReplacePart[q,coe+q[[deg+1]],deg+1];
                        r=r-Join[Table[0,{deg}],coe*g];
                        While[Length[r]>=1&&r[[-1]]==0,r=Delete[r,-1]]];
		        If[r=={},r={0}];{q,r}]
			
多項式をリストであらわします。

例えば、x^3+2x^2+2x+1 は、{1, 2, 2, 1}

        x^3-2x は、       {0, -2, 0, 1}
	
	のように、
	
	左から順に、定数項の係数、1次の項の係数、2次の項の係数・・・
	
	というようにリストにします。

ListGCD[多項式のリスト、多項式のリスト]と入力すると、

2つの多項式の最大公約数をモニック多項式のリストで出力します。	



(Example)

In[2]:=ListGCD[{-6, -5, 2, 1}, {-8, 2, 1}]

Out[2]={-2, 1}
		
		
応用として、 3つの多項式の最大公約数を求めるプログラムをつくりました。

List3GCD[f_,g_,h_]:=List3GCD[f,g,h]=List3GCD[f,ListGCD[g,h]]

さらに、任意の個数の多項式の最大公約数を求めるプログラムをつくりました。

ListGCDs[f_]:=ListGCDs[f]=Module[{s,h},s=Length[f];h=f[[1]];
                          Do[h=ListGCD[h,f[[i]]],{i,2,s}];h]
			  
ListGCDs[{f1,f2,...,fn}]      (f1,f2,...,fn は、多項式のリスト)
のように入力します。