Die sicherste und effizienteste Methode zum Berechnen einer ganzzahligen Operation, die überlaufen kann

Angenommen, wir haben 2 Konstanten A & B und eine Variable i, alle 64-Bit-Ganzzahlen. Und wir wollen eine einfache allgemeine arithmetische Operation berechnen, wie zum Beispiel:

i * A / B    (1)

Um das Problem zu vereinfachen, nehmen wir diese Variable an i ist immer im Sortiment [INT64_MIN*B/A, INT64_MAX*B/A]damit das Endergebnis der arithmetischen Operation (1) nicht überläuft (also: passt im Sortiment [INT64_MIN, INT64_MAX]).

Zusätzlich, i wird eher in der angenommen freundlich Angebot Bereich1 = [INT64_MIN/A, INT64_MAX/A] (dh: nahe 0), jedoch i kann (weniger wahrscheinlich) außerhalb dieses Bereichs liegen. Im ersten Fall eine triviale ganzzahlige Berechnung von i * A würde nicht überlaufen (deshalb haben wir den Bereich genannt freundlich); und im letzteren Fall eine triviale ganzzahlige Berechnung von i * A würde überlaufen, was zu einem fehlerhaften Ergebnis bei der Berechnung von (1) führen würde.

Was wäre der „sicherste“ und „effizienteste“ Weg, um die Operation (1) zu berechnen (wobei „sicher“ bedeutet: Beibehaltung der Genauigkeit oder zumindest einer anständigen Genauigkeit, und „am effizientesten“ bedeutet: niedrigste durchschnittliche Rechenzeit), vorausgesetzt i ist eher in der freundlich Angebot Bereich1.

Derzeit ist die derzeit im Code implementierte Lösung die folgende:

(int64_t)((double)A / B * i)

Diese Lösung ist ziemlich sicher (kein Überlauf), aber ungenau (Präzisionsverlust aufgrund der doppelten signifikanten 53-Bit-Beschränkung) und ziemlich schnell, weil doppelte Division (double)A / B wird zur Kompilierzeit vorberechnet, sodass zur Laufzeit nur eine doppelte Multiplikation berechnet werden kann.

Wenn Sie die betroffenen Bereiche nicht besser eingrenzen können, befolgen Sie am besten die Ratschläge von iammilind __int128.

Der Grund dafür ist, dass Sie andernfalls die vollständige Logik der Wort-zu-Doppelwort-Multiplikation und der Doppelwort-zu-Wort-Division implementieren müssten. Die Intel- und AMD-Prozessorhandbücher enthalten hilfreiche Informationen und vorgefertigten Code, aber es wird ziemlich kompliziert, und die Verwendung von C/C++ anstelle von Assembler macht die Dinge doppelt kompliziert.

Alle guten Compiler legen nützliche Primitive als Intrinsics offen. Liste von Microsoft scheint kein muldiv-ähnliches Primitiv zu enthalten, aber das __mul128 Intrinsic gibt Ihnen die beiden Hälften des 128-Bit-Produkts als zwei 64-Bit-Ganzzahlen. Auf dieser Grundlage können Sie eine lange Division von zwei Ziffern durch eine Ziffer durchführen, wobei eine „Ziffer“ eine 64-Bit-Ganzzahl wäre (normalerweise „Glied“ genannt, weil größer als eine Ziffer, aber immer noch nur ein Teil des Ganzen). Immer noch ziemlich kompliziert, aber viel besser als die Verwendung von reinem C/C++. In Bezug auf die Portabilität ist es jedoch nicht besser als die Verwendung __int128 direkt. Zumindest haben die Compiler-Implementierer auf diese Weise bereits die ganze harte Arbeit für Sie erledigt.

Wenn Ihre Anwendungsdomäne Ihnen nützliche Grenzen geben kann, so (u % d) * v wird nicht überlaufen, dann können Sie die Identität verwenden

(u * v) / d = (u / d) * v + ((u % d) * v) / d

wo / bedeutet ganzzahlige Division, solange u nichtnegativ und d positiv ist (andernfalls könnten Sie mit dem Spielraum in Konflikt geraten, der für die Semantik von operator zulässig ist %).

In jedem Fall müssen Sie möglicherweise die Vorzeichen der Operanden trennen und vorzeichenlose Operationen verwenden, um nützlichere Mechanismen zu finden, die Sie ausnutzen können – oder um Sabotage durch den Compiler zu umgehen, wie die von Ihnen erwähnte sättigende Multiplikation. Der Überlauf von Operationen mit vorzeichenbehafteten Ganzzahlen ruft undefiniertes Verhalten hervor, Compiler können tun, was sie wollen. Im Gegensatz dazu ist der Überlauf für vorzeichenlose Typen wohldefiniert.

Auch bei unsignierten Typen können Sie auf solche Regeln zurückgreifen s = a (+) b (wo (+) ist möglicherweise überlaufender vorzeichenloser Zusatz) Sie werden beides haben s == a + b oder s < a && s < bwodurch Sie mit billigen Operationen nachträglich einen Überlauf erkennen können.

Allerdings werden Sie auf diesem Weg wahrscheinlich nicht viel weiter kommen, da der erforderliche Aufwand schnell an den Aufwand für die Durchführung der zuvor erwähnten Doppeloperationen heranreicht oder diese sogar übersteigt. Nur eine gründliche Analyse der Anwendungsdomäne könnte die Informationen liefern, die für die Planung/Bereitstellung solcher Verknüpfungen erforderlich sind. Im allgemeinen Fall und mit den von Ihnen angegebenen Grenzen haben Sie ziemlich Pech.

Um eine quantifizierte Antwort auf die Frage zu geben, habe ich einen Benchmark verschiedener Lösungen als Teil der hier in diesem Beitrag vorgeschlagenen Lösungen erstellt (dank Kommentare und Antworten).

