La.系ぶろぐ

個人的いろいろメモ。シャープペンのメモにちょっぴりゲ○ツの悪口が混じってるただのチラ裏。

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

PageTop

16bit整数平方根の話

なんか昔書いたコードを見つけたので。
前にガンマの話なんか書いたりしましたが(なんか途中で放置したような気も……)その辺で使っていたり。

コードで書くのも面倒なので適当に書くと、
0<=x<1024でt(x)=8√xのテーブルを作って、aの平方根を求めると、
a<1024の時……
  解r=t(a)/8;
それ以上の時……
  r=t(a/64);
  if(r*(r+2)<a) r++;

えっと、適当に解説すると、今時ならsseで一発(32bit浮動小数で定義域23bit,精度11bitのが求まるので、
そのまま使える。ただ、浮動小数変換が入るけど)だし、テーブル全部作っても解は8bitなので64kBで
済むじゃんってなるのですが。
当時はまだsse無い環境考えたり、キャッシュ少ないよね、って時期だったので、小細工を考えていたわけです。

まあ、真面目に計算するとどうしてもややこしいことになってしまうので、テーブル小さくしない?って事で。
1024で折り返してるところがミソだったりするわけです。
実は平方根を微分して、1024辺りで傾きを取ると1/64で、要するに上のテーブルの最大誤差って1なんですよね。
それを後ろの計算式で補正する、と。r*(r+2)<aは(r+1)^2≦aを小細工で変形したものですね。
(展開すれば分かるかと……後者の方が早くないか?)

というかそもそも、整数乗算が早くないと意味ない補正式ですね。(Z80とかそもそも使えない)
その時はまあ……テーブル使うでもすれば。(こっちは16bitだけど+2kBで、Z80でも何とかなるんじゃない?w
……いや、贅沢だよなぁ)
もうちょっと頭ひねれば、簡単(高速)な補正式が出せるかも知れませんね。

実際は、a<4096でr=t[a/4]/4;とか使えば誤差を圧縮できるのですが、if文増えるし、誤差補正が要らない
わけでもない(工夫すればなくせるかも)ので、あまり美味しくなかったり。でこれで落ち着いたわけですね。

結局何が言いたいかって言うと……エロゲ作ってても数学必要なことはあるよ、と。
微分ばんじゃい、みたいな?
……正直言うと、解説だから微分が出るのであって、作った時はそういう計算してないんですけどねw

スポンサーサイト

PageTop

コメント


管理者にだけ表示を許可する
 

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。