多項式, 有理式の演算
===========

var
---

var(RAT)
     :: RAT の主変数.

return
     不定元

rat
     有理式

  * 主変数に関しては, see Asir で使用可能な型.

  * デフォルトの変数順序は次のようになっている.

     x, y, z, u, v, w, p, q, r, s, t, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o,以後は変数の現れた順.

     [0] var(x^2+y^2+a^2);
     x
     [1] var(a*b*c*d*e);
     a
     [2] var(3/abc+2*xy/efg);
     abc

参照
     ord, vars.

vars
----

vars(OBJ)
     :: OBJ に含まれる変数のリスト.

return
     リスト

obj
     任意

  * 与えられた式に含まれる変数のリストを返す.

  * 変数順序の高いものから順に並べる.

     [0] vars(x^2+y^2+a^2);
     [x,y,a]
     [1] vars(3/abc+2*xy/efg);
     [abc,xy,efg]
     [2] vars([x,y,z]);
     [x,y,z]

参照
     var, uc, ord.

uc
--

uc()
     :: 新たな不定元を生成する.

return
     vtype が 1 の不定元

  * uc() を実行するたびに, _0, _1, _2,... という不定元を生成する.

  * uc() で生成された不定元は, 直接キーボードから入力することができない. これは, プログラム中で未定係数を自動生成する場合, 入力などに含まれる不定元と同一のものが生成されることを防ぐためである.

  * 通常の不定元 (vtype が 0) の自動生成には rtostr(), strtov() を用いる.

  * uc() で生成された不定元の不定元としての型 (vtype) は 1 である. (see 不定元の型)

     [0] A=uc();
     _0
     [1] B=uc();
     _1
     [2] (uc()+uc())^2;
     _2^2+2*_3*_2+_3^2
     [3] (A+B)^2;
     _0^2+2*_1*_0+_1^2

参照
     vtype, rtostr, strtov.

coef
----

coef(POLY,DEG[,VAR])
     :: POLY の VAR (省略時は主変数) に関する DEG 次の係数.

return
     多項式

poly
     多項式

var
     不定元

deg
     自然数

  * POLY の VAR に関する DEG 次の係数を出力する.

  * VAR は, 省略すると主変数 var(POLY) だとみなされる.

  * VAR が主変数でない時, VAR が主変数の場合に比較して効率が落ちる.

     [0] A = (x+y+z)^3;
     x^3+(3*y+3*z)*x^2+(3*y^2+6*z*y+3*z^2)*x+y^3+3*z*y^2+3*z^2*y+z^3
     [1] coef(A,1,y);
     3*x^2+6*z*x+3*z^2
     [2] coef(A,0);
     y^3+3*z*y^2+3*z^2*y+z^3

参照
     var, deg mindeg.

deg, mindeg
-----------

deg(POLY,VAR)
     :: POLY の, 変数 VAR に関する最高次数.

mindeg(POLY,VAR)
     :: POLY の, 変数 VAR に関する最低次数.

return
     自然数

poly
     多項式

var
     不定元

  * 与えられた多項式の変数 VAR に関する最高次数, 最低次数を出力する.

  * 変数 VAR を省略することは出来ない.

     [0] deg((x+y+z)^10,x);
     10
     [1] deg((x+y+z)^10,w);
     0
     [75] mindeg(x^2+3*x*y,x);
     1

nmono
-----

nmono(RAT)
     :: RAT の単項式の項数.

return
     自然数

rat
     有理式

  * 多項式を展開した状態での 0 でない係数を持つ単項式の項数を求める.

  * 有理式の場合は, 分子と分母の項数の和が返される.

  * 函数形式 (see 不定元の型) は, 引数が何であっても単項とみなされる. (1 個の不定元と同じ. )

     [0] nmono((x+y)^10);
     11
     [1] nmono((x+y)^10/(x+z)^10);
     22
     [2] nmono(sin((x+y)^10));
     1

参照
     vtype.

ord
---

ord([VARLIST])
     :: 変数順序の設定

return
     変数のリスト

