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


In[1]:=ListGCD[f_,g_]:=ListGCD[f,g]=Module[{h,s,rem},
                       h=f;s=g;
		       While[s=!={0},rem=ListDiv[h,s][[2]];h=s;s=rem];h]
		       
		       
	     但し、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]={-6, 3}
		
		
応用として、 3つの多項式の最大公約数を求めるプログラムをつくりました。

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