2013/12/13

sqrtが遅かった話

https://twitter.com/tk_riple/status/411433966952923136

最初は環境がネストしてるからだと思ってフラットにしたんだけど変わらなかったので、多分Gaucheだとsqrtが遅いんだな。プロファイラ見てみると%sqrtの呼び出したがsqrtの呼び出しの倍くらいになってる。実装は知らない。

ヘロン三角形

gosh> (time (find-heron 100))
;(time (find-heron 100))
; real   1.011
; user   0.967
; sys    0.032
((100 100 56) (100 99 89) ...

norm> (time (find-heron 100))
((100 100 56) (100 99 89) ...
total 0.897 second
GC    0.0 second
#<undef>
norm> 

ああ、そうか。

sqrt は正確な正の平方数が与えられたら、正確な結果を返す (cf. Exact sqrt) のだけど、その計算を

1. exact-integer-sqrt で正確な正の引数nに対し n = q*q + m (0 <= m < q) なる正確数q, mを計算
2. mが0ならqが答え
3. そうでなければnは正確数の平方数ではないので浮動小数点数にしてCのsqrtに投げる

としていた。これだと引数が有理数の平方数でない場合、 exact-integer-sqrt で一回平方根に近い正確値を計算し、 さらに3.でもう一度sqrtを計算するという二度手間をやってたことになる。

二度手間を避けるようにしたらこれこのとおり。

変更前

shiro@scherzo:~/src/Gauche/src$ ./gosh -ftest ../heron.scm
;(time (find-heron 100))
; real   0.722
; user   0.720
; sys    0.000

変更後

shiro@scherzo:~/src/Gauche/src$ ./gosh -ftest ../heron.scm
;(time (find-heron 100))
; real   0.617
; user   0.620
; sys    0.000

Tags: Programming, Gauche