Return to num.tex CVS log

Up to [local] / OpenXM / doc / compalg

Added a comment on Karatsuba algorithm for computing integer products.

%$OpenXM: OpenXM/doc/compalg/num.tex,v 1.3 2000/10/03 01:44:03 noro Exp $
\chapter{$B@0?t(B}

\section{$B@0?t$NI=8=(B}
$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
$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
bignum}) $B$KBP$9$k1i;;$O(B

\begin{enumerate}
\item $B@0?t$r(B, $B$"$k@0?t(B $B$ $B$K$h$j(B $B$ $B?JI=<($9$k(B. 
\item $B3F7e$I$&$7$N1i;;$r(B CPU $B$N@0?t1i;;5!G=$K$h$j9T$J$&(B. 
\item $B$3$l$i$NAH9g$;$K$h$j85$N@0?t$I$&$7$N1i;;7k2L$rF@$k(B.
\end{enumerate}
$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
$B9g$,B?$$(B. $B$3$l$O(B,

\begin{itemize}
\item $B$ $B$rBg$-$/$9$k$H(B $B$ $B?JI=8=$N7e?t$,>/$J$/$G:Q$`(B
\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
\end{itemize}
$B$H$$$&M}M3$K$h$k(B. $B$7$+$7(B, $B$ $B$r(B, $BH>%o!<%ID9$h$jBg(B
$B$-$/$H$k>l9g(B, $B>h=|;;$K$*$$$F(B,

\begin{enumerate}
\item
$BC1@:EY@0?t(B $\times$ $BC1@:EY@0?t(B $\rightarrow$ $BG\@:EY@0?t(B
\item
$BG\@:EY@0?t(B $\rightarrow$ $BC1@:EY@0?t(B $\times$ $BC1@:EY@0?t(B + $BC1@:EY@0?t(B
\end{enumerate}
$B$H$$$&Fs$D$N1i;;$,I,MW$K$J$k(B. 

$BI8=`E*$J(B C $B8@8l$K$*$$$F$O>e5-$N1i;;$ODL>oDs6!$5$l$F$*$i$:(B, $B%"%;%s%V%j(B
$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
{\tt gcc} $B$G$O(B{\tt long long} $B$"$k$$$O(B {\tt unsigned long long} $B@k8@$K(B
$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
$B$,2DG=$H$J$k(B. $BNc$($P(B 1. $B$N1i;;$O(B

\begin{verbatim}
typedef unsigned int UL;
typedef unsigned long long ULL;
UL a,b,ch,cl;
ULL c;
...
c = (ULL)a*(ULL)b;
ch = (UL)(c>>32);
cl = (UL)(c&(((ULL)1)<<32));
\end{verbatim}
$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 
$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
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
$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
$BF@$J$$(B.

$B0J2<(B, $B$ $B?JI=8=$5$l$?Fs$D$N<+A3?t(B
$$u=u_nB^n+u_{n-1}B^{n-1}+\cdots+u_0$$
$$v=v_mB^m+v_{m-1}B^{m-1}+\cdots+v_0$$
($0\le u_i, v_j \le B-1$) $B$KBP$7(B, $B2C8:>h=|1i;;$r9T$&$3$H$r9M$($k(B. 

\section{$B2C;;(B}
$B2C;;$O(B, $BI.;;$r9T$&$h$&$K2<0L$N7e$+$i7+$j>e$,$j$H$H$b$KB-$7$F$$$1$P$h$$(B. 
$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
$B$N%o!<%ID90lGU(B (32bit CPU $B$J$i(B $B=2^{32}$) $B$rA*$s$@>l9g(B, $B<!$N$h$&$J%"(B
$B%k%4%j%:%`$H$J$k(B.

\begin{al}
\begin{tabbing}
\\
Input : $u=\sum_{i=0}^{n-1} u_iB^i$, $v=\sum_{i=0}^{n-1}v_iB^i$\\
Output : $w = u+v$\\
$c \leftarrow 0$\\
for \= $i=0$ to $n-1$\\
\> $t \leftarrow u_i+v_i \bmod B$\\
\> if \= $t < u_i$\\
\>\> $t \leftarrow t+c \bmod B$\\
\>\> $c\leftarrow 1$\\
\> else\\
\>\> $t \leftarrow t+c \bmod B$\\
\>\> if $t < c$ then $c \leftarrow 1$ else $c \leftarrow 0$\\
\> $w_i \leftarrow t$\\
$w_n \leftarrow c$\\
return $\sum_{i=0}^n w_iB^i$
\end{tabbing}
\end{al}
$B$3$N%"%k%4%j%:%`$K8=$l$k(B $c \leftarrow a+b \bmod B$ $B$O(B,
$$a+b \ge B \Rightarrow c \leftarrow a+b-B$$ $B$r0UL#$9$k(B. $B$ $B$,%o!<%ID90lGU(B
$B$N>l9g(B, Section \ref{cpuint} $B$G=R$Y$?$h$&$K2C;;$O(B $B$ $B$rK!$H$7$F9T$o$l(B
$B$k(B. $B$3$l$O(B, C $B8@8l$G$O(B,

\begin{verbatim}
unsigned int a,b,c;
...
c = a+b;
\end{verbatim}
$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
$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
$B2C;;$,@5$7$/<B9T$G$-$k$N$G$"$k(B.

\section{$B8:;;(B}
$B8:;;$b(B, $BI.;;$HF1MM$N;EJ}$G9T$&(B. 

\begin{al}
\begin{tabbing}
\\
Input : $u=\sum_{i=0}^{n-1} u_iB^i$, $v=\sum_{i=0}^{n-1}v_iB^i$ ($u\ge v$)\\
Output : $w = u-v$\\
$b \leftarrow 0$\\
for \= $i=0$ to $n-1$\\
\> $t \leftarrow u_i-v_i \bmod B$\\
\> if \= $t > u_i$\\
\>\> $t \leftarrow t-b$\\
\>\> $b\leftarrow 1$\\
\> else\\
\>\> $t \leftarrow t-b \bmod B$\\
(B)\>\> if $t = B-1$ then $b \leftarrow 1$ else $b \leftarrow 0$\\
\> $w_i \leftarrow t$\\
return $\sum_{i=0}^{n-1} w_iB^i$
\end{tabbing}
\end{al}
$B$3$N%"%k%4%j%:%`$K8=$l$k(B $c \leftarrow a-b \bmod B$ $B$O(B,
$$a-b < 0 \Rightarrow c \leftarrow a-b+B$$ $B$r0UL#$9$k(B. $B$3$NA`:n$b(B, 
C $B8@8l$G$O(B 

\begin{verbatim}
unsigned int a,b,c;
...
c = a-b;
\end{verbatim}
$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
$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$ 
$B$+$D(B $b=1$ $B$N>l9g$K$N$_@8$:$k$?$a$G$"$k(B. 

\section{$B>h;;(B}

$B>h;;$bI.;;$HF1MM$NJ}K!$G7W;;$G$-$k(B. 

\begin{al}
\begin{tabbing}
\\
Input : $u=\sum_{i=0}^{n-1} u_iB^i$, $v=\sum_{i=0}^{m-1}v_iB^i$\\
Output : $w = uv$\\
for \= $i=0$ to $n-1$\\
\> $w_i \leftarrow 0$\\
for $j=0$ to $m-1$\\
\>$c \leftarrow 0$\\
\>for \= $i=0$ to $n-1$\\
\>\> $t \leftarrow w_{i+j}+u_iv_j+c$\\
(M)\>\> $t = t_hB+t_l$ ($0 \le t_h, t_l < B$) $B$HJ,2r(B\\
\>\> $w_{i+j}\leftarrow t_l$\\
\>\> $c\leftarrow t_h$\\
\>$w_{n+j} \leftarrow c$\\
\end{tabbing}
\end{al}
(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
$$ 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 
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,
$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$ 
$B$N7W;;$K$OG\@:EY@0?t>h;;$,I,MW$H$J$k(B.

$B$3$N%"%k%4%j%:%`$G$O(B, $BF~NO$N7e?t$N@Q(B $mn$ $B$KHfNc$9$k<j4V$,$+$+$k(B. $B7e?t(B
$B$NBg$-$$?t$N@Q$N<j4V$r8:$i$99)IW$H$7$F(B Karatsuba $BK!$*$h$S(BFFT $BK!$,$"$k(B. 
$B$3$l$i$N$&$A(B, $BB?9`<0$K4X$9$k(B Karatsuba $BK!$K$D$$$F$O(BSection \ref{kara} 
$B$G=R$Y$k$,(B, $B@0?t$KBP$7$F$bA4$/F1MM$N%"%k%4%j%:%`$,E,MQ$G$-$k(B. ($B$ $B?J(B
$B@0?t$O(B, $B$ $B$K4X$9$kB?9`<0$H$_$J$;$k$3$H$KCm0U(B.)  $B0lHL$K(B, Karatsuba $BK!(B
$B$O$$$/$i$+$N(B overhead $B$rH<$&$?$a(B, $B<B:]$K$O(B, $B$"$k7e?t(B ($B$7$-$$CM(B)
$B$r@_Dj$7$F(B, $B$7$-$$CM0J>e$N7e?t$G$O(B Karatsuba $BK!(B, $B$=$l0J2<$G$O$3$3$G=R(B
$B$Y$?%"%k%4%j%:%`$rE,MQ$9$k$3$H$G(B, $B$5$^$6$^$J7e?t$N?t$KBP$7$F9bB.$J(B
$B<BAu$,F@$i$l$k(B. 

\section{$B=|;;(B}
$B@0?t=|;;$b4pK\$OI.;;$HF1MM$G(B, $B>&$N>e0L$N7e$+$i5a$a$F$$$/(B. 
$B4JC1$N$?$a(B, $BHo=|?t(B, $B=|?t$r$=$l$>$l(B
$$u = u_{n+1}B^{n+1}+\cdots+u_0$$
$$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
$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
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, 
$BHo=|?t$N>e0L(B 3 $B7e$+$i5a$a$k(B. 
$\lfloor a \rfloor$ $B$O(B, $a$ $B$r1[$($J$$:GBg$N@0?t$H$9$k(B. 
$q = \lfloor u/v \rfloor$ $B$G$"$k(B. 

\begin{pr}
\label{approx}
$\hat{q} = \min(B-1,\lfloor (u_{n+1}B+u_n)/v_n \rfloor)$ $B$H$9$k(B. 
$B$3$N;~(B, $v_n \ge \lfloor B/2 \rfloor \Rightarrow q \le \hat{q} \le q+2.$
\end{pr}
$BL?Bj(B \ref{approx} $B$K$h$j(B, $v_n \ge \lfloor B/2 \rfloor$ $B$N85$G(B, $B??$NCM(B 
$q$ $B$h$j9b!9(B 2 $B$@$1Bg$-$$6a;wCM(B $\hat{q}$ $B$,F@$i$l$k(B. 

\begin{pr}
\label{check}
$\hat{q} \ge q$ $B$+$D(B
$\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.$
\end{pr}
$\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
$B$N%A%'%C%/$r9b!9(B 2 $B2s9T$J$&$3$H$G(B, 
$\hat{q} = q$ $B$^$?$O(B $\hat{q}=q+1$ 
$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
$B2DG=@-$K$D$$$F$O<!$NL?Bj$,@.$jN)$D(B. 

\begin{pr}
$\hat{q} > q$ $B$+$D(B
$\hat{q}(v_n B + v_{n-1}) \le u_{n+1}B^2+u_n B + u_{n-1}$
$\Rightarrow u \bmod v \ge (1-2/B)v.$
\end{pr}
$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
$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
$B5/$3$i$J$$$3$H$,J,$+$k(B. 
$B$3$N(B $\hat{q}$ $B$K$h$j(B, 
$\hat{r} = u-\hat{q}v$ $B$r<B:]$K7W;;$7(B
$B$F(B, $B$b$7(B $\hat{r}$ $B$,Ii$J$i$P(B $q = \hat{q}-1$ $B$G$"$j(B, 
$r = u-qv = \hat{r}+v $
$B$H$J$k(B. 
$BL?Bj(B \ref{check} $B$NITEy<0$O(B
$$\hat{q}v_{n-1} > (u_{n+1}B+u_n-\hat{q}v_n)B+u_{n-1}$$
$B$H=q$1$k$+$i(B, $B$3$N%A%'%C%/$GI,MW(B
$B$K$J$k@0?t1i;;$O9b!9G\@:EY$G==J,$G$"$k(B. $B$^$H$a$k$H(B,

\begin{itemize}
\item $\hat{q} = q$ $B$^$?$O(B $\hat{q} = q + 1$$B$G(B, $B8e<T$H$J$k3NN($O6K$a$F>.$5$$(B. 
\item $B@0?t>h=|;;$OG\@:EY>h=|;;$G==J,$G$"$k(B. 
\end{itemize}
$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
$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
$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
$B%4%j%:%`$O<B8=2DG=$G$"$k$3$H$r<($7$F$$$k(B.
$B>e5-$NJ}K!$G(B, $v_n \ge \lfloor B/2 \rfloor$ $B$J$k@)8B$,M?$($i$l$F$$$k$,(B, 
$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
$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
$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
$B>h=|;;$O(B, $B%7%U%H1i;;$H$J$jET9g$,$h$$(B. 

\section{$BQQ(B}

$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. 

\begin{al}
\label{ipwr0}
\begin{tabbing}
\\
Input : $u \in \Z$, $e \in \N$\\
Output : $w = u^e$\\
$(k_mk_{m-1}\cdots k_0)_2 \leftarrow e$ $B$N(B 2 $B?JI=<((B ($k_m=1$)\\
$t \leftarrow u$\\
$w \leftarrow 1$\\
for \= $i=0$ to $m$\{\\
(a)\> if ( $k_i=1$ ) then $w = wt$\\
\> if ( $i=m$ ) then return $w$\\
\> $t \leftarrow t^2$\\
\}
\end{tabbing}
\end{al}

\begin{pr}
$B%"%k%4%j%:%`(B \ref{ipwr0} $B$O(B $u^e$ $B$r=PNO$9$k(B. 
\end{pr}
\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$
$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

\begin{al}
\label{ipwr1}
\begin{tabbing}
\\
Input : $u \in \Z$, $e \in \N$\\
Output : $w = u^e$\\
$(k_mk_{m-1}\cdots k_0)_2 \leftarrow e$ $B$N(B 2 $B?JI=<((B ($k_m=1$)\\
$w \leftarrow 1$\\
for \= $i=m$ to $0$\{\\
(a)\> $w \leftarrow w^2$\\
\> if ( $k_i=1$ ) then $w = wu$\\
\}\\
return $w$
\end{tabbing}
\end{al}

\begin{pr}
$B%"%k%4%j%:%`(B \ref{ipwr1} $B$O(B $u^e$ $B$r=PNO$9$k(B. 
\end{pr}
\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. 
$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
$B2>Dj$K$h$j(B, $i=0$ $B$G(B (a) $B$K$*$$$F(B $w=u^{e_1}$.
$B$3$N$H$-(B, $B$3$N%"%k%4%j%:%`$O(B $w^2\cdot u^{k_0}=u^{2e_1+k_0}$
$B$r=PNO$9$k$,(B, $B$3$l$O(B $u^e$ $B$KEy$7$$(B. \qed\\
$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
$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
$B>l9g$KMQ$$$i$l$kHFMQE*$J$b$N$G$"$k(B. $BA0<T$N%"%k%4%j%:%`$O(B, 
\begin{itemize}
\item $B;X?t(B $e$ $B$N3F%S%C%H$r1&$+$i:8$K%9%-%c%s$9$k(B. 
\item $B>o$K3]$1$k?t$OF1$8(B. 
\item $BJ];}$9$Y$-ESCf7k2L$O(B $w$ $B$N$_(B. 
\end{itemize}
$B8e<T$O(B
\begin{itemize}
\item $B;X?t(B $e$ $B$N3F%S%C%H$r:8$+$i1&$K%9%-%c%s$9$k(B. 
\item $B3]$1$k?t$,JQ2=$7$F$$$/(B. 
\item $BJ];}$9$Y$-ESCf7k2L$O(B $w$, $t$ $B$NN>J}(B. 
\end{itemize}
$B$H$$$&FCD'$r;}$A(B, $B$=$l$>$l0lD90lC;$,$"$k(B.