Z80での平方根計算が非常におもしろい件

昨日の記事のブックマークコメントで、Z80の平方根計算が紹介されてた。
http://b.hatena.ne.jp/entry/d.hatena.ne.jp/nowokay/20120604%231338773843

んで、見てみると、なんでこれで平方根もとめれるの！って感じだったので非常におもしろかった。
http://wikiti.brandonw.net/index.php?title=Z80_Routines:Math:Square_root

このサイズ最適化のほう、遅いけど12バイトで実装できるってのが、結構わけわかんないって書いたら、id:finalfusionさんにこの解説を教えてもらった。
https://twitter.com/AoiMoe/status/209542023575904256

このコードなんだけど

sqrt:
   ld a,$ff
   ld de,1
sqrtloop:
   inc a
   dec e
   dec de
   add hl,de
   jr c,sqrtloop
   ret 

Javaで書くなら

int sqrt(int hl){
  int a = -1;
  int de = 1;
  for(;;){
    ++a;
    --de;
    --de;
    hl += de;
    if(hl < 0) break;
  }
  return a; 
}

のようなコードになる。

ここで、deを減らすのに一回目はdec e、二回目はdec deとしてるのは、プログラムサイズ上は意味がないんだけど、ちょっとだけ8ビット演算のdec eのほうが速い。両方1バイトのコードなんだけど、dec eは4ステート、dec deは6ステート。
deは奇数なんで、１回目のデクリメントでは1ビット目だけの演算になるから、わざわざ16ビット演算を使う必要がないってことだと思う。

んで、なんでこれで平方根が求められるのかって話なんだけど、ここで、奇数を足していくと2乗の数値の列挙になるってのが使われてる。
つまり

となって、となりあった2乗の数の差は奇数になるんで、-1、-3、-5・・・と足していくことで、-1、-4、-9・・・のように2乗の数の負数をそれぞれ足していることになる。
で、２乗した数が引数より大きくなったところでカウンタaを返すと、それが平方根になっているという話。
上記のJavaコードを

int sqrt(int hl){
  int a = -1;
  int de = -1;
  int tmp =  0;
  for(;;){
    ++a;
    de += 2;
    tmp += de;
    if(hl < tmp) break;
  }
  return a; 
}

にするとちょっとわかりやすい。

int sqrt(int hl){
  for(int a = 1;; ++a){
    if(hl < a * a) return a - 1;
  }
}

ってやると、ふつうのコードになる。

こういうのは、ハッカーのたのしみに書いてあるのかな。あとで見にいこう。

ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか