C++: Register Überlauf beim Rechnen abfangen

[Tom]

Hello,

kann mir jemand der C++ Profis einen Hinweis geben, wo ich suchen muss?
Wie kann ich in C++ einen Überlauf-Fehler abfangen, wie er z.B. bei der Berechnung einer Fakultät recht schnell auftritt?

unsigned int Fakultaet::calc(const int op)
{
// errno = 0; // ist nur für IO
 unsigned int result = 1;

for (int i = 1; i <= op; i++)
 {
            try           // nur zum Testen eingebaut...
            {
         result *= i;
            }
            catch (std::exception &e)
            {
                std::cerr << e.what() << std::endl;
            }
 }

return result;
}

So geht es leider nicht.
Eingebunden ist <stdexcept>

Kann man die Flags abfragen? Aber dazu müsste man wissen, welches Register als Zielregister beio der Multiplikation benutzt wird und außerdem sollte das in einer Hochsprache auch deren Sachen sein?!

Liebe Grüße aus Syburg bei Dortmund

Tom vom Berg

[Marc Reichelt]

Hallo Tom,

kann mir jemand der C++ Profis einen Hinweis geben, wo ich suchen muss?
Wie kann ich in C++ einen Überlauf-Fehler abfangen, wie er z.B. bei der Berechnung einer Fakultät recht schnell auftritt?

Soweit ich das eben durch kurze Recherche festgestellt habe hast du in C oder C++ keine Möglichkeit, im Nachhinein zu testen ob ein Überlauf aufgetreten ist.
Als verantwortungsbewusster Programmierer musst du dafür sorgen, dass kein Überlauf auftritt - etwa durch das Werfen einer entsprechenden Exception, wenn der Wert für die Fakultäts-Funktion zu groß ist.

Dafür liefert die Bibliothek <stdexcept> dir immerhin schon mal einen "overflow_error".

Grüße

Marc Reichelt || http://www.marcreichelt.de/

[Tom]

Hello,

Soweit ich das eben durch kurze Recherche festgestellt habe hast du in C oder C++ keine Möglichkeit, im Nachhinein zu testen ob ein Überlauf aufgetreten ist.
Als verantwortungsbewusster Programmierer musst du dafür sorgen, dass kein Überlauf auftritt - etwa durch das Werfen einer entsprechenden Exception, wenn der Wert für die Fakultäts-Funktion zu groß ist.

Das dafür sorgen, tue ich ja durch die Abfrage des Carry-Flags, so es denn möglich ist. Das ist zulässig und mMn auch der einzig richtige Weg.

Das habe ich befürchtet.
Auf einer Intel-Plattform iX86 wird allerdings bei einem MUL-Befehl bei Überlauf das Carry-Flag gesetzt. Wenn eine Hochsprache das nicht abfragbar machte, wäre ihr Entwickler dämlich. Da ich den Bjarne eher für pfiffig halte, wird es etwas geben. Schade nur, dass man so sehr danach suchen muss. Es sind jetzt schon ca. 12 Mannstunden draufgegangen. Dabei gibt es an diversen Stellen ebensolche Vermutungen, dass es eine Compilereinstellung sein könnte, die das CF nach der Multiplikation zugänglich macht.

Ich vermute eine Compiler-Einstellung.
Leider kenne ich die auch nicht

Dafür liefert die Bibliothek <stdexcept> dir immerhin schon mal einen "overflow_error".

Ja, soweit war ich schon.

Liebe Grüße aus Syburg bei Dortmund

Tom vom Berg

[EisFuX]

(H[ae]llo|Hi(ho)|Nabend) Tom,

kann mir jemand der C++ Profis einen Hinweis geben, wo ich suchen muss?
Wie kann ich in C++ einen Überlauf-Fehler abfangen, wie er z.B. bei der Berechnung einer Fakultät recht schnell auftritt?

