思いついた。

一昨日以来の悩み。アセンブラで平方根の解法をコンパクトに
行う方法。色々考えて見たところ、よさげなのを思いついた。

平方根といえば、まずはニュートン法。1箇所適当な初期値
を与えて、そこから漸化式で近づけていく方法。これは
計算が面倒だし、割り算（しかも割るほうの数が変数）が
出てくるし、収束条件を考えるのも大変だし…


というわけで、別の方法が無いかな…と。
そもそも平方根って何よ？って考えると、０．５乗するわけ。
それを旨く利用できないか数理的に攻めてみる。
しかも、今回は16ビット幅のデータを開平して、8ビット幅
の整数データを取り出せれば十分だから、精度はせいぜい
その範囲。そのあたりの条件を旨く適用しちゃう。

まずａという変数（とりあえず0～65535の16ビット幅）を
2進数の浮動小数表示にしてみるところから。

　ａ＝ｎ×２＾ｍ

固定小数表示のａを浮動小数表示のｎ×２＾ｍという形で
表してみたわけ。
ここでｎは仮数部、ｍは指数部とします。ｎは8ビット幅
精度の数値に丸めちゃう。←実はこれポイント。
2進数だから、ａを適宜右にシフトしたのがｎに、シフト
した回数がｍに入るだけ。ここは処理的には単純。

で、両辺平方根を取ると

　ｓｑｒｔ（ａ）＝ａ＾0.5＝（ｎ×２＾ｍ）＾0.5

となるので、整理すると

　＝ｎ＾0.5　×　２＾（ｍ/2）

となるわけ。ｍがもし偶数ならこの右半分はシフト命令
の組み合わせだけで組めちゃう。奇数なら、最後に
定数の１．４１４…（＝ｓｑｒｔ（２））を掛ければｏｋ。
ってことでここはシフト命令とハードウェア乗算器だけで
組めることが判っちゃう。

で、問題は残った部分のｎ＾0.5の部分。結局平方根が
出てきちゃうジャン！って言うのは早計。上述の通り
ｎは8ビット幅に丸めちゃってるので、実際に取り得る
数値は128個から多くても256個のはず。
（個数は処理ロジック次第）

この程度の定数テーブル、しかも1個1バイトしかないことを
考えると、128～256バイト程度。十分収まる範囲。バッチリ！
16ビット幅だと65536個の定数テーブルになっちゃうのと
比べれば月とすっぽん。

あとは、ｍが偶数なら
　　ｓｑｒｔ（ｎ）×２＾（ｍ/2）
を、奇数なら
　　ｓｑｒｔ（ｎ）×２＾（（ｍ-1）/2）×１．４１４…
を計算すれば良い訳。これらすべて平方根の定数テーブル、
シフト演算、ハードウェア乗算という処理速度の速い命令
だけで済んじゃうはず。

あとは計算途中で精度を下げたりしてることの影響度合い
だな…ってことで表計算ソフトでシミュレーション。

試しに、適当に作り出した数値を元に平方根の計算を
やってみると…

0001001010110100b （10進数で4788）は、平方根を取ると
69.195となるので、小数点以下四捨五入すると69。
これが求まればゴール。

さて、表計算上でシミュレーションをしてみると…

まずｎですが、アタマの0三つを取り除いてから8桁取り出し、
ついでに9桁目が1なので四捨五入で繰り上げておくと、
ｎ＝10010110bとなります。本来は仮数部は左端の1が
1の位になるんだけど、モロモロ端折る都合で今回はこの
8ビットデータを全部小数点以上の位としてしまいます。
すると指数ｍはこの場合5。つまり切り捨てた部分の桁数が
2進数で5桁（5ビット）分。
整理すると、
　　ａ＝10010110×２＾5
　　　　　ｎ＝10010110
　　　　　ｍ＝5
というわけ。数学的には美しくないけど、おいらは数学者
じゃないのでこれはこれで良しとしちゃいます。

で、この場合のｎは10進数でいうと150。
１５０を定数テーブルでサーチしたつもりになって
電卓で平方根取ると12.247…となるので、まるめて
１２と仮定することにします。

さて、ａ（＝4788）の平方根はというと、さっきの式を使って
　ｓｑｒｔ（150）×２＾((5-1)/2) ×1.414…
　＝　12 ×　２＾2　×　１．４１４…
　≒　68

…うーん、微妙に惜しい感じだけど、まぁこのくらい
まで求まればいいんじゃない？一番大きい誤差は150の
平方根が12って仮定しているところだな。ここはちょっと
誤差がでかすぎる…。

その辺も含めて整理しなおせば、16ビット数値の平方根を
求めて8ビット幅で返す処理はまぁまぁ実用レベルの精度
かつ速い処理速度（皮算用では100クロック～200クロック
程度？）に収まるんじゃないかと。

今回参考にしたページを。↓
http://d.hatena.ne.jp/Koonies/mobile?date=20090715&section=sqrt
ありがとうございました。


そういえば、ＣｈａＮさんの所に便利なライブラリが
載ってたな…と思って見てみる。
http://elm-chan.org/cc.html

16ビット幅の平方根はおいらが考えた方法よりもっと
メモリ効率よくできてるみたい。うーん、どんなロジック
で開平してるんだろう？