So-net無料ブログ作成
English Version

Z80での10の高速除算方法 [Z80]

 今回はtwitterで見かけたZ80で10で割る処理に関するお題について書いてみます。

 お題としてはZ80で100未満の数値を10で除算処理する場合、如何に高速にできるか?というもので

    Breg ÷ 10 = Hreg ... Areg

という処理です。

 具体的な処理例も挙げられていて次の処理を高速化できるか? という問題です。
 100要素分の回答の配列から引っ張るのが一番速いですがそれは無しという条件付きです。
 尚、以下に示す各処理は0..99の入力に対するリターン値(AregとHreg)が全て同じであることを確認済みのものです。

処理例
; +++ asking method +++ 78 chk10: ld a,b ; input value 21 00A0 ld hl, 10 SHL 4 BD cp l 38 03 jr c,chk0 95 sub l 26 10 ld h,16 CB 0D chk0: rrc l BD cp l 38 03 jr c,chk1 95 sub l CB DC set 3,h CB 2D chk1: sra l BD cp l 38 03 jr c,chk2 95 sub l CB D4 set 2,h CB 2D chk2: sra l BD cp l 38 03 jr c,chk3 95 sub l CB CC set 1,h CB 2D chk3: sra l BD cp l 38 03 jr c,put2 95 sub l CB C4 set 0,h C9 put2: ret


 上記の処理内容を見ると通常の割算処理のループを展開したような形になっています。
 ループが展開されているので被除数が小さい場合には上位桁の演算をスキップするショートカット方式を最初に思いつきました。
 ショートカットすることで

    0~39なら -54clk
   40~99なら+18clk

となり平均すれば-10.8clk分速くなりそうです。

最初に思いついたショートカット方式
; +++ my first method +++ ; when 40..99 0..39 78 my1_10: ld a,b ; input value 4 4 21 0028 ld hl, 10 SHL 2 ; 10 10 BD cp l ; add 4 4 38 18 jr c,my1_2 ; add 7 12 2E A0 ld l,10 SHL 4 ; add 7 BD cp l ; 0a0h ; 4 38 03 jr c,my1_0 ; 7 12 ave 15 95 sub l ; 4 26 10 ld h,16 ; 7 CB 0D my1_0: rrc l ; 4 BD cp l ; 050h ; 4 38 03 jr c,my1_1 ; 7 12 ave 15.5 95 sub l ; 4 CB DC set 3,h ; 8 CB 2D my1_1: sra l ; 4 BD cp l ; 028h ; 4 38 03 jr c,my1_2 ; 7 12 ave 15.5 95 sub l ; 4 CB D4 set 2,h ; 8 CB 2D my1_2: sra l ; 4 4 BD cp l ; 014h ; 4 4 38 03 jr c,my1_3 ; 7 12 ave 15.5 15.5 95 sub l ; 4 4 CB CC set 1,h ; 8 8 CB 2D my1_3: sra l ; 4 4 BD cp l ; 00ah ; 4 4 38 03 jr c,my1_4 ; 7 12 ave 15.5 15.5 95 sub l ; 4 CB C4 set 0,h ; 8 C9 my1_4: ret


 しかし、既に下記のバイナリサーチのような処理案(「引き放し法」と言うそうです)が出ていて処理内容が複雑そうですが確かに速そうです。

引き放し法
; +++ twitter's solution +++ DIV10: 78 LD A,B ; 4 D6 50 SUB 80 ; 7 38 15 JR C,ADD40 ; 7,12 26 08 LD H,8 ; 7 D6 28 SUB 40 ; 7 38 15 JR C,ADD20 ; 7,12 SUB20: CB D4 SET 2,H ; 8 D6 14 SUB 20 ; 7 38 13 JR C,ADD10 ; 7,12 SUB10: CB CC SET 1,H ; 8 D6 0A SUB 10 ; 7 38 11 JR C,NEG_EX ; 7,12 POS_EX: CB C4 SET 0,H ; 8 C9 RET ; 10 ADD40: 26 00 LD H,0 ; 7 C6 28 ADD A,40 ; 7 38 EB JR C,SUB20 ; 7,12 ADD20: C6 14 ADD A,20 ; 7 38 ED JR C,SUB10 ; 7,12 ADD10: C6 0A ADD A,10 ; 7 38 EF JR C,POS_EX ; 7,12 NEG_EX: C6 0A ADD A,10 ; 7 C9 RET ; 10


 ぱっと見は処理内容が解り辛いですが、10 x (2のべき乗) の大きい方(80)から引いていき(キャリが出たら次は足す)、10未満になったら終了するような処理が見えてきます。
 最初に書いた処理例では比較(CP)で確認後減算(SUB)していますが、比較による確認無しに減算し、マイナスになっても元に戻さず(だから「引き放し法」)次に半分の値を足すことで結果として半分の値を引いたのと等価になるというものです。

 しかし、入力値の条件が100未満なので80を引けた場合、直後に40を引いているのは無駄なように見えます。
 80を引いた後は0..19の範囲内なので10を引けるかのチェックをした方が早く収束するはずなので改善してみたものが下の処理です。

