MC6800のプログラミングテクニック(24) 除算の再検討 整数除算
いままで開設した整数除算では、被除数Aを1bitずつ左シフトしつつ除数と比較していた。以下の8bit比較法除算を例に考えてみよう。
被除数 AccAの上位ビットを、ワーク領域 AccBに 1ビットずつシフトしている。シフトして除数を引いて、引けたら商として1を立てる。
この方法は一見すると無駄があるようにも思える。 被除数のMSBの位置が除数のMSBと等しくなるまでは 被除数<除数であり減算する意味がない。
_div8x8: tsx tba ldab 2,x stab @tmp1 ; divisor ldx #8 clrb loop: asla ; 2 1 rolb ; 2 1 cmpb @tmp1 ; 3 2 bcs next ; 4 2 subb @tmp1 ; 3 2 inca next: dex ; 4 1 bne loop ; 4 2 tab clra rts
しかしシフト演算のコストが大きい
現代的なCPUなら、レジスタのうち一番左にある1のbit位置を調べる命令（clz:Count Leading Zero）があり、除数と被除数の最左bitを調べてその差だけシフトするのは簡単だ。
（そもそも今どきのCPUには除算命令があるだろ、と突っ込まれそうではある）
しかし、MC6800には clzのような便利な命令はないので、1bitずつシフトして調べる必要がある、遅いのである。
除数の左シフト
筆算で除算を行うときは、除数は左詰めで書くのが普通だ。
昔のMC6800の除算ルーチンも先頭位置を合わせるコードになっている。
MC6800出荷の翌年の1975年に出版された「M6800 Microprocessor Applications Manual 1975」の除算ルーチン（P.2-23）も、GAME言語（ASCII誌1978年7月号）・GAME68コンパイラの除算ルーチンもそうなっている。
除数が小さいときに左シフトが多く発生し遅くなるので、後で開発された6800用プログラムはこの方法を使っていない。
1977年に出版された “6800 Programming for Logic Design by Adam Osborne” の除算ルーチン（P.7-16）は冒頭のプログラムのように左シフトし、キャリー反転を使っている。
その和訳「マイクロコンピュータプログラミング (6800編) 論理設計のための6800プログラミング」は1978年7月に出版されている。
こちらが速いことは昔から知られていたのだと思う。
多バイト除算の場合はバイトシフトできそう
32bit除算の場合、無駄な左シフトが多くなる。上位bitが0なら、バイト単位でシフトして速くなるかもしれない。
高速化のためチェックもバイト単位とし、0-3バイト目が0かどうかを見ることにしよう。
被除数は上からみて0であるバイトがあれば、その分だけ左シフトして良い。
除数の場合は、除数が最上位バイトまで入っていれば、被除数を24bit左シフトして良い。最上位バイトが0でも2バイト目が0でなければ16bitシフトできる。
両方見るともっとシフト量は増やせるが、手間がかかりすぎるようにも思われる。速くなるだろうか？