Return to num.tex CVS log

Up to [local] / OpenXM / doc / compalg

Annotation of OpenXM/doc/compalg/num.tex, Revision 1.2

1.2     ! noro        1: %$OpenXM$
1.1       noro        2: \chapter{$B@0?t(B}
                      3:
                      4: \section{$B@0?t$NI=8=(B}
                      5: $B7W;;5!$K$*$$$F$O9b!9%l%8%9%?$N%S%C%HD9(B ($B%o!<%ID9(B)$B$N?t$KBP$9$k1i;;(B
                      6: $B$7$+Ds6!$5$l$:(B, $B$=$l0J>e$NBg$-$5$N@0?t(B ({\bf $BB?G\D9@0?t(B} $B$"$k$$$O(B {\bf
                      7: bignum}) $B$KBP$9$k1i;;$O(B
                      8:
                      9: \begin{enumerate}
                     10: \item $B@0?t$r(B, $B$"$k@0?t(B $B$ $B$K$h$j(B $B$ $B?JI=<($9$k(B.
                     11: \item $B3F7e$I$&$7$N1i;;$r(B CPU $B$N@0?t1i;;5!G=$K$h$j9T$J$&(B.
                     12: \item $B$3$l$i$NAH9g$;$K$h$j85$N@0?t$I$&$7$N1i;;7k2L$rF@$k(B.
                     13: \end{enumerate}
                     14: $B$H$$$&7A$G9T$o$l$k(B. $B$ $B$NCM$O(B, $B%o!<%ID9$K6a$$Bg$-$5$N(B 2 $B%Y%-$H$9$k>l(B
                     15: $B9g$,B?$$(B. $B$3$l$O(B,
                     16:
                     17: \begin{itemize}
                     18: \item $B$ $B$rBg$-$/$9$k$H(B $B$ $B?JI=8=$N7e?t$,>/$J$/$G:Q$`(B
                     19: \item $B$ $B0J>e$N@0?t$N>e0L(B, $B2<0L$N7e$X$NJ,2r$,(B, $B%S%C%H%7%U%H1i;;$G:Q$`(B
                     20: \end{itemize}
                     21: $B$H$$$&M}M3$K$h$k(B. $B$7$+$7(B, $B$ $B$r(B, $BH>%o!<%ID9$h$jBg(B
                     22: $B$-$/$H$k>l9g(B, $B>h=|;;$K$*$$$F(B,
                     23:
                     24: \begin{enumerate}
                     25: \item
                     26: $BC1@:EY@0?t(B $\times$ $BC1@:EY@0?t(B $\rightarrow$ $BG\@:EY@0?t(B
                     27: \item
                     28: $BG\@:EY@0?t(B $\rightarrow$ $BC1@:EY@0?t(B $\times$ $BC1@:EY@0?t(B + $BC1@:EY@0?t(B
                     29: \end{enumerate}
                     30: $B$H$$$&Fs$D$N1i;;$,I,MW$K$J$k(B.
                     31:
                     32: $BI8=`E*$J(B C $B8@8l$K$*$$$F$O>e5-$N1i;;$ODL>oDs6!$5$l$F$*$i$:(B, $B%"%;%s%V%j(B
                     33: $B8@8l$K$h$j$3$l$i$r5-=R$9$kI,MW$b@8$:$k(B. $B$?$@$7(B, $B:G6a9-$/;HMQ$5$l$F$$$k(B
                     34: {\tt gcc} $B$G$O(B{\tt long long} $B$"$k$$$O(B {\tt unsigned long long} $B@k8@$K(B
                     35: $B$h$j(B64 bit $B@0?t1i;;$rMQ$$$k$3$H$,$G$-(B, $B$=$l$K$h$j(B C $B8@8l$N$_$G$3$l$i$N1i;;(B
                     36: $B$,2DG=$H$J$k(B. $BNc$($P(B 1. $B$N1i;;$O(B
                     37:
                     38: \begin{verbatim}
                     39: typedef unsigned int UL;
                     40: typedef unsigned long long ULL;
                     41: UL a,b,ch,cl;
                     42: ULL c;
                     43: ...
                     44: c = (ULL)a*(ULL)b;
                     45: ch = (UL)(c>>32);
                     46: cl = (UL)(c&(((ULL)1)<<32));
                     47: \end{verbatim}
                     48: $B$K$h$j(B, {\tt ch}, {\tt cl} $B$K3F!9(B 64bit $B$N>h;;7k2L$N>e0L(B, $B2<0L(B 32bit
                     49: $B$,3JG<$5$l$k(B. $B$7$+$7(B, {\tt gcc} $B$N(B CPU $BKh$N<BAu$N;EJ}$K$h$C$F$O(B, 32
                     50: bit $B>h=|;;$,>o$K4X?t8F$S=P$7$K$J$C$?$j$9$k>l9g$b$"$k$N$G(B, $B3N<B$J9bB.2=(B
                     51: $B$N$?$a$K$O$d$O$j%"%;%s%V%i$"$k$$$O%$%s%i%$%s%"%;%s%V%i$r;H$&$N$b;_$`$r(B
                     52: $BF@$J$$(B.
                     53:
                     54: $B0J2<(B, $B$ $B?JI=8=$5$l$?Fs$D$N<+A3?t(B
                     55: $$u=u_nB^n+u_{n-1}B^{n-1}+\cdots+u_0$$
                     56: $$v=v_mB^m+v_{m-1}B^{m-1}+\cdots+v_0$$
                     57: ($0\le u_i, v_j \le B-1$) $B$KBP$7(B, $B2C8:>h=|1i;;$r9T$&$3$H$r9M$($k(B.
                     58:
                     59: \section{$B2C;;(B}
                     60: $B2C;;$O(B, $BI.;;$r9T$&$h$&$K2<0L$N7e$+$i7+$j>e$,$j$H$H$b$KB-$7$F$$$1$P$h$$(B.
                     61: $B$7$+$7(B, $B<B:]$N7W;;5!>e$G$N<B8=$O$=$l$[$I<+L@$G$O$J$$(B. $B$ $B$H$7$F7W;;5!(B
                     62: $B$N%o!<%ID90lGU(B (32bit CPU $B$J$i(B $B=2^{32}$) $B$rA*$s$@>l9g(B, $B<!$N$h$&$J%"(B
                     63: $B%k%4%j%:%`$H$J$k(B.
                     64:
                     65: \begin{al}
                     66: \begin{tabbing}
                     67: \\
                     68: Input : $u=\sum_{i=0}^{n-1} u_iB^i$, $v=\sum_{i=0}^{n-1}v_iB^i$\\
                     69: Output : $w = u+v$\\
                     70: $c \leftarrow 0$\\
                     71: for \= $i=0$ to $n-1$\\
                     72: \> $t \leftarrow u_i+v_i \bmod B$\\
                     73: \> if \= $t < u_i$\\
                     74: \>\> $t \leftarrow t+c \bmod B$\\
                     75: \>\> $c\leftarrow 1$\\
                     76: \> else\\
                     77: \>\> $t \leftarrow t+c \bmod B$\\
                     78: \>\> if $t < c$ then $c \leftarrow 1$ else $c \leftarrow 0$\\
                     79: \> $w_i \leftarrow t$\\
                     80: $w_n \leftarrow c$\\
                     81: return $\sum_{i=0}^n w_iB^i$
                     82: \end{tabbing}
                     83: \end{al}
                     84: $B$3$N%"%k%4%j%:%`$K8=$l$k(B $c \leftarrow a+b \bmod B$ $B$O(B,
                     85: $$a+b \ge B \Rightarrow c \leftarrow a+b-B$$ $B$r0UL#$9$k(B. $B$ $B$,%o!<%ID90lGU(B
                     86: $B$N>l9g(B, Section \ref{cpuint} $B$G=R$Y$?$h$&$K2C;;$O(B $B$ $B$rK!$H$7$F9T$o$l(B
                     87: $B$k(B. $B$3$l$O(B, C $B8@8l$G$O(B,
                     88:
                     89: \begin{verbatim}
                     90: unsigned int a,b,c;
                     91: ...
                     92: c = a+b;
                     93: \end{verbatim}
                     94: $B$K$h$j<B9T$G$-$k(B. $B7+$j>e$,$j$O(B, $a+b \bmod B$ $B$,(B $a$ $B$^$?$O(B $b$ $B$h$j>.(B
                     95: $B$5$/$J$C$F$$$k$+$I$&$+$G8!=P$G$-$k$?$a(B, $B$3$3$G=R$Y$?%"%k%4%j%:%`$K$h$j(B
                     96: $B2C;;$,@5$7$/<B9T$G$-$k$N$G$"$k(B.
                     97:
                     98: \section{$B8:;;(B}
                     99: $B8:;;$b(B, $BI.;;$HF1MM$N;EJ}$G9T$&(B.
                    100:
                    101: \begin{al}
                    102: \begin{tabbing}
                    103: \\
                    104: Input : $u=\sum_{i=0}^{n-1} u_iB^i$, $v=\sum_{i=0}^{n-1}v_iB^i$ ($u\ge v$)\\
                    105: Output : $w = u-v$\\
                    106: $b \leftarrow 0$\\
                    107: for \= $i=0$ to $n-1$\\
                    108: \> $t \leftarrow u_i-v_i \bmod B$\\
                    109: \> if \= $t > u_i$\\
                    110: \>\> $t \leftarrow t-b$\\
                    111: \>\> $b\leftarrow 1$\\
                    112: \> else\\
                    113: \>\> $t \leftarrow t-b \bmod B$\\
                    114: (B)\>\> if $t = B-1$ then $b \leftarrow 1$ else $b \leftarrow 0$\\
                    115: \> $w_i \leftarrow t$\\
                    116: return $\sum_{i=0}^{n-1} w_iB^i$
                    117: \end{tabbing}
                    118: \end{al}
                    119: $B$3$N%"%k%4%j%:%`$K8=$l$k(B $c \leftarrow a-b \bmod B$ $B$O(B,
                    120: $$a-b < 0 \Rightarrow c \leftarrow a-b+B$$ $B$r0UL#$9$k(B. $B$3$NA`:n$b(B,
                    121: C $B8@8l$G$O(B
                    122:
                    123: \begin{verbatim}
                    124: unsigned int a,b,c;
                    125: ...
                    126: c = a-b;
                    127: \end{verbatim}
                    128: $B$K$h$j<B9T$5$l$k(B. $B7+$j2<$,$j$O(B, $a-b \bmod B$ $B$,(B $a$ $B$h$jBg$-$$$+$I$&$+(B
                    129: $B$G8!=P$G$-$k(B. (B) $B$K$*$1$k(B $B-1$ $B$H$NHf3S$O(B, $B$3$3$G$N7+$j2<$,$j$,(B, $t=0$
                    130: $B$+$D(B $b=1$ $B$N>l9g$K$N$_@8$:$k$?$a$G$"$k(B.
                    131:
                    132: \section{$B>h;;(B}
                    133:
                    134: $B>h;;$bI.;;$HF1MM$NJ}K!$G7W;;$G$-$k(B.
                    135:
                    136: \begin{al}
                    137: \begin{tabbing}
                    138: \\
                    139: Input : $u=\sum_{i=0}^{n-1} u_iB^i$, $v=\sum_{i=0}^{m-1}v_iB^i$\\
                    140: Output : $w = uv$\\
                    141: for \= $i=0$ to $n-1$\\
                    142: \> $w_i \leftarrow 0$\\
                    143: for $j=0$ to $m-1$\\
                    144: \>$c \leftarrow 0$\\
                    145: \>for \= $i=0$ to $n-1$\\
                    146: \>\> $t \leftarrow w_{i+j}+u_iv_j+c$\\
                    147: (M)\>\> $t = t_hB+t_l$ ($0 \le t_h, t_l < B$) $B$HJ,2r(B\\
                    148: \>\> $w_{i+j}\leftarrow t_l$\\
                    149: \>\> $c\leftarrow t_h$\\
                    150: \>$w_{n+j} \leftarrow c$\\
                    151: \end{tabbing}
                    152: \end{al}
                    153: (M) $B$G7W;;$5$l$k(B $t$ $B$O(B, $0\le, w_{i+j}, c<B$ ($B$ $B?J(B 1 $B7e(B) $B$N85$h$j(B
                    154: $$ t=w_{i+j}+u_iv_j+c \le (B-1)+(B-1)^2+B-1 = B^2-1$$$B$h$j(B $B$ $B?J$G9b!9(B
                    155: 2 $B7e$N?t$G$"$k(B. $B$h$C$F(B $t_h$, $t_l$ $B$O(B $B$ $B?J(B 1 $B7e$H$J$j(B, $B5"G<E*$K(B,
                    156: $w_{i+j}$, $c$ $B$,>o$K(B $B$ $B?J(B 1 $B7e$H$J$k$3$H$,J,$+$k(B. $B$?$@$7(B, $u_iv_j$
                    157: $B$N7W;;$K$OG\@:EY@0?t>h;;$,I,MW$H$J$k(B.
                    158:
                    159: \section{$B=|;;(B}
                    160: $B@0?t=|;;$b4pK\$OI.;;$HF1MM$G(B, $B>&$N>e0L$N7e$+$i5a$a$F$$$/(B.
                    161: $B4JC1$N$?$a(B, $BHo=|?t(B, $B=|?t$r$=$l$>$l(B
                    162: $$u = u_{n+1}B^{n+1}+\cdots+u_0$$
                    163: $$v = v_n B^n+\cdots+v_0$$ ($0\le u_i,v_i < B$, $u/v < B$) $B$H$9$k(B.  $BLd(B
                    164: $BBj$O(B, $B>&$rG!2?$K@53N$K8+@Q$b$k$3$H$,$G$-$k$+$G$"$k(B. $B<!$K>R2p$9$k$N$O(B
                    165: Knuth \cite[Section 4.3]{KNUTH} $B$K=R$Y$i$l$F$$$k$b$N$G(B, $B>&$N8uJd$r(B, $B=|?t$N>e0L(B 2 $B7e(B,
                    166: $BHo=|?t$N>e0L(B 3 $B7e$+$i5a$a$k(B.
                    167: $\lfloor a \rfloor$ $B$O(B, $a$ $B$r1[$($J$$:GBg$N@0?t$H$9$k(B.
                    168: $q = \lfloor u/v \rfloor$ $B$G$"$k(B.
                    169:
                    170: \begin{pr}
                    171: \label{approx}
                    172: $\hat{q} = \min(B-1,\lfloor (u_{n+1}B+u_n)/v_n \rfloor)$ $B$H$9$k(B.
                    173: $B$3$N;~(B, $v_n \ge \lfloor B/2 \rfloor \Rightarrow q \le \hat{q} \le q+2.$
                    174: \end{pr}
                    175: $BL?Bj(B \ref{approx} $B$K$h$j(B, $v_n \ge \lfloor B/2 \rfloor$ $B$N85$G(B, $B??$NCM(B
                    176: $q$ $B$h$j9b!9(B 2 $B$@$1Bg$-$$6a;wCM(B $\hat{q}$ $B$,F@$i$l$k(B.
                    177:
                    178: \begin{pr}
                    179: \label{check}
                    180: $\hat{q} \ge q$ $B$+$D(B
                    181: $\hat{q}(v_n B + v_{n-1}) > u_{n+1}B^2+u_n B + u_{n-1} \Rightarrow q \le \hat{q}-1.$
                    182: \end{pr}
                    183: $\hat{q} = q+2$ $B$J$i$P>o$KL?Bj(B \ref{check} $B$NITEy<0$,@.N)$9$k$+$i(B, $B$3(B
                    184: $B$N%A%'%C%/$r9b!9(B 2 $B2s9T$J$&$3$H$G(B,
                    185: $\hat{q} = q$ $B$^$?$O(B $\hat{q}=q+1$
                    186: $B$H$G$-$k(B. $B$3$N%A%'%C%/$r9T$C$?$N$A(B, $B$J$*(B $\hat{q} \neq q$ $B$H$J$k(B
                    187: $B2DG=@-$K$D$$$F$O<!$NL?Bj$,@.$jN)$D(B.
                    188:
                    189: \begin{pr}
                    190: $\hat{q} > q$ $B$+$D(B
                    191: $\hat{q}(v_n B + v_{n-1}) \le u_{n+1}B^2+u_n B + u_{n-1}$
                    192: $\Rightarrow u \bmod v \ge (1-2/B)v.$
                    193: \end{pr}
                    194: $B$9$J$o$A(B, $B%i%s%@%`$K(B $u$, $v$ $B$rA*$s$@$H$-(B, $\hat{q} \neq q$ $B$H$J$k(B
                    195: $B3NN($O(B $2/B$ $BDxEY$H$J$j(B, $B=2^{32}$ $B$N>l9g$K$O6K$a$F>.$5$$3NN($G$7$+(B
                    196: $B5/$3$i$J$$$3$H$,J,$+$k(B.
                    197: $B$3$N(B $\hat{q}$ $B$K$h$j(B,
                    198: $\hat{r} = u-\hat{q}v$ $B$r<B:]$K7W;;$7(B
                    199: $B$F(B, $B$b$7(B $\hat{r}$ $B$,Ii$J$i$P(B $q = \hat{q}-1$ $B$G$"$j(B,
                    200: $r = u-qv = \hat{r}+v $
                    201: $B$H$J$k(B.
                    202: $BL?Bj(B \ref{check} $B$NITEy<0$O(B
                    203: $$\hat{q}v_{n-1} > (u_{n+1}B+u_n-\hat{q}v_n)B+u_{n-1}$$
                    204: $B$H=q$1$k$+$i(B, $B$3$N%A%'%C%/$GI,MW(B
                    205: $B$K$J$k@0?t1i;;$O9b!9G\@:EY$G==J,$G$"$k(B. $B$^$H$a$k$H(B,
                    206:
                    207: \begin{itemize}
                    208: \item $\hat{q} = q$ $B$^$?$O(B $\hat{q} = q + 1$$B$G(B, $B8e<T$H$J$k3NN($O6K$a$F>.$5$$(B.
                    209: \item $B@0?t>h=|;;$OG\@:EY>h=|;;$G==J,$G$"$k(B.
                    210: \end{itemize}
                    211: $BA0<T$O(B, $B<B:]$KB-$7La$7$,I,MW$K$J$k>l9g$,6K$a$F>.$5$$$3$H$r0UL#$7(B, $B=|;;(B
                    212: $B$N8zN(8~>e$K$D$J$,$k$,(B, $BH?LL(B, $BB-$7La$7$r9T$J$&ItJ,$N%P%0$H$j$K6lO+$9$k(B
                    213: $B$3$H$J$k(B. $B$^$?(B, $B8e<T$O(B, $BG\@:EY@0?t>h=|;;$5$(<B8=$5$l$F$$$l$P(B, $B$3$N%"%k(B
                    214: $B%4%j%:%`$O<B8=2DG=$G$"$k$3$H$r<($7$F$$$k(B.
                    215: $B>e5-$NJ}K!$G(B, $v_n \ge \lfloor B/2 \rfloor$ $B$J$k@)8B$,M?$($i$l$F$$$k$,(B,
                    216: $B$3$l$O(B, $B$"$i$+$8$a(B $u, v$ $B$K(B $d=\lfloor B/(v_n+1)\rfloor$ $B$r3]$1$F$*$1$P(B
                    217: $BK~$?$5$l$k(B. $B>&$OJQ2=$;$:(B, $B>jM>$O(B $d$ $B$G3d$l$P$h$$(B. $B$^$?(B, $B$ $B$,(B 2 $B$NQQ(B
                    218: $B$N>l9g$K$O(B, $d$ $B$HCM$H$7$F(B $BE,Ev$J(B 2 $B$NQQ$,$H$l$k(B. $B$3$N>l9g(B, $d$ $B$K$h$k(B
                    219: $B>h=|;;$O(B, $B%7%U%H1i;;$H$J$jET9g$,$h$$(B.
                    220:
                    221: \section{$BQQ(B}
                    222:
                    223: $B@0?t$NQQ>h$N7W;;$O(B, $B<!$N$h$&$J(B 2 $BDL$j$N%"%k%4%j%:%`$G9T$&$3$H$,$G$-$k(B.
                    224:
                    225: \begin{al}
                    226: \label{ipwr0}
                    227: \begin{tabbing}
                    228: \\
                    229: Input : $u \in \Z$, $e \in \N$\\
                    230: Output : $w = u^e$\\
                    231: $(k_mk_{m-1}\cdots k_0)_2 \leftarrow e$ $B$N(B 2 $B?JI=<((B ($k_m=1$)\\
                    232: $t \leftarrow u$\\
                    233: $w \leftarrow 1$\\
                    234: for \= $i=0$ to $m$\{\\
                    235: (a)\> if ( $k_i=1$ ) then $w = wt$\\
                    236: \> if ( $i=m$ ) then return $w$\\
                    237: \> $t \leftarrow t^2$\\
                    238: \}
                    239: \end{tabbing}
                    240: \end{al}
                    241:
                    242: \begin{pr}
                    243: $B%"%k%4%j%:%`(B \ref{ipwr0} $B$O(B $u^e$ $B$r=PNO$9$k(B.
                    244: \end{pr}
                    245: \proof (a) $B$K$*$$$F(B, $t=u^{2^i}$ $B$h$j(B, $B$3$N%"%k%4%j%:%`$O(B, $k_i=1$
                    246: $B$J$k(B $i$ $B$KBP$9$k(B $u^{2^i}$ $B$N@Q$r=PNO$9$k(B. $B$3$NCM$O(B $u^e$ $B$KEy$7$$(B. \qed
                    247:
                    248: \begin{al}
                    249: \label{ipwr1}
                    250: \begin{tabbing}
                    251: \\
                    252: Input : $u \in \Z$, $e \in \N$\\
                    253: Output : $w = u^e$\\
                    254: $(k_mk_{m-1}\cdots k_0)_2 \leftarrow e$ $B$N(B 2 $B?JI=<((B ($k_m=1$)\\
                    255: $w \leftarrow 1$\\
                    256: for \= $i=m$ to $0$\{\\
                    257: (a)\> $w \leftarrow w^2$\\
                    258: \> if ( $k_i=1$ ) then $w = wu$\\
                    259: \}\\
                    260: return $w$
                    261: \end{tabbing}
                    262: \end{al}
                    263:
                    264: \begin{pr}
                    265: $B%"%k%4%j%:%`(B \ref{ipwr1} $B$O(B $u^e$ $B$r=PNO$9$k(B.
                    266: \end{pr}
                    267: \proof $m=0$ $B$N;~(B $w=u$ $B$H$J$j@5$7$$(B. $m-1$ $B$^$G@5$7$$$H$9$k(B.
                    268: $e_1 = (k_mk_{m-1}\cdots k_1)$ $B$r(B $m$ bit $B?t$H$_$J$;$P(B, $B5"G<K!$N(B
                    269: $B2>Dj$K$h$j(B, $i=0$ $B$G(B (a) $B$K$*$$$F(B $w=u^{e_1}$.
                    270: $B$3$N$H$-(B, $B$3$N%"%k%4%j%:%`$O(B $w^2\cdot u^{k_0}=u^{2e_1+k_0}$
                    271: $B$r=PNO$9$k$,(B, $B$3$l$O(B $u^e$ $B$KEy$7$$(B. \qed\\
                    272: $B$3$l$i$N%"%k%4%j%:%`$O(B, $e$ $B>h$r(B, $B$=$l$>$l(B $\log_2 e$ $B2sDxEY$N(B 2 $B>h;;$H(B
                    273: $B>h;;$G<B9T$G$-$k(B. $B$3$N%"%k%4%j%:%`$O(B, $B@0?t$NQQ>h$K8B$i$:(B, $B$"$i$f$k(B
                    274: $B>l9g$KMQ$$$i$l$kHFMQE*$J$b$N$G$"$k(B. $BA0<T$N%"%k%4%j%:%`$O(B,
                    275: \begin{itemize}
                    276: \item $B;X?t(B $e$ $B$N3F%S%C%H$r1&$+$i:8$K%9%-%c%s$9$k(B.
                    277: \item $B>o$K3]$1$k?t$OF1$8(B.
                    278: \item $BJ];}$9$Y$-ESCf7k2L$O(B $w$ $B$N$_(B.
                    279: \end{itemize}
                    280: $B8e<T$O(B
                    281: \begin{itemize}
                    282: \item $B;X?t(B $e$ $B$N3F%S%C%H$r:8$+$i1&$K%9%-%c%s$9$k(B.
                    283: \item $B3]$1$k?t$,JQ2=$7$F$$$/(B.
                    284: \item $BJ];}$9$Y$-ESCf7k2L$O(B $w$, $t$ $B$NN>J}(B.
                    285: \end{itemize}
                    286: $B$H$$$&FCD'$r;}$A(B, $B$=$l$>$l0lD90lC;$,$"$k(B.