Der Benchmark misst die Rechenzeit verschiedener Implementierungen, wann i ist drinnen freundlich Angebot Bereich1 = [INT64_MIN/A, INT64_MAX/A]und wann i ist außerhalb der freundlich Bereich (noch in der sicher Angebot Bereich2 = [INT64_MIN*B/A, INT64_MAX*B/A]).

Jede Implementierung führt eine “sichere” (dh ohne Überlauf) Berechnung der Operation durch: i * A / B (außer der 1. Implementierung, angegeben als Referenzrechenzeit). Einige Implementierungen können jedoch selten ungenaue Berechnungsergebnisse zurückgeben (welches Verhalten gemeldet wird).

Einige vorgeschlagene Lösungen wurden nicht getestet oder sind nachstehend nicht aufgeführt; diese sind: Lösung mit __int128 (vom ms vc-Compiler nicht unterstützt), noch steigern int128_t wurde stattdessen verwendet; Lösungen mit erweiterten 80 Bit long double (wird vom ms vc-Compiler nicht unterstützt); Lösung verwenden InfInt (funktioniert und getestet, aber zu langsam, um ein anständiger Konkurrent zu sein).

Zeitmessungen werden in ps/op (Pikosekunden pro Operation) angegeben. Benchmark-Plattform ist ein Intel Q6600@3GHz unter Windows 7 x64, ausführbar, kompiliert mit MS vc14, x64/Release-Target. Die Variablen, Konstanten und Funktionen, auf die im Folgenden verwiesen wird, sind wie folgt definiert:

int64_t       i;
const int64_t A     = 1234567891;
const int64_t B     = 4321987;
inline bool   in_safe_range(int64_t i) { return (INT64_MIN/A <= i) && (i <= INT64_MAX/A); }

1. (i * A / B) [reference]
   ich in Bereich1: 1469 ps/op, ich außen Bereich1: irrelevant (überläuft)
2. ((int64_t)((double)i * A / B))
   ich in Bereich1: 10613 ps/op, ich außen Bereich1: 10606 ps/op

   Hinweis: Seltenes ungenaues Ergebnis (maximaler Fehler = 1 Bit) im gesamten Bereich Reichweite2

3. ((int64_t)((double)A / B * i))
   ich in Bereich1: 1073ps/op, ich außen Bereich1: 1071ps/op

   Hinweis: Seltenes ungenaues Ergebnis (maximaler Fehler = 1 Bit) im gesamten Bereich Reichweite2

   Hinweis: Der Compiler berechnet wahrscheinlich vor (double)A / B was zu der beobachteten Leistungssteigerung gegenüber der vorherigen Lösung führt.

4. (!in_safe_range(i) ? (int64_t)((double)A / B * i) : (i * A / B))
   ich in Bereich1: 2009 ps/op, ich außen Bereich1: 1606 ps/op

   Hinweis: seltenes ungenaues Ergebnis (max. Fehler = 1 Bit) außerhalb Bereich1
5. ((int64_t)((int128_t)i * A / B)) [boost int128_t]
   ich in Bereich1: 89924 ps/op, ich außen Bereich1: 89289 ps/op

   Hinweis: steigern int128_t schneidet auf der Bankplattform dramatisch schlecht ab (keine Ahnung warum)

6. ((i / B) * A + ((i % B) * A) / B)
   ich in Bereich1: 5876 ps/op, ich außen Bereich1: 5879 ps/op
7. (!in_safe_range(i) ? ((i / B) * A + ((i % B) * A) / B) : (i * A / B))
   ich in Bereich1: 1999 ps/op, ich außen Bereich1: 6135 ps/op

Fazit

a) Wenn im gesamten Bereich geringfügige Rechenfehler akzeptabel sind Reichweite2dann Lösung (3) ist die schnellste, sogar schneller als die als Referenz angegebene direkte ganzzahlige Berechnung.
b) Wenn Berechnungsfehler inakzeptabel sind freundlich Angebot Bereich1jedoch außerhalb dieses Bereichs akzeptabel, dann Lösung (4) ist der schnellste.
c) Wenn Berechnungsfehler im gesamten Bereich nicht akzeptabel sind Reichweite2dann Lösung (7) führt so gut wie Lösung (4) in der freundlich Angebot Bereich1und bleibt außerhalb dieses Bereichs ordentlich schnell.

Ich denke, Sie können den Überlauf erkennen, bevor er passiert. In Ihrem Fall von i * A / BSie sind nur besorgt über die i * A Teil, weil die Division nicht überlaufen kann.

Sie können den Überlauf erkennen, indem Sie einen Test von durchführen bool overflow = i > INT64_MAX / A. Diese müssen Sie je nach Vorzeichen von Operanden und Ergebnis modifizieren.

Einige Implementierungen erlauben __int128_t. Überprüfen Sie, ob Ihre Implementierung dies zulässt, damit Sie sie stattdessen als Platzhalter verwenden können double. Siehe folgenden Beitrag:
Warum gibt es kein int128_t?

Wenn Sie nicht sehr besorgt über die “Schnelligkeit” sind, würde ich für eine gute Portabilität vorschlagen, nur die Header-C++-Bibliothek zu verwenden “InfInt”.

Es ist ziemlich einfach, die Bibliothek zu benutzen. Erstellen Sie einfach eine Instanz der Klasse InfInt und verwenden Sie sie:

InfInt myint1 = "15432154865413186646848435184100510168404641560358"; 
InfInt myint2 = 156341300544608LL;

myint1 *= --myint2 - 3;
std::cout << myint1 << std::endl;

Ich bin mir bei den Wertgrenzen nicht sicher, will (i / B) * A + (i % B) * A / B Hilfe?