Z80 除算アルゴリズム : プログラミング指南

乗算に続いて今回は除算、そう割り算です。割り算はA÷Bだと、AからBを何回引けるかという計算なので、単純にA-Bを引けなくなるまで繰り返すと答えが出ます。これまた簡単です。

この処理も乗算の時と同様に、最大で256回ループする可能性がある（1で割れば…ですが）ので、こちらも何とか減らしたいと思います。今回は自分でアルゴリズム検討中に X(Twitter)で有志にいろいろ助けられましたので、そちらのコードを元に検証していきたいと思います。

例えば、191÷5 という除算を考えてみます。算数の考え方では、桁をズラしながら最大値を引き算していきます。計算式だと


    191 - 150 = 41 // 5 * 30
     41 -  40 =  1 // 5 * 8
  ----------------------------
    ∴ 38 ... 1 (余り)

割る数を増やしている30回とか8回というのは、やはり10進数で考察している状態です。乗算の時と同様、これを2進数で考えてみます。


    191 = %10111111
      5 = %00000101

こちらも割る数の %00000101 で上位の 0 は無視します。


      %10111111 - %10100000 ; <<=5 (32)
    = %00011111 - %00010100 ; <<=2 (4)
    = %00001011 - %00001010 ; <<=1 (2)
    = %00000001 (余り)

割る時の左シフト回数が 2倍の回数と同じなので、2^5 + 2^2 + 2^1 = 38 となります。このように、割る数のシフトした位置を加算していけば答えが出ます。割る数のシフト回数をカウンタレジスタに入れて、シフト回数を加味した計算を、Z80のコードに落とし込むと以下になります。

大元のコードは @kousainas さんから提示していただきましたが、一部問題が残っていました。それをすかさず秋川藤志 @akikawa134 さんにバグ修正して頂いています。

【Amazon】
キングジム(Kingjim) 電子メモパッドブギーボード10.5インチ電池交換可 BB-9 黒

キングジム(Kingjim)

2017-07-20

ちょっとした伝言とか電話メモなどで、いちいち紙を消費するぐらいなら、こんなのを使ってみてはどうでしょうか。事務用品販売のキングジムなので安心です。
そして、このルーチンから inc a というビットを立てる処理を、事前の計算結果の CF を活かして省略してプチ高速化した処理がこちらです。

正しく引けたときは CF=0、ダメだったときは CF=1 になりますので、それをそのまま Acc に格納して最後の最後にビット反転することで、正しい結果としています。ここまででも素晴らしかったのですが、割られる数のビットの空きを利用して、計算式全体を 8bit で済ませるコードが skyriver @wcinp さんより提供されました。そして、さらに高速化されて…