掛け算
目次
計算手順逆転
2014.8.6 未明追記
これを書いている時点で、MSX とファミコンでは、２割の速度差で MSX が勝っています。
掛け算はレジスタを多数駆使しなくてはならず、6502 にはなかなか難敵の様子…
特に、筆算の１段を処理するごとに、16bit+16bit の加算を行わなくてはならないのが辛いです。
そこで、この計算を「16bit + 8bit + 繰上り処理」に単純化したのが次のプログラム
LDA #101 ; 2
STA >3 ; 3
LDA #100 ; 2
STA >4 ; 3
LDA #0 ;2
STA >0 ; 3
SEC ; 2
BEQ START ; 3 / 2
ADD:
BEQ END ; 3 / 2
CLC ; 2
ADC >3 ; 3
BCC LOOP ; 3 / 2
INC >0 ; 5
LOOP:
ASL A ; 2
ROL >0 ; 5
START:
ROL >4 ; 5
BCS ADD ; 3 / 2
JMP LOOP ; 3
END:
LSR >0 ; 5
ROR A ; 2
STA >1 ; 3
２進数の掛け算は、筆算の方法で行われます…というのはよくある説明。
Z80 のプログラムでは、乗数を左シフトしながら、結果に足し合わせています。
しかし、ここでは乗数は固定したまま、結果を左シフトしていく方法にしてみました。
乗数をシフトすると、16bit + 16bit の足し算が生じてしまいますが、乗数をシフトしなければ 16bit + 8bit で済みます。上位バイトは繰上り処理のみでゼロページに対して直接インクリメント命令が使えるので、A レジスタを使いまわす必要がなくなります。
そこで、A レジスタは常に結果の下位 8bit を保持するようにしました。それ以外は、基本のプログラムと同じメモリの使い方をしていますが、乗数は 8bit なので、16bit 分用意されたメモリの上位バイトは初期化すらしていません。
基本の方法は、下のビットから筆算で掛け算した形になっていました。しかし、ここでの方法は、上のビットから計算しています。
そのため、必ず 8bit 全てを計算しなくては、桁が合わなくなります。普通なら８回繰り返すのにカウンタ変数を持つのですが、この方法ではメインループ中に、変数のデクリメントと条件分岐、という大きなオーバーヘッドが生じます。
ここでは、乗数の外側（9bit目）に、1 を付けることで、問題を回避しています。この１は、はじめてシフトを行うときだけ、右側から入りますが、以降のシフトでは 0 が入ります。
そして、左シフトで9bit 目の 1 が追い出され、8bitの内容が 0 になった時が計算の終了するときです。
1が追い出されたときですから、その時には必ず加算ルーチンに分岐します。加算ルーチンの冒頭で終了条件をチェックすれば、メインループで毎回チェックを行う必要はなくなります。
ただ、この方法もデメリットがあり、終了が９回目のループ冒頭になってしまいます。基本プログラムではループは７回なのに、２回も増えるのです。これも重大なデメリットです。
クロック数を計算してみましょう。前処理と後処理は、それぞれ 20クロックと 10 クロック。終了判定に、９回目のループとして11クロック必要です。
ループ中は、加算無しが 17クロック。加算有りはさらに細かくわかれ、繰上りなしが 25クロック、ありが 29クロック。
例題では、加算無しが５回、繰上りなしが２回、繰上りありが１回生じます。
20 + 10 + 11 + (17*5 + 25*2 +29*1) = 205 クロック。
デメリット部分が大きく、大改造した割には 9 クロックしか速くなっていません。
ループ展開
2014.8.6 未明追記
…そこで、お約束のループ展開です。
ループ部分以外は先に書いた「計算手順逆転」と同じなので、LOOP から END の間だけを示します。
LOOP:
ASL A ; 2
ROL >0 ; 5
START:
ROL >4 ; 5
BCS ADD ; 3 / 2
ASL A ; 2
ROL >0 ; 5
ROL >4 ; 5
BCS ADD ; 3 / 2
ASL A ; 2
ROL >0 ; 5
ROL >4 ; 5
BCS ADD ; 3 / 2
JMP LOOP ; 3
…うん。わかりやすいループ展開。実は、先のプログラムではループ展開しやすいように、メインループをコンパクトになるようにしていました。
展開は３回だけです。もしこれ以上の処理が必要になった場合は、JMP でLOOP に戻ります。
そして、今回の例題では、これで十分です。乗数の 100 は、2進数では 0110 0100 。任意のビットから右に進み、必ず 3bit 以内に 1 が現れます。
1 が来た場合、BCS ADD で、LOOP の上にある ADD に戻り、再度 LOOP の先頭から実行が始まります。つまり、最後の JMP LOOP には到達しません。
先の計算で、メインループは加算無しの際に 17クロックでした。これは、加算無しの際に JMP LOOP が実行されるためで、ループ展開で加算無しの際は 14クロックに減少します。３クロックの高速化です。
加算無しは５回あるので、15クロック高速化されて、190 クロックになります。やっと 200クロックを切りました。