割り算

目次

概要

Z80 基本

Z80 引き放し法変数共用さらに引き放し法

6502基本

変数共用さらに引き放し法

速度判定


さらに引き放し法

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の特性に合わせてアルゴリズムが変わっています。


まず、初期化処理の後に、最初の1回目の計算だけをやってしまっています。


最初の1回目も、計算としては他とそれほど変わりません。

PLUS_AFTER から入った処理とほぼ同一…なのですが、INC L が不要だったり、PLUS_AFTER から入ると無駄にジャンプが入ったりします。


それを、「特別扱い」することで全体を高速化しているのです。


その分、繰り返し回数も1回減っていて、本来 B に 16 を入れるべきところ、15が入っています。


1bit の計算では、ADD HL,HL で HL を左シフトしては、あふれたビットを A に下から入れてローテートします。

これで、「HL を上の桁から順次取り出し」しているのです。


A から除数を引いたり足したりして、引き放し法の計算を行います。

結果ビットを立てるべき時は、 L をインクリメントします。

先ほど左シフトしているので、再下位ビットは必ず 0 になっているはずで、他のビットに影響を与えません。


前処理(上のプログラムで最初の空行まで)で、32クロック。


最初の一回の計算は、例ではマイナスになり、MINUS_BEFORE に飛びます。

その次の ADD HL,HL までが「最初の一回」の計算。47クロック。


1桁の計算は、プラスの時は 49クロック、マイナスの時は 44 クロック。

それぞれ、5回、10回あります。

(マイナスは全部で 11回ですが、最初の1回もマイナスです)


連続した計算の符号が変わる場合、ジャンプのために +5クロック。8回あります。


最後だけ、終了処理が入ります。

まず、ループのジャンプが行われないため、通常より -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 に剰余


プログラムにバグがありますね。SBC の動作を少し勘違いしていました。
近いうちに修正したいと思いますが、すでにより高速なプログラムが投稿されているため、速度勝負に影響はありません。


前処理の「左詰め」では、最上位ビットを見られるために、Z80 で生じる「無駄な」処理が無くなっています。

(Z80 では、追い出されてキャリーに入るまで分からないため、行き過ぎて戻る、2回の無駄なローテート動作が生じてしまう)


そのほかはほぼ同じ。ただし、16bit の扱いが苦手な 6502 では、8bit の演算を繰り返して 16bit にしています。


前処理 22クロック


左詰め処理は、1bit 左詰めにつき、7 クロック。

その後、次への準備などで 4 クロック。


Z80 と異なり、無駄なローテートは生じず、4bit 詰めて終わります。

7*4 +4 = 32 クロック。


1桁分の計算は、結果がプラスの時、 50 クロック(最後だけ +5)、マイナスの時、 45 クロック(最後だけ +5)。


ただし、結果が同じ符号で連続しなかった時は、処理の切り替えに +1 クロック。


Z80 と同じように計算すると、次のようになります。


22 + 32 + 50*8 + 45*5 +5 +8 = 692


総計 692クロック


次ページ: 変数共用


前ページ 1 2 3 4 次ページ

(ページ作成 2014-08-20)
(最終更新 2015-04-28)
第2版 …他の版 初版

前記事:コマンド入力     戻る     次記事:10進表示
トップページへ

-- share --

7000

-- follow --




- Reverse Link -