http://www.fefe.de/intof.html
Suche nach der Überschrift "Issue 3: Multiplication can overflow, too".

Kann man die Flags abfragen? Aber dazu müsste man wissen, welches Register als Zielregister beio der Multiplikation benutzt wird und außerdem sollte das in einer Hochsprache auch deren Sachen sein?!

Um Prozessor-Flags "in C abzufragen" würden mir höchstens eingestreute Inline-Assembler einfallen. Das hat dann zwar nicht mehr viel mit C zu tun, aber es ist auch Wurst, in welchem Register der Überlauf auftrat. Man fragt halt einfach das Status- oder Flag-Register (je nachdem, wie es heißt) nach dem Overflow-Bit (oder Carry-Bit) ab.

MffG
EisFuX

[Tom]

Hello EisFuX,

Um Prozessor-Flags "in C abzufragen" würden mir höchstens eingestreute Inline-Assembler einfallen. Das hat dann zwar nicht mehr viel mit C zu tun, aber es ist auch Wurst, in welchem Register der Überlauf auftrat. Man fragt halt einfach das Status- oder Flag-Register (je nachdem, wie es heißt) nach dem Overflow-Bit (oder Carry-Bit) ab.

So eine verrückte Idee hatte ich auch schon, aber damit wäre das Programm dann nicht mehr plattformübergreifend nutzbar. C++ müsste darauf Rücksicht nehmen.
Wenn es eine dann nicht kann, muss der Programmierer beim Compilieren eben entscheiden, ob er das Programm dort tortzdem laufen lassen will...

Naja, ich suche noch ein wenig weiter, bevor ich die Bits selber anfasse.

Liebe Grüße aus Syburg bei Dortmund

Tom vom Berg

[Christian Seiler]

Hallo,

Wie kann ich in C++ einen Überlauf-Fehler abfangen, wie er z.B. bei der Berechnung einer Fakultät recht schnell auftritt?

Den Link zu Fefes Eintrag hast Du ja schon bekommen. Ansonsten: Geht nicht in C++.

Kann man die Flags abfragen? Aber dazu müsste man wissen, welches Register als Zielregister beio der Multiplikation benutzt wird und außerdem sollte das in einer Hochsprache auch deren Sachen sein?!

C und C++ definieren einen Integer-Überlauf als "undefiniertes Verhalten", d.h. was dann tatsächlich passiert, ist nicht klar. Wenn es irgendwo eine Platform + einen Compiler gäbe, bei der nach einem überlauf die Integervariable immer 42 enthalten würde, wäre das vollkommen legal nach dem C- oder C++-Standard.

Und genau aus dem Grund kann man das auch grundsätzlich in C oder C++ nicht abfangen: Beide Sprachen setzen nämlich nicht voraus, dass es überhaupt so etwas wie ein Flag für den Überlauf gibt! Ich weiß nicht, ob sowas in der Realität tatsächlich existiert, aber es wäre zumindest theoretisch problemlos denkbar, einen vollkommen standardkonformen C++-Compiler für eine Platform zu schreiben, die sowas gar nicht im Prozessor abfangen *kann*.

Man kann das jetzt natürlich als Designschwäche sowohl von C als auch von C++ ansehen, aber das ändert nichts an der Tatsache, dass das, was Du willst, nicht möglich ist.

Von Inline-Assembler würde ich übrigens DRINGENST abraten - es ist nämlich nicht gesagt, dass ein Compiler auf x86 tatsächlich ein MUL erzeugt bei einer Multiplikation - wenn der Compiler optimiert, darf er auch komplett andere Anweisungen generieren, die ihm schneller oder für den Prozessor besser geeignet erscheinen. Außerdem verliert man dadurch die Portabilität.

Viele Grüße,
Christian

[Tom]

Hello,

