1

短いバージョン:ここで説明されている固定小数点乗算を使用してオーバーフローを検出するにはどうすればよいですか?

長いバージョン:

私のQ31.32 固定小数点型にはまだオーバーフローの問題があります。紙の上で例を作成しやすくするために、同じアルゴリズムを使用して、はるかに小さい型 (sbyte に基づく Q3.4) を作成しました。Q3.4 タイプのねじれをすべて解決できれば、Q31.32 タイプにも同じロジックが適用されるはずです。

Q3.4 の乗算は 16 ビット整数で実行することで非常に簡単に実装できることに注意してください。存在しません (そして BigInteger は遅すぎます)。

乗算で飽和によるオーバーフローを処理する必要があります。つまり、オーバーフローが発生すると、結果はオペランドの符号に応じて表現できる最大値または最小値になります。

これは、基本的に型の表現方法です。

struct Fix8 {
    sbyte m_rawValue;
    public static readonly Fix8 One = new Fix8(1 << 4);
    public static readonly Fix8 MinValue = new Fix8(sbyte.MinValue);
    public static readonly Fix8 MaxValue = new Fix8(sbyte.MaxValue);

    Fix8(sbyte value) {
        m_rawValue = value;
    }

    public static explicit operator decimal(Fix8 value) {
        return (decimal)value.m_rawValue / One.m_rawValue;
    }

    public static explicit operator Fix8(decimal value) {
        var nearestExact = Math.Round(value * 16m) * 0.0625m;
        return new Fix8((sbyte)(nearestExact * One.m_rawValue));
    }
}

そして、これは私が現在乗算を処理する方法です：

    public static Fix8 operator *(Fix8 x, Fix8 y) {
        sbyte xl = x.m_rawValue;
        sbyte yl = y.m_rawValue;

        // split x and y into their highest and lowest 4 bits
        byte xlo = (byte)(xl & 0x0F);
        sbyte xhi = (sbyte)(xl >> 4);
        byte ylo = (byte)(yl & 0x0F);
        sbyte yhi = (sbyte)(yl >> 4);

        // perform cross-multiplications
        byte lolo = (byte)(xlo * ylo);
        sbyte lohi = (sbyte)((sbyte)xlo * yhi);
        sbyte hilo = (sbyte)(xhi * (sbyte)ylo);
        sbyte hihi = (sbyte)(xhi * yhi);

        // shift results as appropriate
        byte loResult = (byte)(lolo >> 4);
        sbyte midResult1 = lohi;
        sbyte midResult2 = hilo;
        sbyte hiResult = (sbyte)(hihi << 4);

        // add everything
        sbyte sum = (sbyte)((sbyte)loResult + midResult1 + midResult2 + hiResult);

        // if the top 4 bits of hihi (unused in the result) are neither all 0s or 1s,
        // then this means the result overflowed.
        sbyte topCarry = (sbyte)(hihi >> 4);
        bool opSignsEqual = ((xl ^ yl) & sbyte.MinValue) == 0;
        if (topCarry != 0 && topCarry != -1) {
            return opSignsEqual ? MaxValue : MinValue;
        }

        // if signs of operands are equal and sign of result is negative,
        // then multiplication overflowed upwards
        // the reverse is also true
        if (opSignsEqual) {
            if (sum < 0) {
                return MaxValue;
            }
        }
        else {
            if (sum > 0) {
                return MinValue;
            }
        }

        return new Fix8(sum);
    }

これにより、型の精度内で正確な結果が得られ、ほとんどのオーバーフロー ケースが処理されます。ただし、次のようなものは処理しません。

Failed -8 * 2 : expected -8 but got 0
Failed 3.5 * 5 : expected 7,9375 but got 1,5

最初の乗算がどのように行われるかを考えてみましょう。

-8 and 2 are represented as x = 0x80 and y = 0x20.
xlo = 0x80 & 0x0F = 0x00
xhi = 0x80 >> 4 = 0xf8
ylo = 0x20 & 0x0F = 0x00
yhi = 0x20 >> 4 = 0x02

lolo = xlo * ylo = 0x00
lohi = xlo * yhi = 0x00
hilo = xhi * ylo = 0x00
hihi = xhi * yhi = 0xf0

hihi を除いてすべての項が 0 であるため、合計は明らかに 0 ですが、hihi の下位 4 ビットのみが最終的な合計に使用されます。

私の通常のオーバーフロー検出マジックはここでは機能しません。結果はゼロなので、結果の符号は無意味です (たとえば、0.0625 * -0.0625 == 0 (切り捨てによる)、0 は正ですが、オペランドの符号は異なります); また、hihi の上位ビットは 1111 で、オーバーフローがない場合でもよく発生します。

基本的に、ここでオーバーフローが発生したことを検出する方法がわかりません。より一般的な方法はありますか？

4

2 に答える 2

0

