Return to intro.tex CVS log

Up to [local] / OpenXM / doc / compalg

Annotation of OpenXM/doc/compalg/intro.tex, Revision 1.3

1.3     ! noro        1: %$OpenXM$
1.1       noro        2: \chapter{$B$O$8$a$K(B}
                      3:
                      4: $B7W;;5!Be?t$O(B, $B7W;;5!>e$G(B, $BBe?tE*7W;;$r@53N$K9T$J$&$3$H$rL\I8$H$7$F$$$k(B.
                      5:
                      6: $B7W;;5!$,<BMQ2=$5$l$F0JMh(B, $B7W;;5!>e$G$N7W;;$H$O(B, $B8GDjD9(B, $B$9$J$o$A7W;;5!(B
                      7: $B$,Ds6!$9$k%5%$%:$N@0?t$"$k$$$OIbF0>.?t$rMQ$$$?7W;;$r0UL#$9$k>l9g$,$[$H(B
                      8: $B$s$I$G$"$C$?(B. $BFC$K(B, $BIbF0>.?t$rMQ$$$k(B, $B$$$o$f$k?tCM7W;;$N>l9g(B, $B7W;;8m:9(B
                      9: $B$OHr$1$i$l$:(B, $B0l$D$N%"%k%4%j%:%`$KBP$7$F(B, $B$=$N7k2L$N8m:9$N2r@O$OI,?\$G(B
                     10: $B$"$C$?(B. $B<B:](B, $BDL>o$N?tCM7W;;$G$O8m:9$NN_@Q$,Bg$-2a$.$F(B, $B<BMQ$K$OE,$5$J(B
                     11: $B$$$H$5$l$k%"%k%4%j%:%`$bB8:_$9$k(B. $B$^$?(B, $B?tCM7W;;$O(B, $BBe?tE*7W;;$K8B$i$:(B,
                     12: $BBe?tJ}Dx<0(B, $BHyJ,J}Dx<0$J$I$N6a;w2r$N7W;;$J$I$K9-$/MQ$$$i$l$F$$$k$,(B, $B$=(B
                     13: $B$l$i$N>l9g$K$*$1$k(B, $BBe?tJ}Dx<0(B, $BHyJ,J}Dx<0$O(B, $BB?$/$N>l9g(B, $B$=$N?t3XE*9=(B
                     14: $BB$$O=E;k$5$l$:(B, $B$"$kE@$K$*$1$kCM$r@8@.$9$k%V%i%C%/%\%C%/%9$H$7$FMQ$$$i(B
                     15: $B$l$k(B. $B$3$N$h$&$JJ}K!$O(B, $B9-$$HO0O$NF~NO$KBP$7$F$J$s$i$+$N6a;w2r$r@8@.$9(B
                     16: $B$k$3$H$,$G$-$kH?LL(B, $BF@$i$l$?2r$+$i(B, $B$b$H$NJ}Dx<0$,K\Mh;}$C$F$$$??t3XE*(B
1.2       noro       17: $B$J@-<A$rF@$k$3$H$OB?$/$N>l9g:$Fq$G$"$k(B. $B7W;;5!Be?t$O(B, $B?t3XE*BP>]$r(B, $BCi(B
                     18: $B<B$K7W;;5!>e$KI=8=$7(B, $B8m:9$N$J$$7W;;$r9T$J$&$3$H$K$h$j(B, $B?t3XE*$KL@3N$J(B
                     19: $B0UL#$r$b$D7k2L$rF@$k$3$H$r<g4c$H$7$F$$$k(B. $BEvA3(B, $B?tCM7W;;$KHf3S$7$F(B, $B07(B
                     20: $B$($kBP>]$O8B$i$l$k(B. $B:#$N$H$3$m(B, $B@0?t(B, $BM-M}?t$*$h$S$=$l$i$r78?t$H$9$kB?(B
                     21: $B9`<0(B, $BM-M}<0$,<g$JBP>]$G$"$k$?$a(B, $B7W;;5!(B{\bf $BBe?t(B}$B$H8F$P$l$k(B. $B$7$+$7(B,
                     22: $B$=$N5Z$VHO0O$O(B, $BB?9`<0$N0x?tJ,2r$r=i$a$H$7$F(B, $BB?9`<0%$%G%"%kO@$N1~MQ$H(B
                     23: $B$7$F$NBe?t4v2?3X$r%+%P!<$9$k$^$G$K$J$j(B, $B%$%G%"%k$N=`AG%$%G%"%kJ,2r$,9=(B
                     24: $B@.E*$K2DG=$H$J$C$F$$$k(B. $B$3$NJ,Ln$K$*$1$k4pK\E*$J%D!<%k$O(B, Buchberger
                     25: $B$K$h$j9M0F$5$l$?%0%l%V%J4pDl$G$"$k(B. $B$3$l$r4^$`35G0$,(B, standard basis
                     26: $B$H$7$F(B, $B9-Cf$K$h$j(B Buchberger $B0JA0$K9M0F$5$l$F$$$?$,(B, $BB?9`<04D$N>l9g$K(B
                     27: $B9=@.E*$J@8@.%"%k%4%j%:%`$r(B Buchberger $B$,M?$($?$3$H$K$h$j(B, $B0J>e$N$3$H$,(B
                     28: $B7W;;5!>e$G2DG=$H$J$C$?$o$1$G$"$k(B.
1.1       noro       29:
                     30: $B0J>e$N$h$&$K(B, $B7W;;5!Be?t$K$*$$$F$O(B, $B@53N$J7W;;$H$$$&$3$H$,4pK\$H$J$C$F(B
                     31: $B$$$k(B. $B:G$b4pK\E*$JC10L$G$"$k@0?t$b(B, $BI,MW$J$@$1$N7e?t$r$9$Y$FI=8=$G$-(B
                     32: $B$kG$0UB?G\D9@0?t(B (bignum) $B$H$$$&7A$GI=8=$5$l$J$1$l$P$J$i$J$$(B. $BEvA3$J$,(B
                     33: $B$i(B, $B7e?t$,A}$($l$PA}$($k$[$I(B, $B$=$l$i$N4V$N1i;;$K$+$+$k;~4V$OA}$($k(B. $B<B(B
                     34: $B:](B, bignum $B$N7W;;;~4V$,(B, $BA4BN$N7W;;;~4V$N<gMW$JItJ,$r@j$a$k>l9g$b$7$P(B
                     35: $B$7$P@8$:$k(B. $B$h$C$F(B, $B7W;;5!Be?t$K$*$$$F$O(B, $B7W;;5!$,Ds6!$9$k@0?t1i;;$N@-(B
                     36: $BG=$,(B, $B7W;;A4BN$N8zN($rBg$-$/:81&$9$k(B.
                     37: $B;DG0$J$,$i(B, $B$D$$:G6a$^$G(B, $B7W;;@-G=$N8~>e$O(B, $B$$$o$f$k(B High Performace
                     38: Computing $B$N$?$a$NIbF0>.?t1i;;$KBP$7$F$N$_7W$i$l$F$-$?(B.
                     39: $B$7$+$7(B, Pentium, SPARC $B$J$I$N(B CPU $B$G$O(B
                     40: $B@0?t1i;;@-G=$N8~>e$b?^$i$l$F$*$j(B, $B7W;;5!Be?t%7%9%F%`$N@-G=$b$=$l$K(B
                     41: $B1~$8$FHtLvE*$K8~>e$7$F$-$?(B.
                     42: $B$5$i$K(B, $B:G6aBg$-$/CmL\$5$l$F$$$k0E9f5;=Q$O(B, RSA $B0E9f(B, $BBJ1_6J@~0E9f(B
                     43: $B$J$I(B, bignum $B$"$k$$$O$=$N>e$NB?9`<01i;;$r%Y!<%9$H$7$F$$$k$b$N$,B?$/(B,
                     44: $B7W;;5!Be?t$GG]$o$l$?$5$^$6$J<jK!$,$=$N$^$^LrN)$D%1!<%9$bB?$$(B.
                     45: $B7W;;5!Be?t$G$O(B, $BB?9`<0(B, $BM-M}<0$J$I(B, $BLZ9=B$$r$b$DBP>]$,?tB?$/(B
                     46: $BMQ$$$i$l$k$?$a(B, $B?t$N1i;;@-G=$@$1$G$J$/(B, $B%G!<%?9=B$$NI=8=J}K!(B, $B$5$^$6$^(B
                     47: $B$J%"%k%4%j%:%`$N8zN($N8~>e(B, $B$"$k$$$O%a%b%j4IM}$J$I$r?<$/9MN8$9$kI,MW$,(B
                     48: $B$"$k(B.
                     49:
                     50: $BK\9V$G$O(B,
                     51: \begin{itemize}
                     52: \item $B@0?t(B, $BB?9`<0$NI=8=$*$h$S;MB'1i;;%"%k%4%j%:%`(B
                     53: \item $BB?9`<0(B GCD, $B=*7k<0(B, $BCf9q>jM>DjM}(B
                     54: \item $BB?9`<0$N0x?tJ,2r(B, $BM-M}4X?t$NITDj@QJ,(B
                     55: \item $B%0%l%V%J4pDl(B, $BBe?tJ}Dx<0$N5a2r(B, $B%$%G%"%k$N=`AGJ,2r(B
                     56: \end{itemize}
                     57: $B$K$D$$$F=R$Y$k(B. $B$3$3$G=R$Y$i$l$k%"%k%4%j%:%`$N$[$H$s$I$O(B, $BI.<T$i$,3+H/(B,
                     58: $BG[I[Cf$N7W;;5!Be?t%7%9%F%`(B Risa/Asir \cite{NS} $B>e$K<BAu$5$l(B, $BMQ$$$i$l$F$$$k(B.
                     59:
                     60: \begin{nt}
                     61: \begin{tabbing}
                     62: \end{tabbing}
                     63: \begin{description}
                     64: \item[$\Z$] $BM-M}@0?t4D(B
                     65: \item[$\N$] $BHsIi@0?tA4BN(B
                     66: \item[$\Q$] $BM-M}?tBN(B
                     67: \item[$\C$] $BJ#AG?t(B
                     68: \item[$|F|$] $F$ $B$,?t$N$H$-@dBPCM(B, $F$ $B$,=89g$N$H$-85$N8D?t(B ($BG;EY(B)
                     69: \end{description}
                     70: \end{nt}
                     71:
                     72: \chapter{$B=`Hw(B}
                     73:
                     74: $BK\>O$G$O(B, $B0J2<$G=R$Y$k$5$^$6$^$J%"%k%4%j%:%`$rM}2r$7(B, $B7W;;5!>e$K<BAu(B
                     75: $B$9$k$?$a$KI,MW$J$3$H$,$i$K$D$$$F@bL@$9$k(B.
                     76:
                     77: \section{CPU $B$N9=B$$*$h$SF0:n(B}
                     78:
                     79: $B$I$N$h$&$J8@8l$G%"%k%4%j%:%`$,5-=R$5$l$k$K$;$h(B, $B:G=*E*$K$O(B
                     80: $B$=$N%"%k%4%j%:%`$O(B CPU $B8GM-$NL?Na$H$7$F<B9T$5$l$k(B. $B$3$3$G$O(B,
                     81: CPU $B$N4pK\E*$J9=B$(B, $BF0:n$K$D$$$F2r@b$9$k(B.
                     82:
                     83: \subsection{CPU $B$K$D$$$F$N$"$i$^$7(B}
                     84:
                     85: CPU $B$KBP$9$kL?Na$O(B, 32bit $B$"$k$$$O(B 64bit $B$H$$$&$"$k7h$^$C$?Bg$-$5$N(B
                     86: bit $BNs$GI=8=$5$l$F$$$k(B. CPU $B$O(B, $B%a%b%jCf$KCV$+$l$?0lO"$NL?NaNs$r=g(B
                     87: $B$KFI$_=P$7(B, $BBP1~$9$kA`:n$r<B9T$9$k(B. CPU $B$O(B, $B%l%8%9%?$H8F$P$l$k(B
                     88: $BFC<l$J%a%b%j$r;}$C$F$$$k(B. $B%l%8%9%?$O(B, CPU $B$N9=@.$K1~$8$F(B 32bit $B$"$k$$$O(B
                     89: 64 bit $B$H$$$&Bg$-$5$r;}$D(B. $B$=$NK\?t$ODL>o?tK\$+$i?t==K\DxEY$H>/$J$$$,(B,
                     90: $B<g5-21$HHf3S$7$F9bB.$KFI$_=q$-$G$-(B, CPU $B$N%G!<%?A`:n$NBP>]$H$J$k(B.
                     91: CPU $B$,9T$&4pK\A`:n$K$O(B, $B<!$N$h$&$J$b$N$,$"$k(B.
                     92:
                     93: \begin{itemize}
                     94: \item $B%a%b%j$KBP$9$kL?Na(B
                     95:
                     96: $B%a%b%j$+$i%l%8%9%?$X$N%G!<%?$NFI$_9~$_(B, $B%l%8%9%?$+$i%a%b%j$X$N(B
                     97: $B%G!<%?$N=q$-=P$7$r9T$&(B.
                     98:
                     99: \item $B1i;;L?Na(B
                    100:
                    101: $B4v$D$+$N%l%8%9%?$KCV$+$l$?%G!<%?$rMQ$$$F<o!9$N1i;;$r9T$&(B. $B1i;;L?Na$K$O(B,
                    102: $B@0?t1i;;L?Na(B, $BIbF0>.?t1i;;L?Na$J$I$,$"$k(B.
                    103:
                    104: \item $BJ,4tL?Na(B
                    105:
                    106: $B%l%8%9%?$NCM$r%F%9%H$7$F(B, $B$=$N7k2L$K1~$8$F%W%m%0%i%`Cf$N;XDj$5$l$?(B
                    107: $B>l=j$K%8%c%s%W$9$k(B.
                    108: \end{itemize}
                    109:
                    110: \subsection{$B@0?t1i;;L?Na(B}
                    111: \label{cpuint}
                    112: $B7W;;5!Be?t$K$*$$$F$O(B, $B8m:9$N$J$$1i;;$r<B8=$9$k$?$a@0?t1i;;$rB?MQ$9$k(B.
                    113: $B$3$3$G$O(B, $B@0?t1i;;L?Na$K$D$$$F4JC1$K2r@b$9$k(B.
                    114:
                    115: $B%l%8%9%?$N(B bit $BD9(B $n$ $B$KBP$7(B $2^n$ $B$r(B $B$ $B$H=q$/(B.  $B%l%8%9%?>e$N%G!<%?(B
                    116: $B$O(B, 0 $B0J>e(B $B-1$ $B0J2<$NHsIi@0?t$rI=$9$3$H$,$G$-$k(B. $B$9$J$o$A(B, $a_i$ $B$r(B
                    117: 0 $B$^$?$O(B 1 $B$H$9$k$H(B, bit $BNs(B $(a_{n-1}a_{n-2}\cdots a_1a_0)$$B$O(B
                    118: $$a=\sum_{i=0}^{n-1}a_i2^i$$ $B$J$k@0?t(B $a$ $B$rI=$9(B ($BFs?J?t(B).  $B0lJ}$G(B, $BIi?t$O(B 2 $B$N(B
                    119: $BJd?tI=<($H8F$P$l$kJ}K!$G(B, $B$d$O$j(B $n$ bit $B$N%G!<%?$GI=$9(B. $B$3$N>l9g(B bit
                    120: $BNs(B $(a_{n-1}a_{n-2}\cdots a_1a_0)$ $B$O(B
                    121: $$a=-a_{n-1}2^{n-1}+\sum_{i=0}^{n-2}a_i2^i$$ $B$J$k@0?t(B $a$ $B$rI=$9(B. $BNc$((B
                    122: $B$P(B, $-1$ $B$O(B $(11\cdots 1)$ $B$J$k(B bit $BNs$GI=$5$l$k(B. $B$3$NJ}K!$K$h$l$P(B,
                    123: $n$ bit $B$N%G!<%?$G(B $-B/2 \le a \le B/2-1$ $B$J$k@0?t$rI=$9$3$H$,$G$-(B
                    124: $B$k(B. $BCm0U$9$Y$-E@$O(B, $B2C8:>h;;$rK!(B $B$ $B$G9T$&>l9g(B, $B$I$A$i$G2r<a$7$F$b7k2L$O(B
                    125: $BF10l$H$J$k$3$H$G$"$k(B. $B$3$l$O(B, $B>e5-Fs$D$NI=8=$N0c$$$,(B $BK!(B $B$ $B$G$NBeI=85(B
                    126: $B$N<h$jJ}$N0c$$$G$"$k$3$H$+$i$o$+$k(B. $B0J2<$G(B, $r = a \bmod B$ $B$O(B
                    127: $0\le r < B$ $B$J$k>jM>$rI=$9(B. $BDL>o(B, CPU $B$K$O<!$N$h$&$J@0?t1i;;L?Na$,MQ(B
                    128: $B0U$5$l$F$$$k(B.
                    129:
                    130: \begin{itemize}
                    131: \item $B2C;;(B
                    132:
                    133: $(a+b) \bmod B$
                    134:
                    135: \item $B8:;;(B
                    136:
                    137: $(a-b) \bmod B$
                    138:
                    139: \item $BHf3S(B
                    140:
                    141: if $a > b$ then 1 else 0
                    142:
                    143: \item $B:8%7%U%H(B
                    144:
                    145: $a$ $B$N(B $k$ bit $B:8%7%U%H(B $\bmod B$
                    146:
                    147: \item $B1&%7%U%H(B
                    148:
                    149: $a$ $B$N(B $k$ bit $B1&%7%U%H(B ($B1&(B $k$ bit $B$O<N$F$i$l$k(B)
1.2       noro      150:
                    151: \item bit $BKh$N(B and, or, exclusive or, not
                    152:
                    153: $B@0?t$r(B bit $BNs$H8+$F(B, $B3F(B bit $BKh$KO@M}1i;;$r9T$&(B.
1.1       noro      154: \end{itemize}
                    155:
                    156: $B%7%U%H1i;;$O(B, $BO@M}1i;;$KMQ$$$i$l$k$@$1$G$J$/(B, $B@0?t$N(B $2^k$ $BG\(B, $B$"$k$$$O(B
1.2       noro      157: $2^k$ $B$G3d$C$?>&$N7W;;$KMQ$$$i$l$k(B. $B$3$l$i0J30$K(B, CPU $B$K$h$C$F$O<!$N(B
1.1       noro      158: $B1i;;$,MQ0U$5$l$F$$$k>l9g$,$"$k(B.
                    159:
                    160: \begin{itemize}
                    161: \item $B>h;;(B
                    162:
                    163: $(a\times b) \bmod B$
                    164:
                    165: \item $BG\@:EY>h;;(B
                    166:
                    167: $(a\times b) \bmod B^2$
                    168:
                    169: \item $B=|;;(B
                    170:
                    171: $a = qd+r$ $B$J$k(B $q$, $r$ ($0\le r < d$)
                    172:
                    173: \item $BG\@:EY=|;;(B
                    174:
                    175: $aB+b = qd+r$ $B$J$k(B $q$, $r$ ($0\le r < d$)
                    176: \end{itemize}
                    177:
                    178: $B$3$l$i$N4pK\A`:n$rMQ$$$F(B, $B<!@a$G=R$Y$k(B, $BB?G\D9@0?t$N;MB'1i;;$,<B8=(B
                    179: $B$5$l$k(B.
                    180:
                    181: \section{C $B8@8l$K$D$$$F(B}
                    182:
1.2       noro      183: $BK\9V$G$O(B, $B%"%k%4%j%:%`$*$h$S%G!<%?9=B$$N7W;;5!>e$G$N<BAuNc$r(BC $B8@8l$K$h(B
                    184: $B$j<($9>l9g$,$"$k(B. $B$3$3$G$O(B, C $B8@8l$NJ8K!$K4X$7$F(B, $B$4$/4pK\E*$J$3$H$K$D(B
                    185: $B$$$F2r@b$9$k(B. $B>\:Y$O(B, \cite{KR} $B$J$I$r;2>H$5$l$?$$(B.
1.1       noro      186:
                    187: \subsection{$BJQ?t(B}
                    188:
                    189: $BJQ?t$H$O%G!<%?$r3JG<$7$F$*$/>l=j$G$"$k(B. $B%G!<%?$N<oN`$K$O@0?t(B, $BIbF0>.?t(B
                    190: $B$r$O$8$a$H$7$F$5$^$6$^$J$b$N(B ($B7?(B) $B$,$"$k(B. $BJQ?t$r;HMQ$9$k$?$a$K$O(B, $B7?$*(B
                    191: $B$h$SL>A0$r@k8@$7$J$1$l$P$J$i$J$$(B. $BNc$($P<!$O(B, {\tt a}, {\tt b}, {\tt
                    192: xyz} $B$H$$$&L>A0$NId9f$D$-@0?t7?JQ?t(B, $B$*$h$S(B {\tt p}, {\tt q}$B$H$$$&L>A0(B
                    193: $B$NId9f$J$7@0?t7?JQ?t$N@k8@$G$"$k(B. $B@0?t7?JQ?t$N%5%$%:$,(B 32bit $B$N>l9g(B,
                    194: {\tt int} $B7?$NJQ?t$O(B $-2^{31} \le x \le 2^{31}-1$, {\tt unsigned int}
                    195: $B7?$NJQ?t$O(B$0 \le x \le 2^{32}-1$ $B$J$k@0?t(B $x$ $B$rI=8=$9$k$3$H$,$G$-$k(B.
                    196:
                    197: \begin{verbatim}
                    198: int a,b,xyz;
                    199: unsigned int p,q;
                    200: \end{verbatim}
                    201:
                    202: \subsection{$B<0(B}
                    203:
1.2       noro      204: $BJQ?t$*$h$SDj?t$KBP$9$k0lO"$N;MB'1i;;(B, $BO@M}1i;;$J$I$r$^$H$a$F0l$D$N<0(B
1.1       noro      205: $B$H$7$F5-=R$9$k$3$H$,$G$-$k(B. $B2C(B, $B8:(B, $B>h$O$=$l$>$l(B {\tt +}, {\tt -},
                    206: {\tt *} $B$GI=$9(B. {\tt /} $B$O=|;;$K$*$1$k>&(B ($B@0?tItJ,(B), {\tt \%} $B$O>jM>$r(B
                    207: $BI=$9(B. $B<0$NCf$GMQ$$$k$3$H$,$G$-$k1i;;;R$K$O(B, $BB>$K(B, {\tt <<} ($B:8%7%U%H(B),
                    208: {\tt >>} ($B1&%7%U%H(B), {\tt |} (bit $B$4$H$N(B or), {\tt \&} (bit $B$4$H$N(B
                    209: and),
                    210: \verb+^+
                    211: (bit $B$4$H$N(B exclusive or) $B$J$I$,$"$k(B. $B$^$?(B, {\tt <},
                    212: {\tt <=}, {\tt >}, {\tt >=}, {\tt ==} ($BEy$7$$(B), {\tt !=}($BEy$7$/$J$$(B)$B$J$I$b(B,
                    213: $B@5$7$1$l$P(B 1, $B$=$&$G$J$1$l$P(B 0 $B$H$$$&CM$rJV$9(B 2 $B9`1i;;;R$H$7$FMQ$$$k$3(B
                    214: $B$H$,$G$-$k(B.  $BId9f$J$7@0?t$KBP$9$k2C8:>h;;(B, $B:8%7%U%H1i;;$O(B, $B@0?t7?$N%5(B
                    215: $B%$%:$r(B $n$ bit $B$H$9$k$H$-(B, $BK!(B $2^n$ $B$G7W;;$5$l$k(B. $BNc$($P(B, $B@0?t7?$,(B
                    216: 32bit $B$N$H$-(B,
                    217:
                    218: \begin{verbatim}
                    219: unsigned int a,r;
                    220: a = 1<<31;
                    221: r = a+a;
                    222: \end{verbatim}
                    223: $B$r<B9T$9$k$H(B {\tt r} $B$O(B 0 $B$H$J$k(B.
                    224:
                    225: \subsection{$BJ8(B}
                    226:
                    227: $BJ8$O(B C $B8@8l$N<B9TC10L$G$"$k(B. $BJ8$K$O(B, $B<0$K%;%_%3%m%s(B {\tt;} $B$rIU$1$?(B
                    228: $BC1J8$NB>$K(B, $B4v$D$+$NJ8$r(B \verb+{+, \verb+}+ $B$G3g$C$?J#J8(B, {\tt if}
                    229: $BJ8(B, {\tt for} $BJ8(B, {\tt while} $BJ8(B, {\tt switch} $BJ8$J$I$N@)8f$rH<$&(B
                    230: $BJ8$J$I$,$"$k(B. $B<!$NNc$O(B, $B>.$5$J(B {\tt n} $B$KBP$7$F3,>h$r7W;;$9$kJ8$G$"$k(B.
                    231:
                    232: \begin{verbatim}
                    233: unsigned int f;
                    234: for ( f = 1; n >= 1; n-- ) f *= n;
                    235: \end{verbatim}
                    236: $B$3$3$G(B, {\tt n--} $B$O(B {\tt n = n-1}, {\tt f *= n} $B$O(B {\tt f = f*n} $B$r$=(B
                    237: $B$l$>$l0UL#$9$k(B. $B$3$NJ8$O(B, $B@0?t7?$,(B 32bit $B$N>l9g(B, {\tt n} $B$,(B 12 $B0J2<$G(B
                    238: $B$N$_@5$7$$CM$rM?$($k(B. $B$3$l$O(B, 13 $B0J>e$G$O7k2L$,(B $2^{32}$ $B0J>e$H$J$k$?$a$G(B
                    239: $B$"$j(B, $B$3$N$h$&$J>l9g$K$b@5$7$$7k2L$rF@$k$?$a$K$O(B, $B<!@a$G=R$Y$k$h$&$J(B
                    240: $BG$0UB?G\D9@0?t$NI=8=$*$h$S$=$l$KBP$9$k%"%k%4%j%:%`$,I,MW$H$J$k(B.
                    241:
                    242: \subsection{$B4X?t(B}
                    243:
                    244: C $B8@8l$K$*$$$F$O(B, $B%W%m%0%i%`$O4X?t$H$7$F5-=R$5$l$k(B. $B4X?t$O(B,$B0z?t(B ($BF~NO(B)
                    245: $B$KBP$9$kA`:n$r$$$/$D$+$NJ8$K$h$j5-=R$7(B, $BI,MW$,$"$l$P7k2L$rJV$9(B, $B$H$$$&(B
                    246: $BA`:n$r$^$H$a$?$b$N$G$"$k(B. $B@h$K=R$Y$?3,>h7W;;$r4X?t$K$9$k$H<!$N$h$&$K$J$k(B.
                    247:
                    248: \begin{verbatim}
                    249: unsigned int factorial(unsigned int n)
                    250: {
                    251:     unsigned int f;
                    252:     for ( f = 1; n >= 1; n-- ) f *= n;
                    253:     return f;
                    254: }
                    255: \end{verbatim}
                    256: $B$3$NNc$G$O(B, $BId9f$J$7@0?t(B {\tt n} $B$r<u$1<h$j(B, $B$=$N3,>h$rId9f$J$7@0?t$H$7$F(B
                    257: $BJV$9(B {\tt factorial} $B$H$$$&4X?t$,@k8@$5$l$F$$$k(B.
                    258:
                    259: \subsection{$BG[Ns(B, $B%]%$%s%?(B}
                    260:
1.2       noro      261: $BG$0UB?G\D9@0?t$O(B, $B%a%b%j>e$N==J,$JD9$5$NO"B3NN0h$H$7$FI=8=$G$-$k(B. $B$3$N$h$&$J(B
1.1       noro      262: $BNN0h$O(B, C $B8@8l$G$OG[Ns$H$7$FI=8=$5$l$k(B.
                    263:
                    264: \begin{verbatim}
                    265: unsigned int a[10];
                    266: \end{verbatim}
                    267: $B$3$l$O(B, $BD9$5(B 10 $B$NId9f$J$7@0?tG[Ns(B {\tt a} $B$r@k8@$7$F$$$k(B. $BG[Ns$N3FMW(B
                    268: $BAG$O(B, {\tt a[0]}, $\cdots$, {\tt a[9]} $B$K$h$jF@$i$l$k(B. ($BE:;z$,(B 0 $B$+$i(B
                    269: $B;O$^$k$3$H$KCm0U(B.) $B<!$N%W%m%0%i%`$O(B, $BD9$5(B 10 $B$NG[Ns$N(B {\tt i} $BHVL\$N(B
                    270: $BMWAG$K(B {\tt i} $B$rBeF~$9$k(B.
                    271:
                    272: \begin{verbatim}
                    273: unsigned int a[10];
                    274: int i;
                    275: for ( i = 0; i < 10; i++ ) a[i] = i;
                    276: \end{verbatim}
                    277: $B$3$N%W%m%0%i%`$O<!$N$h$&$K$b=q$1$k(B.
                    278:
                    279: \begin{verbatim}
                    280: unsigned int a[10];
                    281: int i;
                    282: unsigned int *p;
                    283: for ( i = 0, p = a; i < 10; i++, p++ ) *p = i;
                    284: \end{verbatim}
                    285: {\tt p} $B$O%]%$%s%?$H8F$P$l$k7?$NJQ?t$G$"$k(B. $B%]%$%s%?$O(B, $B%a%b%j$N%"%I%l%9(B
                    286: $B$rCj>]2=$7$?$b$N$G$"$k(B. $B$3$NNc$N>l9g$K$O(B, {\tt p = a} $B$K$h$j(B
                    287: $B:G=i(B {\tt p} $B$OG[Ns(B {\tt a} $B$N@hF,$r;X$7$F$$$k(B. $B$=$7$F(B, {\tt i} $B$,(B
                    288: 1 $BA}$($k$?$S$K(B, {\tt p} $B$N;X$90LCV$b(B, $BG[NsCf$G(B 1 $BMWAG$:$D@h$r;X$9$h$&$K(B
                    289: $BJQ2=$7$F$$$/(B. $B$9$J$o$A(B, {\tt p++} $B$K$h$k(B {\tt p} $B$N%"%I%l%9$H$7$F$N(B
                    290: $BJQ2=NL$O(B {\tt unsigned int *p} $B$J$k@k8@$K$h$j5,Dj$5$l$k$N$G$"$k(B.
                    291: $B$^$?(B, {\tt *p = i} $B$O(B, {\tt p} $B$N;X$9NN0h$NFbMF$r(B {\tt i} $B$H$$$&CM(B
                    292: $B$K=q$-49$($k$3$H$r0UL#$9$k(B.
                    293:
                    294: $B%]%$%s%?$rF3F~$9$kI,MW@-$K$O$5$^$6$^$J$b$N$,$"$k(B.
                    295: $B$3$3$G$O<!$N(B 3 $B$D$K$D$$$F@bL@$9$k(B.
                    296:
                    297: \begin{itemize}
                    298: \item $BF0E*$J%a%b%j3d$jEv$F(B
                    299:
                    300: $B2f!9$N1i;;BP>]$G$"$k@0?t$O(B, $B7W;;$N2aDx$G$$$/$i$G$bBg$-$JCM$H$J$C$F$$$/(B
                    301: $B2DG=@-$,$"$k(B. $B$=$N$?$a(B, $BNc$($P2C;;$r9T$&4X?t$O(B, $BG$0U$NBg$-$5$N0z?t$KBP(B
                    302: $B$7$F(B, $B7k2L$rJ];}$9$k$@$1$NNN0h$r3NJ]$7$F$=$3$K7k2L$r=q$/$H$$$&7A$,<+A3(B
                    303: $B$G$"$k(B. $B$3$N$H$-(B, $B5-213d$jEv$F%k!<%A%s$,JV$9CM$O(B, $B%a%b%jCf$N$"$kNN0h$N(B
                    304: $B@hF,%"%I%l%9$G$"$j(B, $B<u$1<h$kB&$OI,A3E*$K%]%$%s%?$H$7$F07$&I,MW$,$"$k(B.
                    305:
                    306: \item $BLZ9=B$$NI=8=(B
                    307:
                    308: $BB?9`<0$O(B, $B8e$K=R$Y$k$h$&$KLZ9=B$$K$h$jI=8=$5$l$k(B. $B$=$NL>$NDL$j(B, $BLZ$O:,(B
                    309: $B$+$i;^$o$+$l$7$J$,$i$D$J$,$k%G!<%?$rI=8=$9$k(B. $B$3$l$O(B, $B%a%b%j>e$G$O(B, $BB>(B
                    310: $B$NNN0h$r;X$9%]%$%s%?$rJ];}$9$k%G!<%?9=B$$K$h$jI=8=$9$k$N$,<+A3$G$"$k(B.
                    311:
                    312: \item $B4X?t8F$S=P$7B&$NJQ?t$N=q$-49$((B
                    313:
                    314: C $B8@8l$G$O(B, $B4X?t8F$S=P$7$OCM$K$h$k8F$S=P$7(B (call by value) $B$H8F$P$l$k(B
                    315: $BJ}K!$G9T$o$l$k(B. $B$9$J$o$A(B, $B8F$S=P$7B&$NJQ?t$r(B, $B4X?t8F$S=P$7$N0z?t$H$7$F(B
                    316: $BEO$7$F$b(B, $B8F$S=P$5$l$?4X?t$K$O$=$NCM$N$_$,EO$5$l$k$?$a(B, $B8F$S=P$5$l$?4X(B
                    317: $B?t$O(B, $B$=$NJQ?t$NCf?H$r=q$-49$($k$3$H$,$G$-$J$$(B. $B$3$N$h$&$J>l9g$K(B,
                    318: $B0z?t$H$7$FJQ?t$r;X$9%]%$%s%?$rM?$($k$3$H$K$h$j(B, $B$=$NJQ?t$NCf?H$r=q$-49$($k(B
                    319: $B$3$H$,2DG=$K$J$k(B. $BJQ?t(B {\tt a} $B$KBP$7(B, {\tt a} $B$r;X$9%]%$%s%?$NCM$O(B
                    320: {\tt \&a} $B$GF@$i$l$k(B. {\tt \&} $B$H(B {\tt *} $B$O8_$$$K5U$NA`:n$H$J$C$F$$$k(B.
                    321: \end{itemize}
                    322:
                    323: \subsection{$B9=B$BN(B}
                    324:
                    325: $BNc$($PB?G\D9@0?t$r7W;;5!>e$GI=8=$9$k>l9g(B, $B3F7e$rI=$9@0?tG[Ns$*$h$SId9f(B, $B7e?t(B
                    326: $B$N>pJs$O:GDc8BI,MW$G$"$k(B. $B$3$l$i$O$=$l$>$l8DJL$NJQ?t$K3d$jEv$F$k$3$H$b2DG=(B
                    327: $B$G$"$k$,(B, $B0l$D$NBP>]$,J#?t$NJQ?t$KJL$l$FJ];}$5$l$k$N$O(B, $B$=$N<h07$$$r(B
                    328: $BJ#;($K$7(B, $B$^$?%W%m%0%i%`$N2DFI@-$NE@$+$i$b9%$^$7$/$J$$(B. $B$3$N$h$&$J(B
                    329: $B>l9g$K(B, $BJ#?t$NMWAG$r0l$D$K$^$H$a$?9=B$BN$rMQ$$$k$3$H$,$G$-$k(B.
                    330: $BNc$($P(B, $B@0?t$O<!$N$h$&$J9=B$BN$GI=$9$3$H$,$G$-$k(B.
                    331:
                    332: \begin{verbatim}
                    333: struct Integer {
                    334:   int n; /* $B7e?t(B = |n|; n $B$NId9f$,$3$N@0?t$NId9f(B */
                    335:   unsigned int *digits; /* $B3F7e$rI=$9G[Ns$X$N%]%$%s%?(B */
                    336: };
                    337: \end{verbatim}
                    338: $B$b$A$m$s(B, $B%]%$%s%?(B {\tt digits} $B$OD9$5(B {\tt |n|} $B0J>e$NId9f$J$7(B
                    339: $B@0?tG[Ns$r;X$7$F$$$J$1$l$P$J$i$J$$(B.
                    340: