16

int64_tまたはuint64_tオペランドを使用した乗算演算がCでオーバーフローした場合に、効率的で移植性のあるチェック方法はありますか？

たとえば、uint64_tを追加するには、次のようにします。

if (UINT64_MAX - a < b) overflow_detected();
else sum = a + b;

しかし、私は乗算のための同様の単純な式に到達することはできません。

私に起こるのは、オペランドを高いuint32_t部分と低いuint32_t部分に分割し、オーバーフローをチェックしながらそれらの部分の乗算を実行することだけです。これは本当に醜く、おそらく非効率的です。

アップデート1：いくつかのアプローチを実装するいくつかのベンチマークコードが追加されました

アップデート2：JensGustedtメソッドが追加されました

ベンチマークプログラム：

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define N 100000000

int d = 2;

#define POW_2_64 ((double)(1 << 31) * (double)(1 << 31) * 4)

#define calc_b (a + c)
// #define calc_b (a + d)

int main(int argc, char *argv[]) {
    uint64_t a;
    uint64_t c = 0;
    int o = 0;
    int opt;

    if (argc != 2) exit(1);

    opt = atoi(argv[1]);

    switch (opt) {

    case 1: /* faked check, just for timing */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            if (c > a) o++;
            c += b * a;
        }
        break;

    case 2: /* using division */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            if (b && (a > UINT64_MAX / b)) o++;
            c += b * a;
        }
        break;

    case 3: /* using floating point, unreliable */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            if ((double)UINT64_MAX < (double)a * (double)b) o++;
            c += b * a;
        }
        break;

    case 4: /* using floating point and division for difficult cases */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            double m = (double)a * (double)b;
            if ( ((double)(~(uint64_t)(0xffffffff)) < m ) &&
                 ( (POW_2_64 < m) ||
                   ( b &&
                     (a > UINT64_MAX / b) ) ) ) o++;
            c += b * a;
        }
        break;

    case 5: /* Jens Gustedt method */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            uint64_t a1, b1;
            if (a > b) { a1 = a; b1 = b; }
            else       { a1 = b; b1 = a; }
            if (b1 > 0xffffffff) o++;
            else {
                uint64_t a1l = (a1 & 0xffffffff) * b1;
                uint64_t a1h = (a1 >> 32) * b1 + (a1l >> 32);
                if (a1h >> 32) o++;
            }
            c += b1 * a1;
        }
        break;

    default:
        exit(2);
    }
    printf("c: %lu, o: %u\n", c, o);
}

これまでのところ、浮動小数点を使用してほとんどのケースをフィルタリングするケース4は、オーバーフローが非常に異常であると想定される場合に最速です。少なくとも、何もしない場合よりも2倍遅いだけの私のコンピューターではそうです。

ケース5は4よりも30％遅いですが、常に同じように実行されます。4の場合のように、処理を遅くする必要のある特別なケース番号はありません。

4

6 に答える 6

9

実際、乗算にも同じ原理を使用できます。

uint64_t a;
uint64_t b;
...
if (b != 0 && a > UINT64_MAX / b) { // if you multiply by b, you get: a * b > UINT64_MAX
    < error >
}
uint64_t c = a * b;

同様のことができる符号付き整数の場合、符号の組み合わせごとにケースが必要になるでしょう。

于 2011-12-16T12:27:55.970 に答える
5

Ambrozの答えのように除算を避けたい場合：

まず、2つの数値のうち小さい方、たとえば、が2 32a未満であることを確認する必要があります。そうでない場合、結果はとにかくオーバーフローします。= 232+である2つの32ビットワードに分解してみましょう。bbcd

その場合、計算はそれほど難しくありません。

uint64_t mult_with_overflow_check(uint64_t a, uint64_t b) {
  if (a > b) return mult_with_overflow_check(b, a);
  if (a > UINT32_MAX) overflow();
  uint32_t c = b >> 32;
  uint32_t d = UINT32_MAX & b;
  uint64_t r = a * c;
  uint64_t s = a * d;
  if (r > UINT32_MAX) overflow();
  r <<= 32;
  return addition_with_overflow_check(s, r);
}

