掛け算

目次

概要

Z80基本

構造整理HL活用参考記録変数共用

6502基本

結果のレジスタ持ち計算手順逆転ループ展開変数共用分岐改良最初の処理を展開

速度比較


変数共用

2014.8.7 午前追記

なんて鮮やか!

投稿されたプログラムを見た時、改良のされ方が鮮やかすぎて、理解できませんでした。

しかし、丹念に動作を追って理解すると、非常に美しいプログラムでした。


	LDA #100 ; 2
	STA >0 ; 3
	STA >3 ; 3
	LDX #8 ; 2
	LDA #0 ; 2
	BEQ START ; 3 / 2

ADD:
	ADC >3 ; 3
	BCC LOOP ; 3 / 2
	INC >0 ; 5

LOOP:
	DEX ; 2
	BEQ END ; 3 / 2

START:
	ASL A ; 2
	ROL >0 ; 5
	BCS ADD ; 3 / 2
	BCC LOOP ; 3 / 2

END:
	LSR >0 ; 5
	ROR A ; 2
	STA >1 ; 3

僕が作った「計算手順逆転」のプログラムでは、ループカウンタを別持ちしてしまうと、カウント操作の分速度が遅くなるから…と、「乗数」を細工してループカウンタの意味を持たせていました。

これによって、ループが1回増えて9回になってしまう、というデメリットがありました。


改良プログラムでは、ループカウンタを X としているので、ループはキッチリ8回しか回りません。

代わりに、「乗数」と、「結果の上位バイト」を、1つにまとめてしまっています。


掛け算の筆算1段を行うたびに、乗数も結果の上位バイトも、左シフトされます。

このシフトの意味はそれぞれで違っていて、乗算は「上位のビットをキャリーフラグに追い出す」ことが狙いです。

結果として、下位のビットは乗数としての意味を持たなくなっていきます。


これに対し、結果の上位バイトは、「下位バイトから追い出されてきたビットを保持する」ことが狙いです。

下位のビットのみが意味を持ち、上位のビットに意味はありません。


だから、乗数と結果の上位バイトは、1つの 8bit 変数の中に同居できます。

そして、同居していれば、遅い左シフトを1つにまとめることができるのです。



もう一つの鮮やかな改良は、足し算の際に必ず必要な CLC を無くしてしまったこと。

ADD ラベルに分岐するのは、キャリーフラグが 1 になっているときです。

6502 の足し算命令は必ずキャリーを一緒に足しますから、このキャリーは邪魔です。CLC (CLear Carry) が必要だ…と思っていました。


でも、ここで足す数は固定です。なら、足す数をあらかじめ 1 引いておけばいい。

しかも、この例題(1~100 の足し算を、公式を使って高速に求める)で使う公式 n * (n+1) / 2 でいえば、足す数は (n+1) の部分です。これを 1 引けば n になり、被乗数と同じ値になります。

このため、前処理部分では 100 を2か所にコピーするだけですみ、前処理の高速化にもなっています。


僕が作ったプログラムは、高速化させようとするあまり、ちょっと無理やりなところがありました。しかし、このプログラムはそうした「無理やり」部分を全てそぎ落とし、綺麗にまとめることで一層の高速化を実現しているのです。これが鮮やかと評する理由。



前処理が15クロック、後処理が10クロック。

ループ内は、加算無しが16クロック、加算有りの時は、繰上りなしで 20クロック、ありで24クロック。

ループは終了条件で飛び出していますので、最後に1クロック遅くなります。


15 + 10 + (16*5 + 20*2 +24*1) +1 = 170クロックです。


これも3回だけループ展開すればもっと早くなりますね。ここではプログラムは示しませんが、ループ展開の説明と同じく、15クロック速くなって 152 クロックになります。

(ここでは、167クロックを採用します。Z80 がもっと高速化されたら 152クロックにする(笑))


分岐改良

2014.8.8 午後追記

変数共用プログラムに改良を加えたものが投稿されました。

巧妙に4か所の無駄が省かれています。


	LDA #100 ; 2
	STA >3 ; 3
	ASL A ; 2
	STA >0 ; 3
	LDX #8 ; 2
	LDA #0 ; 2
	BCC SKIP ; 3 / 2

ADD:
	ADC >3 ; 3
	BCC SKIP ; 3 / 2
	INC >0 ; 5

SKIP:
	DEX ; 2
	BEQ END ; 3 / 2

LOOP:
	ASL A ; 2
	ROL >0 ; 5
	BCS ADD ; 3 / 2
	DEX ; 2
	BNE LOOP ; 3 / 2

END:
	LSR >0 ; 5
	ROR A ; 2
	STA >1 ; 3

4か所の無駄のうち、まずは2つを説明しましょう。

・処理開始時に、常にループ中にジャンプする

・乗数をゼロページメモリに入れているが、メモリに対するシフトは遅い


ジャンプは遅いです。だからループ展開したりするのですが、「常に」ジャンプは常に 3クロック。

これに対し、条件判断はジャンプすれば 3クロックで一緒ですが、ジャンプしなければ 2クロックで1クロック速い。

だから、メインループ中でも「良く通る側」を、条件分岐しないように組んだりします。6502 のプログラムで、前処理からメインループの真ん中あたりに飛び込んでいるものが多いのも、そのせい。

でも、ここでは前処理の中で、筆算の1段目の計算を始めてしまっています。そして条件によってはジャンプしないで「加算プログラム」に入ってしまう。


ここで、もうひとつの無駄も一緒に省いています。

前処理の段階では、乗数は一旦 A レジスタに代入され、それからゼロページメモリに書き込まれます。しかし、メモリに書き込む前にレジスタを使って段目の計算を始めてしまうので、この時だけはシフトは高速なのです。(ゼロページでは 5クロック、A レジスタは 2クロック)


残りの2つは、共にループ中のジャンプです。

・ループの最後は、常に冒頭にジャンプする

・処理終了時には、条件判断でループ中からジャンプする


元となったプログラムでは、メインループの最後では、必ずジャンプし、ループの途中で条件によって後処理にジャンプしていました。

これを1つにまとめ、メインループの最後で条件分岐するようにしてあります。ジャンプ1個分が、メインループから丸ごと無くなっているのです。


ただし、加算ルーチンに進んだ場合は、メインループ最後の条件分岐を通らないため、改めて条件分岐が必要です。これは元のプログラムと同じ速度になるだけで悪化はしないのですが、コード量がわずかに増加しています。


前処理、および1段目の計算終了までで 21 クロック。例題の乗数 100 の場合、加算無しの計算1回をここまでで終わらせています。

以降の筆算1段分の計算は加算無し 14 クロック、加算有りの繰上りなしが 20 クロック、繰上りありが 24 クロック。

最後は条件分岐を「しない」ので、1クロック速くなります。後処理は 10 クロック。


21 + 14*4 + 20*2 + 24*1 -1 + 10 = 150


総計で 150クロックです。


次ページ: 最初の処理を展開


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

(ページ作成 2014-08-03)
(最終更新 2014-09-01)
第2版 …他の版 初版

前記事:Z80 vs 6502     戻る     次記事:ブロック転送
トップページへ

-- share --

0000

-- follow --




- Reverse Link -