Von Inline-Assembler würde ich übrigens DRINGENST abraten - es ist nämlich nicht gesagt, dass ein Compiler auf x86 tatsächlich ein MUL erzeugt bei einer Multiplikation - wenn der Compiler optimiert, darf er auch komplett andere Anweisungen generieren, die ihm schneller oder für den Prozessor besser geeignet erscheinen. Außerdem verliert man dadurch die Portabilität.

So hatte ich das eigentlich auch gedacht. Könnte ja sein, dass er so schlau ist, und Shift-Operationen vorschaltet oder ähnliches...

Was mich aber noch ein wenig verwundert ist, dass bei einem stattgefundenen Überlauf immer 0 herauskommt. Wird das Multiplikationsergebnis bei einem 32-BitProzessor nun doch als 64-Bit Zahl in zwei Registern abgelegt und könnte es sein, dass der gcc das dann ähnlich, wie in Abs. 3, "Multiplying two 32-bit integers" beschrieben ist, umsetzt und dann bei "Überlauf" 0 zurückgibt?

Dann könnte man den ja doch abfangen, indem man fragt, ob keine der beiden Zahlen 0 ist. Wenn dann 0 als Ergebnis herauskommt, hätte ein "Überlauf" stattgefunden. Das wäre natürlich schade um die 32 vferlorenen Bits des Ergebnisses, aber wenn C/C++ sowieso keinen Quad-Word Typ kennt... Oder habe ich den übersehen?

Liebe Grüße aus Syburg bei Dortmund

Tom vom Berg

[Vinzenz Mai]

Hallo Tom,

Was mich aber noch ein wenig verwundert ist, dass bei einem stattgefundenen Überlauf immer 0 herauskommt.

Immer? Bist Du Dir sicher?

Meine Erinnerung sagt mir, dass gegebenenfalls auch 'ne negative Zahl herauskommen kann, wenn Du normale, d.h. vorzeichenbehaftete, int-Variablen nimmst. Ein kurzer Test bestätigt dies auch fürs aktuelle Visual C++.

Freundliche Grüße

Vinzenz

[Tom]

Hello,

Was mich aber noch ein wenig verwundert ist, dass bei einem stattgefundenen Überlauf immer 0 herauskommt.

Immer? Bist Du Dir sicher?

Bei unsigned int als Faktoren
Mit negativen Zahlen sind Fakultäten ja nicht definiert.

Liebe Grüße aus Syburg bei Dortmund

Tom vom Berg

[steckl]

Hi,

Hello,

Was mich aber noch ein wenig verwundert ist, dass bei einem stattgefundenen Überlauf immer 0 herauskommt.

Immer? Bist Du Dir sicher?

Bei unsigned int als Faktoren
Mit negativen Zahlen sind Fakultäten ja nicht definiert.

Ich hab mal eine kleine Routine geschrieben, in der ich die Fakultät in einer Subroutine mit einer for-Schleife ausrechnen lasse:

  
unsigned int fak(unsigned int b)  
{  
    unsigned int a = 1;  
  
    for(unsigned int i = 1; i < b; i++)  
    {  
        a *= i;  
    }  
    return a;  
}  

Wenn ich das jetzt in einer weiteren Schleife (die von 1-39 zählt) aufrufe kommen folgende Ergebnisse:

1: 1
 2: 2
 3: 6
 4: 24
 5: 120
 6: 720
 7: 5040
 8: 40320
 9: 362880
10: 3628800
11: 39916800
12: 479001600
13: 1932053504
14: 1278945280
15: 2004310016
16: 2004189184
17: 4006445056
18: 3396534272
19: 109641728
20: 2192834560
21: 3099852800
22: 3772252160
23: 862453760
24: 3519021056
25: 2076180480
26: 2441084928
27: 1484783616
28: 2919235584
29: 3053453312
30: 1409286144
31: 738197504
32: 2147483648
33: 2147483648
34: 0
35: 0
36: 0
37: 0
38: 0
39: 0

