kashiの日記

2018/06/17(日)kv-0.4.44

およそ半年ぶりに、kvライブラリを0.4.44にアップデートしました。

変更点は、

dd.hpp, rdd-hwround.hpp, rdd-nohwround.hppを修正し、主にddのオーバーフローに関するバグを修正。
affine.hppのepsilon_reduceで、与えられたaffineベクトルが1次元だった場合に正しく動かないバグを修正。
rkf78.hpp追加
その他細かい修正

です。

今回は、dd (double double) を使った区間演算に関する重大なバグフィックスを含んでいます。加減乗除の結果がオーバーフローするかしないかギリギリの値の場合の処理に問題があり、確率は低いものの、精度保証が正しく行われない可能性があるバグです。

以下、その詳細について説明します。ddでの区間演算は、例えば加算では真値と同じか真値よりも大きい値を計算するadd_up、真値と同じか真値よりも小さい値を計算するadd_downによって実現されています。例えばadd_downは、次のようなアルゴリズムによって実現されていました。簡単のため、python-likeに書いています。dd数(x1,x2)とdd数(y1,y2)の和を下向き丸めで計算するものです。

def dd_add_down(x1, x2, y1, y2) :
    z1, z2 = twosum(x1, y1)
    if z1 == -float("inf") :
        return z1, 0
    if z1 == float("inf") :
        return sys.float_info.max, sys.float_info.max * 2.**(-54)
    down()
    z2 = z2 + x2 + y2
    near()
    z1, z2 = twosum(z1, z2)
    return z1, z2

無誤差のtwosumはそのまま計算し、誤差の入る可能性のある「z2 + x2 + y2」の部分は下向き丸めで計算することで、下向き丸めの結果を得ています。これに加えて、赤字で示したオーバーフローの処理を行っています。ddライブラリではIEEE754と同様の無限大の取り扱いを出来るように設計しています。これは、端点に無限大を許す区間演算の実装には不可欠です。無限大は(inf,0)または(-inf,0)のような内部表現にしています。また、twosumは

def twosum(a, b) :
    x = a + b
    if (abs(a) > abs(b)):
        tmp = x - a
        y = b - tmp
    else:
        tmp = x - b
        y = a - tmp
    return x, y

のような実装になっていますが、a,bが無限大でなくa+bがオーバーフローした場合、(inf,-inf)を返すことが分かります。add_downのオーバーフロー処理は、

負の方向へオーバフローした場合は、(-inf,0)を返す。
正の方向へオーバーフローした場合は、下向き丸めなので無限大を返すのは誤りで、ddで表現できる正の最大数を返す。

という処理を行っていました。

自分はこれで抜けは無いと安易に考えていたのですが、研究室の修士の学生だった宮崎敏文さんにまずい場合があるのではないかと指摘され、確かに問題があることが分かりました。

問題は3つあります。

最初の問題は、「add_downで正の方向にオーバーフローするとddでの正の最大数を返すが、x1+y1は確かにddの正の最大数より大きいが、x2とy2が負の数で、全体の合計はddの正の最大数を下回ることがあるのではないか」というものです。宮崎さんの指摘はこの問題でした。
二つ目の問題は、「最初のtwosumの後は無限大の処理をしているが、二つ目のtwosumの後は何もしていない。最初のtwosumではオーバーフローしないが、二つ目のtwosumでオーバーフローする可能性があるのでは」というものです。
三つ目の問題は、「add_downの引数の片方がinf、もう片方が非infだったとき、その和はinfになるべきだが、ddの正の最大数が返ってくる」というものです。

これらの問題点を解決するため、次のように改修しました。

def dd_add_down(x1, x2, y1, y2) :
    if abs(x1) == float("inf") or abs(y1) == float("inf") :
        return x1 + y1, 0
    z1, z2 = twosum(x1, y1)
    if z1 == -float("inf") :
        return z1, 0
    if z1 == float("inf") :
        z1 = sys.float_info.max
        z2 = sys.float_info.max * 2.**(-54)
    down()
    z2 = z2 + x2 + y2
    near()
    z1, z2 = twosum(z1, z2)
    if z1 == -float("inf") :
        return z1, 0
    if z1 == float("inf") :
        z1 = sys.float_info.max
        z2 = sys.float_info.max * 2.**(-54)
    return z1, z2