varlist
     変数のリスト

  * 引数があるとき, 引数の変数リストを先頭に出し, 残りの変数がその後に続くように変数順序を設定する. 引数のあるなしに関わらず, ord() の終了時における変数順序リストを返す.

  * この函数による変数順序の変更を行っても, 既にプログラム変数などに代入されている式の内部形式は新しい順序に従っては変更されない. 従って, この函数による順序の変更は, Asir の起動直後, あるいは, 新たな変数が現れた時点に行われるべきである. 異なる変数順序のもとで生成された式どうしの演算が行われた場合, 予期せぬ結果が生ずることもあり得る.

     [0] ord();
     [x,y,z,u,v,w,p,q,r,s,t,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,_x,_y,_z,_u,_v,_w,_p,
     _q,_r,_s,_t,_a,_b,_c,_d,_e,_f,_g,_h,_i,_j,_k,_l,_m,_n,_o,exp(_x),(_x)^(_y),
     log(_x),(_x)^(_y-1),cos(_x),sin(_x),tan(_x),(-_x^2+1)^(-1/2),cosh(_x),sinh(_x),
     tanh(_x),(_x^2+1)^(-1/2),(_x^2-1)^(-1/2)]
     [1] ord([dx,dy,dz,a,b,c]);
     [dx,dy,dz,a,b,c,x,y,z,u,v,w,p,q,r,s,t,d,e,f,g,h,i,j,k,l,m,n,o,_x,_y,_z,_u,_v,
     _w,_p,_q,_r,_s,_t,_a,_b,_c,_d,_e,_f,_g,_h,_i,_j,_k,_l,_m,_n,_o,exp(_x),
     (_x)^(_y),log(_x),(_x)^(_y-1),cos(_x),sin(_x),tan(_x),(-_x^2+1)^(-1/2),
     cosh(_x),sinh(_x),tanh(_x),(_x^2+1)^(-1/2),(_x^2-1)^(-1/2)]

sdiv, sdivm, srem, sremm, sqr, sqrm
-----------------------------------

sdiv(POLY1,POLY2[,V])
sdivm(POLY1,POLY2,MOD[,V])
     :: POLY1 を POLY2 で割る除算が最後まで実行できる場合に商を求める.

srem(POLY1,POLY2[,V])

sremm(POLY1,POLY2,MOD[,V])
     :: POLY1 を POLY2 で割る除算が最後まで実行できる場合に剰余を求める.

sqr(POLY1,POLY2[,V])

sqrm(POLY1,POLY2,MOD[,V])
     :: POLY1 を POLY2 で割る除算が最後まで実行できる場合に商, 剰余を求める.

return
     sdiv(), sdivm(), srem(), sremm() : 多項式, sqr(), sqrm() : [商,剰余] なるリスト

poly1 poly2
     多項式

v
     不定元

mod
     素数

  * POLY1 を POLY2 の主変数 var(POLY2) ( 引数 V がある場合には V) に関する多項式と見て, POLY2 で, 割り算を行う.

  * sdivm(), sremm(), sqrm() は GF(MOD) 上で計算する.

  * 多項式の除算は, 主係数どうしの割算により得られた商と, 主変数の適当な冪の積を POLY2 に掛けて, POLY1 から引くという操作を POLY1 の次数が POLY2 の次数より小さくなるまで繰り返して行う. この操作が, 多項式の範囲内で行われるためには, 各ステップにおいて主係数どうしの除算が, 多項式としての整除である必要がある. これが, 「除算が最後まで実行できる」ことの意味である.

  * 典型的な場合として, POLY2 の主係数が, 有理数である場合, あるいは, POLY2 が POLY1 の因子であることがわかっている場合などがある.

  * sqr() は商と剰余を同時に求めたい時に用いる.

  * 整数除算の商, 剰余は idiv, irem を用いる.

  * 係数に対する剰余演算は % を用いる.

     [0] sdiv((x+y+z)^3,x^2+y+a);
     x+3*y+3*z
     [1] srem((x+y+z)^2,x^2+y+a);
     (2*y+2*z)*x+y^2+(2*z-1)*y+z^2-a
     [2] X=(x+y+z)*(x-y-z)^2;
     x^3+(-y-z)*x^2+(-y^2-2*z*y-z^2)*x+y^3+3*z*y^2+3*z^2*y+z^3
     [3] Y=(x+y+z)^2*(x-y-z);
     x^3+(y+z)*x^2+(-y^2-2*z*y-z^2)*x-y^3-3*z*y^2-3*z^2*y-z^3
     [4] G=gcd(X,Y);
     x^2-y^2-2*z*y-z^2
     [5] sqr(X,G);
     [x-y-z,0]
     [6] sqr(Y,G);
     [x+y+z,0]
     [7] sdiv(y*x^3+x+1,y*x+1);
     divsp: cannot happen
     return to toplevel

