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