Annotation of OpenXM/src/asir-doc/parts/builtin/upoly.texi, Revision 1.1
1.1 ! noro 1: @node $B0lJQ?tB?9`<0$N1i;;(B,,, $BAH$_9~$_H!?t(B
! 2: @section $B0lJQ?tB?9`<0$N1i;;(B
! 3:
! 4: @menu
! 5: * umul umul_ff usquare usquare_ff utmul utmul_ff::
! 6: * kmul ksquare ktmul::
! 7: * utrunc udecomp ureverse::
! 8: * set_upkara set_uptkara set_upfft::
! 9: * uinv_as_power_series ureverse_inv_as_power_series::
! 10: * udiv urem urembymul urembymul_precomp ugcd::
! 11: @end menu
! 12:
! 13: @node umul umul_ff usquare usquare_ff utmul utmul_ff,,, $B0lJQ?tB?9`<0$N1i;;(B
! 14: @subsection @code{umul}, @code{umul_ff}, @code{usquare}, @code{usquare_ff}, @code{utmul}, @code{utmul_ff}
! 15: @findex umul
! 16: @findex umul_ff
! 17: @findex usquare
! 18: @findex usquare_ff
! 19: @findex utmul
! 20: @findex utmul_ff
! 21:
! 22: @table @t
! 23: @item umul(@var{p1},@var{p2})
! 24: @itemx umul_ff(@var{p1},@var{p2})
! 25: :: $B0lJQ?tB?9`<0$N9bB.>h;;(B
! 26: @item usquare(@var{p1})
! 27: @itemx usquare_ff(@var{p1})
! 28: :: $B0lJQ?tB?9`<0$N9bB.(B 2 $B>h;;(B
! 29: @item utmul(@var{p1},@var{p2},@var{d})
! 30: @itemx utmul_ff(@var{p1},@var{p2},@var{d})
! 31: :: $B0lJQ?tB?9`<0$N9bB.>h;;(B ($BBG$A@Z$j<!?t;XDj(B)
! 32: @end table
! 33:
! 34: @table @var
! 35: @item return
! 36: $B0lJQ?tB?9`<0(B
! 37: @item p1 p2
! 38: $B0lJQ?tB?9`<0(B
! 39: @item d
! 40: $BHsIi@0?t(B
! 41: @end table
! 42:
! 43: @itemize @bullet
! 44: @item
! 45: $B0lJQ?tB?9`<0$N>h;;$r(B, $B<!?t$K1~$8$F7h$^$k%"%k%4%j%:%`$rMQ$$$F(B
! 46: $B9bB.$K9T$&(B.
! 47: @item
! 48: @code{umul()}, @code{usquare()}, @code{utmul()} $B$O(B
! 49: $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.
! 50: $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.
! 51: @item
! 52: @code{umul_ff()}, @code{usquare_ff()}, @code{utmul_ff()} $B$O(B,
! 53: $B78?t$rM-8BBN$N85$H8+$J$7$F(B, $BM-8BBN>e$NB?9`<0$H$7$F(B
! 54: $B@Q$r5a$a$k(B. $B$?$@$7(B, $B0z?t$,A4$/M-8BBN$N85$r4^$^$J$$>l9g$K$O(B,
! 55: $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
! 56: $B$,M-8BBN78?t$G$"$k$3$H$rJ]>Z$9$k$?$a$K$O(B
! 57: $B$"$i$+$8$a(B @code{simp_ff()} $B$G78?t$rM-8BBN$N85$KJQ49$7$F$*$/$H$h$$(B.
! 58: @item
! 59: @code{umul_ff()}, @code{usquare_ff()}, @code{utmul_ff()} $B$O(B,
! 60: GF(2^n) $B78?t$NB?9`<0$r0z?t$K<h$l$J$$(B.
! 61: @item
! 62: @code{umul()}, @code{umul_ff()} $B$N7k2L$O(B @var{p1}, @var{p2} $B$N@Q(B,
! 63: @code{usquare()}, @code{usquare_ff()} $B$N7k2L$O(B @var{p1} $B$N(B 2 $B>h(B,
! 64: @code{utmul()}, @code{utmul_ff()} $B$N7k2L$O(B @var{p1}, @var{p2} $B$N@Q(B
! 65: $B$N(B, @var{d} $B<!0J2<$NItJ,$H$J$k(B.
! 66: @item
! 67: $B$$$:$l$b(B, @code{set_upkara()} (@code{utmul}, @code{utmul_ff} $B$K$D$$$F$O(B
! 68: @code{set_uptkara()}) $B$GJV$5$l$kCM0J2<$N<!?t$KBP$7$F$ODL>o$NI.;;(B
! 69: $B7A<0$NJ}K!(B, @code{set_uufft()} $B$GJV$5$l$kCM0J2<$N<!?t$KBP$7$F$O(B Karatsuba
! 70: $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,
! 71: $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,
! 72: @var{p1}, @var{p2} $B$N78?t$r(B @var{mi} $B$G3d$C$?M>$j$H$7$?$b$N$N@Q$r(B,
! 73: FFT $B$G7W;;$7(B, $B:G8e$KCf9q>jM>DjM}$G9g@.$9$k(B. $B$=$N:](B, $BM-8BBNHG$N4X?t$K(B
! 74: $B$*$$$F$O(B, $B:G8e$K4pACBN$rI=$9K!$G3F78?t$N>jM>$r7W;;$9$k$,(B, $B$3$3$G$O(B
! 75: Shoup $B$K$h$k%H%j%C%/$rMQ$$$F9bB.2=$7$F$"$k(B.
! 76: @end itemize
! 77:
! 78: @example
! 79: [176] load("fff")$
! 80: [177] cputime(1)$
! 81: 0sec(1.407e-05sec)
! 82: [178] setmod_ff(2^160-47);
! 83: 1461501637330902918203684832716283019655932542929
! 84: 0sec(0.00028sec)
! 85: [179] A=randpoly_ff(100,x)$
! 86: 0sec(0.001422sec)
! 87: [180] B=randpoly_ff(100,x)$
! 88: 0sec(0.00107sec)
! 89: [181] for(I=0;I<100;I++)A*B;
! 90: 7.77sec + gc : 8.38sec(16.15sec)
! 91: [182] for(I=0;I<100;I++)umul(A,B);
! 92: 2.24sec + gc : 1.52sec(3.767sec)
! 93: [183] for(I=0;I<100;I++)umul_ff(A,B);
! 94: 1.42sec + gc : 0.24sec(1.653sec)
! 95: [184] for(I=0;I<100;I++)usquare_ff(A);
! 96: 1.08sec + gc : 0.21sec(1.297sec)
! 97: [185] for(I=0;I<100;I++)utmul_ff(A,B,100);
! 98: 1.2sec + gc : 0.17sec(1.366sec)
! 99: [186] deg(utmul_ff(A,B,100),x);
! 100: 100
! 101: @end example
! 102:
! 103: @table @t
! 104: @item $B;2>H(B
! 105: @fref{set_upkara set_uptkara set_upfft},
! 106: @fref{kmul ksquare ktmul}.
! 107: @end table
! 108:
! 109: @node kmul ksquare ktmul,,, $B0lJQ?tB?9`<0$N1i;;(B
! 110: @subsection @code{kmul}, @code{ksquare}, @code{ktmul}
! 111: @findex kmul
! 112: @findex ksquare
! 113: @findex ktmul
! 114:
! 115: @table @t
! 116: @item kmul(@var{p1},@var{p2})
! 117: :: $B0lJQ?tB?9`<0$N9bB.>h;;(B
! 118: @item ksquare(@var{p1})
! 119: :: $B0lJQ?tB?9`<0$N9bB.(B 2 $B>h;;(B
! 120: @item ktmul(@var{p1},@var{p2},@var{d})
! 121: :: $B0lJQ?tB?9`<0$N9bB.>h;;(B ($BBG$A@Z$j<!?t;XDj(B)
! 122: @end table
! 123:
! 124: @table @var
! 125: @item return
! 126: $B0lJQ?tB?9`<0(B
! 127: @item p1 p2
! 128: $B0lJQ?tB?9`<0(B
! 129: @item d
! 130: $BHsIi@0?t(B
! 131: @end table
! 132:
! 133: @itemize @bullet
! 134: @item
! 135: $B0lJQ?tB?9`<0$N>h;;$r(B Karatsuba $BK!$G9T$&(B.
! 136: @item
! 137: $B4pK\E*$K$O(B @code{umul} $B$HF1MM$@$,(B, $B<!?t$,Bg$-$/$J$C$F$b(B
! 138: FFT $B$rMQ$$$?9bB.2=$O9T$o$J$$(B.
! 139: @item
! 140: GF(2^n) $B78?t$NB?9`<0$K$bMQ$$$k$3$H$,$G$-$k(B.
! 141: @end itemize
! 142:
! 143: @example
! 144: [0] load("code/fff");
! 145: 1
! 146: [34] setmod_ff(defpoly_mod2(160));
! 147: x^160+x^5+x^3+x^2+1
! 148: [35] A=randpoly_ff(100,x)$
! 149: [36] B=randpoly_ff(100,x)$
! 150: [37] umul(A,B)$
! 151: umul : invalid argument
! 152: return to toplevel
! 153: [37] kmul(A,B)$
! 154: @end example
! 155:
! 156: @node set_upkara set_uptkara set_upfft,,, $B0lJQ?tB?9`<0$N1i;;(B
! 157: @subsection @code{set_upkara}, @code{set_uptkara}, @code{set_upfft}
! 158: @findex set_upkara
! 159: @findex set_uptkara
! 160: @findex set_upfft
! 161:
! 162: @table @t
! 163: @item set_upkara([@var{threshold}])
! 164: @itemx set_uptkara([@var{threshold}])
! 165: @itemx set_upfft([@var{threshold}])
! 166: :: 1 $BJQ?tB?9`<0$N@Q1i;;$K$*$1$k(B N^2 , Karatsuba, FFT $B%"%k%4%j%:%`$N@ZBX$($NogCM(B
! 167: @end table
! 168:
! 169: @table @var
! 170: @item return
! 171: $B@_Dj$5$l$F$$$kCM(B
! 172: @item threshold
! 173: $BHsIi@0?t(B
! 174: @end table
! 175:
! 176: @itemize @bullet
! 177: @item
! 178: $B$$$:$l$b(B, $B0lJQ?tB?9`<0$N@Q$N7W;;$K$*$1$k(B, $B%"%k%4%j%:%`@ZBX$($NogCM$r(B
! 179: $B@_Dj$9$k(B.
! 180: @item
! 181: $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
! 182: $B$N>l9g(B Karatsuba $B%"%k%4%j%:%`(B, $BBg$-$$>l9g$K$O(B FFT $B%"%k%4%j%:%`$G7W;;(B
! 183: $B$5$l$k(B. $B$3$N@ZBX$($N<!?t$r@_Dj$9$k(B.
! 184: @item
! 185: $B>\:Y$O(B, $B$=$l$>$l$N@Q4X?t$N9`$r;2>H$N$3$H(B.
! 186: @end itemize
! 187:
! 188: @table @t
! 189: @item $B;2>H(B
! 190: @fref{kmul ksquare ktmul},
! 191: @fref{umul umul_ff usquare usquare_ff utmul utmul_ff}.
! 192: @end table
! 193:
! 194: @node utrunc udecomp ureverse,,, $B0lJQ?tB?9`<0$N1i;;(B
! 195: @subsection @code{utrunc}, @code{udecomp}, @code{ureverse}
! 196: @findex utrunc
! 197: @findex udecomp
! 198: @findex ureverse
! 199:
! 200: @table @t
! 201: @item utrunc(@var{p},@var{d})
! 202: @itemx udecomp(@var{p},@var{d})
! 203: @itemx ureverse(@var{p})
! 204: :: $BB?9`<0$KBP$9$kA`:n(B
! 205: @end table
! 206:
! 207: @table @var
! 208: @item return
! 209: $B0lJQ?tB?9`<0$"$k$$$O0lJQ?tB?9`<0$N%j%9%H(B
! 210: @item p
! 211: $B0lJQ?tB?9`<0(B
! 212: @item d
! 213: $BHsIi@0?t(B
! 214: @end table
! 215:
! 216: @itemize @bullet
! 217: @item
! 218: @var{p} $B$NJQ?t$r(B x $B$H$9$k(B. $B$3$N$H$-(B @var{p} = @var{p1}+x^(d+1)@var{p2}
! 219: (@var{p1} $B$N<!?t$O(B @var{d} $B0J2<(B) $B$HJ,2r$G$-$k(B. @code{utrunc()} $B$O(B
! 220: @var{p1} $B$rJV$7(B, @code{udecomp()} $B$O(B [@var{p1},@var{p2}] $B$rJV$9(B.
! 221: @item
! 222: @var{p} $B$N<!?t$r(B @var{e} $B$H$7(B, @var{i} $B<!$N78?t$r(B @var{p[i]} $B$H$9$l$P(B,
! 223: @code{ureverse()} $B$O(B @var{p[e]}+@var{p[e-1]}x+... $B$rJV$9(B.
! 224: @end itemize
! 225:
! 226: @example
! 227: [132] utrunc((x+1)^10,5);
! 228: 252*x^5+210*x^4+120*x^3+45*x^2+10*x+1
! 229: [133] udecomp((x+1)^10,5);
! 230: [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]
! 231: [134] ureverse(3*x^3+x^2+2*x);
! 232: 2*x^2+x+3
! 233: @end example
! 234:
! 235: @table @t
! 236: @item $B;2>H(B
! 237: @fref{udiv urem urembymul urembymul_precomp ugcd}.
! 238: @end table
! 239:
! 240: @node uinv_as_power_series ureverse_inv_as_power_series,,, $B0lJQ?tB?9`<0$N1i;;(B
! 241: @subsection @code{uinv_as_power_series}, @code{ureverse_inv_as_power_series}
! 242: @findex uinv_as_power_series
! 243: @findex ureverse_inv_as_power_series
! 244:
! 245: @table @t
! 246: @item uinv_as_power_series(@var{p},@var{d})
! 247: @itemx ureverse_inv_as_power_series(@var{p},@var{d})
! 248: :: $BB?9`<0$rQQ5i?t$H$_$F(B, $B5U857W;;(B
! 249: @end table
! 250:
! 251: @table @var
! 252: @item return
! 253: $B0lJQ?tB?9`<0(B
! 254: @item p
! 255: $B0lJQ?tB?9`<0(B
! 256: @item d
! 257: $BHsIi@0?t(B
! 258: @end table
! 259:
! 260: @itemize @bullet
! 261: @item
! 262: @code{uinv_as_power_series(@var{p},@var{d})} $B$O(B, $BDj?t9`$,(B 0 $B$G$J$$(B
! 263: $BB?9`<0(B @var{p} $B$KBP$7(B, @var{p}@var{r}-1 $B$N:GDc<!?t$,(B @var{d}+1
! 264: $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.
! 265: @item
! 266: @code{ureverse_inv_as_power_series(@var{p},@var{d})} $B$O(B
! 267: @var{p} $B$N<!?t$r(B @var{e} $B$H$9$k$H$-(B, @var{p1}=@code{ureverse(@var{p},@var{e})}
! 268: $B$KBP$7$F(B @code{uinv_as_power_series(@var{p1},@var{d})} $B$r7W;;$9$k(B.
! 269: @item
! 270: @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.
! 271: @end itemize
! 272:
! 273: @example
! 274: [123] A=(x+1)^5;
! 275: x^5+5*x^4+10*x^3+10*x^2+5*x+1
! 276: [124] uinv_as_power_series(A,5);
! 277: -126*x^5+70*x^4-35*x^3+15*x^2-5*x+1
! 278: [126] A*R;
! 279: -126*x^10-560*x^9-945*x^8-720*x^7-210*x^6+1
! 280: [127] A=x^10+x^9;
! 281: x^10+x^9
! 282: [128] R=ureverse_inv_as_power_series(A,5);
! 283: -x^5+x^4-x^3+x^2-x+1
! 284: [129] ureverse(A)*R;
! 285: -x^6+1
! 286: @end example
! 287:
! 288: @table @t
! 289: @item $B;2>H(B
! 290: @fref{utrunc udecomp ureverse},
! 291: @fref{udiv urem urembymul urembymul_precomp ugcd}.
! 292: @end table
! 293:
! 294: @node udiv urem urembymul urembymul_precomp ugcd,,, $B0lJQ?tB?9`<0$N1i;;(B
! 295: @subsection @code{udiv}, @code{urem}, @code{urembymul}, @code{urembymul_precomp}, @code{ugcd}
! 296: @findex udiv
! 297: @findex urem
! 298: @findex urembymul
! 299: @findex urembymul_precomp
! 300: @findex ugcd
! 301:
! 302: @table @t
! 303: @item udiv(@var{p1},@var{p2})
! 304: @item urem(@var{p1},@var{p2})
! 305: @item urembymul(@var{p1},@var{p2})
! 306: @item urembymul_precomp(@var{p1},@var{p2},@var{inv})
! 307: @item ugcd(@var{p1},@var{p2})
! 308: :: $BB?9`<0$KBP$9$kA`:n(B
! 309: @end table
! 310:
! 311: @table @var
! 312: @item return
! 313: $B0lJQ?tB?9`<0(B
! 314: @item p1,p2,inv
! 315: $B0lJQ?tB?9`<0(B
! 316: @end table
! 317:
! 318: @itemize @bullet
! 319: @item
! 320: $B0lJQ?tB?9`<0(B @var{p1}, @var{p2} $B$KBP$7(B,
! 321: @code{udiv} $B$O>&(B, @code{urem}, @code{urembymul} $B$O>jM>(B,
! 322: @code{ugcd} $B$O(B GCD $B$rJV$9(B.
! 323: $B$3$l$i$O(B, $BL)$J0lJQ?tB?9`<0$KBP$9$k9bB.2=$r?^$C$?$b$N$G$"$k(B.
! 324: @code{urembymul} $B$O(B, @var{p2} $B$K$h$k>jM>7W;;$r(B, @var{p2} $B$N(B
! 325: $BQQ5i?t$H$7$F$N5U857W;;$*$h$S(B, $B>h;;(B 2 $B2s$KCV$-49$($?$b$N$G(B,
! 326: $B<!?t$,Bg$-$$>l9g$KM-8z$G$"$k(B.
! 327: @item @code{urembymul_precomp} $B$O(B, $B8GDj$5$l$?B?9`<0$K$h$k>jM>(B
! 328: $B7W;;$rB??t9T$&>l9g$J$I$K8z2L$rH/4x$9$k(B.
! 329: @end itemize
! 330:
! 331: @example
! 332: [177] setmod_ff(2^160-47);
! 333: 1461501637330902918203684832716283019655932542929
! 334: [178] A=randpoly_ff(200,x)$
! 335: [179] B=randpoly_ff(101,x)$
! 336: [180] cputime(1)$
! 337: 0sec(1.597e-05sec)
! 338: [181] srem(A,B)$
! 339: 0.15sec + gc : 0.15sec(0.3035sec)
! 340: [182] urem(A,B)$
! 341: 0.11sec + gc : 0.12sec(0.2347sec)
! 342: [183] urembymul(A,B)$
! 343: 0.08sec + gc : 0.09sec(0.1651sec)
! 344: [184] R=ureverse_inv_as_power_series(B,101)$
! 345: 0.04sec + gc : 0.03sec(0.063sec)
! 346: [185] urembymul_precomp(A,B,R)$
! 347: 0.03sec(0.02501sec)
! 348: @end example
! 349:
! 350: @table @t
! 351: @item $B;2>H(B
! 352: @fref{uinv_as_power_series ureverse_inv_as_power_series}.
! 353: @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