Fang-und compute-überlauf bei der Multiplikation von zwei großen Ganzzahlen

1. Erkennung von überlauf:

x = a * b;
if (a != 0 && x / a != b) {
    //overflow handling
}

Edit: Fixed division durch 0 (danke Mark!)

2. Computing das tragen ist ziemlich beteiligt. Ein Ansatz HIERFÜR ist die split werden beide Operanden in halben Worten, dann bewerben Sie sich lange Multiplikation um die Hälfte-Wörter:

uint64_t hi(uint64_t x) {
    return x >> 32;
}

uint64_t lo(uint64_t x) {
    return ((1L << 32) - 1) & x;
}

void multiply(uint64_t a, uint64_t b) {
    //actually uint32_t would do, but the casting is annoying
    uint64_t s0, s1, s2, s3; 

    uint64_t x = lo(a) * lo(b);
    s0 = lo(x);

    x = hi(a) * lo(b) + hi(x);
    s1 = lo(x);
    s2 = hi(x);

    x = s1 + lo(a) * hi(b);
    s1 = lo(x);

    x = s2 + hi(a) * hi(b) + hi(x);
    s2 = lo(x);
    s3 = hi(x);

    uint64_t result = s1 << 32 | s0;
    uint64_t carry = s3 << 32 | s2;
}

Zu sehen, dass keine der partiellen Summen selbst überlauf, betrachten wir den schlimmsten Fall:

        x = s2 + hi(a) * hi(b) + hi(x)

Lassen B = 1 << 32. Wir haben dann

            x <= (B - 1) + (B - 1)(B - 1) + (B - 1)
              <= B*B - 1
               < B*B

Ich glaube, das wird funktionieren - zumindest ist es verarbeitet Sjlver test-Fall. Abgesehen davon, dass es nicht getestet ist (und vielleicht nicht einmal kompilieren, da ich nicht über ein C++ - compiler zur hand mehr).

Obwohl es schon einige andere Antworten auf diese Frage, ich, einige von Ihnen haben code ist komplett ungetestet, und so weit niemand hat angemessen im Vergleich der verschiedenen möglichen Optionen.

Aus diesem Grund habe ich geschrieben und getestet mehrere mögliche Implementierungen (die Letzte ist, basierend auf dieser code von OpenBSD, diskutiert auf Reddit hier). Hier ist der code:

/* Multiply with overflow checking, emulating clang's builtin function
 *
 *     __builtin_umull_overflow
 *
 * This code benchmarks five possible schemes for doing so.
 */

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

#ifndef BOOL
    #define BOOL int
#endif

//Option 1, check for overflow a wider type
//   - Often fastest and the least code, especially on modern compilers
//   - When long is a 64-bit int, requires compiler support for 128-bits
//     ints (requires GCC >= 3.0 or Clang)

#if LONG_BIT > 32
    typedef __uint128_t long_overflow_t ;
#else
    typedef uint64_t long_overflow_t;
#endif

BOOL 
umull_overflow1(unsigned long lhs, unsigned long rhs, unsigned long* result)
{
        long_overflow_t prod = (long_overflow_t)lhs * (long_overflow_t)rhs;
        *result = (unsigned long) prod;
        return (prod >> LONG_BIT) != 0;
}

//Option 2, perform long multiplication using a smaller type
//   - Sometimes the fastest (e.g., when mulitply on longs is a library
//     call).
//   - Performs at most three multiplies, and sometimes only performs one.
//   - Highly portable code; works no matter how many bits unsigned long is

BOOL 
umull_overflow2(unsigned long lhs, unsigned long rhs, unsigned long* result)
{
        const unsigned long HALFSIZE_MAX = (1ul << LONG_BIT/2) - 1ul;
        unsigned long lhs_high = lhs >> LONG_BIT/2;
        unsigned long lhs_low  = lhs & HALFSIZE_MAX;
        unsigned long rhs_high = rhs >> LONG_BIT/2;
        unsigned long rhs_low  = rhs & HALFSIZE_MAX;

        unsigned long bot_bits = lhs_low * rhs_low;
        if (!(lhs_high || rhs_high)) {
            *result = bot_bits;
            return 0; 
        }
        BOOL overflowed = lhs_high && rhs_high;
        unsigned long mid_bits1 = lhs_low * rhs_high;
        unsigned long mid_bits2 = lhs_high * rhs_low;

        *result = bot_bits + ((mid_bits1+mid_bits2) << LONG_BIT/2);
        return overflowed || *result < bot_bits
            || (mid_bits1 >> LONG_BIT/2) != 0
            || (mid_bits2 >> LONG_BIT/2) != 0;
}

//Option 3, perform long multiplication using a smaller type (this code is
//very similar to option 2, but calculates overflow using a different but
//equivalent method).
//   - Sometimes the fastest (e.g., when mulitply on longs is a library
//     call; clang likes this code).
//   - Performs at most three multiplies, and sometimes only performs one.
//   - Highly portable code; works no matter how many bits unsigned long is