Ab 35 kommt 0, man sieht aber, dass der Überlauf schon viel früher stattgefunden hat. Es gibt wohl eher bei 34 zufällig einen Überlauf, so dass genau 0 rauskommt. Wenn man dann noch was damit multipliziert bleibt das Ergebnis natürlich immer 0.

Verwendeter Compiler: G++ 4.2.3 unter Ubuntu

mfG,
steckl

[Tom]

Hello steckl,

1: 1
2: 2
3: 6
4: 24
5: 120
6: 720
7: 5040
8: 40320
9: 362880
10: 3628800
11: 39916800
12: 479001600
13: 1932053504
14: 1278945280

Ab 35 kommt 0, man sieht aber, dass der Überlauf schon viel früher stattgefunden hat. Es gibt wohl eher bei 34 zufällig einen Überlauf, so dass genau 0 rauskommt. Wenn man dann noch was damit multipliziert bleibt das Ergebnis natürlich immer 0.

Du hast Recht. 13! ist der letzte richtig ausgerechnete Wert.
Es ist also kein "kontrollierter Überlauf", sondern, wie Du sagst, einfach ein Ergebnis, das zufällig 0 ergibt...

Da wäre es ja bei dieser Aufgabe einfacher, das Ergebnis gelich als Stringarray zu speichern. rechnen kann mit diesem Zahlen mit 32-Bit als Ergebnisgröße sowieso keiner mehr.

Das war auch eigentlich gar nicht die AUfgabe, sondern herauszufinden, ob man den Überlauf sicher erkennen kann. Schade, mit Assembler und Turbo-Pascal geht es. Bei Tp gibt der Compiler einen abfangbaren Fehler - getestet allerdings nur für Intel x86-Plattform. Was OS400 dazu sagen würde, weiß ich nicht.

Liebe Grüße aus Syburg bei Dortmund

Tom vom Berg

[Vinzenz Mai]

Hallo,

Was mich aber noch ein wenig verwundert ist, dass bei einem stattgefundenen Überlauf immer 0 herauskommt.

Immer? Bist Du Dir sicher?

Bei unsigned int als Faktoren
Mit negativen Zahlen sind Fakultäten ja nicht definiert.

ich äußerte hier mich zu einem Überlauf allgemein, nicht zur Fakultätsberechnung. Ich bezog mich explizit auf signed int.

Wenn ich das jetzt in einer weiteren Schleife (die von 1-39 zählt) aufrufe kommen folgende Ergebnisse:

die ich ein klein wenig ergänze:

Zweierpotenz    Zweierpotenz
                  im Faktor       im Produkt

1: 1
2: 2              1               1
3: 6
4: 24             2               3
5: 120
6: 720            1               4
7: 5040
8: 40320          3               7
9: 362880
10: 3628800        1               8
11: 39916800
12: 479001600      2              10
13: 1932053504
14: 1278945280     1              11
15: 2004310016
16: 2004189184     4              15
17: 4006445056
18: 3396534272     1              16
19: 109641728
20: 2192834560     2              18
21: 3099852800
22: 3772252160     1              19
23: 862453760
24: 3519021056     3              22
25: 2076180480
26: 2441084928     1              23
27: 1484783616
28: 2919235584     2              25
29: 3053453312
30: 1409286144     1              26
31: 738197504
32: 2147483648     5              31
33: 2147483648
34: 0              1              32
35: 0

Ab 35 kommt 0, man sieht aber, dass der Überlauf schon viel früher stattgefunden hat. Es gibt wohl eher bei 34 zufällig einen Überlauf, so dass genau 0 rauskommt. Wenn man dann noch was damit multipliziert bleibt das Ergebnis natürlich immer 0.

Nicht zufällig.

Jede Multiplikation mit einer Zahl, die eine Zweierpotenz als Teiler hat, führt dazu, dass sich die Anzahl der niederwertigsten Nullbits entsprechend erhöht. Ist 2^32 als Teiler enthalten, so sind alle 32 Bits einer 32-Bit-Integer aufgebraucht, siehe beigefügte Angaben.

