Annotation of OpenXM/src/asir-doc/parts/builtin/upoly.texi, Revision 1.3
1.3 ! noro 1: @comment $OpenXM: OpenXM/src/asir-doc/parts/builtin/upoly.texi,v 1.2 1999/12/21 02:47:34 noro Exp $
1.2 noro 2: \BJP
1.1 noro 3: @node $B0lJQ?tB?9`<0$N1i;;(B,,, $BAH$_9~$_H!?t(B
4: @section $B0lJQ?tB?9`<0$N1i;;(B
1.2 noro 5: \E
6: \BEG
7: @node Univariate polynomials,,, Built-in Function
8: @section Univariate polynomials
9: \E
1.1 noro 10:
11: @menu
12: * umul umul_ff usquare usquare_ff utmul utmul_ff::
13: * kmul ksquare ktmul::
14: * utrunc udecomp ureverse::
15: * set_upkara set_uptkara set_upfft::
16: * uinv_as_power_series ureverse_inv_as_power_series::
17: * udiv urem urembymul urembymul_precomp ugcd::
18: @end menu
19:
1.2 noro 20: \JP @node umul umul_ff usquare usquare_ff utmul utmul_ff,,, $B0lJQ?tB?9`<0$N1i;;(B
21: \EG @node umul umul_ff usquare usquare_ff utmul utmul_ff,,, Univariate polynomials
1.1 noro 22: @subsection @code{umul}, @code{umul_ff}, @code{usquare}, @code{usquare_ff}, @code{utmul}, @code{utmul_ff}
23: @findex umul
24: @findex umul_ff
25: @findex usquare
26: @findex usquare_ff
27: @findex utmul
28: @findex utmul_ff
29:
30: @table @t
31: @item umul(@var{p1},@var{p2})
32: @itemx umul_ff(@var{p1},@var{p2})
1.2 noro 33: \JP :: $B0lJQ?tB?9`<0$N9bB.>h;;(B
34: \EG :: Fast multiplication of univariate polynomials
1.1 noro 35: @item usquare(@var{p1})
36: @itemx usquare_ff(@var{p1})
1.2 noro 37: \JP :: $B0lJQ?tB?9`<0$N9bB.(B 2 $B>h;;(B
38: \EG :: Fast squaring of a univariate polynomial
1.1 noro 39: @item utmul(@var{p1},@var{p2},@var{d})
40: @itemx utmul_ff(@var{p1},@var{p2},@var{d})
1.2 noro 41: \JP :: $B0lJQ?tB?9`<0$N9bB.>h;;(B ($BBG$A@Z$j<!?t;XDj(B)
42: \EG :: Fast multiplication of univariate polynomials with truncation
1.1 noro 43: @end table
44:
45: @table @var
46: @item return
1.2 noro 47: \JP $B0lJQ?tB?9`<0(B
48: \EG univariate polynomial
1.1 noro 49: @item p1 p2
1.2 noro 50: \JP $B0lJQ?tB?9`<0(B
51: \EG univariate polynomial
1.1 noro 52: @item d
1.2 noro 53: \JP $BHsIi@0?t(B
54: \EG non-negative integer
1.1 noro 55: @end table
56:
57: @itemize @bullet
1.2 noro 58: \BJP
1.1 noro 59: @item
60: $B0lJQ?tB?9`<0$N>h;;$r(B, $B<!?t$K1~$8$F7h$^$k%"%k%4%j%:%`$rMQ$$$F(B
61: $B9bB.$K9T$&(B.
62: @item
63: @code{umul()}, @code{usquare()}, @code{utmul()} $B$O(B
64: $B78?t$r@0?t$H8+$J$7$F(B, $B@0?t78?t$NB?9`<0$H$7$F@Q$r5a$a$k(B.
65: $B78?t$,M-8BBN(B GF(p) $B$N85$N>l9g$K$O(B, $B78?t$O(B 0 $B0J>e(B p $BL$K~$N@0?t$H8+$J$5$l$k(B.
66: @item
67: @code{umul_ff()}, @code{usquare_ff()}, @code{utmul_ff()} $B$O(B,
68: $B78?t$rM-8BBN$N85$H8+$J$7$F(B, $BM-8BBN>e$NB?9`<0$H$7$F(B
1.2 noro 69: $B@Q$r5a$a$k(B. $B$?$@$7(B, $B0z?t$N78?t$,@0?t$N>l9g(B,
1.1 noro 70: $B@0?t78?t$NB?9`<0$rJV$9>l9g$b$"$k$N$G(B, $B$3$l$i$r8F$S=P$7$?7k2L(B
71: $B$,M-8BBN78?t$G$"$k$3$H$rJ]>Z$9$k$?$a$K$O(B
72: $B$"$i$+$8$a(B @code{simp_ff()} $B$G78?t$rM-8BBN$N85$KJQ49$7$F$*$/$H$h$$(B.
73: @item
74: @code{umul_ff()}, @code{usquare_ff()}, @code{utmul_ff()} $B$O(B,
75: GF(2^n) $B78?t$NB?9`<0$r0z?t$K<h$l$J$$(B.
76: @item
77: @code{umul()}, @code{umul_ff()} $B$N7k2L$O(B @var{p1}, @var{p2} $B$N@Q(B,
78: @code{usquare()}, @code{usquare_ff()} $B$N7k2L$O(B @var{p1} $B$N(B 2 $B>h(B,
79: @code{utmul()}, @code{utmul_ff()} $B$N7k2L$O(B @var{p1}, @var{p2} $B$N@Q(B
80: $B$N(B, @var{d} $B<!0J2<$NItJ,$H$J$k(B.
81: @item
82: $B$$$:$l$b(B, @code{set_upkara()} (@code{utmul}, @code{utmul_ff} $B$K$D$$$F$O(B
83: @code{set_uptkara()}) $B$GJV$5$l$kCM0J2<$N<!?t$KBP$7$F$ODL>o$NI.;;(B
1.2 noro 84: $B7A<0$NJ}K!(B, @code{set_upfft()} $B$GJV$5$l$kCM0J2<$N<!?t$KBP$7$F$O(B Karatsuba
1.1 noro 85: $BK!(B, $B$=$l0J>e$G$O(B FFT$B$*$h$SCf9q>jM>DjM}$,MQ$$$i$l$k(B. $B$9$J$o$A(B,
86: $B@0?t$KBP$9$k(B FFT $B$G$O$J$/(B, $B==J,B?$/$N(B 1 $B%o!<%I0JFb$NK!(B @var{mi} $B$rMQ0U$7(B,
87: @var{p1}, @var{p2} $B$N78?t$r(B @var{mi} $B$G3d$C$?M>$j$H$7$?$b$N$N@Q$r(B,
88: FFT $B$G7W;;$7(B, $B:G8e$KCf9q>jM>DjM}$G9g@.$9$k(B. $B$=$N:](B, $BM-8BBNHG$N4X?t$K(B
89: $B$*$$$F$O(B, $B:G8e$K4pACBN$rI=$9K!$G3F78?t$N>jM>$r7W;;$9$k$,(B, $B$3$3$G$O(B
1.2 noro 90: Shoup $B$K$h$k%H%j%C%/(B @code{[Shoup]} $B$rMQ$$$F9bB.2=$7$F$"$k(B.
91: \E
92: \BEG
93: @item
94: These functions compute products of univariate polynomials
95: by selecting an appropriate algorithm depending on the degrees
96: of inputs.
97: @item
98: @code{umul()}, @code{usquare()}, @code{utmul()}
99: compute products over the integers.
100: Coefficients in GF(p) are regarded as non-negative integers
101: less than p.
102: @item
103: @code{umul_ff()}, @code{usquare_ff()}, @code{utmul_ff()}
104: compute products over a finite field. However, if some of
105: the coefficients of the inputs are integral,
106: the result may be an integral polynomial. So if one wants
107: to assure that the result is a polynomial over the finite field,
108: apply @code{simp_ff()} to the inputs.
109: @item
110: @code{umul_ff()}, @code{usquare_ff()}, @code{utmul_ff()}
111: cannot take polynomials over GF(2^n) as their inputs.
112: @item
113: @code{umul()}, @code{umul_ff()} produce @var{p1*p2}.
114: @code{usquare()}, @code{usquare_ff()} produce @var{p1^2}.
1.3 ! noro 115: @code{utmul()}, @code{utmul_ff()} produce @var{p1*p2 mod} @var{v}^(@var{d}+1),
1.2 noro 116: where @var{v} is the variable of @var{p1}, @var{p2}.
117: @item
118: If the degrees of the inputs are less than or equal to the
119: value returned by @code{set_upkara()} (@code{set_uptkara()} for
120: @code{utmul}, @code{utmul_ff}), usual pencil and paper method is
121: used. If the degrees of the inputs are less than or equall to
122: the value returned by @code{set_upfft()}, Karatsuba algorithm
123: is used. If the degrees of the inputs exceed it, a combination
124: of FFT and Chinese remainder theorem is used.
125: First of all sufficiently many primes @var{mi}
126: within 1 machine word are prepared.
127: Then @var{p1*p2 mod mi} is computed by FFT for each @var{mi}.
128: Finally they are combined by Chinese remainder theorem.
129: The functions over finite fields use an improvement by V. Shoup @code{[Shoup]}.
130: \E
1.1 noro 131: @end itemize
132:
133: @example
134: [176] load("fff")$
135: [177] cputime(1)$
136: 0sec(1.407e-05sec)
137: [178] setmod_ff(2^160-47);
138: 1461501637330902918203684832716283019655932542929
139: 0sec(0.00028sec)
140: [179] A=randpoly_ff(100,x)$
141: 0sec(0.001422sec)
142: [180] B=randpoly_ff(100,x)$
143: 0sec(0.00107sec)
144: [181] for(I=0;I<100;I++)A*B;
145: 7.77sec + gc : 8.38sec(16.15sec)
146: [182] for(I=0;I<100;I++)umul(A,B);
147: 2.24sec + gc : 1.52sec(3.767sec)
148: [183] for(I=0;I<100;I++)umul_ff(A,B);
149: 1.42sec + gc : 0.24sec(1.653sec)
150: [184] for(I=0;I<100;I++)usquare_ff(A);
151: 1.08sec + gc : 0.21sec(1.297sec)
152: [185] for(I=0;I<100;I++)utmul_ff(A,B,100);
153: 1.2sec + gc : 0.17sec(1.366sec)
154: [186] deg(utmul_ff(A,B,100),x);
155: 100
156: @end example
157:
158: @table @t
1.2 noro 159: \JP @item $B;2>H(B
160: \EG @item References
1.1 noro 161: @fref{set_upkara set_uptkara set_upfft},
162: @fref{kmul ksquare ktmul}.
163: @end table
164:
1.2 noro 165: \JP @node kmul ksquare ktmul,,, $B0lJQ?tB?9`<0$N1i;;(B
166: \EG @node kmul ksquare ktmul,,, Univariate polynomials
1.1 noro 167: @subsection @code{kmul}, @code{ksquare}, @code{ktmul}
168: @findex kmul
169: @findex ksquare
170: @findex ktmul
171:
172: @table @t
173: @item kmul(@var{p1},@var{p2})
1.2 noro 174: \JP :: $B0lJQ?tB?9`<0$N9bB.>h;;(B
175: \EG :: Fast multiplication of univariate polynomials
1.1 noro 176: @item ksquare(@var{p1})
1.2 noro 177: \JP :: $B0lJQ?tB?9`<0$N9bB.(B 2 $B>h;;(B
178: \EG :: Fast squaring of a univariate polynomial
1.1 noro 179: @item ktmul(@var{p1},@var{p2},@var{d})
1.2 noro 180: \JP :: $B0lJQ?tB?9`<0$N9bB.>h;;(B ($BBG$A@Z$j<!?t;XDj(B)
181: \EG :: Fast multiplication of univariate polynomials with truncation
1.1 noro 182: @end table
183:
184: @table @var
185: @item return
1.2 noro 186: \JP $B0lJQ?tB?9`<0(B
187: \EG univariate polynomial
1.1 noro 188: @item p1 p2
1.2 noro 189: \JP $B0lJQ?tB?9`<0(B
190: \EG univariate polynomial
1.1 noro 191: @item d
1.2 noro 192: \JP $BHsIi@0?t(B
193: \EG non-negative integer
1.1 noro 194: @end table
195:
196: @itemize @bullet
1.2 noro 197: \BJP
1.1 noro 198: @item
199: $B0lJQ?tB?9`<0$N>h;;$r(B Karatsuba $BK!$G9T$&(B.
200: @item
201: $B4pK\E*$K$O(B @code{umul} $B$HF1MM$@$,(B, $B<!?t$,Bg$-$/$J$C$F$b(B
202: FFT $B$rMQ$$$?9bB.2=$O9T$o$J$$(B.
203: @item
204: GF(2^n) $B78?t$NB?9`<0$K$bMQ$$$k$3$H$,$G$-$k(B.
1.2 noro 205: \E
206: \BEG
207: These functions compute products of univariate polynomials by Karatsuba
208: algorithm.
209: @item
210: These functions do not apply FFT for large degree inputs.
211: @item
212: These functions can compute products over GF(2^n).
213: \E
1.1 noro 214: @end itemize
215:
216: @example
217: [0] load("code/fff");
218: 1
219: [34] setmod_ff(defpoly_mod2(160));
220: x^160+x^5+x^3+x^2+1
221: [35] A=randpoly_ff(100,x)$
222: [36] B=randpoly_ff(100,x)$
223: [37] umul(A,B)$
224: umul : invalid argument
225: return to toplevel
226: [37] kmul(A,B)$
227: @end example
228:
1.2 noro 229: \JP @node set_upkara set_uptkara set_upfft,,, $B0lJQ?tB?9`<0$N1i;;(B
230: \EG @node set_upkara set_uptkara set_upfft,,, Univariate polynomials
1.1 noro 231: @subsection @code{set_upkara}, @code{set_uptkara}, @code{set_upfft}
232: @findex set_upkara
233: @findex set_uptkara
234: @findex set_upfft
235:
236: @table @t
237: @item set_upkara([@var{threshold}])
238: @itemx set_uptkara([@var{threshold}])
239: @itemx set_upfft([@var{threshold}])
1.2 noro 240: \JP :: 1 $BJQ?tB?9`<0$N@Q1i;;$K$*$1$k(B N^2 , Karatsuba, FFT $B%"%k%4%j%:%`$N@ZBX$($NogCM(B
241: \BEG
242: :: Set thresholds in the selection of an algorithm from N^2, Karatsuba,
243: FFT algorithms for univariate polynomial multiplication.
244: \E
1.1 noro 245: @end table
246:
247: @table @var
248: @item return
1.2 noro 249: \JP $B@_Dj$5$l$F$$$kCM(B
250: \EG value currently set
1.1 noro 251: @item threshold
1.2 noro 252: \JP $BHsIi@0?t(B
253: \EG non-negative integer
1.1 noro 254: @end table
255:
256: @itemize @bullet
1.2 noro 257: \BJP
1.1 noro 258: @item
259: $B$$$:$l$b(B, $B0lJQ?tB?9`<0$N@Q$N7W;;$K$*$1$k(B, $B%"%k%4%j%:%`@ZBX$($NogCM$r(B
260: $B@_Dj$9$k(B.
261: @item
262: $B0lJQ?tB?9`<0$N@Q$O(B, $B<!?t(B N $B$,>.$5$$HO0O$G$ODL>o$N(B N^2 $B%"%k%4%j%:%`(B, $BCfDxEY(B
263: $B$N>l9g(B Karatsuba $B%"%k%4%j%:%`(B, $BBg$-$$>l9g$K$O(B FFT $B%"%k%4%j%:%`$G7W;;(B
264: $B$5$l$k(B. $B$3$N@ZBX$($N<!?t$r@_Dj$9$k(B.
265: @item
266: $B>\:Y$O(B, $B$=$l$>$l$N@Q4X?t$N9`$r;2>H$N$3$H(B.
1.2 noro 267: \E
268: \BEG
269: @item
270: These functions set thresholds in the selection of an algorithm from N^2,
271: Karatsuba, FFT algorithms for univariate polynomial multiplication.
272: @item
273: Products of univariate polynomials are computed by N^2, Karatsuba,
274: FFT algorithms. The algorithm selection is done according to the degrees of
275: input polynomials and the thresholds.
276: @item
277: See the description of each function for details.
278: \E
1.1 noro 279: @end itemize
280:
281: @table @t
1.2 noro 282: \JP @item $B;2>H(B
283: \EG @item References
1.1 noro 284: @fref{kmul ksquare ktmul},
285: @fref{umul umul_ff usquare usquare_ff utmul utmul_ff}.
286: @end table
287:
1.2 noro 288: \JP @node utrunc udecomp ureverse,,, $B0lJQ?tB?9`<0$N1i;;(B
289: \EG @node utrunc udecomp ureverse,,, Univariate polynomials
1.1 noro 290: @subsection @code{utrunc}, @code{udecomp}, @code{ureverse}
291: @findex utrunc
292: @findex udecomp
293: @findex ureverse
294:
295: @table @t
296: @item utrunc(@var{p},@var{d})
297: @itemx udecomp(@var{p},@var{d})
298: @itemx ureverse(@var{p})
1.2 noro 299: \JP :: $BB?9`<0$KBP$9$kA`:n(B
300: \EG :: Operations on polynomials
1.1 noro 301: @end table
302:
303: @table @var
304: @item return
1.2 noro 305: \JP $B0lJQ?tB?9`<0$"$k$$$O0lJQ?tB?9`<0$N%j%9%H(B
306: \EG univariate polynomial or list of univariate polynomials
1.1 noro 307: @item p
1.2 noro 308: \JP $B0lJQ?tB?9`<0(B
309: \EG univariate polynomial
1.1 noro 310: @item d
1.2 noro 311: \JP $BHsIi@0?t(B
312: \EG non-negative integer
1.1 noro 313: @end table
314:
315: @itemize @bullet
1.2 noro 316: \BJP
1.1 noro 317: @item
1.3 ! noro 318: @var{p} $B$NJQ?t$r(B x $B$H$9$k(B. $B$3$N$H$-(B @var{p} = @var{p1}+x^(@var{d}+1)@var{p2}
1.1 noro 319: (@var{p1} $B$N<!?t$O(B @var{d} $B0J2<(B) $B$HJ,2r$G$-$k(B. @code{utrunc()} $B$O(B
320: @var{p1} $B$rJV$7(B, @code{udecomp()} $B$O(B [@var{p1},@var{p2}] $B$rJV$9(B.
321: @item
1.3 ! noro 322: @var{p} $B$N<!?t$r(B @var{e} $B$H$7(B, @var{i} $B<!$N78?t$r(B @var{p}[@var{i}] $B$H$9$l$P(B,
! 323: @code{ureverse()} $B$O(B @var{p}[@var{e}]+@var{p}[@var{e}-1]x+... $B$rJV$9(B.
1.2 noro 324: \E
325: \BEG
326: @item
327: Let @var{x} be the variable of @var{p}. Then @var{p} can be decomposed
1.3 ! noro 328: as @var{p} = @var{p1}+x^(@var{d}+1)@var{p2}, where the degree of @var{p1}
1.2 noro 329: is less than or equal to @var{d}.
330: Under the decomposition, @code{utrunc()} returns
331: @var{p1} and @code{udecomp()} returns [@var{p1},@var{p2}].
332: @item
1.3 ! noro 333: Let @var{e} be the degree of @var{p} and @var{p}[@var{i}] the coefficient
1.2 noro 334: of @var{p} at degree @var{i}. Then
1.3 ! noro 335: @code{ureverse()} returns @var{p}[@var{e}]+@var{p}[@var{e}-1]x+....
1.2 noro 336: \E
1.1 noro 337: @end itemize
338:
339: @example
340: [132] utrunc((x+1)^10,5);
341: 252*x^5+210*x^4+120*x^3+45*x^2+10*x+1
342: [133] udecomp((x+1)^10,5);
343: [252*x^5+210*x^4+120*x^3+45*x^2+10*x+1,x^4+10*x^3+45*x^2+120*x+210]
344: [134] ureverse(3*x^3+x^2+2*x);
345: 2*x^2+x+3
346: @end example
347:
348: @table @t
1.2 noro 349: \JP @item $B;2>H(B
350: \EG @item References
1.1 noro 351: @fref{udiv urem urembymul urembymul_precomp ugcd}.
352: @end table
353:
1.2 noro 354: \JP @node uinv_as_power_series ureverse_inv_as_power_series,,, $B0lJQ?tB?9`<0$N1i;;(B
355: \EG @node uinv_as_power_series ureverse_inv_as_power_series,,, Univariate polynomials
1.1 noro 356: @subsection @code{uinv_as_power_series}, @code{ureverse_inv_as_power_series}
357: @findex uinv_as_power_series
358: @findex ureverse_inv_as_power_series
359:
360: @table @t
361: @item uinv_as_power_series(@var{p},@var{d})
362: @itemx ureverse_inv_as_power_series(@var{p},@var{d})
1.2 noro 363: \JP :: $BB?9`<0$rQQ5i?t$H$_$F(B, $B5U857W;;(B
364: \EG :: Computes the truncated inverse as a power series.
1.1 noro 365: @end table
366:
367: @table @var
368: @item return
1.2 noro 369: \JP $B0lJQ?tB?9`<0(B
370: \EG univariate polynomial
1.1 noro 371: @item p
1.2 noro 372: \JP $B0lJQ?tB?9`<0(B
373: \EG univariate polynomial
1.1 noro 374: @item d
1.2 noro 375: \JP $BHsIi@0?t(B
376: \EG non-negative integer
1.1 noro 377: @end table
378:
379: @itemize @bullet
1.2 noro 380: \BJP
1.1 noro 381: @item
382: @code{uinv_as_power_series(@var{p},@var{d})} $B$O(B, $BDj?t9`$,(B 0 $B$G$J$$(B
383: $BB?9`<0(B @var{p} $B$KBP$7(B, @var{p}@var{r}-1 $B$N:GDc<!?t$,(B @var{d}+1
384: $B0J>e$K$J$k$h$&$J(B $B9b!9(B @var{d} $B<!$NB?9`<0(B @var{r} $B$r5a$a$k(B.
385: @item
386: @code{ureverse_inv_as_power_series(@var{p},@var{d})} $B$O(B
387: @var{p} $B$N<!?t$r(B @var{e} $B$H$9$k$H$-(B, @var{p1}=@code{ureverse(@var{p},@var{e})}
388: $B$KBP$7$F(B @code{uinv_as_power_series(@var{p1},@var{d})} $B$r7W;;$9$k(B.
389: @item
390: @code{rembymul_precomp()} $B$N0z?t$H$7$FMQ$$$k>l9g(B, @code{ureverse_inv_as_power_series()} $B$N7k2L$r$=$N$^$^MQ$$$k$3$H$,$G$-$k(B.
1.2 noro 391: \E
392: \BEG
393: @item
394: For a polynomial @var{p} with a non zero constant term,
395: @code{uinv_as_power_series(@var{p},@var{d})} computes
396: a polynomial @var{r} whose degree is at most @var{d}
1.3 ! noro 397: such that @var{p*r = 1 mod} x^(@var{d}+1), where @var{x} is the variable
1.2 noro 398: of @var{p}.
399: @item
400: Let @var{e} be the degree of @var{p}.
401: @code{ureverse_inv_as_power_series(@var{p},@var{d})} computes
402: @code{uinv_as_power_series(@var{p1},@var{d})} for
403: @var{p1}=@code{ureverse(@var{p},@var{e})}.
404: @item
405: The output of @code{ureverse_inv_as_power_series()} can be used
406: as the input of @code{rembymul_precomp()}.
407: \E
1.1 noro 408: @end itemize
409:
410: @example
411: [123] A=(x+1)^5;
412: x^5+5*x^4+10*x^3+10*x^2+5*x+1
413: [124] uinv_as_power_series(A,5);
414: -126*x^5+70*x^4-35*x^3+15*x^2-5*x+1
415: [126] A*R;
416: -126*x^10-560*x^9-945*x^8-720*x^7-210*x^6+1
417: [127] A=x^10+x^9;
418: x^10+x^9
419: [128] R=ureverse_inv_as_power_series(A,5);
420: -x^5+x^4-x^3+x^2-x+1
421: [129] ureverse(A)*R;
422: -x^6+1
423: @end example
424:
425: @table @t
1.2 noro 426: \JP @item $B;2>H(B
427: \EG @item References
1.1 noro 428: @fref{utrunc udecomp ureverse},
429: @fref{udiv urem urembymul urembymul_precomp ugcd}.
430: @end table
431:
1.2 noro 432: \JP @node udiv urem urembymul urembymul_precomp ugcd,,, $B0lJQ?tB?9`<0$N1i;;(B
433: \EG @node udiv urem urembymul urembymul_precomp ugcd,,, Univariate polynomials
1.1 noro 434: @subsection @code{udiv}, @code{urem}, @code{urembymul}, @code{urembymul_precomp}, @code{ugcd}
435: @findex udiv
436: @findex urem
437: @findex urembymul
438: @findex urembymul_precomp
439: @findex ugcd
440:
441: @table @t
442: @item udiv(@var{p1},@var{p2})
443: @item urem(@var{p1},@var{p2})
444: @item urembymul(@var{p1},@var{p2})
445: @item urembymul_precomp(@var{p1},@var{p2},@var{inv})
446: @item ugcd(@var{p1},@var{p2})
1.2 noro 447: \JP :: $B0lJQ?tB?9`<0$N=|;;(B, GCD
448: \EG :: Division and GCD for univariate polynomials.
1.1 noro 449: @end table
450:
451: @table @var
452: @item return
1.2 noro 453: \JP $B0lJQ?tB?9`<0(B
454: \EG univariate polynomial
1.3 ! noro 455: @item p1 p2 inv
1.2 noro 456: \JP $B0lJQ?tB?9`<0(B
457: \EG univariate polynomial
1.1 noro 458: @end table
459:
460: @itemize @bullet
1.2 noro 461: \BJP
1.1 noro 462: @item
463: $B0lJQ?tB?9`<0(B @var{p1}, @var{p2} $B$KBP$7(B,
464: @code{udiv} $B$O>&(B, @code{urem}, @code{urembymul} $B$O>jM>(B,
465: @code{ugcd} $B$O(B GCD $B$rJV$9(B.
466: $B$3$l$i$O(B, $BL)$J0lJQ?tB?9`<0$KBP$9$k9bB.2=$r?^$C$?$b$N$G$"$k(B.
467: @code{urembymul} $B$O(B, @var{p2} $B$K$h$k>jM>7W;;$r(B, @var{p2} $B$N(B
468: $BQQ5i?t$H$7$F$N5U857W;;$*$h$S(B, $B>h;;(B 2 $B2s$KCV$-49$($?$b$N$G(B,
469: $B<!?t$,Bg$-$$>l9g$KM-8z$G$"$k(B.
1.2 noro 470: @item
471: @code{urembymul_precomp} $B$O(B, $B8GDj$5$l$?B?9`<0$K$h$k>jM>(B
1.1 noro 472: $B7W;;$rB??t9T$&>l9g$J$I$K8z2L$rH/4x$9$k(B.
1.2 noro 473: $BBh(B 3 $B0z?t$O(B, $B$"$i$+$8$a(B @code{ureverse_inv_as_power_series()} $B$K(B
474: $B$h$j7W;;$7$F$*$/(B.
475: \E
476: \BEG
477: @item
478: For univariate polynomials @var{p1} and @var{p2},
479: there exist polynomials @var{q} and @var{r} such that
480: @var{p1=q*p2+r} and the degree of @var{r} is less than that of @var{p2}.
481: Then @code{udiv} returns @var{q}, @code{urem} and @code{urembymul} return
482: @var{r}. @code{ugcd} returns the polynomial GCD of @var{p1} and @var{p2}.
483: These functions are specially tuned up for dense univariate polynomials.
484: In @code{urembymul} the division by @var{p2} is replaced with
485: the inverse computation of @var{p2} as a power series and
486: two polynomial multiplications. It speeds up the computation
487: when the degrees of inputs are large.
488: @item
489: @code{urembymul_precomp} is efficient when one repeats divisions
490: by a fixed polynomial.
491: One has to compute the third argument by @code{ureverse_inv_as_power_series()}.
492: \E
1.1 noro 493: @end itemize
494:
495: @example
496: [177] setmod_ff(2^160-47);
497: 1461501637330902918203684832716283019655932542929
498: [178] A=randpoly_ff(200,x)$
499: [179] B=randpoly_ff(101,x)$
500: [180] cputime(1)$
501: 0sec(1.597e-05sec)
502: [181] srem(A,B)$
503: 0.15sec + gc : 0.15sec(0.3035sec)
504: [182] urem(A,B)$
505: 0.11sec + gc : 0.12sec(0.2347sec)
506: [183] urembymul(A,B)$
507: 0.08sec + gc : 0.09sec(0.1651sec)
508: [184] R=ureverse_inv_as_power_series(B,101)$
509: 0.04sec + gc : 0.03sec(0.063sec)
510: [185] urembymul_precomp(A,B,R)$
511: 0.03sec(0.02501sec)
512: @end example
513:
514: @table @t
1.2 noro 515: \JP @item $B;2>H(B
516: \EG @item References
1.1 noro 517: @fref{uinv_as_power_series ureverse_inv_as_power_series}.
518: @end table
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to upoly.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