BOOL 
umull_overflow3(unsigned long lhs, unsigned long rhs, unsigned long* result)
{
        const unsigned long HALFSIZE_MAX = (1ul << LONG_BIT/2) - 1ul;
        unsigned long lhs_high = lhs >> LONG_BIT/2;
        unsigned long lhs_low  = lhs & HALFSIZE_MAX;
        unsigned long rhs_high = rhs >> LONG_BIT/2;
        unsigned long rhs_low  = rhs & HALFSIZE_MAX;

        unsigned long lowbits = lhs_low * rhs_low;
        if (!(lhs_high || rhs_high)) {
            *result = lowbits;
            return 0; 
        }
        BOOL overflowed = lhs_high && rhs_high;
        unsigned long midbits1 = lhs_low * rhs_high;
        unsigned long midbits2 = lhs_high * rhs_low;
        unsigned long midbits  = midbits1 + midbits2;
        overflowed = overflowed || midbits < midbits1 || midbits > HALFSIZE_MAX;
        unsigned long product = lowbits + (midbits << LONG_BIT/2);
        overflowed = overflowed || product < lowbits;

        *result = product;
        return overflowed;
}

//Option 4, checks for overflow using division
//   - Checks for overflow using division
//   - Division is slow, especially if it is a library call

BOOL
umull_overflow4(unsigned long lhs, unsigned long rhs, unsigned long* result)
{
        *result = lhs * rhs;
        return rhs > 0 && (SIZE_MAX / rhs) < lhs;
}

//Option 5, checks for overflow using division
//   - Checks for overflow using division
//   - Avoids division when the numbers are "small enough" to trivially
//     rule out overflow
//   - Division is slow, especially if it is a library call

BOOL
umull_overflow5(unsigned long lhs, unsigned long rhs, unsigned long* result)
{
        const unsigned long MUL_NO_OVERFLOW = (1ul << LONG_BIT/2) - 1ul;
        *result = lhs * rhs;
        return (lhs >= MUL_NO_OVERFLOW || rhs >= MUL_NO_OVERFLOW) &&
            rhs > 0 && SIZE_MAX / rhs < lhs;
}

#ifndef umull_overflow
    #define umull_overflow2
#endif

/*
 * This benchmark code performs a multiply at all bit sizes, 
 * essentially assuming that sizes are logarithmically distributed.
 */

int main()
{
        unsigned long i, j, k;
        int count = 0;
        unsigned long mult;
        unsigned long total = 0;

        for (k = 0; k < 0x40000000 / LONG_BIT / LONG_BIT; ++k)
                for (i = 0; i != LONG_MAX; i = i*2+1)
                        for (j = 0; j != LONG_MAX; j = j*2+1) {
                                count += umull_overflow(i+k, j+k, &mult);
                                total += mult;
                        }
        printf("%d overflows (total %lu)\n", count, total);
}

Hier sind die Ergebnisse der Tests mit verschiedenen Compilern und Systemen ich habe (in diesem Fall werden alle Tests durchgeführt, die auf OS X, aber die Ergebnisse sollten ähnlich sein wie bei BSD oder Linux Systeme):

+------------------+----------+----------+----------+----------+----------+
|                  | Option 1 | Option 2 | Option 3 | Option 4 | Option 5 |
|                  |  BigInt  | LngMult1 | LngMult2 |   Div    |  OptDiv  |
+------------------+----------+----------+----------+----------+----------+
| Clang 3.5 i386   |    1.610 |    3.217 |    3.129 |    4.405 |    4.398 |
| GCC 4.9.0 i386   |    1.488 |    3.469 |    5.853 |    4.704 |    4.712 |
| GCC 4.2.1 i386   |    2.842 |    4.022 |    3.629 |    4.160 |    4.696 |
| GCC 4.2.1 PPC32  |    8.227 |    7.756 |    7.242 |   20.632 |   20.481 |
| GCC 3.3   PPC32  |    5.684 |    9.804 |   11.525 |   21.734 |   22.517 |
+------------------+----------+----------+----------+----------+----------+
| Clang 3.5 x86_64 |    1.584 |    2.472 |    2.449 |    9.246 |    7.280 |
| GCC 4.9 x86_64   |    1.414 |    2.623 |    4.327 |    9.047 |    7.538 |
| GCC 4.2.1 x86_64 |    2.143 |    2.618 |    2.750 |    9.510 |    7.389 |
| GCC 4.2.1 PPC64  |   13.178 |    8.994 |    8.567 |   37.504 |   29.851 |
+------------------+----------+----------+----------+----------+----------+

Basierend auf diesen Ergebnissen, können wir ziehen ein paar Folgerungen:

• Klar, die division-basierten Ansatz, obwohl einfache und tragbar, ist langsam.
• Keine Technik ist ein klarer Sieger in allen Fällen.
• Auf moderne Compiler, der-einen-größeren-int-Ansatz ist am besten, wenn Sie es verwenden können
• Auf älteren Compilern, die long-Multiplikation Ansatz ist am besten
• Überraschend, GCC 4.9.0 hat performance-Regressionen über das GCC-4.2.1 und GCC 4.2.1, hat die Leistung Regressionen über das GCC-3.3

