Ich muss diese Gleichung in C / C ++ berechnen:
%Vor% mit a, b, c, x vom Typ __int64 (a, b, c, x & lt; 10 ^ 13). In allen Fällen wird a, b, c ausgewählt, um x in __int64 anzupassen.
Jedoch ist a * b sehr groß, was Überlauf verursacht und x ist falsch.
Ich versuche a * b durch typecasting zu trennen:
Auf diese Weise wird a / c zuerst berechnet und es tritt kein Überlauffehler auf.
Allerdings ist das Problem ((doppelt) a / c) * (doppelt) b haben manchmal großen Wert (etwa Milliarden) und die Genauigkeit ist reduziert, so dass 1,0 / c (sehr klein) keine Wirkung und verursachen einen Fehler innerhalb + -1.
Beispiel: (__int64) (((doppelt) a / c) * (doppelt) b = 123456789.01 wird eher 123456789.0 und 1.0 / c = 0.02 In diesem Fall liegt ein Fehler von +1 vor.
Gibt es eine Möglichkeit, x ohne externe Bibliothek wie Boost oder Bignum zu berechnen? Selbst mit Fehler + -1 kann ich meinen Code vermasseln.
Vielen Dank im Voraus.
Übrigens benutze ich Visual Studio 10.
Sie könnten die lange Arithmetik von Hand implementieren und mit 32-Bit-Blöcken arbeiten:
Lange Multiplikation:
%Vor%Schulteilung, angenommene vorzeichenlose Arithmetik:
%Vor% Wenn a und b signiert sind, fixiere das Zeichen zuerst und berechne mit absoluten Werten, wie von @Serge vorgeschlagen:
Wenn a oder b Null ist, x=(-1)/c
Andernfalls sign(x)=sign(a)*sign(b)*sign(c)
Wenn Ihr Code CPU-abhängig sein kann, könnte es am einfachsten sein, Assembler zu verwenden, um die höherwertigen 8 Byte zu behalten. x64, nimmt an, dass das Ergebnis in 8 Bytes passt:
%Vor%[1] Ссылка
Versuchen Sie, den maximalen Multiplikator für a herauszufinden, der nicht überläuft. Zum Beispiel, wenn ein * 4 einen Überlauf machen würde, dann tu es teilweise:
%Vor%also, wenn Sie mittlere Werte wie
finden %Vor%dann
%Vor%Sie finden den größten verfügbaren Wert von b1 = floor (MAX_INT / a), dann ist b2 der Rest von b nur wenn b-b1 & lt; b1 wenn nicht müssen Sie wiederholen.
Sie können Ihre Berechnung vielleicht einfach neu anordnen:
%Vor%Das Problem wäre ein Genauigkeitsverlust. Dies kann minimiert werden, indem die Wertebereiche verfolgt und Skalierungsfaktoren eingeführt werden (um Zwischenwerte so groß wie möglich ohne Überlauf zu machen).
Wenn a beispielsweise zwischen 0 und 1024 liegt, kann b von 0 bis 16777215 und c zwischen 4096 und 8192 liegen. dann:
In diesem Fall (256*b) <= 0xFFFFFF00 (so groß wie möglich, um das Überlaufen einer 32-Bit-Ganzzahl ohne Vorzeichen zu vermeiden), ( (256*b) / c) <= 0x000FFFFF und a * ((256*b) /c) <= 0x3FFFFC00 .
Auch für diesen Fall wäre a*b (aus der ursprünglichen Formel) eine 32-Bit-Ganzzahl ohne Vorzeichen übergelaufen; und b/c (von der ersten Umordnung) hätte 8 Bits Genauigkeit mehr verloren als (256 * b) / c .
Natürlich hängt die beste Formel (diejenige, die den geringsten Präzisionsverlust ohne Überlauf ergibt) für Ihren speziellen Fall von den möglichen Bereichen der Variablen in Ihrem speziellen Fall ab.