参照
     idiv irem, %.

tdiv
----

tdiv(POLY1,POLY2)
     :: POLY1 が POLY2 で割り切れるかどうか調べる.

return
     割り切れるならば商, 割り切れなければ 0

poly1 poly2
     多項式

  * POLY2 が POLY1 を多項式として割り切るかどうか調べる.

  * ある多項式が既約因子であることはわかっているが, その重複度がわからない場合に, tdiv() を繰り返し呼ぶことにより重複度がわかる.

     [11] Y=(x+y+z)^5*(x-y-z)^3;
     x^8+(2*y+2*z)*x^7+(-2*y^2-4*z*y-2*z^2)*x^6+(-6*y^3-18*z*y^2-18*z^2*y-6*z^3)*x^5
     +(6*y^5+30*z*y^4+60*z^2*y^3+60*z^3*y^2+30*z^4*y+6*z^5)*x^3+(2*y^6+12*z*y^5
     +30*z^2*y^4+40*z^3*y^3+30*z^4*y^2+12*z^5*y+2*z^6)*x^2+(-2*y^7-14*z*y^6
     -42*z^2*y^5-70*z^3*y^4-70*z^4*y^3-42*z^5*y^2-14*z^6*y-2*z^7)*x-y^8-8*z*y^7
     -28*z^2*y^6-56*z^3*y^5-70*z^4*y^4-56*z^5*y^3-28*z^6*y^2-8*z^7*y-z^8
     [12] for(I=0,F=x+y+z,T=Y; T=tdiv(T,F); I++);
     [13] I;
     5

参照
     sdiv sdivm srem sremm sqr sqrm.

%
-

POLY % M
     :: 整数による剰余

return
     整数または多項式

poly
     整数または整数係数多項式

m
     整数

  * POLY の各係数を M で割った剰余で置き換えた多項式を返す.

  * 結果の係数は全て正の整数となる.

  * POLY は整数でもよい. この場合, 結果が正に正規化されることを除けば irem() と同様に用いることができる.

  * POLY の係数, M とも整数である必要があるが, チェックは行なわれない.

     [0] (x+2)^5 % 3;
     x^5+x^4+x^3+2*x^2+2*x+2
     [1] (x-2)^5 % 3;
     x^5+2*x^4+x^3+x^2+2*x+1
     [2] (-5) % 4;
     3
     [3] irem(-5,4);
     -1

参照
     idiv irem.

subst, psubst
-------------

subst(RAT[,VARN,RATN]*)

psubst(RAT[,VAR,RAT]*)
     :: RAT の VARN に RATN を代入 (N=1,2,... で左から右に順次代入する).

return
     有理式

rat,ratn
     有理式