すなわち、まず引数に無限大が含まれている場合を先に処理し(3.の対策)、次にtwosum後に正方向にオーバーフローして正の最大数に置き換えた場合はreturnせずにそのまま計算を継続するようにし(2.の対策)、最後に2回目のtwosumに対しても同じようにオーバーフロー処理を行なう(2.の対策)ようにしました。

これによって、次のように問題が修正されました。

1.の問題は、例えば(x_1,x_2)=(2^{1023}-2^{970},-(2^{969}-2^{916})), (y_1,y_2)=(2^{1023},-2^{969})という入力で発生します。

#include <kv/interval.hpp>
#include <kv/dd.hpp>
#include <kv/rdd.hpp>

int main()
{
    std::cout.precision(32);
    kv::interval<kv::dd> x, y, z;

    x.lower().a1 = pow(2., 1023) - pow(2., 970);
    x.lower().a2 = -(pow(2., 969) - pow(2., 916));
    x.upper() = x.lower();
    std::cout << x << "\n";

    y.lower().a1 = pow(2., 1023);
    y.lower().a2 = -pow(2., 969);
    y.upper() = y.lower();
    std::cout << y << "\n";

    z = x + y;
    std::cout << z << "\n";
}

これを改修前のkvで計算すると

[8.9884656743115780417662938029053e+307,8.9884656743115780417662938029054e+307]
[8.9884656743115790396864485702651e+307,8.9884656743115790396864485702652e+307]
[1.797693134862315807937289714053e+308,inf]

となりますが、正しい値は1.797693134862315708145274237317049\cdots \times 10^{307}なので下端が真値より大きくなってしまっています。改修後は、

[8.9884656743115780417662938029053e+307,8.9884656743115780417662938029054e+307]
[8.9884656743115790396864485702651e+307,8.9884656743115790396864485702652e+307]
[1.797693134862315708145274237317e+308,inf]

と正しく計算されていることが分かります。

2.の問題は、例えば(x_1,x_2)=(2^{1023},2^{970}), (y_1,y_2)=(2^{1023}-2^{971},2^{969}-2^{916})という入力で発生します。

#include <kv/interval.hpp>
#include <kv/dd.hpp>
#include <kv/rdd.hpp>

int main()
{
    std::cout.precision(32);
    kv::interval<kv::dd> x, y, z;

    x.lower().a1 = pow(2., 1023);
    x.lower().a2 = pow(2., 970);
    x.upper() = x.lower();
    std::cout << x << "\n";

    y.lower().a1 = pow(2., 1023) - pow(2., 971);
    y.lower().a2 = pow(2., 969) - pow(2., 916);
    y.upper() = y.lower();
    std::cout << y << "\n";

    z = x + y;
    std::cout << z << "\n";
}

これを実行すると、改修前は

[8.988465674311580536566680721305e+307,8.9884656743115805365666807213051e+307]
[8.9884656743115780417662938029052e+307,8.9884656743115780417662938029053e+307]
[inf,inf]

のように[inf,inf]という不正な区間が発生していましたが、改修後は

[8.988465674311580536566680721305e+307,8.9884656743115805365666807213051e+307]
[8.9884656743115780417662938029052e+307,8.9884656743115780417662938029053e+307]
[1.797693134862315807937289714053e+308,inf]

のように[ddの最大数、inf]という正しい結果を返すようになりました。

3.の問題は、区間演算では発生しないのですが、add_downを明示的に呼ぶと再現できます。

#include <kv/interval.hpp>
#include <kv/dd.hpp>
#include <kv/rdd.hpp>

int main()
{
        std::cout.precision(32);
        kv::dd x, y, z;

        x = std::numeric_limits<kv::dd>::infinity();
        std::cout << x << "\n";
        y = 0;
        std::cout << y << "\n";
        z = kv::rop<kv::dd>::add_down(x, y);
        std::cout << z << "\n";
}

これを実行すると、

inf
0
1.797693134862315807937289714053e+308

のようにinf+0の下向き丸めが正の最大数になってしまいますが、改修でちゃんと

inf
0
inf

と正常になりました。

以前からこのバグには気付いていたのですが、多忙でなかなか改修できず、モヤモヤした気分が続いていました。確率が低いとはいえ、「精度保証が保証になっていない」バグを放置してはならないと考えていますので。しかし、double-double絡みのバグが目立つのは困りものです。針の穴を通すような繊細さが要求されると感じています。

コメント（0件）

検索条件

2018/06/17(日)kv-0.4.44