割り算
目次
さらに引き放し法
2015.4.28 追記
昨年11月には投稿されていたのですが、僕が忙しくて本文に追記できていませんでした。
先に6502で投稿されていた、変数共用・引き放し法による計算の、Z80版です。
LD HL,12345 ; 10 (11)
LD C,10 ; 7 (8)
LD B,15 ; 7 (8)
XOR A ; 4 (5)
ADD HL,HL ; 11 (12)
RLA ; 4 (5)
SUB C ; 4 (5)
JR C,MINUS_BEFORE ; 12 / 7 (13 / 8)
ADD HL,HL ; 11 (12)
INC L ; 4 (5)
PLUS:
RLA ; 4 (5)
SUB C ; 4 (5)
JR C,MINUS_AFTER ; 12 / 7 (13 / 8)
PLUS_AFTER:
ADD HL,HL ; 11 (12)
INC L ; 4 (5)
DJNZ PLUS ; 13 / 8 (14 / 9)
JP END ; 10 (11)
MINUS_BEFORE:
ADD HL,HL ; 11 (12)
MINUS:
RLA ; 4 (5)
ADD A,C ; 4 (5)
JR C,PLUS_AFTER ; 12 / 7 (13 / 8)
MINUS_AFTER:
ADD HL,HL ; 11 (12)
DJNZ MINUS ; 13 / 8 (14 / 9)
ADD A,C ; 4 (5)
END:
移植と言っても、Z80の特性に合わせてアルゴリズムが変わっています。
まず、初期化処理の後に、最初の１回目の計算だけをやってしまっています。
最初の１回目も、計算としては他とそれほど変わりません。
PLUS_AFTER から入った処理とほぼ同一…なのですが、INC L が不要だったり、PLUS_AFTER から入ると無駄にジャンプが入ったりします。
それを、「特別扱い」することで全体を高速化しているのです。
その分、繰り返し回数も１回減っていて、本来 B に 16 を入れるべきところ、15が入っています。
1bit の計算では、ADD HL,HL で HL を左シフトしては、あふれたビットを A に下から入れてローテートします。
これで、「HL を上の桁から順次取り出し」しているのです。
A から除数を引いたり足したりして、引き放し法の計算を行います。
結果ビットを立てるべき時は、 L をインクリメントします。
先ほど左シフトしているので、再下位ビットは必ず 0 になっているはずで、他のビットに影響を与えません。
前処理（上のプログラムで最初の空行まで）で、32クロック。
最初の一回の計算は、例ではマイナスになり、MINUS_BEFORE に飛びます。
その次の ADD HL,HL までが「最初の一回」の計算。47クロック。
１桁の計算は、プラスの時は 49クロック、マイナスの時は 44 クロック。
それぞれ、5回、10回あります。
（マイナスは全部で 11回ですが、最初の１回もマイナスです）
連続した計算の符号が変わる場合、ジャンプのために +5クロック。８回あります。
最後だけ、終了処理が入ります。
まず、ループのジャンプが行われないため、通常より -5クロック。
そして、最後の計算がマイナスの時だけ、「あまり」の補正処理で +5クロック。
例の場合はマイナスです。
以上をまとめると、以下のようになります。
32+47 + 49*5 + 44*10 + 5*8 -5 + 5 = 804
総計 804クロックです。
6502基本
作るのが面倒なので、6502 は「基本」として引き放し法を示します (^^;
変数などは次のようになっています。
>0 >1 被除数
>2 >3 除数
>4 >5 商
X ループカウンタ
LDA #>12345 ; 2
STA >0 ; 3
LDA #<12345 ; 2
STA >1 ; 3
LDA #0 ; 2
STA >2 ; 3
STA >4 ; 3
LDX #7 ; 2
LDA #10 ; 2
PRE:
INX ; 2
ASL A ; 2
BPL PRE ; 3 / 2
STA >3 ; 3
CLC ; 2
PLUS:
LDA >0 ; 3
SBC >2 ; 3
STA >0 ; 3
LDA >1 ; 3
SBC >3 ; 3
STA >1 ; 3
BMI MINUS_AFTER ; 3 / 2
PLUS_AFTER:
ASL >4 ; 5
ROL >5 ; 5
INC >4 ; 5
LSR >3 ; 5
ROR >2 ; 5
DEX ; 2
BNE PLUS ; 3 / 2
LDA >0 ; 3
BCC END ; 3 / 2
MINUS:
LDA >0 ; 3
ADC >2 ; 3
STA >0 ; 3
LDA >1 ; 3
ADC >3 ; 3
STA >1 ; 3
BPL PLUS_AFTER ; 3 / 2
MINUS_AFTER:
ASL >4 ; 5
ROL >5 ; 5
LSR >3 ; 5
ROR >2 ; 5
DEX ; 2
BNE MINUS ; 3 / 2
LDA >0 ; 3
ADC >2 ; 3
END:
; >4 >5 に商、A に剰余
近いうちに修正したいと思いますが、すでにより高速なプログラムが投稿されているため、速度勝負に影響はありません。
前処理の「左詰め」では、最上位ビットを見られるために、Z80 で生じる「無駄な」処理が無くなっています。
（Z80 では、追い出されてキャリーに入るまで分からないため、行き過ぎて戻る、2回の無駄なローテート動作が生じてしまう）
そのほかはほぼ同じ。ただし、16bit の扱いが苦手な 6502 では、8bit の演算を繰り返して 16bit にしています。
前処理 22クロック
左詰め処理は、1bit 左詰めにつき、7 クロック。
その後、次への準備などで 4 クロック。
Z80 と異なり、無駄なローテートは生じず、4bit 詰めて終わります。
7*4 +4 = 32 クロック。
１桁分の計算は、結果がプラスの時、 50 クロック(最後だけ +5)、マイナスの時、 45 クロック(最後だけ +5)。
ただし、結果が同じ符号で連続しなかった時は、処理の切り替えに +1 クロック。
Z80 と同じように計算すると、次のようになります。
22 + 32 + 50*8 + 45*5 +5 +8 = 692
総計 692クロック