引き放し法の改善案
; +++ my improve method +++ MDIV10: 78 LD A,B ; 4 D6 50 SUB 80 ; 7 38 14 JR C,MADD40 ; 7,12 26 08 LD H,8 ; 7 ; SUB 40 ; 7 del ; JR C,ADD20 ; 7,12 del C3 0512 JP MS10 ; 10 add MSUB20: CB D4 SET 2,H ; 8 D6 14 SUB 20 ; 7 38 13 JR C,MADD10 ; 7,12 MSUB10: CB CC SET 1,H ; 8 D6 0A MS10: SUB 10 ; 7 38 11 JR C,MNEG_EX ; 7,12 MPOS_EX: CB C4 SET 0,H ; 8 C9 RET ; 10 MADD40: 26 00 LD H,0 ; 7 C6 28 ADD A,40 ; 7 38 EB JR C,MSUB20 ; 7,12 MADD20: C6 14 ADD A,20 ; 7 38 ED JR C,MSUB10 ; 7,12 MADD10: C6 0A ADD A,10 ; 7 38 EF JR C,MPOS_EX ; 7,12 MNEG_EX: C6 0A ADD A,10 ; 7 C9 RET ; 10


 発想を変えて、お題がZ80なのでBCD関連の命令をうまく利用できないか考えてみた結果が次の処理です。
★2019/07/13 追記 {
 思考の順番としては100要素の回答テーブルの各要素の規則性は単純なのでもっと短いテーブルにできないものか?という発想から考えた結果として上位ニブルに対するBCDテーブルに行き着きました。
}
 RRD命令のクロック数が多いのが気になりますがこれも結構速そうですね^^

 気合を入れれば平均クロック数を算出して上の処理と比較できますが夜の作業としては他の作業をしたい(上の処理は分岐確率が50%でないところがあるので更にややこしい)

 今時のマイコンであれば統合開発環境内で実行時のクロック数はシミュレータですぐに確認できるのですが、Z80のシミュレータで実行クロック数を確認できるものを少し探しましたが見当たりませんでした。
 0..99をループで回し開始/終了時にI/O命令を実行してロジアナで確認することはある程度容易にできますが、それもやぼったいので、クロック数をモニタできるシミュレータが見つかったら比較してみたいと思います。

現時点で最新の高速処理案
; +++ my method +++ mydiv: 21 0707 ld hl,wrk ; 10 70 ld (hl),b ; 7 set input value AF xor a ; 4 ED 67 rrd ; 18 6E ld l,(hl) ; 7 set high nible 86 add a,(hl) ; 7 add high nible's BCD to low nible 27 daa ; 4 BCD B7 or a ; 4 clear flag 27 daa ; 4 BCD(for high nible) 2E 07 ld l,wrk and 00ffh ; 7 77 ld (hl),a ; 7 AF xor a ; 4 ED 67 rrd ; 18 66 ld h,(hl) ; 7 C9 ret ; 10 org ($ + 255) and 0ff00h ; BCD 00 tbl: db 000h ; 00h 16 db 016h ; 10h 32 db 032h ; 20h 48 db 048h ; 30h 64 db 064h ; 40h 80 db 080h ; 50h 96 db 096h ; 60h wrk: ds 1


★2019/08/01 追記
 このブログの読者にはあまり人気が無かったこのページのアクセスが最近多くなりました。

yasuokaの日記: Z80における定数10の除算は、商と余りのどちらを先に求めるべきか

