2021/03/20(土)kv-0.4.51
変更点は以下の通りです。
- 区間演算を行うinterval.hppにfloorとceilを追加。
- 区間演算と領域の再帰的分割による最適化を行うoptimize.hppが場合によって正しく終了しなかったバグの修正。
- 高階微分を計算するhighderiv.hppが定数関数を渡されたとき動作しなかったバグの修正。
- 昨年11月のNVR2020の発表で作成した、複合Newton-Cotes公式を用いた数値積分のための関数群を追加。
highderiv.hppとoptimize.hppはともに数値積分の誤差項の計算に使われており、昨年11月の発表の際にいろいろ使ってみて不具合が発覚しています。やはり使われて鍛えられないとライブラリの完成度は上がらないので、ご利用下さると大変嬉しいです。
2020/02/12(水)kv-0.4.50
今回は、卒論修論のシーズンが終わって、学生たちがライブラリを使うことで発見してくれた問題点の解決が主な内容です。利用して下さり、問題点を見つけてくれた学生のみなさまに感謝します。
内容は、
- dd (double-double)用のfrexpが、入力が2のベキ乗よりも僅かに小さい値のときに正しく動作していなかったバグの修正。
- interval.hppで、内部型としてfrexpが誤差を含む可能性があるような型を用いていたとき (例えばdd)、logがごく稀に正しい値を返していなかったバグの修正。
- ddの(精度保証付きでない)sinとcosで、引き戻し処理が雑だったのを修正。
ddのfrexpのバグ
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のように正しく計算されるようになりました。
interval<dd>のlogのバグ
前のddのfrexp問題に対処しているうちに、ある問題点に気付きました。それは、例えばx = 1+2-1074みたいな上位と下位の数が非常に離れたdd数に対して、誤差無しでfrexpを実行することが不可能であるという問題です。このxに対するfrexpは、- y = 0.5+2-1075
- i = 1
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数が生成されることは稀であり、このバグに遭遇する確率は極めて低そうですが、可能性がゼロでない限り精度保証付き数値計算のライブラリとしては大きな問題と言えます。発見できて幸運でした。
ddのsin,cosの引き戻し問題
こちらは、精度保証付きのsin,cosでなく、sin,cosにintervalでない素のddを入れたときの問題です。元々ddに数学関数は実装されていなかったのですが、近似計算とはいえあれば便利だろうと、後で割と雑に実装したものです。が、sin,cosの引数を0近辺に引き戻すのに、2πを何度も引き算するようなあまりに雑な実装になっていました。多分後で直そうとして忘れていたものと思われます。元々精度保証は何も考えていない部分ですが、これだと大きな引数のときに計算時間が問題になりそうです。ちゃんと割り算するように直しました。おわりに
ddは本当に鬼門で、何度も予想もしないバグに遭遇します。精度保証付き数値計算のライブラリは、バグがあれば当然精度保証にならないわけで、プログラムにバグがないことをどうやって保証するのか、という宿命的な問題を抱えています。数学の定理の自動証明や、プログラムの自動検証を行うような研究もなされています。
(将来は分かりませんが)現在のところ、数学の定理が正しいかどうかは、多くの数学者が証明を検証してどうやら正しそうだ、と思えたら正しい、という段階のようです。プログラムも同じことで、大勢の人が使い、またソースコードを見て、どうやら正しそうだと思えたら正しい、とするしかないように思います。そのために、精度保証付き数値計算のプログラムは必ずオープンでなければならないし、また大勢の人に使われなければならないと考えています。
2019/11/21(木)kv-0.4.49
今回は、以前から溜めていた、
- 辺に特異性を持つ2変数関数の二重積分
- 一点に特異性を持つ2変数関数の二重積分
言葉で書くと簡単そうですが苦労しています。数値積分のページの第5,6節とか、辺及び一点にベキ型特異性を持つ2変数関数の二重積分を見て下さい。
2019/04/10(水)kv-0.4.48
今回は、区間演算の非常に基本的な部分の更新を含んでいます。
kvライブラリの区間演算は、端点に無限大を含む、 [0,\infty]のような半無限区間や、 [-\infty,\infty]のような無限区間を表現することが出来るように設計されています。これらは、区間が無限大という数?を含むという意味ではなく、 [0,\infty]ならば 0 \le x < \inftyのような、 [-\infty,\infty]なら -\infty < x < \inftyのような範囲を意味します。
このように端点に \inftyを許す区間演算を実装する場合、特に乗算で 0 \times \inftyに注意する必要があります。この計算はIEEE 754 Std.ではNaNになることになっていますが、区間演算の結果としてNaNはふさわしくありません。加算、減算、除算では適切に場合分けを行っていればNaNの危険はありませんが、乗算だけはきちんと考慮する必要があります。で、0.4.47以前では、片方が [0,0]でもう片方が無限大を含む区間だった場合の乗算で、何を考えていたのか、
\begin{eqnarray*}
[0,0] \times [-\infty,\infty] &=& [-\infty, \infty] \\
[0,0] \times [c,\infty] &=& [-\infty, \infty] \\
[0,0] \times [-\infty,c] &=& [-\infty, \infty] \\
\end{eqnarray*}
のような計算をしていました。これらは、無限大を含む区間の意味を考えれば、当然 [0,0]になるべきものです。今回の0.4.48でこれを修正しました。福井大学の石井大輔先生のご指摘によります。大変ありがとうございました。また、使ってる人がいるかどうか分からない、C++で気軽にリアルタイムグラフ表示 (matplotlib.hpp)の記事で書いたmatplotlib.hppですが、長方形を描画する関数rectにバグがあって正しい位置に描画されていなかったのを直しました。
2018/12/26(水)三部会連携 応用数理セミナー
そこでつかったスライドを上げておきます。
40分では少し駆け足になってしまったのが反省点。また、Affine Arithmeticは常微分方程式の精度保証でかなり重要な役割を果たしているにもかかわらず、教科書のどこにも説明がないのが大きな問題点だなあと感じました。