varn
     不定元

  * 有理式の特定の不定元に, 定数あるいは多項式, 有理式などを代入するのに用いる.

  * subst(RAT,VAR1,RAT1,VAR2,RAT2,...) は, subst(subst(RAT,VAR1,RAT1),VAR2,RAT2,...) と同じ意味である.

  * 入力の左側から順に代入を繰り返すために, 入力の順によって結果が変わることがある.

  * subst() は, sin() などの函数の引数に対しても代入を行う. psubst() は, このような函数を一つの独立した不定元と見なして, その引数には代入は行わない. (partial substitution のつもり)

  * Asir では, 有理式の約分は自動的には行わないため, 有理式の代入は, 思わぬ計算時間の増大を引き起こす場合がある. 有理式を代入する場合には, 問題に応じた独自の函数を書いて, なるべく分母, 分子が大きくならないように配慮することもしばしば必要となる.

  * 分数を代入する場合も同様である.

     [0] subst(x^3-3*y*x^2+3*y^2*x-y^3,y,2);
     x^3-6*x^2+12*x-8
     [1] subst(@@,x,-1);
     -27
     [2] subst(x^3-3*y*x^2+3*y^2*x-y^3,y,2,x,-1);
     -27
     [3] subst(x*y^3,x,y,y,x);
     x^4
     [4] subst(x*y^3,y,x,x,y);
     y^4
     [5] subst(x*y^3,x,t,y,x,t,y);
     y*x^3
     [6] subst(x*sin(x),x,t);
     sint(t)*t
     [7] psubst(x*sin(x),x,t);
     sin(x)*t

diff
----

diff(RAT[,VARN]*)

diff(RAT,VARLIST)
     :: RAT を VARN あるいは VARLIST の中の変数で順次微分する.

return
     式

rat
     有理式 (初等函数を含んでもよい)

varn
     不定元

varlist
     不定元のリスト

  * 与えられた初等函数を VARN あるいは VARLIST の中の変数で順次微分する.

  * 左側の不定元より, 順に微分していく. つまり, diff(RAT,x,y) は, diff(diff(RAT,x),y) と同じである.

     [0] diff((x+2*y)^2,x);
     2*x+4*y
     [1] diff((x+2*y)^2,x,y);
     4
     [2] diff(x/sin(log(x)+1),x);
     (sin(log(x)+1)-cos(log(x)+1))/(sin(log(x)+1)^2)
     [3] diff(sin(x),[x,x,x,x]);
     sin(x)

res
---

res(VAR,POLY1,POLY2[,MOD])
     :: VAR に関する POLY1 と POLY2 の終結式.

return
     多項式

var
     不定元

poly1,poly2
     多項式

mod
     素数

  * 二つの多項式 POLY1 と POLY2 の, 変数 VAR に関する終結式を求める.

  * 部分終結式アルゴリズムによる.

  * 引数 MOD がある時, GF(MOD) 上での計算を行う.

     [0] res(t,(t^3+1)*x+1,(t^3+1)*y+t);
     -x^3-x^2-y^3

fctr, sqfr
----------

fctr(POLY)
     :: POLY を既約因子に分解する.

sqfr(POLY)
     :: POLY を無平方分解する.

return
     リスト

poly
     有理数係数の多項式

  * 有理数係数の多項式 POLY を因数分解する. fctr() は既約因子分解, sqfr() は無平方因子分解.

  * 結果は [[数係数,1],[因子,重複度],...] なるリスト.

  * 数係数 と 全ての 因子^重複度 の積が POLY と等しい.

  * 数係数 は, (POLY/数係数) が, 整数係数で, 係数の GCD が 1 となるような多項式になるように選ばれている. (ptozp() 参照)

     [0] fctr(x^10-1);
     [[1,1],[x-1,1],[x+1,1],[x^4+x^3+x^2+x+1,1],[x^4-x^3+x^2-x+1,1]]
     [1] fctr(x^3+y^3+(z/3)^3-x*y*z);
     [[1/27,1],[9*x^2+(-9*y-3*z)*x+9*y^2-3*z*y+z^2,1],[3*x+3*y+z,1]]
     [2] A=(a+b+c+d)^2;
     a^2+(2*b+2*c+2*d)*a+b^2+(2*c+2*d)*b+c^2+2*d*c+d^2
     [3] fctr(A);
     [[1,1],[a+b+c+d,2]]
     [4] A=(x+1)*(x^2-y^2)^2;
     x^5+x^4-2*y^2*x^3-2*y^2*x^2+y^4*x+y^4
     [5] sqfr(A);
     [[1,1],[x+1,1],[-x^2+y^2,2]]
     [6] fctr(A);
     [[1,1],[x+1,1],[-x-y,2],[x-y,2]]

参照
     ufctrhint.

ufctrhint
---------

ufctrhint(POLY,HINT)
     :: 次数情報を用いた 1 変数多項式の因数分解