Freundliche Grüße

Vinzenz

[Jens Holzkämper]

Tach,

Mit negativen Zahlen sind Fakultäten ja nicht definiert.

deswegen hat man ja sicherheitshalber die Gamma-Funktion erfunden und kann den Definitionsbereich gleich von den natürlichen Zahlen auf die komplexe Zahlen ausweiten.

mfg
Woodfighter

[Daniel Thoma]

Hallo Tom,

Eine Alternative zum Abfangen eines Fehlers ist ja immer die Prognose eines Fehlers, man kann also so etwas machen:

  
function factorial(x) {  
  var result = 1;  
  var limit = Math.pow(2, 32) - 1; // Oder was auch immer das Limit ist, evtl. gibt es da auch eine Konstante  
  for (var i = 2; i <= x; ++i) {  
    if (i >= limit) {  
      return 0; // Fehler  
    }  
    limit /= i;  
    result *= i;  
  }  
  return result;  
}  

Das Programm beruht auf der Idee, dass a * b < c => a < c/b (für b > 0).
Man muss evtl. noch darüber nachdenken, welche Rolle die Verwendung der Integer-Division spielt. Außerdem kann man in diesem Fall natürlich einfach das Limit für x statisch ausrechnen, was sicher sinnvoller ist.

Grüße

Daniel

[Tom]

Hello Daniel,

Eine Alternative zum Abfangen eines Fehlers ist ja immer die Prognose eines Fehlers,

prinzipiell ist das sicher ein Lösungsansatz, aber man weiß ja nicht immer, durch welche Rechenwege ein Überlauf erreicht wird.

Beispiel ist der berühmte Taschenrechner, der einen String auswertet und die darin enthaltene Rechnung in arithmetischer Schreibweise (oder auch bereits in polnischer Notation) ausrechnet.

Kann man das so auflösen, dass man den Lösungsansatz immer verwenden kann?

Liebe Grüße aus Syburg bei Dortmund

Tom vom Berg

[steckl]

Hi,

Beispiel ist der berühmte Taschenrechner, der einen String auswertet und die darin enthaltene Rechnung in arithmetischer Schreibweise (oder auch bereits in polnischer Notation) ausrechnet.

Kann man das so auflösen, dass man den Lösungsansatz immer verwenden kann?

Ich würde sagen, da müsstest du eben für jede Rechenart deine eigene Näherung machen.

Beispiel bei +:
Wenn höchste mögliche Zahl (0-1) minus erster Summand kleiner als der zweite Summand ist würde die Rechnung zu einem Überlauf führen.
(angenommen du rechnest nur mit positiven Zahlen)

Bei * das gleiche mit geteilt statt minus.
Usw. ...

So würde es ich machen, aber keine Ahnung ob das ein guter Weg ist.

Je nachdem wieviel Zeit du für das Problem noch aufwenden willst könntest du auch mal in den Code eines fertigen Taschenrechners schauen.
Ich habe mal kurz den Code von gcalctool, das ich als Taschenrechner unter Ubuntu verwende, überflogen.
Es sind gut 11000 Zeilen Code (aber teilweise nur Zeug für die GUI).
In der Datei mpmath.c die letzte Funktion (calc_factorial) ist für das Berechnen der Fakultät zuständig.
Der Überlauf entsteht in Zeile 1159 oder 1160 (ich glaub eher in 1160) beim Aufruf der Funktionen aus mp.c.
Ich hab dann noch bisschen tiefer reingeschaut, aber bei den goto-Anweisungen in mpmul2() (auch in mp.c) hatte ich fürs erste keine Lust mehr.
Aber ich glaube eh, dass der Overflow eher in cast_to_double (mp.c) in Zeile 782 und folgenden irgendwie ausgewertet wird.

