Fangen und berechnen Überlauf bei Multiplikation zweier großer Zahlen
https://stackoverflow.com/questions/1815367
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich bin auf der Suche nach einer effizienten (optional Standard, elegant und einfach zu implementieren) Lösung relativ große Zahlen zu multiplizieren, und das Ergebnis in eine oder mehr ganzen Zahlen:
Lassen Sie uns sagen, ich habe zwei 64-Bit-Integer wie folgt deklariert:
uint64_t a = xxx, b = yyy;
Wenn ich a * b tun, wie kann ich erkennen, ob die Operation zu einem Überlauf und in diesem Fall speichert die irgendwo tragen?
Bitte beachten Sie, dass Ich will keine große Anzahl Bibliothek verwenden , da ich Einschränkungen für die Art und Weise speichere ich die Zahlen.
Lösung
1. Erfassen der Überlauf :
x = a * b;
if (a != 0 && x / a != b) {
// overflow handling
}
Edit: Feste Division durch 0 (! Dank Mark)
2. Die Berechnung des Übertrags ist recht kompliziert. Ein Ansatz ist es, beide Operanden in Halbworte zu spalten, dann gelten lange Multiplikation auf die Hälfte -words:
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;
}
Um sicherzustellen, dass keine der Teilsummen sehen sich überlaufen kann, betrachten wir den schlimmsten Fall:
x = s2 + hi(a) * hi(b) + hi(x)
Lassen Sie B = 1 << 32. Wir haben dann
x <= (B - 1) + (B - 1)(B - 1) + (B - 1)
<= B*B - 1
< B*B
Ich glaube, dass dies funktionieren wird - zumindest es Griffe Sjlver des Testfalls. Abgesehen davon, es ist nicht getestet (und vielleicht nicht einmal kompilieren, da ich mehr, kein C ++ Compiler zur Hand haben).
Andere Tipps
Die Idee ist folgende Tatsache zu verwenden, die für die integrierten Betrieb wahr ist:
a*b > c, wenn und nur wenn a > c/b
/ ist integrale Abteilung hier.
Der Pseudo-Code zu überprüfen, gegen Überlauf für positive Zahlen folgt:
if (a> max_int64 / b) dann "Überlauf" else "ok" .
So behandeln Nullen und negative Zahlen Sie sollten mehr Kontrollen hinzuzufügen.
C-Code für nicht negative a und b folgt:
if (b > 0 && a > 18446744073709551615 / b) {
// overflow handling
}; else {
c = a * b;
}
Hinweis:
18446744073709551615 == (1<<64)-1
Übertrag berechnen wir Ansatz verwenden können Nummer in zwei 32-Ziffern zu spalten und sie vermehren sich wie wir auf dem Papier tun. Wir brauchen Zahlen aufteilen Überlauf zu vermeiden.
-Code folgt:
// split input numbers into 32-bit digits
uint64_t a0 = a & ((1LL<<32)-1);
uint64_t a1 = a >> 32;
uint64_t b0 = b & ((1LL<<32)-1);
uint64_t b1 = b >> 32;
// The following 3 lines of code is to calculate the carry of d1
// (d1 - 32-bit second digit of result, and it can be calculated as d1=d11+d12),
// but to avoid overflow.
// Actually rewriting the following 2 lines:
// uint64_t d1 = (a0 * b0 >> 32) + a1 * b0 + a0 * b1;
// uint64_t c1 = d1 >> 32;
uint64_t d11 = a1 * b0 + (a0 * b0 >> 32);
uint64_t d12 = a0 * b1;
uint64_t c1 = (d11 > 18446744073709551615 - d12) ? 1 : 0;
uint64_t d2 = a1 * b1 + c1;
uint64_t carry = d2; // needed carry stored here
Obwohl es mehrere andere Antworten auf diese Frage waren, ich von ihnen mehrere Code haben, der völlig ungetestet ist und bisher niemand angemessen auf die verschiedenen möglichen Optionen verglichen hat.
Aus diesem Grund schrieb ich und testete mehrere mögliche Implementierungen (die letzte basiert 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 mit verschiedenen Compilern und Systemen zu testen Ich habe (in diesem Fall alle Tests auf OS X getan wurde, aber die Ergebnisse sollten auf BSD oder Linux-Systemen ähnlich sein):
+------------------+----------+----------+----------+----------+----------+
| | 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 einige Schlüsse ziehen:
- Offensichtlich ist die Teilung basierten Ansatz, obwohl einfach und handlich, ist langsam.
- Keine Technik ist ein klarer Sieger in allen Fällen.
- Auf modernen Compiler, der Einsatz-a-größer-int Ansatz ist am besten, wenn Sie es verwenden können,
- Bei älteren Compiler, der lang Multiplikation Ansatz ist am besten
- Überraschenderweise GCC hat 4.9.0 Performance-Regressionen über GCC 4.2.1 und GCC 4.2.1 hat Performance-Regressionen über 3,3 GCC
Eine Version, die auch funktioniert, wenn a == 0:
x = a * b;
if (a != 0 && x / a != b) {
// overflow handling
}
Wenn Sie nicht brauchen nur einen Überlauf zu erfassen, sondern auch den Übertrag zu erfassen, sind Sie am besten von Ihren Zahlen nach unten in 32-Bit-Teile zu brechen. 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 Teilprodukte, sondern die Tatsache, dass jeder der Summen überlaufen kann.
Wenn ich das richtig zu tun habe, würde ich eine erweiterte-Multiply-Routine in der lokalen Assemblersprache schreiben. Das heißt zum Beispiel, multiplizieren zwei 64-Bit-Integer ein 128- zu erhalten Bit-Ergebnis, das in zwei 64-Bit-Registern gespeichert ist. All vernünftige Hardware diese Funktionalität in einem einzigen nativen mehrfach liefert Befehl es ist nicht nur von C aus.
Dies ist einer der seltenen Fälle, in denen die Lösung, die eleganteste und einfach zu programmieren ist eigentlich Assembler-Sprache zu verwenden. Aber es ist sicherlich nicht tragbar: - (
Ich habe diese Tage mit diesem Problem gearbeitet, und ich muss sagen, dass es mir die Anzahl der Male beeindruckt Ich habe Leute gesehen, die beste Art und Weise zu sagen wissen, ob es ein Überlauf wurde, ist das Ergebnis zu teilen, das ist völlig ineffizient und unnötig. Der Punkt für diese Funktion ist, dass es so schnell wie möglich sein muss.
Es gibt zwei Optionen für die Überlauferkennung:
1º- Wenn möglich, das Ergebnis Variable erstellen 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)
}
Sie werden wissen inmediately wenn ein Überlauf gewesen ist, und der Code ist die schnellstmögliche, ohne sie in Maschinencode zu schreiben. Je nach Compiler kann dieser Code in Maschinencode verbessert werden.
2º- ist unmöglich, eine Ergebnisgröße doppelt so groß wie die Multiplikatoren Variablen zu erstellen: Dann sollten Sie mit spielen, wenn die Bedingungen, den besten Weg zu bestimmen. 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, dass dieser Code hilft Ihnen, ein ziemlich effizientes Programm zu haben, und ich hoffe, dass der Code klar ist, wenn nicht ich einige coments gesetzt werden.
Mit freundlichen Grüßen.
Vielleicht ist der beste Weg, um dieses Problem zu lösen, ist eine Funktion zu haben, die zwei UInt64 multipliziert und ergeben ein Paar von UInt64, die einen oberen Teil und einen unteren Teil des UInt128 Ergebnisses. Hier ist die Lösung, einschließlich einer Funktion, die das Ergebnis im hex. Ich denke, man vielleicht eine C ++ Lösung bevorzugen, aber ich habe eine funktionierende Swift-Lösung, die zeigt, wie das Problem zu verwalten:
func hex128 (_ hi: UInt64, _ lo: UInt64) -> String
{
var s: String = String(format: "%08X", hi >> 32)
+ String(format: "%08X", hi & 0xFFFFFFFF)
+ String(format: "%08X", lo >> 32)
+ String(format: "%08X", lo & 0xFFFFFFFF)
return (s)
}
func mul64to128 (_ multiplier: UInt64, _ multiplicand : UInt64)
-> (result_hi: UInt64, result_lo: UInt64)
{
let x: UInt64 = multiplier
let x_lo: UInt64 = (x & 0xffffffff)
let x_hi: UInt64 = x >> 32
let y: UInt64 = multiplicand
let y_lo: UInt64 = (y & 0xffffffff)
let y_hi: UInt64 = y >> 32
let mul_lo: UInt64 = (x_lo * y_lo)
let mul_hi: UInt64 = (x_hi * y_lo) + (mul_lo >> 32)
let mul_carry: UInt64 = (x_lo * y_hi) + (mul_hi & 0xffffffff)
let result_hi: UInt64 = (x_hi * y_hi) + (mul_hi >> 32) + (mul_carry >> 32)
let result_lo: UInt64 = (mul_carry << 32) + (mul_lo & 0xffffffff)
return (result_hi, result_lo)
}
Hier ist ein Beispiel, um zu überprüfen, dass die Funktion funktioniert:
var c: UInt64 = 0
var d: UInt64 = 0
(c, d) = mul64to128(0x1234567890123456, 0x9876543210987654)
// 0AD77D742CE3C72E45FD10D81D28D038 is the result of the above example
print(hex128(c, d))
(c, d) = mul64to128(0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF)
// FFFFFFFFFFFFFFFE0000000000000001 is the result of the above example
print(hex128(c, d))
Hier ist ein Trick, zum Erfassen, ob die Multiplikation zweier ganzer Zahlen ohne Vorzeichen überläuft.
Wir machen die Beobachtung, dass, wenn wir einen N-Bit breiten Binärzahl mit einer M-Bit breiten binären Zahl multiplizieren, ist das Produkt nicht mehr als N + M Bits hat.
Zum Beispiel, wenn wir gefragt werden, eine Drei-Bit-Zahl mit neunundzwanzig Bit-Zahl zu multiplizieren, wir wissen, dass dies nicht Überlauf zweiunddreißig Bits.
#include <stdlib.h>
#include <stdio.h>
int might_be_mul_oflow(unsigned long a, unsigned long b)
{
if (!a || !b)
return 0;
a = a | (a >> 1) | (a >> 2) | (a >> 4) | (a >> 8) | (a >> 16) | (a >> 32);
b = b | (b >> 1) | (b >> 2) | (b >> 4) | (b >> 8) | (b >> 16) | (b >> 32);
for (;;) {
unsigned long na = a << 1;
if (na <= a)
break;
a = na;
}
return (a & b) ? 1 : 0;
}
int main(int argc, char **argv)
{
unsigned long a, b;
char *endptr;
if (argc < 3) {
printf("supply two unsigned long integers in C form\n");
return EXIT_FAILURE;
}
a = strtoul(argv[1], &endptr, 0);
if (*endptr != 0) {
printf("%s is garbage\n", argv[1]);
return EXIT_FAILURE;
}
b = strtoul(argv[2], &endptr, 0);
if (*endptr != 0) {
printf("%s is garbage\n", argv[2]);
return EXIT_FAILURE;
}
if (might_be_mul_oflow(a, b))
printf("might be multiplication overflow\n");
{
unsigned long c = a * b;
printf("%lu * %lu = %lu\n", a, b, c);
if (a != 0 && c / a != b)
printf("confirmed multiplication overflow\n");
}
return 0;
}
A smattering die Prüfungen: (auf 64-Bit-System):
$ ./uflow 0x3 0x3FFFFFFFFFFFFFFF 3 * 4611686018427387903 = 13835058055282163709 $ ./uflow 0x7 0x3FFFFFFFFFFFFFFF might be multiplication overflow 7 * 4611686018427387903 = 13835058055282163705 confirmed multiplication overflow $ ./uflow 0x4 0x3FFFFFFFFFFFFFFF might be multiplication overflow 4 * 4611686018427387903 = 18446744073709551612 $ ./uflow 0x5 0x3FFFFFFFFFFFFFFF might be multiplication overflow 5 * 4611686018427387903 = 4611686018427387899 confirmed multiplication overflow
Die Schritte in might_be_mul_oflow an Sicherheit grenzender Wahrscheinlichkeit langsamer als nur die Teilung Test zu tun, zumindest auf Mainstream-Prozessoren in Desktop-Workstations, Server und mobile Geräte verwendet. Auf Chips ohne gute Aufteilung Unterstützung, könnte es nützlich sein.
Es kommt zu mir, dass es eine andere Art und Weise ist diese frühe Ablehnung Test zu tun.
-
Wir beginnen mit einem Zahlenpaar
arngundbrng, die0x7FFF...FFFFund1initialisiert werden. -
Wenn
a <= arngundb <= brngkönnen wir schließen, dass es keinen Überlauf ist. -
Ansonsten verschieben wir
arngnach rechts, und verschiebenbrngnach links und fügte hinzu, ein Bit zubrng, so dass sie0x3FFF...FFFFund3sind. -
Wenn
arngNull ist, zu vollenden; wiederholen sonst bei 2.
Die Funktion nun wie folgt aussieht:
int might_be_mul_oflow(unsigned long a, unsigned long b)
{
if (!a || !b)
return 0;
{
unsigned long arng = ULONG_MAX >> 1;
unsigned long brng = 1;
while (arng != 0) {
if (a <= arng && b <= brng)
return 0;
arng >>= 1;
brng <<= 1;
brng |= 1;
}
return 1;
}
}
Wenn Sie wollen einfach nur Überlauf zu erfassen, wie etwa die Umwandlung der Multiplikation und wenn
zu verdoppeln, zu tun| x | <2 ^ 53, konvertieren INT64
| x | <2 ^ 63, macht die Multiplikation mit int64
sonst produzieren, was Fehler, den Sie wollen?
Dies scheint zu funktionieren:
int64_t safemult(int64_t a, int64_t b) {
double dx;
dx = (double)a * (double)b;
if ( fabs(dx) < (double)9007199254740992 )
return (int64_t)dx;
if ( (double)INT64_MAX < fabs(dx) )
return INT64_MAX;
return a*b;
}
