２点間の距離を近似
この記事はある２点間の距離を近似して求めてしまおうというもの。普通距離は2点をA、Bとすると
x = A.x - B.x , y = A.y - B.y
distance = (x2 + y2)1/2
記事中のその近似式は
distance_approx = 1007/1024·max(|x|,|y|) + 441/1024·min(|x|,|y|)
distance_approx = k · { α·max(|x|,|y|) + (1-α)·min(|x|,|y|) }
まず係数kだが、これは、範囲における全体の大きさが、
(x2 + y2)1/2,max(|x|,|y|),min(|x|,|y|)
でちがうので、これを調整する。x、yのそれぞれの範囲を-1から1とするとき、その値の和つまり積分を取ってだからその比をとって
k = √2
つぎにαだが
α = |1/ k·distance - min(|x|,|y|)| / |max(|x|,|y|) - min(|x|,|y|)|
・・・で求めました。α = 0.5888230227と出ました。kをかけて、0.8329845781。記事中の係数は1007/1024で0.9833984375・・・あれ全然違う。
しかたないので乱数１０００回で試してエラーを計測したところ*3自家製 約3.75%、記事 約4.59%・・・う勝ってるよ。記事よりましだと。*4まあそこそこの精度ではないだろうか。精度はニュートン法使えば補正できるだろうし。
で問題は速度ですな。ループを使って10000×10000つまり１０億回適当に計算してみたところ近似関数は約5.6秒、近似でない(std::sqrt)関数は約6.3秒。かなり微妙だ。近似関数のなかでは x,y の絶対値を取るのに１回ずつ、最小最大をとるのに１回の計三回の比較式を用いる。これがネックなのだろう。ましてや素直に絶対値、最小最大を関数で実装すればもっと遅くなる。あと
double distance_approx(double x,double y){
double ax = (x<0)?-x:x;
double ay = (y<0)?-y:y;
if(axを途中に変数をはさむだけで
double distance_approx(double x,double y){
double ax = (x<0)?-x:x;
double ay = (y<0)?-y:y;
double out; //ここです。
if(ax上記のループでの時間が下のコードの場合、約6.35秒となって使い物にならなくなる。
記事中では固定小数点の場合の関数を作成している。固定小数点の場合には(もともと二乗根を求める関数がないわけだから)役立つだろうし、多少速くなるかもしれない。ただ浮動小数点の場合は精度との兼ね合いから見て意味がないだろう。
無駄足だったかな・・・・。
- 追記 sqrtの近似式でこちらへやってきた人へsqrt(N)のニュートン法
Xn+1 = (Xn2+N)/(2·Xn)
