Überlauf von usigned long int? Große Zahlen verarbeiten schlägt fehl.



  • Guten Tag liebe Community,

    ich habe mit folgendem selbst geschriebenen Code-Snippet etwas hin und her experimentiert:

    #include <stdio.h>
    
    int main(){
    
    	long unsigned int large_num = 0lu;
    	printf("Enter large number. \n");
    	fflush(stdout);
    	scanf("%lu", &large_num);
    	printf("Your input was: %lu",(long unsigned int) large_num);
    
    	return 1;
    }
    

    Hier soll der Benutzer zum Eingeben einer (nicht negativen, bevorzugt großen) Zahl aufgefordert werden, welche im Anschluss direkt wieder ausgegeben wird.

    Eingaben wie z.B. 4000000000 funktionieren problemlos:

    Enter large number.
    4000000000
    Your input was: 4000000000

    Bei noch größeren Eingaben (bspw. 10010010010010) passiert Folgendes:

    Enter large number.
    10010010010010
    Your input was: 2736210330

    Dies sieht nach einem Überlauf aus, wobei sich mir nun die Frage stellt: Wieso?

    Normalerweise kann ein unsigned long int Werte bis (2^64)-1 (= ca. 1.845*10^19) verarbeiten, was meine eingegebene Zahl durchaus erfüllt (10010010010010 = ca. 1.001*10^13) und somit keinen Überlauf verursachen dürfte.

    Suchen im Internet ergaben Vorschläge mit externen Bibliotheken speziell zur Verarbeitung größerer Zahlen, jedoch gingen die dortigen Fragesteller von Zahlen weit über dem Wertebereich von unsigned long int aus (z.B. 2^346), was hier nicht der Fall ist.

    Ich wäre deshalb um jegliche Vorschläge/Ideen zur Lösung des Problems dankbar!

    Außerdem hoffe ich alle relevanten Informationen angegeben zu haben, falls dem nicht so sei werde ich selbstverständlich alles Notwendige nachreichen.

    Liebe Grüße,
    Mike



  • sirgsus schrieb:

    ich habe mit folgendem selbst geschriebenen Code-Snippet etwas hin und her experimentiert:

    Für C solltest du deinen Funktionen als Parameter void zuweisen, wenn du keine Parameter erwartest. Eine leere Parameterliste sagt, dass du beliebig viele Argumente übernimmst.
    Suffixe brauchst du nur bei größeren Zahlen zu verwenden ( (x & 0xf0f0f0f0f0f0f0f0ULL) ).
    Die Ausgabe sollte mit dem '\n' geflusht werden, fflush sollte nicht nötig sein. Alternativ kannst du auch direkt puts verwenden.
    Hast du dir mal die Mühe gemacht, die Größe von large_num ausgeben zu lassen ( sizeof )? Bist du zufälligerweise auf einem Windows-System? Diese definieren unsigned long int immer auf 32 Bit.
    Wenn du keine Unsicherheit über die Größe deiner Typen haben willst, solltest du stdint.h einbinden und uint64_t benutzen.



  • sirgsus schrieb:

    Normalerweise kann ein unsigned long int Werte bis (2^64)-1 (= ca. 1.845*10^19) verarbeiten

    Das sind Mutmaßungen von dir, was ist denn auf deinem System sizeof(unsigned long int) ?



  • Hallo,

    vielen Dank für Eure schnellen Antworten!

    Bekomme mit sizeof(unsigned long int) die Ausgabe 4 Byte, dh. wie dachschaden sagte 32 Bit.

    Stehe aber gerade noch ein wenig auf dem Schlauch - was sagen mir die 32 Bit aus (also klar, allozierter Speicher dieser Variable = 32 Bit, aber auf was muss ich mit den 32 Bit achten?) und wie kann ich nun "10010010010010" mit diesem Wissen einspeichern?

    Liebe Grüße,
    Mike



  • sirgsus schrieb:

    Hallo,

    vielen Dank für Eure schnellen Antworten!

    Bekomme mit sizeof(unsigned long int) die Ausgabe 4 Byte, dh. wie dachschaden sagte 32 Bit.

    Stehe aber gerade noch ein wenig auf dem Schlauch - was sagen mir die 32 Bit aus (also klar, allozierter Speicher dieser Variable = 32 Bit, aber auf was muss ich mit den 32 Bit achten?) und wie kann ich nun "10010010010010" mit diesem Wissen einspeichern?

    Liebe Grüße,
    Mike

    Gar nicht.
    10010010010010 braucht 44 Bit

    Maximalwert ist 232-1



  • DirkB schrieb:

    Maximalwert ist 232-1

    Und einen weitergezählt biste wieder bei 0. 😉

    Wenn ich mich richtig erinnere, kann man Überläufe mit (a+b) < a feststellen. Schade dass C keinen Zugriff auf's Carry-Flag ermöglicht.



  • Du kannst auch schauen, ob es einen Datentyp mit größerem Wertebereich gibt.
    Z.B.

    long long
    unsigned long long
    int64_t
    uint64_t
    


  • DirkB schrieb:

    Du kannst auch schauen, ob es einen Datentyp mit größerem Wertebereich gibt.
    Z.B.

    long long
    unsigned long long
    int64_t
    uint64_t
    

    Aber nicht während das Programm ausgeführt wird. 😉



  • Andromeda schrieb:

    Wenn ich mich richtig erinnere, kann man Überläufe mit (a+b) < a feststellen.

    Das funktioniert NUR bei unsigned Overflows. Ein Compiler kann (und wird auch in der Regel) diese Prüfung (EDIT: bei signed Ganzzahlwerten) entfernen.

    Andromeda schrieb:

    Schade dass C keinen Zugriff auf's Carry-Flag ermöglicht.

    Gute Compiler (wie der GCC z.B.) erlauben es, Intrinsics zu verwenden, mit denen man ordentlich auf einen Overflow prüfen kann.



  • dachschaden schrieb:

    Das funktioniert NUR bei unsigned Overflows.

    Darum geht es ja auch hier. Nebenbei bemerkt: hast du ein Beispiel für signed integers, bei dem ein (a+b)<a keinen Überlauf detektieren kann?

    dachschaden schrieb:

    Ein Compiler kann (und wird auch in der Regel) diese Prüfung entfernen.

    Echt nicht, Alter. So einen Compiler würde ich aber reklamieren.

    dachschaden schrieb:

    Andromeda schrieb:

    Schade dass C keinen Zugriff auf's Carry-Flag ermöglicht.

    Gute Compiler (wie der GCC z.B.) erlauben es

    Das ist eher keine Frage der "Güte", sondern der Inkompatibilität zum Standard. Der gibt das leider nicht her. Wobei ich persönlich kein Problem mit nicht-standardkonformen Erweiterungen habe.


  • Mod

    dachschaden schrieb:

    Andromeda schrieb:

    Wenn ich mich richtig erinnere, kann man Überläufe mit (a+b) < a feststellen.

    Das funktioniert NUR bei unsigned Overflows. Ein Compiler kann (und wird auch in der Regel) diese Prüfung entfernen.

    Kann er nicht. Unsigned Overflows sind genau definiertes Verhalten, daher ist dies eine legitime Prüfung.

    Andromeda schrieb:

    dachschaden schrieb:

    Das funktioniert NUR bei unsigned Overflows.

    Darum geht es ja auch hier. Nebenbei bemerkt: hast du ein Beispiel für signed integers, bei dem ein (a+b)<a keinen Überlauf detektieren kann?

    Bei Integern ist dies hingegen undefiniertes Verhalten. Der Compiler dürfte dies beispielsweise zu etwas in der Art von if (b < 0) optimieren.


  • Mod

    Andromeda schrieb:

    Nebenbei bemerkt: hast du ein Beispiel für signed integers, bei dem ein (a+b)<a keinen Überlauf detektieren kann?

    Vorzeigenbehafteter Überlauf führt immer zu undefiniertem Verhalten. Ein Programm, dass sich nur auf das beschränkt, was der Sprachstandard hergibt, kann eine solche Prüfung in dieser Form nicht durchführen - weil nunmal die gesamte Programmausführung nach Eintreten eines solchen Überlaufes undefiniert bleibt.



  • camper schrieb:

    Andromeda schrieb:

    Nebenbei bemerkt: hast du ein Beispiel für signed integers, bei dem ein (a+b)<a keinen Überlauf detektieren kann?

    Vorzeigenbehafteter Überlauf führt immer zu undefiniertem Verhalten. Ein Programm, dass sich nur auf das beschränkt, was der Sprachstandard hergibt, kann eine solche Prüfung in dieser Form nicht durchführen - weil nunmal die gesamte Programmausführung nach Eintreten eines solchen Überlaufes undefiniert bleibt.

    Was wirklich schade ist und die Frage aufwirft, wieso der C-Standard so viele Freiheiten lässt. Klar, Hardware ist nunmal sehr unterschiedlich, aber mehr Verbindlichkeit wäre manchmal sehr wünschenswert.



  • Andromeda schrieb:

    Darum geht es ja auch hier.

    Dann SAG das aber auch. Denn ein Anfänger, der diesen Thread liest, wird sich denken: "Ach, das gilt dann halt auch für alle Integer-Typen!", und dann haben wir den Salat.

    Andromeda schrieb:

    Nebenbei bemerkt: hast du ein Beispiel für signed integers, bei dem ein (a+b)<a einen Überlauf detektieren kann?

    Frühere Versionen des GCC haben meines Wissens einfach mit dem Überlauf auf Hardwarelevel weitergemacht. Spätere Versionen kamen dann auf die Idee, dies als UB zu betrachten und der Compilerbauer weiß was reinzutun. 3.4.5 hat das noch unterstützt, ab mindestens 4.1 war schluss damit.

    Fefe hat das schon vor mehr als zehn Jahren angesagt.

    Andromeda schrieb:

    Echt nicht, Alter. So einen Compiler würde ich aber reklamieren.

    Der vielfach zitierte GCC macht genau das. Und sprachjustisch liegt er auch im Recht.

    SeppJ schrieb:

    Kann er nicht. Unsigned Overflows sind genau definiertes Verhalten, daher ist dies eine legitime Prüfung.

    Habe mich unklar ausgedrückt, ist mir im Nachhinein auch aufgefallen.
    Also: Overflow für unsigned Typen sind definiert, für signed undefiniert.



  • Andromeda schrieb:

    Was wirklich schade ist und die Frage aufwirft, wieso der C-Standard so viele Freiheiten lässt.

    weil Maschinen denkbar sind, die signed integers nicht im 2-Komplement kodieren.


  • Mod

    zufallswert schrieb:

    Andromeda schrieb:

    Was wirklich schade ist und die Frage aufwirft, wieso der C-Standard so viele Freiheiten lässt.

    weil Maschinen denkbar sind, die signed integers nicht im 2-Komplement kodieren.

    Und es verhindert Optimierungen, wie die von mir gezeigte. (a+b)<a nach b < 0 optimieren zu können ist eine sehr mächtige Optimierung, weil man viel weniger Anweisungen hat. Sich das (und viele andere Optimierungen) zu verbauen wäre dumm. Aber das weißt du ja sicher mit deiner vielen Praxiserfahrung 🙄



  • zufallswert schrieb:

    Andromeda schrieb:

    Was wirklich schade ist und die Frage aufwirft, wieso der C-Standard so viele Freiheiten lässt.

    weil Maschinen denkbar sind, die signed integers nicht im 2-Komplement kodieren.

    Was in diesem Kontext doch eigentlich wurscht ist.

    Auch für "signed int" sollte a+b bei einem Überlauf einen kleineren Wert als a ausspucken, wenn a und b positiv sind. Und letzteres kann man ja vorher testen. Dass mir ein Compiler trotzdem in die Suppe spuckt, indem er aufgrund undefinierten Verhaltens bestimmte "Optimierungen" macht, finde ich sehr betrüblich. 😞



  • Andromeda schrieb:

    Was in diesem Kontext doch eigentlich wurscht ist.

    Nein, ist es nicht. Die Maschine kann was anderes als das 2er-Komplement verwenden. Der Standard sagt klipp und klar, dass signed Overflow undefiniert ist. Damit sind die Fluttore offen für nicht Standard-konforme Optimierungen. End of story.

    Wenn dir das nicht gefällt, geh doch zu Java. Meines Wissens definieren die dort signed Overflow. Du bist glücklich, weil du keine aus deiner Sicht kaputte Software mehr benutzen musst, die deine Unzulänglichkeiten nicht verdeckt, und wir sind glücklich, dass du Werkzeuge, die sowohl eine Nummer zu groß für dich sind wie auch deren Funktionsweise für dich unverständlich zu sein scheinen, nicht mehr benutzen musst. Und die Anfänger sind glücklich, weil sie nicht mehr mit deinem Halbwissen konfrontiert werden. Win-Win-Win!



  • dachschaden schrieb:

    Andromeda schrieb:

    Was in diesem Kontext doch eigentlich wurscht ist.

    Nein, ist es nicht. Die Maschine kann was anderes als das 2er-Komplement verwenden.

    Aber wo ist der Zusammenhang zu (a+b) < a ?
    Das wird ja nicht durchs Zweierkomplement vorgegeben.



  • Andromeda schrieb:

    Aber wo ist der Zusammenhang zu (a+b) < a ?
    Das wird ja nicht durchs Zweierkomplement vorgegeben.

    Doch, eben das schlussendliche Binärformat. Weil es verschiedene Systeme dafür gibt: Sign-Magnitude, Einer-Komplement, Zweier-Komplement, und K-Excess.

    Nach einem Überlauf kann eine Zahl je nach Hardware in diesen verschiedenen Formaten konvertiert werden, ein einheitliches Verhalten ist also auf Hardwarelevel nicht möglich. An dieser Stelle hat man sich dann für Geschwindigkeit entschieden und gesagt, dass das für C einfach undefiniert ist, und wenn man Überlauf mit vorzeichenbehafteten Zahlen macht, ist das dein Problem.

    Beispiel: 01111111 (127) läuft über, raus kommt 10000000. Was ist das jetzt? Excess-128, also 0? Oder Zweier-Komplement, -128? Oder Einer-Komplement, also -127? Oder Signed-Magnitude, also -0? Ist -0 kleiner als 0?

    Es gibt da draußen sogar Systeme, die extra für unsigned eine andere Bitrepräsentation wählen. Excess-128 wieder. Da ist das gleiche Bitmuster (01111111 entweder -1 oder 127. Für den gleichen positiven Werteraum. Letzteres nach dem C-Standard kompatibel und hat Overflow definiert. Ist ein addierter Wert kleiner? Oder größer? Oder ändert er sich gar nicht?

    Und genau deswegen hat man das offengelassen.



  • dachschaden schrieb:

    Beispiel: 01111111 (127) läuft über, raus kommt 10000000. Was ist das jetzt?

    Wenn 127 überlaufen soll, betrachtest du nur die ersten 7 Bits um den Überlauf festzustellen. Ist doch gar nicht so schwer. Mit dem Zweierkomplement hat das immer noch nichts zu tun. 🙂


Anmelden zum Antworten