[gelöst] Integer-Überlauf bei Uint64 feststellen (FreePascal)

[TuxPeter]

Hi,
da es sich hier nicht um eine mehr oder weniger wichtige Support-Bitte, sondern nur um relativ sinnfreie Basteleien handelt, dies in Smalltalk.

Ich spiele gerade ein bisschen mit Zahlenreihen (Collatz-Reihen) herum und nutze dabei auch etwas größere Werte. Ob diese nun korrekt berechnet oder nur aus Blödsinn bestehen, sollte mir ein Range-Check zeigen. Hier ein Beispiel-Programm:

Code: Alles auswählen

uses crt;

// var n : Uint32;
var n : Uint64;

{$R+}
BEGIN
// n := 4294967295;        // = 2 ^ 32 - 1
// n := 18446744073709551615; // = 2 ^ - 1
// n := 1152921504606846976 + 1;   // 2 ^ 60 + 1
// n := 1125899906842624;      // 2 ^ 50
n := 9223372036854775807; // 2 ^63 -1

while n > 1 do
   begin
   if odd (n) then n := 3 * n + 1
              else n := n div 2;
    writeln (n);  
    end;
END.

Es zeigt sich nun, dass, zumindest in FP, der Range-Check bei den 64-bit Integer-Typen nicht funktioniert, bei allen anderen schon. Kann mir auch denken, warum das so ist. Volle Registerbreite ausgenutzt, kein Platz mehr, Überlauf festzustellen. Die Frage wäre, ob das programmtechnisch nicht doch irgendwie feststellbar ist? Diese Folgen können schwer in die Höhe gehen, darum weiß man nie, ob genügende "Sicherheitsabstand" da war.

[JTH]

Ich habs trotzdem mal ins Unterforum Softwareentwicklungentwicklung verschoben, kein Problem, wenns nur eine Bastelei ist. Die tauchen da öfter auf.

Mein letzter Kontakt mit einem Pascal-Dialekt ist ein Jahrzehnt her, aber was ich so auf die Schnelle gefunden habe:
Suchst du nicht eher {$Q} (Overflow checking)? Das {$R} ist anscheinend für Range-/Out-of-bounds-Checks bei Arrayzugriffen gedacht, die du hier ja gar nicht machst.

Ignorier meine Antwort, wenn ich Unsinn schreibe

[TuxPeter]

Nun - ist doch in Softwarentwicklung gelandet - hat das jemand verschoben oder habe ich das entgegen ursprünglicher Absicht gemacht?

Aber ich glaube, ich habs schon: Differenz zu Maxwert bilden, durch 3 teilen, wenns größer als n ist, dann passt es.
Wieder das leidige Phänomen: Problem formuliert, Lösung selber gefunden. Sorry, wenn ich jemanden "aufgescheucht" habe.

Grüße, TuxPeter

[TuxPeter]

Ok, Deine Reaktion war schneller ... Danke für die Antwort

Wie gesagt, bei anderen Integer-Typen funktioniert der Range-Check schon, wie ich erwarte.

Grüße, TuxPeter

[Meillo]

Wieder das leidige Phänomen: Problem formuliert, Lösung selber gefunden.

Das Forum freut sich (durch blosse Anwesenheit) geholfen zu haben.


(Ich persoenlich finde es immer wieder interessant, wie hier, einen Einblick in andere Programmierwelten zu bekommen. Insofern: Danke fuer deinen Thread!)

[uname]

@TuxPeter
Zu deinem Problem gab es vor zwei Wochen ein tolles Youtube-Video.
So wurden wohl bis heute mindestens die Zahlen bis 2^68 getestet

The Simplest Math Problem No One Can Solve
Veritasium
https://www.youtube.com/watch?v=094y1Z2wpJg

Toll ist auch der Kanal "Numberphile"

UNCRACKABLE? The Collatz Conjecture - Numberphile
Numberphile
https://www.youtube.com/watch?v=5mFpVDpKX70

[tobo]

Ok, Deine Reaktion war schneller ... Danke für die Antwort