return
     リスト

poly
     有理数係数の 1 変数多項式

hint
     自然数

  * 各既約因子の次数が HINT の倍数であることがわかっている場合に POLY の既約因子分解を fctr() より効率良く行う. POLY が, D 次の拡大体上におけるある多項式のノルム (see 代数的数に関する演算) で無平方である場合, 各既約因子の次数は D の倍数となる. このような場合に用いられる.

     [10] A=t^9-15*t^6-87*t^3-125;
     t^9-15*t^6-87*t^3-125
     0msec
     [11] N=res(t,subst(A,t,x-2*t),A);
     -x^81+1215*x^78-567405*x^75+139519665*x^72-19360343142*x^69+1720634125410*x^66
     -88249977024390*x^63-4856095669551930*x^60+1999385245240571421*x^57
     -15579689952590251515*x^54+15956967531741971462865*x^51
     ...
     +140395588720353973535526123612661444550659875*x^6
     +10122324287343155430042768923500799484375*x^3
     +139262743444407310133459021182733314453125
     980msec + gc : 250msec
     [12] sqfr(N);
     [[-1,1],[x^81-1215*x^78+567405*x^75-139519665*x^72+19360343142*x^69
     -1720634125410*x^66+88249977024390*x^63+4856095669551930*x^60
     -1999385245240571421*x^57+15579689952590251515*x^54
     ...
     -10122324287343155430042768923500799484375*x^3
     -139262743444407310133459021182733314453125,1]]
     20msec
     [13] fctr(N);
     [[-1,1],[x^9-405*x^6-63423*x^3-2460375,1],
     [x^18-486*x^15+98739*x^12-9316620*x^9+945468531*x^6-12368049246*x^3
     +296607516309,1],[x^18-8667*x^12+19842651*x^6+19683,1],
     [x^18-324*x^15+44469*x^12-1180980*x^9+427455711*x^6+2793253896*x^3+31524548679,1],
     [x^18+10773*x^12+2784051*x^6+307546875,1]]
     167.050sec + gc : 1.890sec
     [14] ufctrhint(N,9);
     [[-1,1],[x^9-405*x^6-63423*x^3-2460375,1],
     [x^18-486*x^15+98739*x^12-9316620*x^9+945468531*x^6-12368049246*x^3
     +296607516309,1],[x^18-8667*x^12+19842651*x^6+19683,1],
     [x^18-324*x^15+44469*x^12-1180980*x^9+427455711*x^6+2793253896*x^3+31524548679,1],
     [x^18+10773*x^12+2784051*x^6+307546875,1]]
     119.340sec + gc : 1.300sec

参照
     fctr sqfr.

modfctr
-------

modfctr(POLY,MOD)
     :: 有限体上での 1 変数多項式の因数分解

return
     リスト

poly
     整数係数の 1 変数多項式

mod
     自然数

  * 2^31 未満の自然数 MOD を標数とする素体上で一変数多項式 POLY を既約因子に分解する.

  * 結果は [[数係数,1],[因子,重複度],...] なるリスト.

  * 数係数 と 全ての 因子^重複度 の積が POLY と等しい.

     [0] modfctr(x^10+x^2+1,2147483647);
     [[1,1],[x+1513477736,1],[x+2055628767,1],[x+91854880,1],
     [x+634005911,1],[x+1513477735,1],[x+634005912,1],
     [x^4+1759639395*x^2+2045307031,1]]

参照
     fctr sqfr.

ptozp
-----

ptozp(POLY)
     :: POLY を有理数倍して整数係数多項式にする.

return
     多項式

poly
     多項式

  * 与えられた多項式 POLY に適当な有理数を掛けて, 整数係数かつ係数の GCD が 1 になるようにする.

  * 分数の四則演算は, 整数の演算に比較して遅いため, 種々の多項式演算の前に, 多項式を整数係数にしておくことが望ましい.

  * 有理式を約分する red() で分数係数有理式を約分しても, 分子多項式の係数は有理数のままであり, 有理式の分子を求める nm() では, 分数係数多項式は, 分数係数のままの形で出力されるため, 直ちに整数係数多項式を得る事は出来ない.

     [0] ptozp(2*x+5/3);
     6*x+5
     [1] nm(2*x+5/3);
     2*x+5/3