つまり、これは2つの乗算、2つのシフト、いくつかの加算、および条件チェックです。たとえば、2つの乗算を並列にパイプライン化できるため、これは除算よりも効率的です。何が自分に適しているかを確認するには、ベンチマークを行う必要があります。

于 2011-12-16T15:50:02.783 に答える
1

正確なオーバーフローは検出されない場合がありますが、一般に、乗算の結果を対数スケールでテストできます。

if (log(UINT64_MAX-1) - log(a) - log(b) < 0) overflow_detected(); // subtracting 1 to allow some tolerance when the numbers are converted to double
else prod = a * b;

正確なUINT64_MAXまで乗算を実行する必要があるかどうかによって異なります。そうでない場合、これは、大きな数の乗算をチェックするための非常にポータブルで便利な方法です。

于 2011-12-22T13:46:20.980 に答える
1 
case 6:
    for (a = 0; a < N; a++) {
        uint64_t b = a + c;
        uint64_t a1, b1;
        if (a > b) { a1 = a; b1 = b; }
        else       { a1 = b; b1 = a; }
        uint64_t cc = b1 * a1;
        c += cc;
        if (b1 > 0xffffffff) o++;
        else {
            uint64_t a1l = (a1 & 0xffffffff) + (a1 >> 32);
            a1l = (a1 + (a1 >> 32)) & 0xffffffff;
            uint64_t ab1l = a1l * b1;
            ab1l = (ab1l & 0xffffffff) + (ab1l >> 32);
            ab1l += (ab1l >> 32);
            uint64_t ccl = (cc & 0xffffffff) + (cc >> 32);
            ccl += (ccl >> 32);
            uint32_t ab32 = ab1l; if (ab32 == 0xffffffff) ab32 = 0;
            uint32_t cc32 = ccl; if (cc32 == 0xffffffff) cc32 = 0;
            if (ab32 != cc32) o++;
        }
    }
    break;

このメソッドは、通常の乗算​​の (オーバーフローの可能性がある) 結果を、オーバーフローできない乗算の結果と比較します。すべての計算はモジュロ (2^32 - 1) です。

Jens Gustedt の方法よりも複雑で (おそらく) 高速ではありません。

いくつかの小さな変更の後、96 ビット精度で乗算される場合があります (ただし、オーバーフロー制御はありません)。さらに興味深いことに、このメソッドのアイデアは、一連の算術演算 (乗算、加算、減算) のオーバーフローをチェックするために使用できます。

いくつかの質問に答えました

まず、について"your code is not portable"。uint64_tはい、元の質問で要求されている を使用しているため、コードは移植できません。厳密に言えば、(u)int64_t標準で要求されていないため、ポータブルな答えを得ることができません。

について"once some overflow happens, you can not assume the result value to be anything"。標準では、符号なし iteger はオーバーフローできないと規定されています。第 6.2.5 章、項目 9:

結果の符号なし整数型で表現できない結果は、結果の型で表現できる最大値よりも 1 大きい数値を法として減らされるため、符号なしオペランドを含む計算はオーバーフローすることはありません。

したがって、符号なし 64 ビット乗算は、オーバーフローなしで 2^64 を法として実行されます。

について"logic behind"。「ハッシュ関数」はここでは正しい言葉ではありません。モジュロ計算のみを使用します(2^32 - 1)。乗算の結果は として表すことができますn*2^64 + m。ここmで、 は目に見える結果であり、nオーバーフローする量を意味します。から2^64 = 1 (mod 2^32 - 1)、 を計算することができます[true value] - [visible value] = (n*2^64 + m) - m = n*2^64 = n (mod 2^32 - 1)。の計算値がnゼロでない場合は、オーバーフローが発生しています。ゼロの場合、オーバーフローはありません。の後にのみ衝突が発生する可能性がありn >= 2^32 - 1ます。被乗数の 1 つが より小さいことを確認するため、これは決して起こりません2^32。

于 2011-12-20T11:15:05.710 に答える
1

いくつかの（うまくいけば）役立つ答えを含む関連する質問：C/C++ で整数オーバーフローを検出する最良の方法。さらに、それはカバーするuint64_tだけではありません;）

于 2011-12-16T13:30:45.993 に答える