或るプログラマの一生

uint8_t での Predict Median で予測値を計算する際、uint8_t のままで計算すると gradient の計算でオーバーフロー（やアンダーフロー）が発生しうるため、その後に大小比較をすると不正確な結果になってしまう、という話をだいぶ前に記事にしました。

オーバーフローしないようにするにはたとえば int にしたり場合分けをしたりする必要があるよね、というのがその記事での結論でした。場合分けをする場合はもちろん、ビット数を広げる場合でも SIMD 計算していると変換にかかる時間も無視できません。

で、最近頭をひねっていたところ、ビット数を広げずに場合分けも回避できることに気が付きました。中央値を与える median 関数には以下の自明な性質があります。

median(a + x, b + x, c + x) = median(a, b, c) + x
median(-a, -b, -c) = -median(a, b, c)

よって、Predict Median の式は以下のように変形できます。(a = left, b = top, c = topleft)

  median(a, b, a + b - c)
= median((a + b) - a, (a + b) - b, (a + b) - c)
= (a + b) + median(-a, -b, -c)
= a + b - median(a, b, c)

こうすればオーバーフローの後に大小比較を行うことを避けることができます。

この変形の結果、行う演算の種類と数は変化しておらず、しかも後で残差を計算することを考慮するとクリティカルパスは短くなっています。以前の記事でも言及している通り圧縮比は改善されるため、いいことづくめです。

9年前に気づいてればなぁ…