参照
     nm dn.

prim, cont
----------

prim(POLY[,V])
     :: POLY の原始的部分 (primitive part).

cont(POLY[,V])
     :: POLY の容量 (content).

return poly
     有理数係数多項式

v
     不定元

  * POLY の主変数 (引数 V がある場合には V) に関する原始的部分, 容量を求める.

     [0] E=(y-z)*(x+y)*(x-z)*(2*x-y);
     (2*y-2*z)*x^3+(y^2-3*z*y+2*z^2)*x^2+(-y^3+z^2*y)*x+z*y^3-z^2*y^2
     [1] prim(E);
     2*x^3+(y-2*z)*x^2+(-y^2-z*y)*x+z*y^2
     [2] cont(E);
     y-z
     [3] prim(E,z);
     (y-z)*x-z*y+z^2

参照
     var, ord.

gcd, gcdz
---------

gcd(POLY1,POLY2[,MOD])

gcdz(POLY1,POLY2)
     :: POLY1 と POLY2 の gcd.

return
     多項式

poly1,poly2
     多項式

mod
     素数

  * 二つの多項式の最大公約式 (GCD) を求める.

  * gcd() は有理数体上の多項式としての GCD を返す. すなわち, 結果は整数係数で, かつ係数の GCD が 1 になるような多項式, または, 互いに素の場合は 1 を返す.

  * gcdz() は POLY1, POLY2 ともに整数係数の場合に, 整数環上の多項式としての GCD を返す. すなわち, gcd() の値に, 係数全体の整数 GCDの値を掛けたものを返す.

  * 引数 MOD がある時, gcd() は GF(MOD) 上での GCD を返す.

  * gcd(), gcdz() Extended Zassenhaus アルゴリズムによる. 有限体上の GCD は PRS アルゴリズムによっているため, 大きな問題, GCD が 1 の場合などにおいて効率が悪い.

     [0] gcd(12*(x^2+2*x+1)^2,18*(x^2+(y+1)*x+y)^3);
     x^3+3*x^2+3*x+1
     [1] gcdz(12*(x^2+2*x+1)^2,18*(x^2+(y+1)*x+y)^3);
     6*x^3+18*x^2+18*x+6
     [2] gcd((x+y)*(x-y)^2,(x+y)^2*(x-y));
     x^2-y^2
     [3] gcd((x+y)*(x-y)^2,(x+y)^2*(x-y),2);
     x^3+y*x^2+y^2*x+y^3

参照
     igcd igcdcntl.

red
---

red(RAT)
     :: RAT を約分したもの.

return
     有理式

rat
     有理式

  * Asir は有理数の約分を常に自動的に行う. しかし, 有理式については通分は行うが, 約分はユーザーが指定しない限り行わない. この約分を行うコマンドが red である.

  * EZGCD により RAT の分子, 分母を約分する.

  * 出力される有理式の分母の多項式は, 各係数の GCD が 1 の整数係数多項式である. 分子については整数係数多項式となるとは限らない.

  * GCD は大変重い演算なので, 他の方法で除ける共通因子は可能な限り除くのが望ましい. また, 分母, 分子が大きくなってからのこの函数の呼び出しは, 非常に時間が掛かる場合が多い. 有理式演算を行う場合は, ある程度頻繁に, 約分を行う必要がある.

     [0] (x^3-1)/(x-1);
     (x^3-1)/(x-1)
     [1] red((x^3-1)/(x-1));
     x^2+x+1
     [2] red((x^3+y^3+z^3-3*x*y*z)/(x+y+z));
     x^2+(-y-z)*x+y^2-z*y+z^2
     [3] red((3*x*y)/(12*x^2+21*y^3*x));
     (y)/(4*x+7*y^3)
     [4] red((3/4*x^2+5/6*x)/(2*y*x+4/3*x));
     (9/8*x+5/4)/(3*y+2)

参照
     nm dn, gcd gcdz, ptozp.