掛け算

目次

概要

Z80基本

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

6502基本

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

速度比較


計算手順逆転

2014.8.6 未明追記

これを書いている時点で、MSX とファミコンでは、2割の速度差で MSX が勝っています。

掛け算はレジスタを多数駆使しなくてはならず、6502 にはなかなか難敵の様子…

特に、筆算の1段を処理するごとに、16bit+16bit の加算を行わなくてはならないのが辛いです。


そこで、この計算を「16bit + 8bit + 繰上り処理」に単純化したのが次のプログラム


	LDA #101 ; 2
	STA >3 ; 3
	LDA #100 ; 2
	STA >4 ; 3

	LDA #0 ;2
	STA >0 ; 3
	SEC ; 2
	BEQ START ; 3 / 2

ADD:
	BEQ END ; 3 / 2
	CLC ; 2

	ADC >3 ; 3
	BCC LOOP ; 3 / 2

	INC >0 ; 5

LOOP:
	ASL A ; 2
	ROL >0 ; 5

START:
	ROL >4 ; 5
	BCS ADD ; 3 / 2
	JMP LOOP ; 3


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

2進数の掛け算は、筆算の方法で行われます…というのはよくある説明。

Z80 のプログラムでは、乗数を左シフトしながら、結果に足し合わせています。

しかし、ここでは乗数は固定したまま、結果を左シフトしていく方法にしてみました。


乗数をシフトすると、16bit + 16bit の足し算が生じてしまいますが、乗数をシフトしなければ 16bit + 8bit で済みます。上位バイトは繰上り処理のみでゼロページに対して直接インクリメント命令が使えるので、A レジスタを使いまわす必要がなくなります。

そこで、A レジスタは常に結果の下位 8bit を保持するようにしました。それ以外は、基本のプログラムと同じメモリの使い方をしていますが、乗数は 8bit なので、16bit 分用意されたメモリの上位バイトは初期化すらしていません。


基本の方法は、下のビットから筆算で掛け算した形になっていました。しかし、ここでの方法は、上のビットから計算しています。

そのため、必ず 8bit 全てを計算しなくては、桁が合わなくなります。普通なら8回繰り返すのにカウンタ変数を持つのですが、この方法ではメインループ中に、変数のデクリメントと条件分岐、という大きなオーバーヘッドが生じます。

ここでは、乗数の外側(9bit目)に、1 を付けることで、問題を回避しています。この1は、はじめてシフトを行うときだけ、右側から入りますが、以降のシフトでは 0 が入ります。

そして、左シフトで9bit 目の 1 が追い出され、8bitの内容が 0 になった時が計算の終了するときです。

1が追い出されたときですから、その時には必ず加算ルーチンに分岐します。加算ルーチンの冒頭で終了条件をチェックすれば、メインループで毎回チェックを行う必要はなくなります。


ただ、この方法もデメリットがあり、終了が9回目のループ冒頭になってしまいます。基本プログラムではループは7回なのに、2回も増えるのです。これも重大なデメリットです。


クロック数を計算してみましょう。前処理と後処理は、それぞれ 20クロックと 10 クロック。終了判定に、9回目のループとして11クロック必要です。

ループ中は、加算無しが 17クロック。加算有りはさらに細かくわかれ、繰上りなしが 25クロック、ありが 29クロック。

例題では、加算無しが5回、繰上りなしが2回、繰上りありが1回生じます。


20 + 10 + 11 + (17*5 + 25*2 +29*1) = 205 クロック。

デメリット部分が大きく、大改造した割には 9 クロックしか速くなっていません。


ループ展開

2014.8.6 未明追記

…そこで、お約束のループ展開です。

ループ部分以外は先に書いた「計算手順逆転」と同じなので、LOOP から END の間だけを示します。


LOOP:
	ASL A ; 2
	ROL >0 ; 5

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

	ROL >4 ; 5
	BCS ADD ; 3 / 2
	ASL A ; 2
	ROL >0 ; 5

	ROL >4 ; 5
	BCS ADD ; 3 / 2
	JMP LOOP ; 3

…うん。わかりやすいループ展開。実は、先のプログラムではループ展開しやすいように、メインループをコンパクトになるようにしていました。

展開は3回だけです。もしこれ以上の処理が必要になった場合は、JMP でLOOP に戻ります。

そして、今回の例題では、これで十分です。乗数の 100 は、2進数では 0110 0100 。任意のビットから右に進み、必ず 3bit 以内に 1 が現れます。


1 が来た場合、BCS ADD で、LOOP の上にある ADD に戻り、再度 LOOP の先頭から実行が始まります。つまり、最後の JMP LOOP には到達しません。

先の計算で、メインループは加算無しの際に 17クロックでした。これは、加算無しの際に JMP LOOP が実行されるためで、ループ展開で加算無しの際は 14クロックに減少します。3クロックの高速化です。

加算無しは5回あるので、15クロック高速化されて、190 クロックになります。やっと 200クロックを切りました。


次ページ: 変数共用


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

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

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

-- share --

2000

-- follow --




- Reverse Link -