割り算
目次
変数共用
2014.8.23 午前追記
掛け算で変数を共用してシフト動作を減らしたように、割り算でも変数共用したプログラムが投稿されました。
LDA #>12345 ;2
ASL A ;2
STA >0 ;3
LDA #<12345 ;2
ROL A ;2
STA >1 ;3
LDA #10 ;2
STA >2 ;3
LDA #0 ;2
LDX #16 ;2
LOOP:
ROL A ;2
CMP >2 ;3
BCC SHIFT ;3/2
SBC >2 ;3
SHIFT:
ROL >0 ;5
ROL >1 ;5
DEX ;2
BNE LOOP ;3/2
掛け算と同じように、ローテートなどを整理すれば高速化できるだろう、とはおもいつつ、自分ではうまく処理できませんでした。
掛け算では乗数の 1bit だけが重要だったので、16bit で同居できたのですが、除算では除数 8bit 全てが重要なので、16bit ではどうしようもなく…
…16bit でできないなら、24bit にすればよかったのですね。上記プログラムではそのように処理しています。>0 >1 と A を3つつなげて 24bit 。1桁ごとの処理対象は、つねに A の8bit のみです。
と同時に、A が「引けた」際には、>0 に 1 が入ります。これが商となります。最終的には、商は被除数を置き変える形で >0 >1 に入ります。
16bit 分、16回ループすると処理が終了します。
前処理に 23クロック。
1桁の計算は、結果がプラスだと 25 クロック。マイナスだと 23クロック。最後は1クロック速くなります。
16ビット処理しているので、結果がマイナスの時が増え、11回あります。(プラスは変わらず5回)
23 + 23*11 + 25*5 -1 = 400
総計400クロックです。
さらに引き放し法
2014.9.1 追記
変数共用プログラムに、さらに引き放し法を加えたものが投稿されました。
出来るだろう、とは思ってましたが、ここしばらく僕が忙しく (^^; 実際作っていただけるのはありがたいです。
LDA #>12345 ;2
ASL A ;2
STA >0 ;3
LDA #<12345 ;2
ROL A ;2
STA >1 ;3
LDX #10 ;2
DEX ;2
STX >2 ;3
LDA #0 ;2
LDX #16 ;2
PLUS:
ROL A ;2
SBC >2 ;3
BCC MINUS_AFTER ;3/2
PLUS_AFTER:
ROL >0 ;5
ROL >1 ;5
DEX ;2
BNE PLUS ;3/2
BEQ END ;3
MINUS:
ROL A ;2
ADC >2 ;3
BCS PLUS_AFTER ;3/2
MINUS_AFTER:
ROL >0 ;5
ROL >1 ;5
DEX ;2
BNE MINUS ;3/2
SEC ;2
ADC >2 ;3
END:
除数である 10 は、あらかじめ1減算して 9 として格納されています。
6502 では加算・減算ともキャリーフラグを一緒に扱うものしかないのですが、プログラム上は必ず、キャリーフラグが効いて 10 として扱われるようになっています。
前処理 25クロック
1桁の処理は、22クロックで、16桁処理します。
結果が同じ符号で連続しなかった時は、処理の切り替えに +1 クロック。8回あるので +8 クロック。
16桁の処理後、最後がプラスで終われば、 +2 クロックです。
最後がマイナスの場合、剰余の補正処理があるため、 +4 クロックになります。
例題では最後はマイナス。
25 +22*16 +8 +4 = 389
総計、389クロックです。
…プログラムが大きくなった割には、わずか 11クロックの高速化。
ループ部分が高速化された分、前処理と後処理が少し増えたので打ち消してしまっています。ちょっと残念。
速度判定
2015.4.28時点の結果です。
6502 は 389 クロック。周波数を考慮して倍にすると、MSX での 778クロック相当の実時間になります。
Z80 は 804クロックなので、差は26クロック。ファミコンが 3%高速です。
掛け算は Z80 の方が速かったし、レジスタだけで済むような算術計算は Z80 の方が速いかな、と思っていたのでちょっと意外な結果。
割り算は比較的「複雑なアルゴリズム」になるので、命令読み込みが遅い(メモリアクセスが遅い)Z80に不利だったかもしれません。
次の例題は…10進表示