Vielleicht kann ich mich morgen nochmal motivieren, mich da bisschen tiefer reinzuarbeiten, weil das interessiert mich auch, wie das geht.

mfG,
steckl

[Tom]

Hello steckl,

danke für die viele Mühe.
Das schaue ich mir heute näher an. Soviel Zeit muss sein.
Außerdem ist es eine gute Übung für mich, ob ich endlich Code von Anderen lesen kann.

Liebe Grüße aus Syburg bei Dortmund

Tom vom Berg

[Daniel Thoma]

Hallo steckl,

Beispiel bei +:
Wenn höchste mögliche Zahl (0-1) minus erster Summand kleiner als der zweite Summand ist würde die Rechnung zu einem Überlauf führen.
(angenommen du rechnest nur mit positiven Zahlen)

Bei * das gleiche mit geteilt statt minus.
Usw. ...

So würde es ich machen, aber keine Ahnung ob das ein guter Weg ist.

Ja, das ist ja auch, was ich gemacht habe. Ich habe das nur für die Fakultät noch etwas verändert, da man da ja mehrere Multiplikationen nacheinander durchführt. Im Prinzip führt man immer die umgekehrte Operation auf der oberen Schranke durch.
Dieses vorgehen ist sinnvoll, wenn man wirklich absichern muss, dass das Programm korrekt rechnet. Wenn man hingegen einfach mit großen Zahlen rechnen will, sollte man einfach einen entsprechenden Datentyp verwenden, der das ermöglicht. Es gibt ja die von Mark erwähnten Klassen, die mit Integer-Arrays o.ä. rechnen.

Grüße

Daniel

[Tom]

Hello,

Dieses vorgehen ist sinnvoll, wenn man wirklich absichern muss, dass das Programm korrekt rechnet. Wenn man hingegen einfach mit großen Zahlen rechnen will, sollte man einfach einen entsprechenden Datentyp verwenden, der das ermöglicht. Es gibt ja die von Mark erwähnten Klassen, die mit Integer-Arrays o.ä. rechnen.

Die Klasse, die Marc vorgeschlagen hat, habe ich heute versucht, in unser Projektlein einzubauen. Aber die scheint denn doch wohl eher für Linux zu sein und nicht für Windows?
Jedenfalls aheb wir sie nicht zum Laufen gebracht und mangels Doku auch nicht wirklich feststellen können, wie man das ändern kann. Allzu viel Zeit war dann leider auch nicht und so ist sie erstmal auf meinem TODO-Stapel gelandet.

Liebe Grüße aus Syburg bei Dortmund

Tom vom Berg

[Daniel Thoma]

Hallo Tom,

Ich hab gar nicht genau gelesen, was Marc da vorgeschlagen hat.
Ich würde wohl GMP verwenden, wenn ich so etwas bräuchte. Kurzer Blick in die Doku sagt, dass man das auch unter Windows compilieren kann, vermutlich aber eher mit GCC und Cygwin u.ä. statt mit Visual Studio. Wahrscheinlich findet sich in irgend welchen Microsoft-Bibliotheken auch so etwas, wenn vielleicht auch nicht mit dem Funktionsumfang.

Grüße

Daniel

[Marc Reichelt]

Hallo Tom,

wenn du sehr großen Zahlen als Resultat einer Fakultäts-Funktion benötigst - wie wäre es da mit einer BigInt-Klasse?
So etwas gibt's in Java auch, dort heißt sie BigInteger.

Grüße

Marc Reichelt || http://www.marcreichelt.de/

[Tom]

Hello,

wenn du sehr großen Zahlen als Resultat einer Fakultäts-Funktion benötigst - wie wäre es da mit einer BigInt-Klasse?
So etwas gibt's in Java auch, dort heißt sie BigInteger.

Danke für den Tipp. Die schaue ich mir an.
Werde nachher gleich mal damit spielen ;-)

Liebe Grüße aus Syburg bei Dortmund

Tom vom Berg