これには長い時間がかかりましたが、最終的にすべてを理解しました。このコードは、sbyte で許可されている範囲内の x と y のすべての可能な組み合わせに対して機能することがテストされています。コメント付きのコードは次のとおりです。

    static sbyte AddOverflowHelper(sbyte x, sbyte y, ref bool overflow) {
        var sum = (sbyte)(x + y);
        // x + y overflows if sign(x) ^ sign(y) != sign(sum)
        overflow |= ((x ^ y ^ sum) & sbyte.MinValue) != 0;
        return sum;
    }

    /// <summary>
    /// Multiplies two Fix8 numbers.
    /// Deals with overflow by saturation.
    /// </summary>
    public static Fix8 operator *(Fix8 x, Fix8 y) {
        // Using the cross-multiplication algorithm, for learning purposes.
        // It would be both trivial and much faster to use an Int16, but this technique
        // won't work for a Fix64, since there's no Int128 or equivalent (and BigInteger is too slow).

        sbyte xl = x.m_rawValue;
        sbyte yl = y.m_rawValue;

        byte xlo = (byte)(xl & 0x0F);
        sbyte xhi = (sbyte)(xl >> 4);
        byte ylo = (byte)(yl & 0x0F);
        sbyte yhi = (sbyte)(yl >> 4);

        byte lolo = (byte)(xlo * ylo);
        sbyte lohi = (sbyte)((sbyte)xlo * yhi);
        sbyte hilo = (sbyte)(xhi * (sbyte)ylo);
        sbyte hihi = (sbyte)(xhi * yhi);

        byte loResult = (byte)(lolo >> 4);
        sbyte midResult1 = lohi;
        sbyte midResult2 = hilo;
        sbyte hiResult = (sbyte)(hihi << 4);

        bool overflow = false;
        // Check for overflow at each step of the sum, if it happens overflow will be true
        sbyte sum = AddOverflowHelper((sbyte)loResult, midResult1, ref overflow);
        sum = AddOverflowHelper(sum, midResult2, ref overflow);
        sum = AddOverflowHelper(sum, hiResult, ref overflow);

        bool opSignsEqual = ((xl ^ yl) & sbyte.MinValue) == 0;

        // if signs of operands are equal and sign of result is negative,
        // then multiplication overflowed positively
        // the reverse is also true
        if (opSignsEqual) {
            if (sum < 0 || (overflow && xl > 0)) {
                return MaxValue;
            }
        }
        else {
            if (sum > 0) {
                return MinValue;
            }
            // If signs differ, both operands' magnitudes are greater than 1,
            // and the result is greater than the negative operand, then there was negative overflow.
            sbyte posOp, negOp;
            if (xl > yl) {
                posOp = xl;
                negOp = yl;
            }
            else {
                posOp = yl;
                negOp = xl;
            }
            if (sum > negOp && negOp < -(1 << 4) && posOp > (1 << 4)) {
                return MinValue;
            }
        }

        // if the top 4 bits of hihi (unused in the result) are neither all 0s nor 1s,
        // then this means the result overflowed.
        sbyte topCarry = (sbyte)(hihi >> 4);
        // -17 (-1.0625) is a problematic value which never causes overflow but messes up the carry bits
        if (topCarry != 0 && topCarry != -1 && xl != -17 && yl != -17) {
            return opSignsEqual ? MaxValue : MinValue;
        }

        // Round up if necessary, but don't overflow
        var lowCarry = (byte)(lolo << 4);
        if (lowCarry >= 0x80 && sum < sbyte.MaxValue) {
            ++sum;
        }

        return new Fix8(sum);
    }

これらすべてを .NET 用の適切に単体テストされた固定小数点数学ライブラリにまとめています。これはhttps://github.com/asik/FixedMath.Netから入手できます。

于 2013-01-02T04:56:43.487 に答える
0

hihi結果の範囲外の関連ビットが含まれているかどうかを調べる必要があります。また、結果の最上位ビットと対応するビットを比較してhihi、キャリーがそこまで伝播したかどうかを確認し、伝播した場合 (つまり、ビットが変更された場合)、それがオーバーフロー (つまり、ビットが間違った方向に変更された) を示しているかどうかを確認することもできます。 . 1 の補数表記を使用していて、符号ビットを別々に扱っていれば、これらすべてを定式化するのはおそらく簡単でしょう。しかし、その場合、-8 の例は無意味です。

あなたの例を見ると、hihi = 0xf0.

hihi   11110000
result     ±###.####

したがって、この場合、hihi単独でオーバーフローがなければ、最初の 5 ビットはすべて同じになり、結果の符号は の符号と一致しhihiます。ここではそうではありません。これを使用して確認できます

if ((hihi & 0x08) * 0x1f != (hihi & 0xf8))
  handle_overflow();

キャリーhihiインは、一度に 1 つの被加数を加算し、各ステップの後に一般的なオーバーフロー検出を実行することによって、おそらく最も簡単に検出できます。そのための素敵なコードが用意されていません。

于 2013-01-02T00:28:09.860 に答える