関連の書込み記事からのアクセスのおかげのようです^^

 51/512倍することで商を出す手法で末尾に ret を加えると108clk(ステート)で上記のもの(118clk)より高速です(上記のものもRRD命令部をシフト化して数clkの短縮は可能ですが)。

 今回の問題では入力範囲が0..99なのでこのような分数演算の手法では誤差を1%未満にする必要があります。私も13/128でやってみたところ誤差が1%以上なので回答が途中からズレた結果になりました。
 また、整数演算なので誤差が1%未満であっても誤差の範囲内の変動で回答が影響を受けないように inc a で微調整されています。

 普通に考えると16bitでシフトしたいところですが、なんと8bitのシフトや演算で処理を完結しています・・すばらしい!

 私も新たなアイディアを思いついたら追記したいと思います。


★2019/08/02 追記
 アイディアが浮かんだので試してみた結果をメモしておきます。
 今回、複数のアイディアを盛り込み、結果として上記の分数方式(108clk)より4clk短縮(104clk)できました。(^^)/
★2019/08/03 変更 {
yasuokaの日記: Re:Z80における定数10の除算は、商と余りのどちらを先に求めるべきかの記事がアップされ剰余を先に求める方法で103clk(最後にretを追加した場合)達成とのこと。
 今回追記した処理に関してもまだ少しのりしろがあったので一部見直し103clkになりました^^
}

 今回適用した主要なアイディアとしては、少数演算の使用と上位/下位のnibleを逆転することによる4bitシフト処理の省略です。
 後者についてはピンと来ないかも知れませんが以下に概要を説明します。

  1. 小数点で処理
     分数方式だと前回記載したように誤差が1%未満の条件で分子と分母の組合せを色々考えることになりますが、0.1を2進数で表現し、その乗算値を求めればいいのでは?と考えました。
     小数点であれば分数のように組合せを考える必要が無いし、誤差は桁数に依存し一意に決まります。
     また、シフトが一方向なので往復するようなシフト処理が発生しません。

     下表に示すように 0.1を2進数で表すと2進数の循環小数になります。
     下表の1~9(橙色部分)の合計は 0.099609 なのでここまで算出すれば1%未満という条件を満たす誤差範囲になるはずです。


  2. 小数点の桁のアサイン
     速度優先で計算は8bitで行うので8bit分の有効桁数を維持するために表中のNo.1~3のゼロの部分は省略してNo4をMSBに割り振ります。
     この場合、16倍したことになるので最終的に上位nibleに結果が求まることになり、結果を取り出すために4回のシフト処理が必要になりますが、この問題は後述の対策で解決します。

  3. 循環小数の求め方
     表中のNo4と5の合計を求め、1/16倍(4bitシフト)すればNo8と9の合計になります。

  4. 上位/下位ニブルの逆転処理
     上記の循環小数のための4bitシフトでRRCAを使用することで、上位のnibleと下位のnibleが入代ります。
     ここでLSB側のnibleの方を上位、MSB側のnibleを下位と考えるとシフト前の値がシフト後の値の1/16と考えることができます。
     また、0.1倍した結果がLSB側のnibleに入るようになるので、前述した結果を取り出す際の4回のシフト処理が不要になります。

  5. 加算部の処理
     表中のNo.4,5にNo.8,9を加算する際は、MSB側の下位nibleから上位nibleへ桁上り(キャリー)が発生するか否かが必要な情報であり、キャリーが発生した場合、LSB側の上位nibleに反映するために、No.8,9を加算後にキャリ付き加算(ADC)を実行しています。

  6. 剰余の計算
     商が求まったら、商の10倍を入力値から減算して余りを算出しています。


小数点で0.1倍した改善処理
      ; +++ my method2 +++ 78 MYDEV2: LD A,B ; 4 F6 01 OR 1 ; 7 1F RRA ; 4 88 ADC A,B ; 4 4F LD C,A ; 4 0F RRCA ; 4 0F RRCA ; 4 0F RRCA ; 4 0F RRCA ; 4 5F LD E,A ; 4 81 ADD A,C ; 4 3E 00 LD A,0 ; 7 8B ADC A,E ; 4 E6 0F AND 0FH ; 7 67 LD H,A ; 4 87 ADD A,A ; 4 87 ADD A,A ; 4 84 ADD A,H ; 4 2F CPL ; 4 07 RLCA ; 4 88 ADC A,B ; 4 C9 RET ; 10


