合同算術
割り算の余りに注目した計算(合同算術)と、決まったビット数で計算するCPUとの関係について説明します。
<注意>
このページでは、数式を表示するためにMathJaxを使用しています。ブラウザの設定でスクリプト実行をブロックしている場合、ページ内の数式が正しく表示されません。
余りと合同
整数\(\ a\ \)を正の整数\(\ m\ \)で割ると、商\(\ q\ \)と余り\(\ r\ \)が決まります。
\[ a = qm + r \qquad (0 \le r < m) \]この余り\(\ r\ \)を\(\ a \bmod m\ \)と書きます。
余りは必ず0以上\(\ m\ \)未満になるように決めます。たとえば\(\ -3 \bmod 8 = 5\ \)です(\(\ -3 = (-1)\times 8 + 5\ \))。
定義 (合同)
2つの整数\(\ a,\ b\ \)を\(\ m\ \)で割った余りが等しいとき、\(\ a\ \)と\(\ b\ \)は\(\ m\ \)を法として合同であると言い、\(\ a \equiv b \pmod m\ \)と書く。
これは、\(\ a-b\ \)が\(\ m\ \)で割り切れることと同じである。
8を法とすると、すべての整数は余りによって0～7の8つの組に分かれます。
数直線を8ずつ巻き取って円にすると、同じ組の数は円の同じ位置に重なります。7の次は0に戻ります。
合同な数どうしの計算
合同な数は、足し算・引き算・掛け算の中で、互いに入れ替えても余りが変わりません。
定理
\[ a+b \equiv a'+b',\quad a-b \equiv a'-b',\quad ab \equiv a'b' \pmod m \]
\(\ a \equiv a',\ b \equiv b' \pmod m\ \)ならば、
つまり、途中で何度余りをとっても、最後に余りをとっても、結果の余りは同じです。
大きな数の計算の最後の数桁だけが必要なときは、途中の値を小さく保ったまま計算できます。
割り算だけは、このままでは成り立ちません。割り算の扱いは逆元で説明します。
CPUの計算は合同算術
8ビットのレジスタは0～255の256通りの値しか持てないので、計算の結果が256以上になると、上の桁があふれて捨てられます。
これは、計算の結果を256で割った余りだけを残していることと同じです。
定理
\(\ n\ \)ビットのレジスタでの足し算・引き算・掛け算(結果の下位\(\ n\ \)ビットを残すもの)の結果は、本当の結果と\(\ 2^n\ \)を法として合同である。
たとえば8ビットで\(\ 200 + 100\ \)を計算すると、結果は\(\ 300 \bmod 256 = 44\ \)になり、あふれた分はキャリーフラグに出ます。
2の補数がうまく働く理由
\(\ 2^n\ \)を法とすると、\(\ -x\ \)と\(\ 2^n - x\ \)は合同です。
8ビットの2の補数で\(\ -1\ \)を$FF(255)、\(\ -128\ \)を$80(128)で表すのは、負の数を256を法として合同な0～255の値に置き換えていることにあたります。
合同な数どうしは、足し算・引き算・掛け算の結果も合同です。
そのため、値を符号付きと見るか符号なしと見るかに関係なく、同じADC命令・SBC命令で計算でき、結果の下位8ビットはどちらの見方でも正しくなります。
違うのは、結果があふれたかどうかの判定だけです(符号なしはキャリーフラグ、符号付きはオーバーフローフラグで判定します)。
2のべき乗で割る
法が2のべき乗\(\ 2^k\ \)のとき、余りは下位\(\ k\ \)ビット、商はそれより上のビットです。
\[ a \bmod 2^k = a\ \mathrm{AND}\ (2^k - 1), \qquad \left\lfloor \frac{a}{2^k} \right\rfloor = a \gg k \]割り算の命令がなくても、AND命令とシフト命令だけで済みます。
負の数(2の補数)でも、ANDで取り出した下位ビットは0以上\(\ 2^k\ \)未満の正しい余りになります。
商のほうは、符号を保ったまま右にシフトする(算術右シフト)と、小さいほうに丸めた商(\(\ \lfloor a/2^k \rfloor\ \))になります(固定小数点数の「丸め」)。
法が2のべき乗でないときは割り算が必要なので、表の大きさや周期を2のべき乗に揃えておくと、計算がずっと軽くなります。
角度の差
三角関数の256方位では、角度は256を法とした値です。
角度に何を足しても、8ビットに収めるだけで自動的に1周して戻ってきます。
2つの角度\(\ a,\ b\ \)の差を求めるときは、\(\ d = (b - a) \bmod 256\ \)を計算し、その値を符号付き8ビット(−128～127)として読みます。
\(\ a = 250,\ b = 10\ \)のとき、\(\ d = (10 - 250) \bmod 256 = 16\ \)です。
ふつうに引き算すると−240になりますが、これは反対向きに大回りした差です。
256を法とした差を符号付きで読むと、短いほうの回り方(+16)が得られます。
敵が自機のほうへ向きを変えるとき、どちら向きに回ればよいかは、この差の符号で決められます。
リングバッファ
大きさ\(\ N\ \)の表を、末尾の次は先頭に戻る輪として使うものをリングバッファと言います。
書き込む位置は、\(\ i \leftarrow (i + 1) \bmod N\ \)で進めます。
\(\ N\ \)を2のべき乗にしておけば、\(\ (i + 1)\ \mathrm{AND}\ (N - 1)\ \)で済みます。
さらに\(\ N = 256\ \)なら、8ビットのレジスタで1を足すだけで、自動的に0に戻ります。
転送の予約(VRAM転送のキュー)、音のデータ、入力の記録などに使われます。
一定の間隔で巡る
\(\ x \leftarrow (x + c) \bmod m\ \)を繰り返すと、\(\ x\ \)は\(\ c\ \)ずつ飛びながら0～\(\ m-1\ \)を巡ります。
定理
\(\ c\ \)と\(\ m\ \)の最大公約数が1(互いに素)のとき、\(\ x \leftarrow (x + c) \bmod m\ \)は、\(\ m\ \)回で0～\(\ m-1\ \)のすべての値をちょうど1回ずつ通る。
たとえば\(\ m = 256\ \)なら、\(\ c\ \)が奇数であれば256通りすべてを通ります。
表の要素を、決まった順番ではなく飛び飛びに、ただし1つも漏らさずに処理したいときに使えます。
\(\ c\ \)が偶数だと、通らない値が出てきます(たとえば\(\ c = 2\ \)なら偶数だけを通ります)。
この性質は、確率と乱数の線形合同法の周期を考えるときにも使います。
逆元
\(\ a \times b \equiv 1 \pmod m\ \)となる\(\ b\ \)を、\(\ m\ \)を法とした\(\ a\ \)の逆元と言い、\(\ a^{-1}\ \)と書きます。
逆元を掛けることが、\(\ m\ \)を法とした世界での「\(\ a\ \)で割る」にあたります。
定理
\(\ a\ \)の逆元が存在するのは、\(\ a\ \)と\(\ m\ \)が互いに素のときだけである。
\(\ m = 256\ \)なら、奇数には逆元があり、偶数にはありません。
たとえば\(\ 3 \times 171 = 513 = 2 \times 256 + 1\ \)なので、256を法とした3の逆元は171です。
同じように、7の逆元は183です。
この性質を使うと、3で割り切れることが分かっている数は、171を掛けて下位8ビットを取るだけで3で割れます。
たとえば\(\ 105 \times 171 = 17955\ \)の下位8ビットは35で、\(\ 105 \div 3 = 35\ \)と一致します。
割り切れない数に使うと意味のない値になるので、使える場面は限られますが、割り算を掛け算に置き換える考え方の一例です。
逆元は、ユークリッドの互除法を少し変えた方法(拡張ユークリッドの互除法)で求められます。