Wie gesagt, bei anderen Integer-Typen funktioniert der Range-Check schon, wie ich erwarte.

Wie JTH schon schrieb, das was du da oben verwendest ist keine Überlaufprüfung. Richtig ist $Q+ und dann kommt auch die Fehlermeldung. Erstes Ergebnis (3n+1) ist 27670116110564327422 und nicht 9223372036854775806.

[TuxPeter]

So, dankeschön allerseits, mit $Q+ funktioniert es auch bei den 64bit-typen. Prima! Ich hatte inzwischen einen eigenen Range-Check gebastelt und mit einem übersichtlichen Wert (160) getestet, da ist sogar noch ein kleiner Sicherheitsabstand von 1; möchte Euch das Programm inklusive Test-Spuren nicht vorenthalten:

Code: Alles auswählen

uses crt;

var n : Uint64;

const MaxUint64 = 18446744073709551615; // 2 ^ 64 - 1
// const MaxUint64 = 160;

{$Q+}
BEGIN
// n := 15;
// n := 9223372036854775807;
n := 922337203685477591;

while n > 1 do
	begin
    if odd (n) then // ungerade
		n := 3 * n + 1
{       begin
		if (maxUint64 - n) div 2 > n then // passt es?
		    n := 3 * n + 1
	    else 
			begin 
			writeln (n, ' * 3 + 1 ist zu gross!');
			Exit;
			end    
       end        }
   else n := n div 2;
   writeln (n);  
   end;
END.

[tobo]

Apropos Collatz:

Code: Alles auswählen

/*
    Problem 14:
    The following iterative sequence is defined for the set of positive integers:
    n → n/2 (n is even)
    n → 3n + 1 (n is odd)
    Using the rule above and starting with 13, we generate the following sequence:
    13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
    It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
    Which starting number, under one million, produces the longest chain?
    NOTE: Once the chain starts the terms are allowed to go above one million.
*/

Und weitere interessante Rätsel:
https://projecteuler.net/

[TuxPeter]

@ tobo,
ich habe auch ein Progrämmchen geschrieben, welches zu einem Bereich von ... bis als jeweilige Ausgangszahl die Längen der zugehörigen Reihen ermittelt, und zwar nach geraden und ungeraden Steps getrennt. Interessant auch: Welche zusammenhängende Zahlenfolge bringt es auf die längste Folge gleichlanger Zahlenreihen? (Erst danach den Wikipedia-Artikel zu Collatz gelesen)
Bin jetzt aber nicht der Mathe-Fan, der sich auf weitere Probleme dieser Art stürzen wird. Nett sieht es auch aus, wenn man verschiedene Folgen bzw Längen der Reihen in Gnuplot einspeist.

[TuxPeter]

So, ich noch mal.

Also: Die Overflow-Checks funktionieren definitiv nicht zuverlässig. Weder mit R+ noch mit Q+
Ich habe das jetzt relativ ausführlich durchgetestet und dabei festgestellt, dass nur nur mein expliziter Code durchgängig funktioniert.
Hier mal ein Link zu freepascal.org: https://www.freepascal.org/docs-html/prog/progsu64.html So ganz 100%-ig klar ist das alles auch nicht

Wer selbst ein wenig herumprobieren möchte, hier das Progrämmchen, Version für den normalen word-Typ:
41435
In dem gezeigten Beispiel gibt es einen Overflow auf 0.

Danke für Euer Interesse!
TuxPeter

[tobo]

Du hast eine 64-Bit-CPU? Dann lies dir mal den Remark in dem von JTH verlinkten Link über den Overflow Check durch. Auf Datentypen <64 Bit (bei einer 64-Bit-CPU) musst du die Bereichsprüfung {$R+} anwenden.

PS: Das war übrigens auch kein Overflow auf 0, sondern da griff die Bedingung 0 nicht größer als 1!
PPS: Gut, je nachdem wie das gemeint war ist es natürlich dann doch ein Overflow auf 0.

[uname]

@TuxPeter