★2019/08/07 追記
 分数方式についての考察を少し書いてみます。

 初めに前回の小数点方式について動作を判り易く図解してみます。
 下図で一番上に書いてある「x 1.5」の行は被除数を1.5倍したものです。
 0.1を2進数で表すと上記のように「0001100110011・・・」の循環小数になるので「1.5倍」の数を4ビットずつシフトしながら無限回並べたものの合計になります。

 上の小数点方式の説明で「上位/下位ニブルの逆転処理」と書いた部分でキャリーを足している対象は正確に言うと下図の「整数部分」になります。

小数点方式の処理イメージ図


 因みに4bit周期の循環小数なのでうまくやれば誤差無しに計算可能で(循環部で桁上りした場合、下の桁からも必ず桁上りしてくるので)、小数点部分を正確に求められれば、小数点の上位3bitの2倍と8倍を足すことで余りの値も計算結果から求められるはずなのですが、
  • 8bitでは処理が難しい
    シフトする塊が被除数の3倍なので桁落ちせずに計算するには 99 x 3 = 297 まで扱う必要があり、1バイト処理では難しい
  • 小数部からの余りの取り出し処理
    現状の商から余りを求める部分と比較し大きな効果が出るとは思えない。

の理由から断念しました。

 話を分数方式に戻すと分母が2のべき乗の場合、分子のビットパターンは結局上記の0.1の循環小数と同様になり(分母が2のべき乗なら分子は0.1の循環小数のパターンをシフトしたものの近似になるのは当然)、処理内容は前回書いた小数点方式とほぼ同様になります。

 試しに 25.5 / 256(1バイトなので判り易い)を例にすると下図のように1.5倍したものを RLCA で4回左シフトし、整数部は下位4bitに折り返した形になります(折り返し部分は不要なのですが、上の小数点方式の観点で見れば、演算精度を上げる方向に作用するのでワザワザ削除する必要はない)。
 シフト前とシフト後の値の合計を取り、発生したキャリーを整数部に加える処理となり、前回書いた小数点方式と処理内容は同じになります。
 小数点方式も同様ですが(ウルトラCのアイディアがあれば)循環小数点部分の処理の高速化については検討の余地があるかもしれません。

分数方式(25.5/256)の処理イメージ図


nice!(0)  コメント(7) 
共通テーマ:趣味・カルチャー

nice! 0

コメント 7

skyriver

10の割算処理について、改善処理を追記しました。

by skyriver (2019-08-02 23:47) 

skyriver

このページに改善版を追記した後に
https://srad.jp/~yasuoka/journal/631908/
に更に高速な処理が記載されていることに気付きこちらも少し改善してみました。
by skyriver (2019-08-03 09:48) 

skyriver

2のべき乗を分母にした分数方式についての考察を追記しました。

by skyriver (2019-08-07 23:10) 

skyriver

なんと誤差1%以上の分数計算(13/128)方式で最速記録が更新されました。すごぃ。
 「2019/08/07 追記」で書いた「循環小数点部分の処理の高速化」の一つの方法として「000110011」を「0001101」に丸めることにあったとは驚きです。

https://srad.jp/~yo4/journal/632067/

by skyriver (2019-08-09 07:50) 

skyriver

ソースを見比べると13/128方式は商が求まるタイミングは同じですが商から余りを算出する部分でCレジで4倍値を使いまわすことで早くなっている・・ということですね。
by skyriver (2019-08-09 08:14) 

skyriver

 誤差1%未満が必要条件だと思ってましたが13/128で問題なかったということが気になったので以前、13/128で評価した時のソースを使って検証してみました。
 このソースはまずはアルゴリズムの確認のために16bitでロスレスで処理しています。
 結果は 「06 03 06 05」で1個ズレ(64の余りが5になった)、その後終わりまでズレています。
 LSBをゼロにしたことが影響したのかと思い AND 0FEHにしてやってみましたが結果は同じでした。
 8bit処理で右シフトの度に下位bitを捨てていることが補正になり、ずれが発生しなかったものと思われます。

by skyriver (2019-08-09 18:15) 

skyriver

やはり最初に0FEHでANDしていることが補正になっていました。
シフト途中の加算をLSB付きの値(=Breg)で行うと69で10の桁が7になってしまいました。
by skyriver (2019-08-11 17:14) 

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。