kvライブラリを0.4.50にアップデートしました。
今回は、卒論修論のシーズンが終わって、学生たちがライブラリを使うことで発見してくれた問題点の解決が主な内容です。利用して下さり、問題点を見つけてくれた学生のみなさまに感謝します。
内容は、
- dd (double-double)用のfrexpが、入力が2のベキ乗よりも僅かに小さい値のときに正しく動作していなかったバグの修正。
- interval.hppで、内部型としてfrexpが誤差を含む可能性があるような型を用いていたとき (例えばdd)、logがごく稀に正しい値を返していなかったバグの修正。
- ddの(精度保証付きでない)sinとcosで、引き戻し処理が雑だったのを修正。
の3点です。特に、2番目は精度保証が破れている可能性があるため、重大な修正です。
frexpは、
double x, y;
int i;
y = frexp(x, &i);
のように呼び出すと、xを入力として 0.5 ≤ |y| < 1, x = y × 2iを満たすようなyとiを計算してくれる関数で、(IEEE754の指数部とは1ずれるが)指数部を取り出してくれる関数としてよく用いられます。ddに対しても、
kv::dd x, y;
int i;
y = frexp(x, &i);
のように同様に使える関数を用意していました。これの実装は、
friend dd frexp(const dd& x, int* m) {
double z1, z2;
z1 = std::frexp(x.a1, m);
z2 = std::ldexp(x.a2, -(*m));
return dd(z1, z2);
}
のようなものでした。しかしこれだと、xが(1, -2-54)のように2のベキ乗よりわずかに小さく、2のベキ乗と小さな負の数の和で表現されている場合、指数部を正しく取り出すことが出来ません。これを、
friend dd frexp(const dd& x, int* m) {
double z1, z2;
z1 = std::frexp(x.a1, m);
z2 = std::ldexp(x.a2, -(*m));
if ((z1 == 0.5 && z2 < 0) || (z1 == -0.5 && z2 > 0)) {
z1 *= 2;
z2 *= 2;
(*m)--;
}
return dd(z1, z2);
}
のように修正する必要がありました。完全に作者の見落としであり、これを見つけてくれた学生には感謝しかないです。このバグが発生する確率は非常に低いので、かなりしつこく追い込まないと見つからない種類のバグだと思います。これにより、x = 1-2-54に対して、
x: 0.999999999999999944488848768742172978818416595458984375
y: 0.4999999999999999722444243843710864894092082977294921875
i: 1
のように誤った(0.5 ≤ |y| < 1を満たしていない)値を返していたのに対して、
x: 0.999999999999999944488848768742172978818416595458984375
y: 0.999999999999999944488848768742172978818416595458984375
i: 0
のように正しく計算されるようになりました。
前のddのfrexp問題に対処しているうちに、ある問題点に気付きました。それは、例えばx = 1+2-1074みたいな上位と下位の数が非常に離れたdd数に対して、誤差無しでfrexpを実行することが不可能であるという問題です。このxに対するfrexpは、
となるべきですが、2-1075を今のdoubleで表現することは出来ません。よって、必然的に誤差が生じることになります。
frexpなんてあまり使わないし、誤差が生じることを断っておけばいいか、くらいに思ったのですが、ライブラリ内でfrexpを使っている箇所を探していたらありました、数学関数logです。log(x)を計算するのに、x=y×2iのように分解する方法を使っていました。そして、frexpに誤差が発生する可能性を考慮しておらず、frexpの戻り値を信用してそのまま計算していました。実際、doubleやmpfrではfrexpで誤差が発生することは無いのですが、ddだとこれが問題になります。
実際、log(1+2-1074)をinterval<dd>で計算すると、
[0,0]
のように誤った(真値を含まない)値が計算されました。frexpは、返却値のうち仮数部yが問題であり、指数部iは信頼できるので、指数部iのみ使って、yは改めて区間演算するように精度保証付きlogの計算方法を改めることで対処しました。これで、
[0,9.881312916824930883531375857364427447301196052286495288511713650013510145404
17503730599672723271984759593129390891435461853313420711879592797549592021563756
25260142638062280905569163433569796420737743727211399746144610001277481830712996
87746249467945463392302800634307707961482524771311823420533171133735363740791206
21249863890543182984910658610913088802254960259419999083863978818160833126649049
51429573802945356031871047722310026960705298694403875805362142149834066644536895
06671441664863872184765786916736120212023012339619506156684554636658495809965049
46155275185449574931216955640746893939906729403594535543517025132110239826300978
22029020757254763345019116747794671979873296198823284114052741805584855350891304
5817507736501283943653106689453125e-324]
のように正しい値を含む区間が返されるようになりました。
一応表現可能とはいえ、1+2-1074のような上位と下位が大きく離れたdd数が生成されることは稀であり、このバグに遭遇する確率は極めて低そうですが、可能性がゼロでない限り精度保証付き数値計算のライブラリとしては大きな問題と言えます。発見できて幸運でした。
こちらは、精度保証付きのsin,cosでなく、sin,cosにintervalでない素のddを入れたときの問題です。元々ddに数学関数は実装されていなかったのですが、近似計算とはいえあれば便利だろうと、後で割と雑に実装したものです。が、sin,cosの引数を0近辺に引き戻すのに、2πを何度も引き算するようなあまりに雑な実装になっていました。多分後で直そうとして忘れていたものと思われます。元々精度保証は何も考えていない部分ですが、これだと大きな引数のときに計算時間が問題になりそうです。ちゃんと割り算するように直しました。
ddは本当に鬼門で、何度も予想もしないバグに遭遇します。
精度保証付き数値計算のライブラリは、バグがあれば当然精度保証にならないわけで、プログラムにバグがないことをどうやって保証するのか、という宿命的な問題を抱えています。数学の定理の自動証明や、プログラムの自動検証を行うような研究もなされています。
(将来は分かりませんが)現在のところ、数学の定理が正しいかどうかは、多くの数学者が証明を検証してどうやら正しそうだ、と思えたら正しい、という段階のようです。プログラムも同じことで、大勢の人が使い、またソースコードを見て、どうやら正しそうだと思えたら正しい、とするしかないように思います。そのために、精度保証付き数値計算のプログラムは必ずオープンでなければならないし、また大勢の人に使われなければならないと考えています。