循環(wraparound)する整数型のOverflowを検出する方法

Julia を触っているときに悩んだので備忘録的に残しておきます。

考え方

乗算がオーバーフローしやすいと思うので、その場合で考えていきます。

説明で使う関数などは Julia-like に書きます。わからない人は下記の表を確認してください。


Int64	64bitの整数
typemax(T)	T型の最大値 ex) typemax(Int64) = 2⁶³ - 1
typemin(T)	T型の最小値 ex) typemin(Int64) = -2⁶³
typeof(x)	xの型を返す

任意の型Tについて、 $a, b \in \mathrm{T}, \, a > 0, b > 0$ がオーバーフローすると仮定すると、

$a \cdot b > \mathrm{typemax(T)} \tag{1}$

が成り立ちます。しかし、ラップアラウンドする整数型に対して、この式は必ずしも成り立つとは言えません。以下に例を挙げてみます。

julia> x = 1000000000000000000
1000000000000000000

julia> typeof(x)
Int64

julia> x * 10
-8446744073709551616

このとき、(1) の $a\cdot b$ でラップアラウンドが発生しています。

では、ラップアラウンドが起こらないように (1) を変形してみましょう。

$b > \mathrm{typemax(T)} / a \tag{2}$

これでラウンドアップを起こさずにオーバーフローを検出できるはずです。プログラム言語によっては、 $\mathrm{typemax(T)} / a$ の部分で切り捨て除算が起こり正しく判定できないかもしれないので、適宜処理をしてください。

$a, b$ の他の場合分けについても同様に考えることができ、オーバーフローする条件は、

$\begin{cases} a > 0, b > 0 & \qquad \mathrm{typemax(T)} / a < b \\ a < 0, b < 0 & \qquad \mathrm{typemax(T)} / a > b \\ a > 0, b < 0 & \qquad \mathrm{typemin(T)} / a > b \\ a < 0, b > 0 & \qquad \mathrm{typemin(T)} / a < b \end{cases}$

の4パターンです。

実装の例

上記を考慮して「オーバーフロー時に、より範囲の広い整数型で計算する」関数を Julia で作ると以下のようになります。Base.Checked.checked_mul() を使って OverflowError を try catch するより断然早いはずです。

function ovf_mul(x::T, y::T) where T<:Integer
    (x == zero(T)) && (return zero(T))
    (y == zero(T)) && (return zero(T))
    if x > zero(T)
        if y > zero(T)
            return (typemax(T) / x) < y ? widen(x) * widen(y) : x * y
        else
            return (typemin(T) / x) > y ? widen(x) * widen(y) : x * y
        end
    else
        if y > zero(T)
            return (typemin(T) / x) < y ? widen(x) * widen(y) : x * y
        else
            return (typemax(T) / x) > y ? widen(x) * widen(y) : x * y
        end
    end
end

northclimbの備忘録

徒然なるままに...です。

循環(wraparound)する整数型のOverflowを検出する方法

考え方

実装の例