割り算
目次
Z80 引き放し法
1桁ごとの、計算後の処理を軽減したものです。
LD L,0 ; 7 (8)
EXX ; 4 (5)
LD HL,12345 ; 10 (11)
LD A,10 ; 7 (8)
LD B,7 ; 7 (8)
; 前処理。割る数 A を左詰め。
PRE:
INC B ; 4 (5)
RLCA ; 4 (5)
JR NC,PRE ; 12 / 7 (13 / 8)
RRCA ; 4 (5)
LD D,A ; 4 (5)
LD E,0 ; 7 (8)
AND A ; 4 (5) ; キャリーフラグを消す
; 筆算の引き放し法で割り算
PLUS:
SBC HL,DE ; 15 (17)
JR C,MINUS_AFTER ; 12 / 7 (13 / 8)
PLUS_AFTER:
EXX ; 4 (5)
ADD HL,HL ; 11 (12)
INC L ; 4 (5)
EXX ; 4 (5)
SRL D ; 8 (10)
RR E ; 8 (10)
DJNZ PLUS ; 13 / 8 (14 / 9)
LD A,L ; 4 (5)
JP END ; 10 (11)
MINUS:
ADD HL,DE ; 11 (12)
JR NC,PLUS_AFTER ; 12 / 7 (13 / 8)
MINUS_AFTER:
EXX ; 4 (5)
ADD HL,HL ; 11 (12)
EXX ; 4 (5)
SRL D ; 8 (10)
RR E ; 8 (10)
DJNZ MINUS ; 13 / 8 (14 / 9)
LD A,L ; 4 (5)
ADD A,E ; 4 (5)
END:
EXX ; 4 (5)
; HL に商、A に余り
基本のプログラムでは、1桁の演算後、結果がマイナスの時は元に戻し、次の桁に進んでいました。
次の桁では、除数を1ビット右シフト…つまり 1/2 してから引いています。
数式で書くと、HL = HL - DE の後、 HL<0 ならば、 HL = HL + DE - DE/2 します。
DE が2回出てくるのでまとめると HL = HL + DE/2 と同じです。
そして、DE/2 というのは「次の桁」の処理であることを意味します。
つまり、結果がマイナスなら次の桁は「引き算」ではなく「足し算」をするようにしてやれば、処理が軽減できます。
この計算方法を「引き放し法」と呼びます。
（読みは「ひきはなし」ですが、意味としては「ひきっぱなし」です。引いた後元に戻さないため）
高速なのですが、プラスの場合とマイナスの場合で類似処理が２つになるため、プログラムは長くなっています。
１桁分の計算は、結果がプラスの時、 86 クロック(最後だけ +11)、マイナスの時、 76 クロック(最後だけ + 5)。
ただし、連続した途中結果の符号が異なるとき、+5クロック。
ループ内の計算では「連続した途中結果の符号が異なる」のは、8回あります。
また、最後がマイナスで終わった際、「剰余」の補正に5クロックの追加時間が必要になります。
そのほかの条件は、基本と同じです。
40 + 138 + 86*8 + 76*5 +5*8 +5 +5 = 1296
総計 1296クロックです。
変数共用
2014.9.1 追記
6502 で先に投稿された「変数共用」を、Z80 に移植したものが投稿されました。
LD HL, 12345 ; 10 (11)
LD C, 10 ; 7 (8)
LD B, 16 ; 7 (8)
XOR A ; 4 (5)
LOOP:
ADD HL, HL ; 11 (12)
RLA ; 4 (5)
CP C ; 4 (5)
JR C, SHIFT ; 12 / 7 (13 / 8)
SUB C ; 4 (5)
INC L ; 4 (5)
SHIFT:
DJNZ LOOP ; 13 / 8 (14 / 9)
移植とはいえ、処理は Z80 で速くなるように若干順序を変えています。しかし、基本的には同じことをしています。
HL と A で 24bit のローテートを行い、C を除数として A と演算しています。
投稿プログラムでは、ここまでのプログラムに合わせて A に除数を設定したうえで C にコピーしてくださっていました。しかし、レジスタの使い方に制約は設けていないので、ここでは最初から C に除数を入れています。
前処理に 32 クロック。
１桁の計算は、結果がプラスだと54クロック、マイナスだと 49クロック。最後は5クロック速くなります。
16桁を処理しますが、マイナスが 11 回、プラスが 5回です。
32 + 49*11 + 54*5 -5 = 836
総計 836クロックです。