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


In[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次の項の係数・・・
	
	というようにリストにします。

ListDiv[割られる多項式のリスト, 割る多項式のリスト] と入力すると、

{商の多項式のリスト, 余りの多項式のリスト} を出力します。



(Example)

In[2]:=ListDiv[{1, 2, 2, 1}, {1, 2}]

Out[2]={{5/8, 3/4, 1/2}, {3/8}}}