[BACK]Return to poly.texi CVS log [TXT][DIR] Up to [local] / OpenXM / src / asir-doc / parts / builtin

Annotation of OpenXM/src/asir-doc/parts/builtin/poly.texi, Revision 1.2

1.2     ! noro        1: @comment $OpenXM$
        !             2: \BJP
1.1       noro        3: @node $BB?9`<0$*$h$SM-M}<0$N1i;;(B,,, $BAH$_9~$_H!?t(B
                      4: @section $BB?9`<0(B, $BM-M}<0$N1i;;(B
1.2     ! noro        5: \E
        !             6: \BEG
        !             7: @node Polynomials and rational expressions,,, Built-in Function
        !             8: @section operations with polynomials and rational expressions
        !             9: \E
1.1       noro       10:
                     11: @menu
                     12: * var::
                     13: * vars::
                     14: * uc::
                     15: * coef::
                     16: * deg mindeg::
                     17: * nmono::
                     18: * ord::
                     19: * sdiv sdivm srem sremm sqr sqrm::
                     20: * tdiv::
                     21: * %::
                     22: * subst psubst::
                     23: * diff::
                     24: * res::
                     25: * fctr sqfr::
                     26: * modfctr::
                     27: * ufctrhint::
                     28: * ptozp::
                     29: * prim cont::
                     30: * gcd gcdz::
                     31: * red::
                     32: @end menu
                     33:
1.2     ! noro       34: \JP @node var,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !            35: \EG @node var,,, Polynomials and rational expressions
1.1       noro       36: @subsection @code{var}
                     37: @findex var
                     38:
                     39: @table @t
                     40: @item var(@var{rat})
1.2     ! noro       41: \JP :: @var{rat} $B$N<gJQ?t(B.
        !            42: \EG :: Main variable (indeterminate) of @var{rat}.
1.1       noro       43: @end table
                     44:
                     45: @table @var
                     46: @item return
1.2     ! noro       47: \JP $BITDj85(B
        !            48: \EG indeterminate
1.1       noro       49: @item rat
1.2     ! noro       50: \JP $BM-M}<0(B
        !            51: \EG rational expression
1.1       noro       52: @end table
                     53:
                     54: @itemize @bullet
1.2     ! noro       55: \BJP
1.1       noro       56: @item
                     57: $B<gJQ?t$K4X$7$F$O(B, @xref{Asir $B$G;HMQ2DG=$J7?(B}.
                     58: @item
                     59: $B%G%U%)%k%H$NJQ?t=g=x$O<!$N$h$&$K$J$C$F$$$k(B.
                     60:
                     61: @code{x}, @code{y}, @code{z}, @code{u}, @code{v}, @code{w}, @code{p}, @code{q}, @code{r}, @code{s}, @code{t}, @code{a}, @code{b}, @code{c}, @code{d}, @code{e},
                     62: @code{f}, @code{g}, @code{h}, @code{i}, @code{j}, @code{k}, @code{l}, @code{m}, @code{n}, @code{o},$B0J8e$OJQ?t$N8=$l$?=g(B.
1.2     ! noro       63: \E
        !            64: \BEG
        !            65: @item
        !            66: @xref{Types in Asir} for main variable.
        !            67: @item
        !            68: Indeterminates (variables) are ordered by default as follows.
        !            69:
        !            70: @code{x}, @code{y}, @code{z}, @code{u}, @code{v}, @code{w}, @code{p}, @code{q},
        !            71: @code{r}, @code{s}, @code{t}, @code{a}, @code{b}, @code{c}, @code{d}, @code{e},
        !            72: @code{f}, @code{g}, @code{h}, @code{i}, @code{j}, @code{k}, @code{l}, @code{m},
        !            73: @code{n}, @code{o}. The other variables will be ordered after the above noted variables
        !            74: so that the first comer will be ordered prior to the followers.
        !            75: \E
1.1       noro       76: @end itemize
                     77:
                     78: @example
                     79: [0] var(x^2+y^2+a^2);
                     80: x
                     81: [1] var(a*b*c*d*e);
                     82: a
                     83: [2] var(3/abc+2*xy/efg);
                     84: abc
                     85: @end example
                     86:
                     87: @table @t
1.2     ! noro       88: \JP @item $B;2>H(B
        !            89: \EG @item References
1.1       noro       90: @fref{ord}, @fref{vars}.
                     91: @end table
                     92:
1.2     ! noro       93: \JP @node vars,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !            94: \EG @node vars,,, Polynomials and rational expressions
1.1       noro       95: @subsection @code{vars}
                     96: @findex vars
                     97:
                     98: @table @t
                     99: @item vars(@var{obj})
1.2     ! noro      100: \JP :: @var{obj} $B$K4^$^$l$kJQ?t$N%j%9%H(B.
        !           101: \EG :: A list of variables (indeterminates) in an expression @var{obj}.
1.1       noro      102: @end table
                    103:
                    104: @table @var
                    105: @item return
1.2     ! noro      106: \JP $B%j%9%H(B
        !           107: \EG list
1.1       noro      108: @item obj
1.2     ! noro      109: \JP $BG$0U(B
        !           110: \EG arbitrary
1.1       noro      111: @end table
                    112:
                    113: @itemize @bullet
1.2     ! noro      114: \BJP
1.1       noro      115: @item
                    116: $BM?$($i$l$?<0$K4^$^$l$kJQ?t$N%j%9%H$rJV$9(B.
                    117: @item
                    118: $BJQ?t=g=x$N9b$$$b$N$+$i=g$KJB$Y$k(B.
1.2     ! noro      119: \E
        !           120: \BEG
        !           121: @item
        !           122: Returns a list of variables (indeterminates) contained in a given expression.
        !           123: @item
        !           124: Lists variables according to the variable ordering.
        !           125: \E
1.1       noro      126: @end itemize
                    127:
                    128: @example
                    129: [0] vars(x^2+y^2+a^2);
                    130: [x,y,a]
                    131: [1] vars(3/abc+2*xy/efg);
                    132: [abc,xy,efg]
                    133: [2] vars([x,y,z]);
                    134: [x,y,z]
                    135: @end example
                    136:
                    137: @table @t
1.2     ! noro      138: \JP @item $B;2>H(B
        !           139: \EG @item References
1.1       noro      140: @fref{var}, @fref{uc}, @fref{ord}.
                    141: @end table
                    142:
1.2     ! noro      143: \JP @node uc,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !           144: \EG @node uc,,, Polynomials and rational expressions
1.1       noro      145: @subsection @code{uc}
                    146: @findex uc
                    147:
                    148: @table @t
                    149: @item uc()
1.2     ! noro      150: \JP :: $BL$Dj78?tK!$N$?$a$NITDj85$r@8@.$9$k(B.
        !           151: \EG :: Create a new indeterminate for an undermined coeficient.
1.1       noro      152: @end table
                    153:
                    154: @table @var
                    155: @item return
1.2     ! noro      156: \JP @code{vtype} $B$,(B 1 $B$NITDj85(B
        !           157: \EG indeterminate with its @code{vtype} 1.
1.1       noro      158: @end table
                    159:
                    160: @itemize @bullet
1.2     ! noro      161: \BJP
1.1       noro      162: @item
                    163: @code{uc()} $B$r<B9T$9$k$?$S$K(B, @code{_0}, @code{_1}, @code{_2},... $B$H$$$&(B
                    164: $BITDj85$r@8@.$9$k(B.
                    165: @item
                    166: @code{uc()} $B$G@8@.$5$l$?ITDj85$O(B, $BD>@\%-!<%\!<%I$+$iF~NO$9$k$3$H$,$G$-$J$$(B.
                    167: $B$3$l$O(B, $B%W%m%0%i%`Cf$GL$Dj78?t$r<+F0@8@.$9$k>l9g(B, $BF~NO$J$I$K4^$^$l$k(B
                    168: $BITDj85$HF10l$N$b$N$,@8@.$5$l$k$3$H$rKI$0$?$a$G$"$k(B.
                    169: @item
                    170: $BDL>o$NITDj85(B (@code{vtype} $B$,(B 0) $B$N<+F0@8@.$K$O(B @code{rtostr()},
                    171: @code{strtov()} $B$rMQ$$$k(B.
                    172: @item
                    173: @code{uc()} $B$G@8@.$5$l$?ITDj85$NITDj85$H$7$F$N7?(B (@code{vtype}) $B$O(B 1 $B$G$"$k(B.
                    174: (@xref{$BITDj85$N7?(B})
1.2     ! noro      175: \E
        !           176: \BEG
        !           177: @item
        !           178: At every evaluation of command @code{uc()}, a new indeterminate in
        !           179: the sequence of indeterminates @code{_0}, @code{_1}, @code{_2}, @dots{}
        !           180: is created successively.
        !           181: @item
        !           182: Indeterminates created by @code{uc()} cannot be input on the keyboard.
        !           183: By this property, you are free, no matter how many indeterminates you
        !           184: will create dynamically by a program, from collision of created names
        !           185: with indeterminates input from the keyboard or from program files.
        !           186: @item
        !           187: Functions, @code{rtostr()} and @code{strtov()}, are used to create
        !           188: ordinary indeterminates (indeterminates having 0 for their @code{vtype}).
        !           189: @item
        !           190: Kernel sub-type of indeterminates created by @code{uc()} is 1.
        !           191: (@code{vtype(uc())}=1)
        !           192: \E
1.1       noro      193: @end itemize
                    194:
                    195: @example
                    196: [0] A=uc();
                    197: _0
                    198: [1] B=uc();
                    199: _1
                    200: [2] (uc()+uc())^2;
                    201: _2^2+2*_3*_2+_3^2
                    202: [3] (A+B)^2;
                    203: _0^2+2*_1*_0+_1^2
                    204: @end example
                    205:
                    206: @table @t
1.2     ! noro      207: \JP @item $B;2>H(B
        !           208: \EG @item References
1.1       noro      209: @fref{vtype}, @fref{rtostr}, @fref{strtov}.
                    210: @end table
                    211:
1.2     ! noro      212: \JP @node coef,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !           213: \EG @node coef,,, Polynomials and rational expressions
1.1       noro      214: @subsection @code{coef}
                    215: @findex coef
                    216:
                    217: @table @t
                    218: @item coef(@var{poly},@var{deg}[,@var{var}])
1.2     ! noro      219: \JP :: @var{poly} $B$N(B @var{var} ($B>JN,;~$O<gJQ?t(B) $B$K4X$9$k(B @var{deg} $B<!$N78?t(B.
        !           220: \BEG
        !           221: :: The coefficient of a polynomial @var{poly} at degree @var{deg}
        !           222: with respect to the variable @var{var} (main variable if unspecified).
        !           223: \E
1.1       noro      224: @end table
                    225:
                    226: @table @var
                    227: @item return
1.2     ! noro      228: \JP $BB?9`<0(B
        !           229: \EG polynomial
1.1       noro      230: @item poly
1.2     ! noro      231: \JP $BB?9`<0(B
        !           232: \EG polynomial
1.1       noro      233: @item var
1.2     ! noro      234: \JP $BITDj85(B
        !           235: \EG indeterminate
1.1       noro      236: @item deg
1.2     ! noro      237: \JP $B<+A3?t(B
        !           238: \EG non-negative integer
1.1       noro      239: @end table
                    240:
                    241: @itemize @bullet
1.2     ! noro      242: \BJP
1.1       noro      243: @item
                    244: @var{poly} $B$N(B @var{var} $B$K4X$9$k(B @var{deg} $B<!$N78?t$r=PNO$9$k(B.
                    245: @item
                    246: @var{var} $B$O(B, $B>JN,$9$k$H<gJQ?t(B @t{var}(@var{poly}) $B$@$H$_$J$5$l$k(B.
                    247: @item
                    248: @var{var} $B$,<gJQ?t$G$J$$;~(B, @var{var} $B$,<gJQ?t$N>l9g$KHf3S$7$F(B
                    249: $B8zN($,Mn$A$k(B.
1.2     ! noro      250: \E
        !           251: \BEG
        !           252: @item
        !           253: The coefficient of a polynomial @var{poly} at degree @var{deg}
        !           254: with respect to the variable @var{var}.
        !           255: @item
        !           256: The default value for @var{var} is the main variable, i.e.,
        !           257: @t{var(@var{poly})}.
        !           258: @item
        !           259: For multi-variate polynomials, access to coefficients depends on
        !           260: the specified indeterminates.  For example, taking coef for the main
        !           261: variable is much faster than for other variables.
        !           262: \E
1.1       noro      263: @end itemize
                    264:
                    265: @example
                    266: [0] A = (x+y+z)^3;
                    267: 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
                    268: [1] coef(A,1,y);
                    269: 3*x^2+6*z*x+3*z^2
                    270: [2] coef(A,0);
                    271: y^3+3*z*y^2+3*z^2*y+z^3
                    272: @end example
                    273:
                    274: @table @t
1.2     ! noro      275: \JP @item $B;2>H(B
        !           276: \EG @item References
1.1       noro      277: @fref{var}, @fref{deg mindeg}.
                    278: @end table
                    279:
1.2     ! noro      280: \JP @node deg mindeg,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !           281: \EG @node deg mindeg,,, Polynomials and rational expressions
1.1       noro      282: @subsection @code{deg}, @code{mindeg}
                    283: @findex deg
                    284: @findex mindeg
                    285:
                    286: @table @t
                    287: @item deg(@var{poly},@var{var})
1.2     ! noro      288: \JP :: @var{poly} $B$N(B, $BJQ?t(B @var{var} $B$K4X$9$k:G9b<!?t(B.
        !           289: \EG :: The degree of a polynomial @var{poly} with respect to variable.
1.1       noro      290: @item mindeg(@var{poly},@var{var})
1.2     ! noro      291: \JP :: @var{poly} $B$N(B, $BJQ?t(B @var{var} $B$K4X$9$k:GDc<!?t(B.
        !           292: \BEG
        !           293: :: The least exponent of the terms with non-zero coefficients in
        !           294: a polynomial @var{poly} with respect to the variable @var{var}.
        !           295: In this manual, this quantity is sometimes referred to the minimum
        !           296: degree of a polynomial for short.
        !           297: \E
1.1       noro      298: @end table
                    299:
                    300: @table @var
                    301: @item return
1.2     ! noro      302: \JP $B<+A3?t(B
        !           303: \EG non-negative integer
1.1       noro      304: @item poly
1.2     ! noro      305: \JP $BB?9`<0(B
        !           306: \EG polynomial
1.1       noro      307: @item var
1.2     ! noro      308: \JP $BITDj85(B
        !           309: \EG indeterminate
1.1       noro      310: @end table
                    311:
                    312: @itemize @bullet
1.2     ! noro      313: \BJP
1.1       noro      314: @item
                    315: $BM?$($i$l$?B?9`<0$NJQ?t(B @var{var} $B$K4X$9$k:G9b<!?t(B, $B:GDc<!?t$r=PNO$9$k(B.
                    316: @item
                    317: $BJQ?t(B @var{var} $B$r>JN,$9$k$3$H$O=PMh$J$$(B.
1.2     ! noro      318: \E
        !           319: \BEG
        !           320: @item
        !           321: The least exponent of the terms with non-zero coefficients in
        !           322: a polynomial @var{poly} with respect to the variable @var{var}.
        !           323: In this manual, this quantity is sometimes referred to the minimum
        !           324: degree of a polynomial for short.
        !           325: @item
        !           326: Variable @var{var} must be specified.
        !           327: \E
1.1       noro      328: @end itemize
                    329:
                    330: @example
                    331: [0] deg((x+y+z)^10,x);
                    332: 10
                    333: [1] deg((x+y+z)^10,w);
                    334: 0
                    335: [75] mindeg(x^2+3*x*y,x);
                    336: 1
                    337: @end example
                    338:
1.2     ! noro      339: \JP @node nmono,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !           340: \EG @node nmono,,,Polynomials and rational expressions
1.1       noro      341: @subsection @code{nmono}
                    342: @findex nmono
                    343:
                    344: @table @t
                    345: @item nmono(@var{rat})
1.2     ! noro      346: \JP :: @var{rat} $B$NC19`<0$N9`?t(B.
        !           347: \EG :: Number of monomials in rational expression @var{rat}.
1.1       noro      348: @end table
                    349:
                    350: @table @var
                    351: @item return
1.2     ! noro      352: \JP $B<+A3?t(B
        !           353: \EG non-negative integer
1.1       noro      354: @item rat
1.2     ! noro      355: \JP $BM-M}<0(B
        !           356: \EG rational expression
1.1       noro      357: @end table
                    358:
                    359: @itemize @bullet
1.2     ! noro      360: \BJP
1.1       noro      361: @item
                    362: $BB?9`<0$rE83+$7$?>uBV$G$N(B 0 $B$G$J$$78?t$r;}$DC19`<0$N9`?t$r5a$a$k(B.
                    363: @item
                    364: $BM-M}<0$N>l9g$O(B, $BJ,;R$HJ,Jl$N9`?t$NOB$,JV$5$l$k(B.
                    365: @item
                    366: $BH!?t7A<0(B (@xref{$BITDj85$N7?(B}) $B$O(B, $B0z?t$,2?$G$"$C$F$bC19`$H$_$J$5$l$k(B. (1 $B8D$NITDj85$HF1$8(B. )
1.2     ! noro      367: \E
        !           368: \BEG
        !           369: @item
        !           370: Number of monomials with non-zero number coefficients in the full
        !           371: expanded form of the given polynomial.
        !           372: @item
        !           373: For a rational expression, the sum of the numbers of monomials
        !           374: of the numerator and denominator.
        !           375: @item
        !           376: A function form is regarded as a single indeterminate no matter how
        !           377: complex arguments it has.
        !           378: \E
1.1       noro      379: @end itemize
                    380:
                    381: @example
                    382: [0] nmono((x+y)^10);
                    383: 11
                    384: [1] nmono((x+y)^10/(x+z)^10);
                    385: 22
                    386: [2] nmono(sin((x+y)^10));
                    387: 1
                    388: @end example
                    389:
                    390: @table @t
1.2     ! noro      391: \JP @item $B;2>H(B
        !           392: \EG @item References
1.1       noro      393: @fref{vtype}.
                    394: @end table
                    395:
1.2     ! noro      396: \JP @node ord,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !           397: \EG @node ord,,, Polynomials and rational expressions
1.1       noro      398: @subsection @code{ord}
                    399: @findex ord
                    400:
                    401: @table @t
                    402: @item ord([@var{varlist}])
1.2     ! noro      403: \JP :: $BJQ?t=g=x$N@_Dj(B
        !           404: \EG :: It sets the ordering of indeterminates (variables).
1.1       noro      405: @end table
                    406:
                    407: @table @var
                    408: @item return
1.2     ! noro      409: \JP $BJQ?t$N%j%9%H(B
        !           410: \EG list of indeterminates
1.1       noro      411: @item varlist
1.2     ! noro      412: \JP $BJQ?t$N%j%9%H(B
        !           413: \EG list of indeterminates
1.1       noro      414: @end table
                    415:
                    416: @itemize @bullet
1.2     ! noro      417: \BJP
1.1       noro      418: @item
                    419: $B0z?t$,$"$k$H$-(B, $B0z?t$NJQ?t%j%9%H$r@hF,$K=P$7(B, $B;D$j$NJQ?t$,$=$N8e$K(B
                    420: $BB3$/$h$&$KJQ?t=g=x$r@_Dj$9$k(B. $B0z?t$N$"$k$J$7$K4X$o$i$:(B, @code{ord()}
                    421: $B$N=*N;;~$K$*$1$kJQ?t=g=x%j%9%H$rJV$9(B.
                    422:
                    423: @item
                    424: $B$3$NH!?t$K$h$kJQ?t=g=x$NJQ99$r9T$C$F$b(B, $B4{$K%W%m%0%i%`JQ?t$J$I$K(B
                    425: $BBeF~$5$l$F$$$k<0$NFbIt7A<0$O?7$7$$=g=x$K=>$C$F$OJQ99$5$l$J$$(B.
                    426: $B=>$C$F(B, $B$3$NH!?t$K$h$k=g=x$NJQ99$O(B, @b{Asir} $B$N5/F0D>8e(B,
                    427: $B$"$k$$$O(B, $B?7$?$JJQ?t$,8=$l$?;~E@$K9T$o$l$k(B
                    428: $B$Y$-$G$"$k(B. $B0[$J$kJQ?t=g=x$N$b$H$G@8@.$5$l$?<0$I$&$7$N1i;;(B
                    429: $B$,9T$o$l$?>l9g(B, $BM=4|$;$L7k2L$,@8$:$k$3$H$b$"$jF@$k(B.
1.2     ! noro      430: \E
        !           431: \BEG
        !           432: @item
        !           433: When an argument is given,
        !           434: this function rearranges the ordering of variables (indeterminates)
        !           435: so that the indeterminates in the argument @var{varlist} precede
        !           436: and the other indeterminates follow in the system's variable ordering.
        !           437: Regardless of the existence of an argument, it always returns the
        !           438: final variable ordering.
        !           439:
        !           440: @item
        !           441: Note that no change will be made to the variable ordering of internal
        !           442: forms of objects which already exists in the system, no matter what
        !           443: reordering you specify.  Therefore, the reordering should be limited to
        !           444: the time just after starting @b{Asir}, or to the time when one has
        !           445: decided himself to start a totally new computation which has no relation
        !           446: with the previous results.
        !           447: Note that unexpected results may be obtained from operations between
        !           448: objects which are created under different variable ordering.
        !           449: \E
1.1       noro      450: @end itemize
                    451:
                    452: @example
                    453: [0] ord();
                    454: [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,
                    455: _q,_r,_s,_t,_a,_b,_c,_d,_e,_f,_g,_h,_i,_j,_k,_l,_m,_n,_o,exp(_x),(_x)^(_y),
                    456: log(_x),(_x)^(_y-1),cos(_x),sin(_x),tan(_x),(-_x^2+1)^(-1/2),cosh(_x),sinh(_x),
                    457: tanh(_x),(_x^2+1)^(-1/2),(_x^2-1)^(-1/2)]
                    458: [1] ord([dx,dy,dz,a,b,c]);
                    459: [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,
                    460: _w,_p,_q,_r,_s,_t,_a,_b,_c,_d,_e,_f,_g,_h,_i,_j,_k,_l,_m,_n,_o,exp(_x),
                    461: (_x)^(_y),log(_x),(_x)^(_y-1),cos(_x),sin(_x),tan(_x),(-_x^2+1)^(-1/2),
                    462: cosh(_x),sinh(_x),tanh(_x),(_x^2+1)^(-1/2),(_x^2-1)^(-1/2)]
                    463: @end example
                    464:
1.2     ! noro      465: \JP @node sdiv sdivm srem sremm sqr sqrm,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !           466: \EG @node sdiv sdivm srem sremm sqr sqrm,,, Polynomials and rational expressions
1.1       noro      467: @subsection @code{sdiv}, @code{sdivm}, @code{srem}, @code{sremm}, @code{sqr}, @code{sqrm}
                    468: @findex sdiv
                    469: @findex sdivm
                    470: @findex srem
                    471: @findex sremm
                    472: @findex sqr
                    473: @findex sqrm
                    474:
                    475: @table @t
                    476: @item sdiv(@var{poly1},@var{poly2}[,@var{v}])
                    477: @itemx sdivm(@var{poly1},@var{poly2},@var{mod}[,@var{v}])
1.2     ! noro      478: \JP :: @var{poly1} $B$r(B @var{poly2} $B$G3d$k=|;;$,:G8e$^$G<B9T$G$-$k>l9g$K>&$r5a$a$k(B.
        !           479: \BEG
        !           480: :: Quotient of @var{poly1} divided by @var{poly2} provided that the
        !           481: division can be performed within polynomial arithmetic over the
        !           482: rationals.
        !           483: \E
1.1       noro      484: @item srem(@var{poly1},@var{poly2}[,@var{v}])
                    485: @item sremm(@var{poly1},@var{poly2},@var{mod}[,@var{v}])
1.2     ! noro      486: \JP :: @var{poly1} $B$r(B @var{poly2} $B$G3d$k=|;;$,:G8e$^$G<B9T$G$-$k>l9g$K>jM>$r5a$a$k(B.
        !           487: \BEG
        !           488: :: Remainder of @var{poly1} divided by @var{poly2} provided that the
        !           489: division can be performed within polynomial arithmetic over the
        !           490: rationals.
        !           491: \E
1.1       noro      492: @item sqr(@var{poly1},@var{poly2}[,@var{v}])
                    493: @item sqrm(@var{poly1},@var{poly2},@var{mod}[,@var{v}])
1.2     ! noro      494: \BJP
1.1       noro      495: :: @var{poly1} $B$r(B @var{poly2} $B$G3d$k=|;;$,:G8e$^$G<B9T$G$-$k>l9g$K>&(B, $B>jM>$r(B
                    496: $B5a$a$k(B.
1.2     ! noro      497: \E
        !           498: \BEG
        !           499: :: Quotient and remainder of @var{poly1} divided by @var{poly2} provided
        !           500: that the division can be performed within polynomial arithmetic over
        !           501: the rationals.
        !           502: \E
1.1       noro      503: @end table
                    504:
                    505: @table @var
                    506: @item return
1.2     ! noro      507: \JP @code{sdiv()}, @code{sdivm()}, @code{srem()}, @code{sremm()} : $BB?9`<0(B, @code{sqr()}, @code{sqrm()} : @code{[$B>&(B,$B>jM>(B]} $B$J$k%j%9%H(B
        !           508: \EG @code{sdiv()}, @code{sdivm()}, @code{srem()}, @code{sremm()} : polynomial @code{sqr()}, @code{sqrm()} : a list @code{[quotient,remainder]}
1.1       noro      509: @item poly1 poly2
1.2     ! noro      510: \JP $BB?9`<0(B
        !           511: \EG polynomial
1.1       noro      512: @item v
1.2     ! noro      513: \JP $BITDj85(B
        !           514: \EG indeterminate
1.1       noro      515: @item mod
1.2     ! noro      516: \JP $BAG?t(B
        !           517: \EG prime
1.1       noro      518: @end table
                    519:
                    520: @itemize @bullet
1.2     ! noro      521: \BJP
1.1       noro      522: @item
                    523: @var{poly1} $B$r(B @var{poly2} $B$N<gJQ?t(B @t{var}(@var{poly2})
                    524: ( $B0z?t(B @var{v} $B$,$"$k>l9g$K$O(B @var{v}) $B$K4X$9$kB?9`<0$H8+$F(B,
                    525: @var{poly2} $B$G(B, $B3d$j;;$r9T$&(B.
                    526: @item
                    527: @code{sdivm()}, @code{sremm()}, @code{sqrm()} $B$O(B GF(@var{mod}) $B>e$G7W;;$9$k(B.
                    528: @item
                    529: $BB?9`<0$N=|;;$O(B, $B<g78?t$I$&$7$N3d;;$K$h$jF@$i$l$?>&$H(B, $B<gJQ?t$NE,Ev$JQQ$N(B
                    530: $B@Q$r(B @var{poly2} $B$K3]$1$F(B, @var{poly1} $B$+$i0z$/$H$$$&A`:n$r(B
                    531: @var{poly1} $B$N<!?t$,(B @var{poly2} $B$N<!?t$h$j>.$5$/$J$k$^$G7+$jJV$7$F(B
                    532: $B9T$&(B. $B$3$NA`:n$,(B, $BB?9`<0$NHO0OFb$G9T$o$l$k$?$a$K$O(B, $B3F%9%F%C%W$K$*$$$F(B
                    533: $B<g78?t$I$&$7$N=|;;$,(B, $BB?9`<0$H$7$F$N@0=|$G$"$kI,MW$,$"$k(B. $B$3$l$,(B, $B!V=|;;(B
                    534: $B$,:G8e$^$G<B9T$G$-$k!W$3$H$N0UL#$G$"$k(B.
                    535: @item
                    536: $BE57?E*$J>l9g$H$7$F(B, @var{poly2} $B$N<g78?t$,(B, $BM-M}?t$G$"$k>l9g(B, $B$"$k$$$O(B,
                    537: @var{poly2} $B$,(B @var{poly1} $B$N0x;R$G$"$k$3$H$,$o$+$C$F$$$k>l9g$J$I(B
                    538: $B$,$"$k(B.
                    539: @item
                    540: @code{sqr()} $B$O>&$H>jM>$rF1;~$K5a$a$?$$;~$KMQ$$$k(B.
                    541: @item
                    542: $B@0?t=|;;$N>&(B, $B>jM>$O(B @code{idiv}, @code{irem} $B$rMQ$$$k(B.
                    543: @item
                    544: $B78?t$KBP$9$k>jM>1i;;$O(B @code{%} $B$rMQ$$$k(B.
1.2     ! noro      545: \E
        !           546: \BEG
        !           547: @item
        !           548: Regarding @var{poly1} as an uni-variate polynomial in the main variable
        !           549: of @var{poly2},
        !           550: i.e. @t{var(@var{poly2})} (@var{v} if specified), @code{sdiv()} and
        !           551: @code{srem()} compute
        !           552: the polynomial quotient and remainder of @var{poly1} divided by @var{poly2}.
        !           553: @item @code{sdivm()}, @code{sremm()}, @code{sqrm()} execute the same
        !           554: operation over GF(@var{mod}).
        !           555: @item
        !           556: Division operation of polynomials is performed by the following steps:
        !           557: (1) obtain the quotient of leading coefficients; let it be Q;
        !           558: (2) remove the leading term of @var{poly1} by subtracting, from
        !           559: @var{poly1}, the product of Q with some powers of main variable
        !           560: and @var{poly2}; obtain a new @var{poly1};
        !           561: (3) repeat the above step until the degree of @var{poly1} become smaller
        !           562: than that of @var{poly2}.
        !           563: For fulfillment, by operating in polynomials, of this procedure, the
        !           564: divisions at step (1) in every repetition must be an exact division of
        !           565: polynomials.  This is the true meaning of what we say
        !           566: ``division can be performed within polynomial arithmetic
        !           567: over the rationals.''
        !           568: @item
        !           569: There are typical cases where the division is possible:
        !           570: leading coefficient of @var{poly2} is a rational number;
        !           571: @var{poly2} is a factor of @var{poly1}.
        !           572: @item
        !           573: Use @code{sqr()} to get both the quotient and remainder at once.
        !           574: @item
        !           575: Use @code{idiv()}, @code{irem()} for integer quotient.
        !           576: @item
        !           577: For remainder operation on all integer coefficients, use @code{%}.
        !           578: \E
1.1       noro      579: @end itemize
                    580:
                    581: @example
                    582: [0] sdiv((x+y+z)^3,x^2+y+a);
                    583: x+3*y+3*z
                    584: [1] srem((x+y+z)^2,x^2+y+a);
                    585: (2*y+2*z)*x+y^2+(2*z-1)*y+z^2-a
                    586: [2] X=(x+y+z)*(x-y-z)^2;
                    587: 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
                    588: [3] Y=(x+y+z)^2*(x-y-z);
                    589: 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
                    590: [4] G=gcd(X,Y);
                    591: x^2-y^2-2*z*y-z^2
                    592: [5] sqr(X,G);
                    593: [x-y-z,0]
                    594: [6] sqr(Y,G);
                    595: [x+y+z,0]
                    596: [7] sdiv(y*x^3+x+1,y*x+1);
                    597: divsp: cannot happen
                    598: return to toplevel
                    599: @end example
                    600:
                    601: @table @t
1.2     ! noro      602: \JP @item $B;2>H(B
        !           603: \EG @item References
1.1       noro      604: @fref{idiv irem}, @fref{%}.
                    605: @end table
                    606:
1.2     ! noro      607: \JP @node tdiv,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !           608: \EG @node tdiv,,, Polynomials and rational expressions
1.1       noro      609: @subsection @code{tdiv}
                    610: @findex tdiv
                    611:
                    612: @table @t
                    613: @item tdiv(@var{poly1},@var{poly2})
1.2     ! noro      614: \JP :: @var{poly1} $B$,(B @var{poly2} $B$G3d$j@Z$l$k$+$I$&$+D4$Y$k(B.
        !           615: \EG :: Tests whether @var{poly2} divides @var{poly1}.
1.1       noro      616: @end table
                    617:
                    618: @table @var
                    619: @item return
1.2     ! noro      620: \JP $B3d$j@Z$l$k$J$i$P>&(B, $B3d$j@Z$l$J$1$l$P(B 0
        !           621: \EG Quotient if @var{poly2} divides @var{poly1}, 0 otherwise.
1.1       noro      622: @item poly1 poly2
1.2     ! noro      623: \JP $BB?9`<0(B
        !           624: \EG polynomial
1.1       noro      625: @end table
                    626:
                    627: @itemize @bullet
1.2     ! noro      628: \BJP
1.1       noro      629: @item
                    630: @var{poly2} $B$,(B @var{poly1} $B$rB?9`<0$H$7$F3d$j@Z$k$+$I$&$+D4$Y$k(B.
                    631: @item
                    632: $B$"$kB?9`<0$,4{Ls0x;R$G$"$k$3$H$O$o$+$C$F$$$k$,(B, $B$=$N=EJ#EY$,$o$+$i$J$$(B
                    633: $B>l9g$K(B, @code{tdiv()} $B$r7+$jJV$78F$V$3$H$K$h$j=EJ#EY$,$o$+$k(B.
1.2     ! noro      634: \E
        !           635: \BEG
        !           636: @item
        !           637: Tests whether @var{poly2} divides @var{poly1} in polynomial ring.
        !           638: @item
        !           639: One application of this function: Consider the case where a polynomial
        !           640: is certainly an irreducible factor of the other polynomial, but
        !           641: the multiplicity of the factor is unknown.  Application of @code{tdiv()}
        !           642: to the polynomials repeatedly yields the multiplicity.
        !           643: \E
1.1       noro      644: @end itemize
                    645:
                    646: @example
                    647: [11] Y=(x+y+z)^5*(x-y-z)^3;
                    648: 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
                    649: +(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
                    650: +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
                    651: -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
                    652: -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
                    653: [12] for(I=0,F=x+y+z,T=Y; T=tdiv(T,F); I++);
                    654: [13] I;
                    655: 5
                    656: @end example
                    657:
                    658: @table @t
1.2     ! noro      659: \JP @item $B;2>H(B
        !           660: \EG @item References
1.1       noro      661: @fref{sdiv sdivm srem sremm sqr sqrm}.
                    662: @end table
                    663:
1.2     ! noro      664: \JP @node %,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !           665: \EG @node %,,, Polynomials and rational expressions
1.1       noro      666: @subsection @code{%}
                    667: @findex %
                    668:
                    669: @table @t
                    670: @item @var{poly} % @var{m}
1.2     ! noro      671: \JP :: $B@0?t$K$h$k>jM>(B
        !           672: \EG :: integer remainder to all integer coefficients of the polynomial.
1.1       noro      673: @end table
                    674:
                    675: @table @var
                    676: @item return
1.2     ! noro      677: \JP $B@0?t$^$?$OB?9`<0(B
        !           678: \EG integer or polynomial
1.1       noro      679: @item poly
1.2     ! noro      680: \JP $B@0?t$^$?$O@0?t78?tB?9`<0(B
        !           681: \EG integer or polynomial with integer coefficients
1.1       noro      682: @item m
1.2     ! noro      683: \JP $B@0?t(B
        !           684: \EG intger
1.1       noro      685: @end table
                    686:
                    687: @itemize @bullet
1.2     ! noro      688: \BJP
1.1       noro      689: @item
                    690: @var{poly} $B$N3F78?t$r(B @var{m} $B$G3d$C$?>jM>$GCV$-49$($?B?9`<0$rJV$9(B.
                    691: @item
                    692: $B7k2L$N78?t$OA4$F@5$N@0?t$H$J$k(B.
                    693: @item
                    694: @var{poly} $B$O@0?t$G$b$h$$(B. $B$3$N>l9g(B, $B7k2L$,@5$K@55,2=$5$l$k$3$H$r=|$1$P(B
                    695: @code{irem()} $B$HF1MM$KMQ$$$k$3$H$,$G$-$k(B.
                    696: @item
                    697: @var{poly} $B$N78?t(B, @var{m} $B$H$b@0?t$G$"$kI,MW$,$"$k$,(B, $B%A%'%C%/$O9T$J$o$l$J$$(B.
1.2     ! noro      698: \E
        !           699: \BEG
        !           700: @item
        !           701: Returns a polynomial whose coefficients are remainders of the
        !           702: coefficients of the input polynomial divided by @var{m}.
        !           703: @item
        !           704: The resulting coefficients are all normalized to non-negative integers.
        !           705: @item
        !           706: An integer is allowed for @var{poly}.  This can be used for an
        !           707: alternative for @code{irem()} except that the result is normalized to
        !           708: a non-negative integer.
        !           709: @item
        !           710: Coefficients of @var{poly} and @var{m} must all be integers, though the
        !           711: type checking is not done.
        !           712: \E
1.1       noro      713: @end itemize
                    714:
                    715: @example
                    716: [0] (x+2)^5 % 3;
                    717: x^5+x^4+x^3+2*x^2+2*x+2
                    718: [1] (x-2)^5 % 3;
                    719: x^5+2*x^4+x^3+x^2+2*x+1
                    720: [2] (-5) % 4;
                    721: 3
                    722: [3] irem(-5,4);
                    723: -1
                    724: @end example
                    725:
                    726: @table @t
1.2     ! noro      727: \JP @item $B;2>H(B
        !           728: \EG @item References
1.1       noro      729: @fref{idiv irem}.
                    730: @end table
                    731:
1.2     ! noro      732: \JP @node subst psubst,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !           733: \EG @node subst psubst,,, Polynomials and rational expressions
1.1       noro      734: @subsection @code{subst}, @code{psubst}
                    735: @findex subst
                    736: @findex psubst
                    737:
                    738: @table @t
                    739: @item subst(@var{rat}[,@var{varn},@var{ratn}]*)
                    740: @item psubst(@var{rat}[,@var{var},@var{rat}]*)
1.2     ! noro      741: \BJP
1.1       noro      742: :: @var{rat} $B$N(B @var{varn} $B$K(B @var{ratn} $B$rBeF~(B
                    743: (@var{n=1,2},... $B$G:8$+$i1&$K=g<!BeF~$9$k(B).
1.2     ! noro      744: \E
        !           745: \BEG
        !           746: :: Substitute @var{ratn} for @var{varn} in expression @var{rat}.
        !           747: (@var{n=1,2},@dots{}.
        !           748: Substitution will be done successively from left to right
        !           749: if arguments are repeated.)
        !           750: \E
1.1       noro      751: @end table
                    752:
                    753: @table @var
                    754: @item return
1.2     ! noro      755: \JP $BM-M}<0(B
        !           756: \EG rational expression
1.1       noro      757: @item rat,ratn
1.2     ! noro      758: \JP $BM-M}<0(B
        !           759: \EG rational expression
1.1       noro      760: @item varn
1.2     ! noro      761: \JP $BITDj85(B
        !           762: \EG indeterminate
1.1       noro      763: @end table
                    764:
                    765: @itemize @bullet
1.2     ! noro      766: \BJP
1.1       noro      767: @item
                    768: $BM-M}<0$NFCDj$NITDj85$K(B, $BDj?t$"$k$$$OB?9`<0(B, $BM-M}<0$J$I$rBeF~$9$k$N$KMQ$$$k(B.
                    769: @item
                    770: @t{subst}(@var{rat},@var{var1},@var{rat1},@var{var2},@var{rat2},...) $B$O(B,
                    771: @t{subst}(@t{subst}(@var{rat},@var{var1},@var{rat1}),@var{var2},@var{rat2},...)
                    772: $B$HF1$80UL#$G$"$k(B.
                    773: @item
                    774: $BF~NO$N:8B&$+$i=g$KBeF~$r7+$jJV$9$?$a$K(B, $BF~NO$N=g$K$h$C$F7k2L$,JQ$o$k$3$H$,$"$k(B.
                    775: @item
                    776: @code{subst()} $B$O(B, @code{sin()} $B$J$I$NH!?t$N0z?t$KBP$7$F$bBeF~$r9T$&(B.
                    777: @code{psubst()} $B$O(B, $B$3$N$h$&$JH!?t$r0l$D$NFHN)$7$?ITDj85$H8+$J$7$F(B, $B$=(B
                    778: $B$N0z?t$K$OBeF~$O9T$o$J$$(B. (partial substitution $B$N$D$b$j(B)
                    779: @item
                    780: @b{Asir} $B$G$O(B, $BM-M}<0$NLsJ,$O<+F0E*$K$O9T$o$J$$$?$a(B,
                    781: $BM-M}<0$NBeF~$O(B, $B;W$o$L7W;;;~4V$NA}Bg$r0z$-5/$3$9>l9g$,$"$k(B.
                    782: $BM-M}<0$rBeF~$9$k>l9g$K$O(B, $BLdBj$K1~$8$?FH<+$NH!?t$r=q$$$F(B,
                    783: $B$J$k$Y$/J,Jl(B, $BJ,;R$,Bg$-$/$J$i$J$$$h$&$KG[N8$9$k$3$H$b$7$P$7$PI,MW$H$J$k(B.
                    784: @item
                    785: $BJ,?t$rBeF~$9$k>l9g$bF1MM$G$"$k(B.
1.2     ! noro      786: \E
        !           787: \BEG
        !           788: @item
        !           789: Substitutes rational expressions for specified kernels in a rational
        !           790: expression.
        !           791: @item
        !           792: @t{subst}(@var{rat},@var{var1},@var{rat1},@var{var2},@var{rat2},@dots{})
        !           793: has the same effect as
        !           794: @t{subst}(@t{subst}(@var{rat},@var{var1},@var{rat1}),@var{var2},@var{rat2},@dots{}).
        !           795: @item
        !           796: Note that repeated substitution is done from left to right successively.
        !           797: You may get different result by changing the specification order.
        !           798: @item
        !           799: Ordinary @code{subst()} performs
        !           800: substitution at all levels of a scalar algebraic expression creeping
        !           801: into arguments of function forms recursively.
        !           802: Function @code{psubst()} regards such a function form as an independent
        !           803: indeterminate, and does not attempt to apply substitution to its
        !           804: arguments.  (The name comes after Partial SUBSTitution.)
        !           805: @item
        !           806: Since @b{Asir} does not reduce common divisors of a rational expression
        !           807: automatically, substitution of a rational expression to an expression
        !           808: may cause unexpected increase of computation time.
        !           809: Thus, it is often necessary to write a special function to meet the
        !           810: individual problem so that the denominator and the numerator do not
        !           811: become too large.
        !           812: @item
        !           813: The same applies to substitution by rational numbers.
        !           814: \E
1.1       noro      815: @end itemize
                    816:
                    817: @example
                    818: [0] subst(x^3-3*y*x^2+3*y^2*x-y^3,y,2);
                    819: x^3-6*x^2+12*x-8
                    820: [1] subst(@@@@,x,-1);
                    821: -27
                    822: [2] subst(x^3-3*y*x^2+3*y^2*x-y^3,y,2,x,-1);
                    823: -27
                    824: [3] subst(x*y^3,x,y,y,x);
                    825: x^4
                    826: [4] subst(x*y^3,y,x,x,y);
                    827: y^4
                    828: [5] subst(x*y^3,x,t,y,x,t,y);
                    829: y*x^3
                    830: [6] subst(x*sin(x),x,t);
                    831: sint(t)*t
                    832: [7] psubst(x*sin(x),x,t);
                    833: sin(x)*t
                    834: @end example
                    835:
1.2     ! noro      836: \JP @node diff,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !           837: \EG @node diff,,, Polynomials and rational expressions
1.1       noro      838: @subsection @code{diff}
                    839: @findex diff
                    840:
                    841: @table @t
                    842: @item diff(@var{rat}[,@var{varn}]*)
                    843: @item diff(@var{rat},@var{varlist})
1.2     ! noro      844: \JP :: @var{rat} $B$r(B @var{varn} $B$"$k$$$O(B @var{varlist} $B$NCf$NJQ?t$G=g<!HyJ,$9$k(B.
        !           845: \BEG
        !           846: :: Differentiate @var{rat} successively by @var{var}'s for the first
        !           847: form, or by variables in @var{varlist} for the second form.
        !           848: \E
1.1       noro      849: @end table
                    850:
                    851: @table @var
                    852: @item return
1.2     ! noro      853: \JP $B<0(B
        !           854: \EG expression
1.1       noro      855: @item rat
1.2     ! noro      856: \JP $BM-M}<0(B ($B=iEyH!?t$r4^$s$G$b$h$$(B)
        !           857: \EG rational expression which contains elementary functions.
1.1       noro      858: @item varn
1.2     ! noro      859: \JP $BITDj85(B
        !           860: \EG indeterminate
1.1       noro      861: @item varlist
1.2     ! noro      862: \JP $BITDj85$N%j%9%H(B
        !           863: \EG list of indeterminates
1.1       noro      864: @end table
                    865:
                    866: @itemize @bullet
1.2     ! noro      867: \BJP
1.1       noro      868: @item
                    869: $BM?$($i$l$?=iEyH!?t$r(B @var{varn} $B$"$k$$$O(B @var{varlist} $B$NCf$NJQ?t$G(B
                    870: $B=g<!HyJ,$9$k(B.
                    871: @item
                    872: $B:8B&$NITDj85$h$j(B, $B=g$KHyJ,$7$F$$$/(B. $B$D$^$j(B, @t{diff}(@var{rat},@t{x,y}) $B$O(B,
                    873: @t{diff}(@t{diff}(@var{rat},@t{x}),@t{y}) $B$HF1$8$G$"$k(B.
1.2     ! noro      874: \E
        !           875: \BEG
        !           876: @item
        !           877: Differentiate @var{rat} successively by @var{var}'s for the first
        !           878: form, or by variables in @var{varlist} for the second form.
        !           879: @item
        !           880: differentiation is performed by the specified indeterminates (variables)
        !           881: from left to right.
        !           882: @t{diff}(@var{rat},@t{x,y}) is the same as
        !           883: @t{diff}(@t{diff}(@var{rat},@t{x}),@t{y}).
        !           884: \E
1.1       noro      885: @end itemize
                    886:
                    887: @example
                    888: [0] diff((x+2*y)^2,x);
                    889: 2*x+4*y
                    890: [1] diff((x+2*y)^2,x,y);
                    891: 4
                    892: [2] diff(x/sin(log(x)+1),x);
                    893: (sin(log(x)+1)-cos(log(x)+1))/(sin(log(x)+1)^2)
                    894: [3] diff(sin(x),[x,x,x,x]);
                    895: sin(x)
                    896: @end example
                    897:
1.2     ! noro      898: \JP @node res,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !           899: \EG @node res,,, Polynomials and rational expressions
1.1       noro      900: @subsection @code{res}
                    901: @findex res
                    902:
                    903: @table @t
                    904: @item res(@var{var},@var{poly1},@var{poly2}[,@var{mod}])
1.2     ! noro      905: \JP :: @var{var} $B$K4X$9$k(B @var{poly1} $B$H(B @var{poly2} $B$N=*7k<0(B.
        !           906: \EG :: Resultant of @var{poly1} and @var{poly2} with respect to @var{var}.
1.1       noro      907: @end table
                    908:
                    909: @table @var
                    910: @item return
1.2     ! noro      911: \JP $BB?9`<0(B
        !           912: \EG polynomial
1.1       noro      913: @item var
1.2     ! noro      914: \JP $BITDj85(B
        !           915: \EG indeterminate
1.1       noro      916: @item poly1,poly2
1.2     ! noro      917: \JP $BB?9`<0(B
        !           918: \EG polynomial
1.1       noro      919: @item mod
1.2     ! noro      920: \JP $BAG?t(B
        !           921: \EG prime
1.1       noro      922: @end table
                    923:
                    924: @itemize @bullet
1.2     ! noro      925: \BJP
1.1       noro      926: @item
                    927: $BFs$D$NB?9`<0(B @var{poly1} $B$H(B @var{poly2} $B$N(B, $BJQ?t(B @var{var} $B$K4X$9$k(B
                    928: $B=*7k<0$r5a$a$k(B.
                    929: @item
                    930: $BItJ,=*7k<0%"%k%4%j%:%`$K$h$k(B.
                    931: @item
                    932: $B0z?t(B @var{mod} $B$,$"$k;~(B, GF(@var{mod}) $B>e$G$N7W;;$r9T$&(B.
1.2     ! noro      933: \E
        !           934: \BEG
        !           935: @item
        !           936: Resultant of two polynomials @var{poly1} and @var{poly2}
        !           937: with respect to @var{var}.
        !           938: @item
        !           939: Sub-resultant algorithm is used to compute the resultant.
        !           940: @item
        !           941: The computation is done over GF(@var{mod}) if @var{mod} is specified.
        !           942: \E
1.1       noro      943: @end itemize
                    944:
                    945: @example
                    946: [0] res(t,(t^3+1)*x+1,(t^3+1)*y+t);
                    947: -x^3-x^2-y^3
                    948: @end example
                    949:
1.2     ! noro      950: \JP @node fctr sqfr,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !           951: \EG @node fctr sqfr,,, Polynomials and rational expressions
1.1       noro      952: @subsection @code{fctr}, @code{sqfr}
                    953: @findex fctr
                    954: @findex sqfr
                    955:
                    956: @table @t
                    957: @item fctr(@var{poly})
1.2     ! noro      958: \JP :: @var{poly} $B$r4{Ls0x;R$KJ,2r$9$k(B.
        !           959: \EG :: Factorize polynomial @var{poly} over the rationals.
1.1       noro      960: @item sqfr(@var{poly})
1.2     ! noro      961: \JP :: @var{poly} $B$rL5J?J}J,2r$9$k(B.
        !           962: \EG :: Gets a square-free factorization of polynomial @var{poly}.
1.1       noro      963: @end table
                    964:
                    965: @table @var
                    966: @item return
1.2     ! noro      967: \JP $B%j%9%H(B
        !           968: \EG list
1.1       noro      969: @item poly
1.2     ! noro      970: \JP $BM-M}?t78?t$NB?9`<0(B
        !           971: \EG polynomial with rational coefficients
1.1       noro      972: @end table
                    973:
                    974: @itemize @bullet
1.2     ! noro      975: \BJP
1.1       noro      976: @item
                    977: $BM-M}?t78?t$NB?9`<0(B @var{poly} $B$r0x?tJ,2r$9$k(B. @code{fctr()} $B$O4{Ls0x;RJ,2r(B,
                    978: @code{sqfr()} $B$OL5J?J}0x;RJ,2r(B.
                    979: @item
                    980: $B7k2L$O(B [[@b{$B?t78?t(B},1],[@b{$B0x;R(B},@b{$B=EJ#EY(B}],...] $B$J$k%j%9%H(B.
                    981: @item
                    982: @b{$B?t78?t(B} $B$H(B $BA4$F$N(B @b{$B0x;R(B}^@b{$B=EJ#EY(B} $B$N@Q$,(B @var{poly} $B$HEy$7$$(B.
                    983: @item
                    984: @b{$B?t78?t(B} $B$O(B, (@var{poly}/@b{$B?t78?t(B}) $B$,(B, $B@0?t78?t$G(B, $B78?t$N(B GCD $B$,(B 1 $B$H$J$k(B
                    985: $B$h$&$JB?9`<0$K$J$k$h$&$KA*$P$l$F$$$k(B. (@code{ptozp()} $B;2>H(B)
1.2     ! noro      986: \E
        !           987: \BEG
        !           988: @item
        !           989: Factorizes polynomial @var{poly} over the rationals.
        !           990: @code{fctr()} for irreducible factorization;
        !           991: @code{sqfr()} for square-free factorization.
        !           992: @item
        !           993: The result is represented by a list, whose elements are a pair
        !           994: represented as
        !           995:
        !           996: [[@b{num},1],[@b{factor},@b{multiplicity}],...].
        !           997: @item
        !           998: Products of all @b{factor}^@b{multiplicity} and @b{num} is equal to
        !           999: @var{poly}.
        !          1000: @item
        !          1001: The number @b{num} is determined so that (@var{poly}/@b{num}) is an
        !          1002: integral polynomial and its content (GCD of all coefficients) is 1.
        !          1003: (@xref{ptozp}.)
        !          1004: \E
1.1       noro     1005: @end itemize
                   1006:
                   1007: @example
                   1008: [0] fctr(x^10-1);
                   1009: [[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]]
                   1010: [1] fctr(x^3+y^3+(z/3)^3-x*y*z);
                   1011: [[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]]
                   1012: [2] A=(a+b+c+d)^2;
                   1013: a^2+(2*b+2*c+2*d)*a+b^2+(2*c+2*d)*b+c^2+2*d*c+d^2
                   1014: [3] fctr(A);
                   1015: [[1,1],[a+b+c+d,2]]
                   1016: [4] A=(x+1)*(x^2-y^2)^2;
                   1017: x^5+x^4-2*y^2*x^3-2*y^2*x^2+y^4*x+y^4
                   1018: [5] sqfr(A);
                   1019: [[1,1],[x+1,1],[-x^2+y^2,2]]
                   1020: [6] fctr(A);
                   1021: [[1,1],[x+1,1],[-x-y,2],[x-y,2]]
                   1022: @end example
                   1023:
                   1024: @table @t
1.2     ! noro     1025: \JP @item $B;2>H(B
        !          1026: \EG @item References
1.1       noro     1027: @fref{ufctrhint}.
                   1028: @end table
                   1029:
1.2     ! noro     1030: \JP @node ufctrhint,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !          1031: \EG @node ufctrhint,,, Polynomials and rational expressions
1.1       noro     1032: @subsection @code{ufctrhint}
                   1033: @findex ufctrhint
                   1034:
                   1035: @table @t
                   1036: @item ufctrhint(@var{poly},@var{hint})
1.2     ! noro     1037: \JP :: $B<!?t>pJs$rMQ$$$?(B 1 $BJQ?tB?9`<0$N0x?tJ,2r(B
        !          1038: \BEG
        !          1039: :: Factorizes uni-variate polynomial @var{poly} over the rational number
        !          1040: field when the degrees of its factors are known to be some integer
        !          1041: multiples of @var{hint}.
        !          1042: \E
1.1       noro     1043: @end table
                   1044:
                   1045: @table @var
                   1046: @item return
1.2     ! noro     1047: \JP $B%j%9%H(B
        !          1048: \EG list
1.1       noro     1049: @item poly
1.2     ! noro     1050: \JP $BM-M}?t78?t$N(B 1 $BJQ?tB?9`<0(B
        !          1051: \EG uni-variate polynomial with rational coefficients
1.1       noro     1052: @item hint
1.2     ! noro     1053: \JP $B<+A3?t(B
        !          1054: \EG non-negative integer
1.1       noro     1055: @end table
                   1056:
                   1057: @itemize @bullet
1.2     ! noro     1058: \BJP
1.1       noro     1059: @item
                   1060: $B3F4{Ls0x;R$N<!?t$,(B @var{hint} $B$NG\?t$G$"$k$3$H$,$o$+$C$F$$$k>l9g$K(B
                   1061: @var{poly} $B$N4{Ls0x;RJ,2r$r(B @code{fctr()} $B$h$j8zN(NI$/9T$&(B.
                   1062: @var{poly} $B$,(B, @var{d} $B<!$N3HBgBN>e$K$*$1$k(B
                   1063: $B$"$kB?9`<0$N%N%k%`(B (@xref{$BBe?tE*?t$K4X$9$k1i;;(B}) $B$GL5J?J}$G$"$k>l9g(B,
                   1064: $B3F4{Ls0x;R$N<!?t$O(B @var{d} $B$NG\?t$H$J$k(B. $B$3$N$h$&$J>l9g$K(B
                   1065: $BMQ$$$i$l$k(B.
1.2     ! noro     1066: \E
        !          1067: \BEG
        !          1068: @item
        !          1069: By any reason, if the degree of all the irreducible factors of @var{poly}
        !          1070: is known to be some multiples of @var{hint}, factors can be computed
        !          1071: more efficiently by the knowledge than @code{fctr()}.
        !          1072: @item
        !          1073: When @var{hint} is 1, @code{ufctrhint()} is the same as @code{fctr()} for
        !          1074: uni-variate polynomials.
        !          1075: An typical application where @code{ufctrhint()} is effective:
        !          1076: Consider the case where @var{poly} is a norm (@xref{Algebraic numbers})
        !          1077: of a certain polynomial over an extension field with its extension
        !          1078: degree @var{d}, and it is square free;  Then, every irreducible factor
        !          1079: has a degree that is a multiple of @var{d}.
        !          1080: \E
1.1       noro     1081: @end itemize
                   1082:
                   1083: @example
                   1084: [10] A=t^9-15*t^6-87*t^3-125;
                   1085: t^9-15*t^6-87*t^3-125
                   1086: 0msec
                   1087: [11] N=res(t,subst(A,t,x-2*t),A);
                   1088: -x^81+1215*x^78-567405*x^75+139519665*x^72-19360343142*x^69+1720634125410*x^66
                   1089: -88249977024390*x^63-4856095669551930*x^60+1999385245240571421*x^57
                   1090: -15579689952590251515*x^54+15956967531741971462865*x^51
                   1091: ...
                   1092: +140395588720353973535526123612661444550659875*x^6
                   1093: +10122324287343155430042768923500799484375*x^3
                   1094: +139262743444407310133459021182733314453125
                   1095: 980msec + gc : 250msec
                   1096: [12] sqfr(N);
                   1097: [[-1,1],[x^81-1215*x^78+567405*x^75-139519665*x^72+19360343142*x^69
                   1098: -1720634125410*x^66+88249977024390*x^63+4856095669551930*x^60
                   1099: -1999385245240571421*x^57+15579689952590251515*x^54
                   1100: ...
                   1101: -10122324287343155430042768923500799484375*x^3
                   1102: -139262743444407310133459021182733314453125,1]]
                   1103: 20msec
                   1104: [13] fctr(N);
                   1105: [[-1,1],[x^9-405*x^6-63423*x^3-2460375,1],
                   1106: [x^18-486*x^15+98739*x^12-9316620*x^9+945468531*x^6-12368049246*x^3
                   1107: +296607516309,1],[x^18-8667*x^12+19842651*x^6+19683,1],
                   1108: [x^18-324*x^15+44469*x^12-1180980*x^9+427455711*x^6+2793253896*x^3+31524548679,1],
                   1109: [x^18+10773*x^12+2784051*x^6+307546875,1]]
                   1110: 167.050sec + gc : 1.890sec
                   1111: [14] ufctrhint(N,9);
                   1112: [[-1,1],[x^9-405*x^6-63423*x^3-2460375,1],
                   1113: [x^18-486*x^15+98739*x^12-9316620*x^9+945468531*x^6-12368049246*x^3
                   1114: +296607516309,1],[x^18-8667*x^12+19842651*x^6+19683,1],
                   1115: [x^18-324*x^15+44469*x^12-1180980*x^9+427455711*x^6+2793253896*x^3+31524548679,1],
                   1116: [x^18+10773*x^12+2784051*x^6+307546875,1]]
                   1117: 119.340sec + gc : 1.300sec
                   1118: @end example
                   1119:
                   1120: @table @t
1.2     ! noro     1121: \JP @item $B;2>H(B
        !          1122: \EG @item References
1.1       noro     1123: @fref{fctr sqfr}.
                   1124: @end table
                   1125:
1.2     ! noro     1126: \JP @node modfctr,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !          1127: \EG @node modfctr,,, Polynomials and rational expressions
1.1       noro     1128: @subsection @code{modfctr}
                   1129: @findex modfctr
                   1130:
                   1131: @table @t
                   1132: @item modfctr(@var{poly},@var{mod})
1.2     ! noro     1133: \JP :: $BM-8BBN>e$G$N(B 1 $BJQ?tB?9`<0$N0x?tJ,2r(B
        !          1134: \EG :: Univariate factorizer over small finite fields
1.1       noro     1135: @end table
                   1136:
                   1137: @table @var
                   1138: @item return
1.2     ! noro     1139: \JP $B%j%9%H(B
        !          1140: \EG list
1.1       noro     1141: @item poly
1.2     ! noro     1142: \JP $B@0?t78?t$N(B 1 $BJQ?tB?9`<0(B
        !          1143: \EG univariate polynomial with integer coefficients
1.1       noro     1144: @item mod
1.2     ! noro     1145: \JP $B<+A3?t(B
        !          1146: \EG non-negative integer
1.1       noro     1147: @end table
                   1148:
                   1149: @itemize @bullet
1.2     ! noro     1150: \BJP
1.1       noro     1151: @item
                   1152: 2^31 $BL$K~$N<+A3?t(B @var{mod} $B$rI8?t$H$9$kAGBN>e$G0lJQ?tB?9`<0(B
                   1153: @var{poly} $B$r4{Ls0x;R$KJ,2r$9$k(B.
                   1154: @item
                   1155: $B7k2L$O(B [[@b{$B?t78?t(B},1],[@b{$B0x;R(B},@b{$B=EJ#EY(B}],...] $B$J$k%j%9%H(B.
                   1156: @item
                   1157: @b{$B?t78?t(B} $B$H(B $BA4$F$N(B @b{$B0x;R(B}^@b{$B=EJ#EY(B} $B$N@Q$,(B @var{poly} $B$HEy$7$$(B.
1.2     ! noro     1158: @item
        !          1159: $BBg$-$J0L?t$r;}$DM-8BBN>e$N0x?tJ,2r$K$O(B @code{fctr_ff} $B$rMQ$$$k(B.
        !          1160: (@ref{$BM-8BBN$K4X$9$k1i;;(B},@pxref{fctr_ff}).
        !          1161: \E
        !          1162: \BEG
        !          1163: @item
        !          1164: This function factorizes a univarate polynomial @var{poly} over
        !          1165: the finite prime field of characteristic @var{mod}, where
        !          1166: @var{mod} must be smaller than 2^31.
        !          1167: @item
        !          1168: The result is represented by a list, whose elements are a pair
        !          1169: represented as
        !          1170:
        !          1171: [[@b{num},1],[@b{factor},@b{multiplicity}],...].
        !          1172: @item
        !          1173: Products of all @b{factor}^@b{multiplicity} and @b{num} is equal to
        !          1174: @var{poly}.
        !          1175: @item
        !          1176: To factorize polynomials over large finite fields, use
        !          1177: @code{fctr_ff} (@pxref{Finite fields},@ref{fctr_ff}).
        !          1178: \E
1.1       noro     1179: @end itemize
                   1180:
                   1181: @example
                   1182: [0] modfctr(x^10+x^2+1,2147483647);
                   1183: [[1,1],[x+1513477736,1],[x+2055628767,1],[x+91854880,1],
                   1184: [x+634005911,1],[x+1513477735,1],[x+634005912,1],
                   1185: [x^4+1759639395*x^2+2045307031,1]]
                   1186: @end example
                   1187:
                   1188: @table @t
1.2     ! noro     1189: \JP @item $B;2>H(B
        !          1190: \EG @item References
1.1       noro     1191: @fref{fctr sqfr}.
                   1192: @end table
                   1193:
1.2     ! noro     1194: \JP @node ptozp,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !          1195: \EG @node ptozp,,, Polynomials and rational expressions
1.1       noro     1196: @subsection @code{ptozp}
                   1197: @findex ptozp
                   1198:
                   1199: @table @t
                   1200: @item ptozp(@var{poly})
1.2     ! noro     1201: \JP :: @var{poly} $B$rM-M}?tG\$7$F@0?t78?tB?9`<0$K$9$k(B.
        !          1202: \BEG
        !          1203: :: Converts a polynomial @var{poly} with rational coefficients into
        !          1204: an integral polynomial such that GCD of all its coefficients is 1.
        !          1205: \E
1.1       noro     1206: @end table
                   1207:
                   1208: @table @var
                   1209: @item return
1.2     ! noro     1210: \JP $BB?9`<0(B
        !          1211: \EG polynomial
1.1       noro     1212: @item poly
1.2     ! noro     1213: \JP $BB?9`<0(B
        !          1214: \EG polynomial
1.1       noro     1215: @end table
                   1216:
                   1217: @itemize @bullet
1.2     ! noro     1218: \BJP
1.1       noro     1219: @item
                   1220: $BM?$($i$l$?B?9`<0(B @var{poly} $B$KE,Ev$JM-M}?t$r3]$1$F(B, $B@0?t78?t$+$D(B
                   1221: $B78?t$N(B GCD $B$,(B 1 $B$K$J$k$h$&$K$9$k(B.
                   1222: @item
                   1223: $BJ,?t$N;MB'1i;;$O(B, $B@0?t$N1i;;$KHf3S$7$FCY$$$?$a(B, $B<o!9$NB?9`<01i;;(B
                   1224: $B$NA0$K(B, $BB?9`<0$r@0?t78?t$K$7$F$*$/$3$H$,K>$^$7$$(B.
                   1225: @item
                   1226: $BM-M}<0$rLsJ,$9$k(B @code{red()} $B$GJ,?t78?tM-M}<0$rLsJ,$7$F$b(B,
                   1227: $BJ,;RB?9`<0$N78?t$OM-M}?t$N$^$^$G$"$j(B, $BM-M}<0$NJ,;R$r5a$a$k(B
                   1228: @code{nm()} $B$G$O(B, $BJ,?t78?tB?9`<0$O(B, $BJ,?t78?t$N$^$^$N7A$G=PNO$5$l$k$?$a(B,
                   1229: $BD>$A$K@0?t78?tB?9`<0$rF@$k;v$O=PMh$J$$(B.
1.2     ! noro     1230: \E
        !          1231: \BEG
        !          1232: @item
        !          1233: Converts the given polynomial by multiplying some rational number
        !          1234: into an integral polynomial such that GCD of all its coefficients is 1.
        !          1235: @item
        !          1236: In general, operations on polynomials can be
        !          1237: performed faster for integer coefficients than for rational number
        !          1238: coefficients.  Therefore, this function is conveniently used to improve
        !          1239: efficiency.
        !          1240: @item
        !          1241: Function @code{red} does not convert rational coefficients of the
        !          1242: numerator.
        !          1243: You cannot obtain an integral polynomial by direct use of the function
        !          1244: @code{nm()}.  The function @code{nm()} returns the numerator of its
        !          1245: argument, and a polynomial with rational coefficients is
        !          1246: the numerator of itself and will be returned as it is.
        !          1247: \E
1.1       noro     1248: @end itemize
                   1249:
                   1250: @example
                   1251: [0] ptozp(2*x+5/3);
                   1252: 6*x+5
                   1253: [1] nm(2*x+5/3);
                   1254: 2*x+5/3
                   1255: @end example
                   1256:
                   1257: @table @t
1.2     ! noro     1258: \JP @item $B;2>H(B
        !          1259: \EG @item References
1.1       noro     1260: @fref{nm dn}.
                   1261: @end table
                   1262:
1.2     ! noro     1263: \JP @node prim cont,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !          1264: \EG @node prim cont,,, Polynomials and rational expressions
1.1       noro     1265: @subsection @code{prim}, @code{cont}
                   1266: @findex prim
                   1267:
                   1268: @table @t
                   1269: @item prim(@var{poly}[,@var{v}])
1.2     ! noro     1270: \JP :: @var{poly} $B$N86;OE*ItJ,(B (primitive part).
        !          1271: \EG :: Primitive part of @var{poly}.
1.1       noro     1272: @item cont(@var{poly}[,@var{v}])
1.2     ! noro     1273: \JP :: @var{poly} $B$NMFNL(B (content).
        !          1274: \EG :: Content of @var{poly}.
1.1       noro     1275: @end table
                   1276:
                   1277: @table @var
                   1278: @item return poly
1.2     ! noro     1279: \JP $BM-M}?t78?tB?9`<0(B
        !          1280: \EG polynomial over the rationals
1.1       noro     1281: @item v
1.2     ! noro     1282: \JP $BITDj85(B
        !          1283: \EG indeterminate
1.1       noro     1284: @end table
                   1285:
                   1286: @itemize @bullet
1.2     ! noro     1287: \BJP
1.1       noro     1288: @item
                   1289: @var{poly} $B$N<gJQ?t(B ($B0z?t(B @var{v} $B$,$"$k>l9g$K$O(B @var{v})
                   1290: $B$K4X$9$k86;OE*ItJ,(B, $BMFNL$r5a$a$k(B.
1.2     ! noro     1291: \E
        !          1292: \BEG
        !          1293: @item
        !          1294: The primitive part and the content of a polynomial @var{poly}
        !          1295: with respect to its main variable (@var{v} if specified).
        !          1296: \E
1.1       noro     1297: @end itemize
                   1298:
                   1299: @example
                   1300: [0] E=(y-z)*(x+y)*(x-z)*(2*x-y);
                   1301: (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
                   1302: [1] prim(E);
                   1303: 2*x^3+(y-2*z)*x^2+(-y^2-z*y)*x+z*y^2
                   1304: [2] cont(E);
                   1305: y-z
                   1306: [3] prim(E,z);
                   1307: (y-z)*x-z*y+z^2
                   1308: @end example
                   1309:
                   1310: @table @t
1.2     ! noro     1311: \JP @item $B;2>H(B
        !          1312: \EG @item References
1.1       noro     1313: @fref{var}, @fref{ord}.
                   1314: @end table
                   1315:
1.2     ! noro     1316: \JP @node gcd gcdz,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !          1317: \EG @node gcd gcdz,,, Polynomials and rational expressions
1.1       noro     1318: @subsection @code{gcd}, @code{gcdz}
                   1319: @findex gcd
                   1320:
                   1321: @table @t
                   1322: @item gcd(@var{poly1},@var{poly2}[,@var{mod}])
                   1323: @item gcdz(@var{poly1},@var{poly2})
1.2     ! noro     1324: \JP :: @var{poly1} $B$H(B @var{poly2} $B$N(B gcd.
        !          1325: \EG :: The polynomial greatest common divisor of @var{poly1} and @var{poly2}.
1.1       noro     1326: @end table
                   1327:
                   1328: @table @var
                   1329: @item return
1.2     ! noro     1330: \JP $BB?9`<0(B
        !          1331: \EG polynomial
1.1       noro     1332: @item poly1,poly2
1.2     ! noro     1333: \JP $BB?9`<0(B
        !          1334: \EG polynomial
1.1       noro     1335: @item mod
1.2     ! noro     1336: \JP $BAG?t(B
        !          1337: \EG prime
1.1       noro     1338: @end table
                   1339:
                   1340: @itemize @bullet
1.2     ! noro     1341: \BJP
1.1       noro     1342: @item
                   1343: $BFs$D$NB?9`<0$N:GBg8xLs<0(B (GCD) $B$r5a$a$k(B.
                   1344: @item
                   1345: @code{gcd()} $B$OM-M}?tBN>e$NB?9`<0$H$7$F$N(B GCD $B$rJV$9(B.
                   1346: $B$9$J$o$A(B, $B7k2L$O@0?t78?t$G(B, $B$+$D78?t$N(B GCD
                   1347: $B$,(B 1 $B$K$J$k$h$&$JB?9`<0(B, $B$^$?$O(B, $B8_$$$KAG$N>l9g$O(B 1 $B$rJV$9(B.
                   1348: @item
                   1349: @code{gcdz()} $B$O(B @var{poly1}, @var{poly2} $B$H$b$K@0?t78?t$N>l9g$K(B,
                   1350: $B@0?t4D>e$NB?9`<0$H$7$F$N(B GCD $B$rJV$9(B.
                   1351: $B$9$J$o$A(B, @code{gcd()} $B$NCM$K(B, $B78?tA4BN$N@0?t(B GCD$B$NCM$r3]$1$?$b$N$rJV$9(B.
                   1352: @item
                   1353: $B0z?t(B @var{mod} $B$,$"$k;~(B, @code{gcd()} $B$O(B GF(@var{mod}) $B>e$G$N(B GCD $B$rJV$9(B.
                   1354: @item
                   1355: @code{gcd()}, @code{gcdz()} Extended Zassenhaus $B%"%k%4%j%:%`$K$h$k(B.
                   1356: $BM-8BBN>e$N(B GCD $B$O(B PRS $B%"%k%4%j%:%`$K$h$C$F$$$k$?$a(B, $BBg$-$JLdBj(B,
                   1357: GCD $B$,(B 1 $B$N>l9g$J$I$K$*$$$F8zN($,0-$$(B.
1.2     ! noro     1358: \E
        !          1359: \BEG
        !          1360: @item
        !          1361: Functions @code{gcd()} and @code{gcdz()} return the greatest common divisor
        !          1362: (GCD) of the given two polynomials.
        !          1363: @item
        !          1364: Function @code{gcd()} returns an integral polynomial GCD over the
        !          1365: rational number field.  The coefficients are normalized such that
        !          1366: their GCD is 1.  It returns 1 in case that the given polynomials are
        !          1367: mutually prime.
        !          1368: @item
        !          1369: Function @code{gcdz()} works for arguments of integral polynomials,
        !          1370: and returns a polynomial GCD over the integer ring, that is,
        !          1371: it returns @code{gcd()} multiplied by the contents of all coefficients
        !          1372: of the two input polynomials.
        !          1373: @item
        !          1374: @code{gcd()} computes the GCD over GF(@var{mod}) if @var{mod} is specified.
        !          1375: @item
        !          1376: Polynomial GCD is computed by an improved algorithm based
        !          1377: on Extended Zassenhaus algorithm.
        !          1378: @item
        !          1379: GCD over a finite field is computed by PRS algorithm and it may not be
        !          1380: efficient for large inputs and co-prime inputs.
        !          1381: \E
1.1       noro     1382: @end itemize
                   1383:
                   1384: @example
                   1385: [0] gcd(12*(x^2+2*x+1)^2,18*(x^2+(y+1)*x+y)^3);
                   1386: x^3+3*x^2+3*x+1
                   1387: [1] gcdz(12*(x^2+2*x+1)^2,18*(x^2+(y+1)*x+y)^3);
                   1388: 6*x^3+18*x^2+18*x+6
                   1389: [2] gcd((x+y)*(x-y)^2,(x+y)^2*(x-y));
                   1390: x^2-y^2
                   1391: [3] gcd((x+y)*(x-y)^2,(x+y)^2*(x-y),2);
                   1392: x^3+y*x^2+y^2*x+y^3
                   1393: @end example
                   1394:
                   1395: @table @t
1.2     ! noro     1396: \JP @item $B;2>H(B
        !          1397: \EG @item References
1.1       noro     1398: @fref{igcd igcdcntl}.
                   1399: @end table
                   1400:
1.2     ! noro     1401: \JP @node red,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
        !          1402: \EG @node red,,, Polynomials and rational expressions
1.1       noro     1403: @subsection @code{red}
                   1404: @findex red
                   1405:
                   1406: @table @t
                   1407: @item red(@var{rat})
1.2     ! noro     1408: \JP :: @var{rat} $B$rLsJ,$7$?$b$N(B.
        !          1409: \EG :: Reduced form of @var{rat} by canceling common divisors.
1.1       noro     1410: @end table
                   1411:
                   1412: @table @var
                   1413: @item return
1.2     ! noro     1414: \JP $BM-M}<0(B
        !          1415: \EG rational expression
1.1       noro     1416: @item rat
1.2     ! noro     1417: \JP $BM-M}<0(B
        !          1418: \EG rational expression
1.1       noro     1419: @end table
                   1420:
                   1421: @itemize @bullet
1.2     ! noro     1422: \BJP
1.1       noro     1423: @item
                   1424: @b{Asir} $B$OM-M}?t$NLsJ,$r>o$K<+F0E*$K9T$&(B.
                   1425: $B$7$+$7(B, $BM-M}<0$K$D$$$F$ODLJ,$O9T$&$,(B,
                   1426: $BLsJ,$O%f!<%6!<$,;XDj$7$J$$8B$j9T$o$J$$(B.
                   1427: $B$3$NLsJ,$r9T$&%3%^%s%I$,(B @t{red} $B$G$"$k(B.
                   1428: @item
                   1429: EZGCD $B$K$h$j(B @var{rat} $B$NJ,;R(B, $BJ,Jl$rLsJ,$9$k(B.
                   1430: @item
                   1431: $B=PNO$5$l$kM-M}<0$NJ,Jl$NB?9`<0$O(B, $B3F78?t$N(B GCD $B$,(B 1 $B$N(B
                   1432: $B@0?t78?tB?9`<0$G$"$k(B.
                   1433: $BJ,;R$K$D$$$F$O@0?t78?tB?9`<0$H$J$k$H$O8B$i$J$$(B.
                   1434: @item
                   1435: GCD $B$OBgJQ=E$$1i;;$J$N$G(B, $BB>$NJ}K!$G=|$1$k6&DL0x;R$O2DG=$J8B$j=|$/$N$,(B
                   1436: $BK>$^$7$$(B. $B$^$?(B, $BJ,Jl(B, $BJ,;R$,Bg$-$/$J$C$F$+$i$N$3$NH!?t$N8F$S=P$7$O(B,
                   1437: $BHs>o$K;~4V$,3]$+$k>l9g$,B?$$(B. $BM-M}<01i;;$r9T$&>l9g$O(B, $B$"$kDxEY(B
                   1438: $BIQHK$K(B, $BLsJ,$r9T$&I,MW$,$"$k(B.
1.2     ! noro     1439: \E
        !          1440: \BEG
        !          1441: @item
        !          1442: @b{Asir} automatically performs cancellation of common divisors of rational numb
        !          1443: ers.
        !          1444: But, without an explicit command, it does not cancel common polynomial divisors
        !          1445: of rational expressions.
        !          1446: (Reduction of rational expressions to a common denominator will be always done.)
        !          1447: Use command @t{red()} to perform this cancellation.
        !          1448: @item
        !          1449: Cancel the common divisors of the numerator and the denominator of
        !          1450: a rational expression @var{rat} by computing their GCD.
        !          1451: @item
        !          1452: The denominator polynomial of the result is an integral polynomial
        !          1453: which has no common divisors in its coefficients,
        !          1454: while the numerator may have rational coefficients.
        !          1455: @item
        !          1456: Since GCD computation is a very hard operation, it is desirable to
        !          1457: detect and remove by any means common divisors as far as possible.
        !          1458: Furthermore, a call to this function after swelling of the denominator
        !          1459: and the numerator shall usually take a very long time.  Therefore,
        !          1460: often, to some extent, reduction of common divisors is inevitable for
        !          1461: operations of rational expressions.
        !          1462: \E
1.1       noro     1463: @end itemize
                   1464:
                   1465: @example
                   1466: [0] (x^3-1)/(x-1);
                   1467: (x^3-1)/(x-1)
                   1468: [1] red((x^3-1)/(x-1));
                   1469: x^2+x+1
                   1470: [2] red((x^3+y^3+z^3-3*x*y*z)/(x+y+z));
                   1471: x^2+(-y-z)*x+y^2-z*y+z^2
                   1472: [3] red((3*x*y)/(12*x^2+21*y^3*x));
                   1473: (y)/(4*x+7*y^3)
                   1474: [4] red((3/4*x^2+5/6*x)/(2*y*x+4/3*x));
                   1475: (9/8*x+5/4)/(3*y+2)
                   1476: @end example
                   1477:
                   1478: @table @t
1.2     ! noro     1479: \JP @item $B;2>H(B
        !          1480: \EG @item References
1.1       noro     1481: @fref{nm dn}, @fref{gcd gcdz}, @fref{ptozp}.
                   1482: @end table
                   1483:

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>