Vielleicht umdenken:

Statt

Code: Alles auswählen

3x + 1 

Einfach

Code: Alles auswählen

x + x + x + 1

... und nach jeder Addition natürlich schauen, dass die Summe wirklich größer als der Ausgangswert ist
... auch bei "+ 1" kannst du auf die Überprüfung nicht verzichten ... auch wenn die Wahrscheinlichkeit sehr gering ist genau die Zahlengrenze erreicht zu haben

Ist nicht wirklich performant aber vielleicht optimiert ja dein Compiler den Code
Oder machs wie bei Windows. Kauf dir einen schnelleren Rechner.

[tobo]

Dieser "programmtechnische" Überlaufschutz ist doch schon implementiert (nur halt anders). Es geht um den generischen Überlaufschutz vom fpc selbst. Und da verwendet man dann halt einfach Q+ "und" R+, sofern 64-Bit Datentypen "und" kleiner verwendet werden. Aber diese Prüfungen sind auf Progammebene ja meist sowieso anzuraten, wenn nicht gerade vom Überlauf profitiert werden soll.

[TuxPeter]

Hi,
da ich noch ein wenig an dem Problem gebastelt habe, erlaube ich mir noch mal den Faden hochzuziehen.
Aber erst mal @uname: Das "Ausrollen" der Multiplikation in mehrere Additionen bringt mir speziell bei diesem Problemen gar nix. Und @tobo: " ...da verwendet man dann halt einfach Q+ "und" R+, sofern 64-Bit Datentypen "und" kleiner verwendet werden. " Genau, einfach beide Schalter setzten. Und genau, ein bisschen eigenes Hirnschalz für eine genau passende Prüfung zu verwenden, ist immer empfehlenswert.
Aber reichlich verwirrend und unerwartet ist dies unterschiedliche Verhalten bei an sich simplen Ganzzahl-Typen schon.

Für den Fall, dass jemand selber ein paar Versuche machen will, hier mein Testprog, mit dem ich - ausgehend vom ursprünglichen Problem - alle Möglichkeiten mal durchprobiert habe.
41443
Schönen Sonntag noch!
TuxPeter

[tobo]

Und trotzdem ist die selbstprogrammierte Überlaufkontrolle nicht das, was man verwenden sollte. Wenn man also die Prüfungen aktiviert und nicht möchte, dass das Ergebnis der Prüfungen das Programm beendet, dann verwendet man Ausnahmen:

Code: Alles auswählen

program t;
{$mode delphi} {$Q+} {$R+}

uses crt, sysutils;

var
  q: qword = high(qword);
  c: cardinal = high(cardinal);
  w: word = high(word);
  b: byte = high(byte);

procedure generateOverflow(q:qword; c:cardinal; w:word; b:byte);
begin
  try
    if q<>0 then inc(q);
    if c<>0 then inc(c);
    if w<>0 then inc(w);
    if b<>0 then inc(b);
  except
    on e: exception do
      writeln(e.classname,': ',e.message);
  end;
end;

begin
  write('Max64BitValue: ', q, ' - '); generateOverflow(q,0,0,0);
  write('Max32BitValue: ', c, ' - '); generateOverflow(0,c,0,0);
  write('Max16BitValue: ', w, ' - '); generateOverflow(0,0,w,0);
  write('Max8BitValue: ', b, ' - '); generateOverflow(0,0,0,b);
end.

Code: Alles auswählen

Max64BitValue: 18446744073709551615 - EIntOverflow: Arithmetic overflow
Max32BitValue: 4294967295 - ERangeError: Range check error             
Max16BitValue: 65535 - ERangeError: Range check error     
Max8BitValue: 255 - ERangeError: Range check error

Bei der Ausnahmebehandlung kann man dann natürlich auch vielfältiger reagieren. Das heißt aber nicht, dass man den gesamten Text in try-except einschließen sollte. Das Ding nennt sich Ausnahmebehandlung, um Asunahmen abzufangen. Lokal eingesetzt und dort wo es angebracht ist.