👻

[C#11] Generic Mathで桁あふれしないように足し算を実装する

2023/04/10に公開

何もわからない。もっと良い方法知りたい...

前の記事と類似のネタです。

題材

同じ型の要素が2個のVector構造体を定義します[1]new Vector2<int>(1, 2) とか new Vector2<double>(3.4, 5.6) のような使い方です。

using System.Numerics;

public record struct Vec2<T>(T Item0, T Item1)
    where T : unmanaged, INumber<T>;

ここで、Vec2同士の足し算を実装したいとして、C#11 Generic Mathの時代ではどうすればよいかという話です。

using System.Numerics;

public record struct Vec2<T>(T Item0, T Item1)
    where T : unmanaged, INumber<T>
{
    public static Vec2<T> operator +(Vec2<T> a, Vec2<T> b) 
    {
        ...
    }
}

ここで特殊な仕様を付け加えます。計算結果はオーバーフローせず型の範囲内に切り詰めてもらうようにしたいです。

var v1 = new Vec2<byte>(10, 100);
var v2 = new Vec2<byte>(20, 200);
Console.WriteLine(v1 + v2);  // 期待値: Vec2 { Item0 = 30, Item1 = 255 }

基本の実装

C# 11ではchecked版の演算子を別で定義できるようになっています。そちらも用意しました。

using System.Numerics;

public record struct Vec2<T>(T Item0, T Item1)
    where T : unmanaged, INumber<T>
{
    public static Vec2<T> operator +(Vec2<T> a, Vec2<T> b) 
        => new Vec2<T>(
            a.Item0 + b.Item0,
            a.Item1 + b.Item1);
	    
    public static Vec2<T> operator checked +(Vec2<T> a, Vec2<T> b) 
        => new Vec2<T>(
            checked(a.Item0 + b.Item0),
            checked(a.Item1 + b.Item1));
}

これは計算結果はオーバーフローせず型の範囲内に切り詰めてもらうようにしたい仕様を無視すれば問題ないと思います。実行結果は以下のようになります。checked版は既に申し分ないです。非checked版はしっかりあふれてしまいました。

var v1 = new Vec2<byte>(10, 100);
var v2 = new Vec2<byte>(20, 200);
Console.WriteLine(v1 + v2);  // Vec2 { Item0 = 30, Item1 = 44 }   (オーバーフローして 300-256 の値に)
Console.WriteLine(checked(v1 + v2));  // OverflowException

byte + byte の場合など、int未満のサイズの整数型の演算では、暗黙にintに変換されます(以下参照)。しかしGeneric Mathではそういうことは起きません。その分岐の判定ができそうなメソッド・プロパティも見当たりませんでした。
https://learn.microsoft.com/ja-jp/dotnet/csharp/language-reference/operators/arithmetic-operators

Saturate対応案1: try-catch

checkedによってオーバーフローするかどうか例外送出としてわかるので、それで対処する素朴な案です。例外処理のコストが大変気になりますが、わかりやすさは抜群です。

shortで-30000 + -20000をするような、答えが負でオーバーフローの場合も考えられるため、その考慮も入れています。

その型の最大最小値を知るため、IMinMaxValue<T>の制約を追加しました。

using System.Numerics;

public record struct Vec2<T>(T Item0, T Item1)
    where T : unmanaged, INumber<T>, IMinMaxValue<T>
{
    public static Vec2<T> operator +(Vec2<T> a, Vec2<T> b)
    {
        T item0, item1;
        try
        {
            item0 = checked(Item0 + other.Item0);
        }
        catch (OverflowException)
        {
            if (T.IsNegative(Item0) && T.IsNegative(other.Item0))
                item0 = T.MinValue;	        
	    else
                item0 = T.MaxValue;
        }
        try
        {
            item1 = checked(Item1 + other.Item1);
        }
        catch (OverflowException)
        {
            if (T.IsNegative(Item1) && T.IsNegative(other.Item1))
                item1 = T.MinValue;	        
	    else
                item1 = T.MaxValue;
        }

        return new Vec2<T>(item0, item1);
    }
}

Saturate対応案2: オーバーフローしないよう式を変形

tryをしたくない場合です。自信なし...

オーバーフローしないようにあらかじめ確認するという作戦です。byteを例にとると、以下の分岐を書きます。ここで a + b がまずいわけです。

add(a, b) = \left\{ \begin{array}{ll} 255 & (a + b \gt 255)\\ a + b & (otherwise) \end{array} \right.

ここで条件式のところを移項するとオーバーフローの恐れはなくなります。

add(a, b) = \left\{ \begin{array}{ll} 255 & (\mathbf{a \gt 255 - b})\\ a + b & (otherwise) \end{array} \right.

しかし、今度は sbyte のような符号のある型を考えると、127 - bbが負の場合に実質足し算に変わるためオーバーフローの恐れがあります。負の場合は絶対値を見て判断することにします。ここで絶対値を見る際、sbyteの値域(-128~+127)については最小値の-128だけは絶対値を取ると範囲外に出てしまうので、予め1を足すようにします。

add(a, b) = \left\{ \begin{array}{ll} 127 & (a > 0, b > 0, a \gt 127 - b)\\ -128 & (a < 0, b < 0, |a| \gt |-128+1| - |b+1|)\\ a + b & (otherwise) \end{array} \right.

浮動小数点数は、例えば checked(double.MaxValue + 1) がOverflowExceptionにならないなど、上記の考えではどうにもならないようで、いったん考慮せずスルーします。

以上をまとめてみました。ここでも IMinMaxValue<T> の制約を利用します。加えてAbsOneも使用しました。

using System.Numerics;

public record struct Vec2<T>(T Item0, T Item1)
    where T : unmanaged, IBinaryNumber<T>, IMinMaxValue<T>
{
    public static Vec2<T> operator +(Vec2<T> a, Vec2<T> b)
    {
        if (typeof(T).GetInterface("System.Numerics.IFloatingPointIeee754`1") is not null)
        {
            return new Vec2<T>(
                Item0 + other.Item0,
                Item1 + other.Item1);
        }

        T result0, result1;
        if (T.IsNegative(other.Item0))
        {
            if (T.IsNegative(Item0))
            {
                T diff = T.Abs(T.MinValue + T.One) - T.Abs(other.Item0 + T.One);
                if (T.Abs(Item0) > diff)
                    result0 = T.MinValue;
                else
                    result0 = Item0 + other.Item0;
            }
            else
                result0 = Item0 + other.Item0;
        }
        else
        {
            T diff = T.MaxValue - other.Item0;
            if (Item0 > diff)
                result0 = T.MaxValue;
            else
                result0 = Item0 + other.Item0;
        }

        if (T.IsNegative(other.Item1))
        {
            if (T.IsNegative(Item1))
            {
                T diff = T.Abs(T.MinValue + T.One) - T.Abs(other.Item1 + T.One);
                if (T.Abs(Item1) > diff)
                    result1 = T.MinValue;
                else
                    result1 = Item1 + other.Item1;
            }
            else
                result1 = Item1 + other.Item1;
        }
        else
        {
            T diff = T.MaxValue - other.Item1;
            if (Item1 > diff)
                result1 = T.MaxValue;
            else
                result1 = Item1 + other.Item1;
        }

        return new Vec2<T>(result0, result1);
    }
}

引き算も同様に可能です。まあまあ込み入ってしまいました。

掛け算・割り算の場合

スカラー値を係数として掛ける・割る演算を定義するとして、その場合は上記の境界値チェックの要領だと苦しいと思います。そもそもVectorの「掛け算」の定義にもよると思いまして、例えば係数の方に応じて要素の型を決めてしまうのは一案です。

using System.Numerics;

public record struct Vec2<T>(T Item0, T Item1)
    where T : unmanaged, INumber<T>, IMinMaxValue<T>
{
    public static Vec2<int> operator *(Vec2<T> obj, int alpha) => new(
        int.CreateSaturating(obj.Item0) * alpha,
        int.CreateSaturating(obj.Item1) * alpha);
    public static Vec2<double> operator *(Vec2<T> obj, double alpha) => new(
        double.CreateSaturating(obj.Item0) * alpha,
        double.CreateSaturating(obj.Item1) * alpha);
}

あとはなんだかんだ、checkedしてcatchしかないかなと思っています...。何もわからない。どうやってもエッジケースを拾える感じがしないので、あらかじめ型を変えてからの慎重な計算を促すべく、演算子は定義しないのが現場向きな気もします。

全体的に、浮動小数点数への考慮が甘い(INFやNaNはどうする等)気もしています。

脚注
  1. 本記事としてはstructでもclassでも内容に変わりありません。 ↩︎

Discussion