Wenn Sie nicht nur brauchen, um zu erkennen, überlauf, sondern auch zu erfassen, die tragen, sind Sie am besten aus, dass Sie Ihre zahlen nach unten in die 32-bit-Teile. Der code ist ein Alptraum; was folgt, ist nur eine Skizze:

#include <stdint.h>

uint64_t mul(uint64_t a, uint64_t b) {
  uint32_t ah = a >> 32;
  uint32_t al = a;  //truncates: now a = al + 2**32 * ah
  uint32_t bh = b >> 32;
  uint32_t bl = b;  //truncates: now b = bl + 2**32 * bh
  //a * b = 2**64 * ah * bh + 2**32 * (ah * bl + bh * al) + al * bl
  uint64_t partial = (uint64_t) al * (uint64_t) bl;
  uint64_t mid1    = (uint64_t) ah * (uint64_t) bl;
  uint64_t mid2    = (uint64_t) al * (uint64_t) bh;
  uint64_t carry   = (uint64_t) ah * (uint64_t) bh;
  //add high parts of mid1 and mid2 to carry
  //add low parts of mid1 and mid2 to partial, carrying
  //   any carry bits into carry...
}

Das problem ist nicht nur die teilweise Produkte, sondern die Tatsache, dass jede der Summen kann überlaufen.

Wenn ich hatte dies für real, ich würde schreiben Sie eine extended-multiplizieren routine in der lokalen assembly language. Das heißt, zum Beispiel, multiplizieren von zwei 64-bit-Ganzzahlen um eine 128-bit-Ergebnis, das gespeichert ist, in zwei 64-bit-Register. Alle vernünftigen hardware bietet diese Funktionalität in einer einzigen nativen multiplizieren Unterricht—es ist nicht nur zugänglich von C.

Dies ist einer jener seltenen Fälle, in denen die Lösung, die am meisten elegante und einfach zu Programmieren ist eigentlich assembly-Sprache verwenden. Aber es ist sicherlich nicht tragbar 🙁

Habe ich daran gearbeitet, dieses problem dieser Tage und ich muss sagen, es hat mich beeindruckt die Anzahl der Zeiten ich habe gesehen, Menschen, die sagen, der beste Weg, zu wissen, ob es ein überlauf ist, teilen Sie das Resultat, das ist völlig ineffizient und unnötig. Der Punkt für diese Funktion ist, dass es sein muss, so schnell wie möglich.

Gibt es zwei Optionen für die überlauf-Erkennung:

1º - Wenn möglich, erstellen der Ergebnis-variable als doppelt so groß wie die Multiplikatoren, zum Beispiel:

struct INT32struct {INT16 high, low;};
typedef union
{
  struct INT32struct s;
  INT32 ll;
} INT32union;

INT16 mulFunction(INT16 a, INT16 b)
{
  INT32union result.ll = a * b; //32Bits result
  if(result.s.high > 0) 
      Overflow();
  return (result.s.low)
}

Wissen Sie unseren Kurs, wenn es zu einem überlauf, und der code ist am schnellsten möglich, ohne dass das schreiben in Maschinen-code. Je nach compiler dieser code kann verbessert werden, in Maschinen-code.

2º - Ist unmöglich zu schaffen, eine Ergebnis-variable zweimal so groß wie die Multiplikatoren variable:
Dann sollten Sie spielen mit, wenn die Bedingungen zu bestimmen, den besten Weg. Weiter mit dem Beispiel:

INT32 mulFunction(INT32 a, INT32 b)
{

  INT32union s_a.ll = abs(a);
  INT32union s_b.ll = abs(b); //32Bits result
  INT32union result;
  if(s_a.s.hi > 0 && s_b.s.hi > 0)
  {
      Overflow();
  }
  else if (s_a.s.hi > 0)
  {
      INT32union res1.ll = s_a.s.hi * s_b.s.lo;
      INT32union res2.ll = s_a.s.lo * s_b.s.lo;
      if (res1.hi == 0)
      {
          result.s.lo = res1.s.lo + res2.s.hi;
          if (result.s.hi == 0)
          {
            result.s.ll = result.s.lo << 16 + res2.s.lo;
            if ((a.s.hi >> 15) ^ (b.s.hi >> 15) == 1)
            {
                result.s.ll = -result.s.ll; 
            }
            return result.s.ll
          }else
          {
             Overflow();
          }
      }else
      {
          Overflow();
      }
  }else if (s_b.s.hi > 0)
{

   //Same code changing a with b

}else 
{
    return (s_a.lo * s_b.lo);
}
}

Ich hoffe, dieser code hilft Sie haben ein sehr effizientes Programm, und ich hoffe, der code ist klar,, wenn nicht, werde ich einige coments.

beste Grüße.

Einfach und schnell mit clang und gcc:

unsigned long long t a, b, result;
if (__builtin_umulll_overflow(a, b, &result)) {
    //overflow!!
}

Dies wird mit hardware-Unterstützung für überlauf-Erkennung verfügbar. Durch compiler-Erweiterungen kann es auch handhaben-Ganzzahl-überlauf (ersetzen umul mit smul), eventhough das ist Undefiniertes Verhalten in C++.