Overflow verhindern?

[Noob4Life]

Hi,

ich hätte ne Frage bezüglich Overflows von primitiven Datentypen (byte, short,int,long,float,double).
Wenn ich z.B. in meinem Programm die Fakultät einer Zahl n (n € N) ausrechnen lassen will, reicht int grad mal für das Intervall [1,12] aus, danach wird nur noch Schrott produziert.
Die Fakultät von 12 ist 479001600, von 13 wäre sie 13*479001600=6227020800, mit int gibt Java aber 1932053504 aus.
Sieht nett aus, ist aber falsch.

Tja, und meine Frage wäre nun, wie kann ich es hinkriegen, dass Java, sobald es zu einem Overflow kommen würde, eine Fehlermeldung ausgibt bzw. die Schleife abbricht bzw. in eine Schleife mit BigInteger/BigDecimal übergeht ?

Ich kann ja schlecht bei jedem Program erst mal von Hand ausrechnen ab wann es nen Overflow gibt und dann von vornerein im Code die Beschränkung für ein Intervall [1,x) implementieren. Ob ich die Beschränkung bei der Eingabe mach oder ab einem festen x eine andere Funktion, die dann mit BigIntegern oder BigDecimal arbeitet, mache, spielt ja keine große Rolle, da ich vorher schon die Zahl x wissen muss.
Und wenn ich x schon weiss, wozu brauch ich dann das Programm noch ???:L Kann ja dann von Anfang an alles von Hand machen.:### :meld:

Bei nem Program das lediglich die Fakultät berechnet ists ja noch kein Problem den Overflow festzustellen, aber schon allein bei einem Program das mit der Fakultät eine weitere Berechnung durchführen soll könnte es schwieriger werden. Gut, da weiss man das bei 12 Schluß ist, aber bei Berechnungen mit Potenzen oder Fibonaccizahlen usw. wirds schon schwerer. Vor allem wenn das Ergebnis der Berechnung in einer Schleife wiederverwendet wird, was auch zu Overflows führt, wenn man simple Addition oder Multiplikation zweier oder mehrerer beliebiger x,y,z €N durchführt.
Die einzige Möglichkeit die mir bisher eingefallen ist, ist einfach alles von Anfang an mit BigIntegern/BigDecimal zu machen, was aber nicht Sinn der Sache sein kann, wobei der Code natürlich kürzer wäre, als 2 oder mehrere Funktionen für diverse Fälle zu schreiben.
Bin für jede Hilfe oder Denkanstoß dankbar

 

[meez]

Warum testest du nicht, ob Integer.MAX_VALUE schon erreicht ist?

 

[Guest]

Gute Frage.
Habs nicht hinbekommen, falls es damit möglich ist.

 

[0xdeadbeef]

Das ist ein ganz grundsätzliches Problem beim Arbeiten mit Integertypen. Wenn Du große ganze Zahlen genau rechnen willst, nimm BigInteger.
Ansonsten mußt Du vor jeder Addition/Multiplikation usw. abtesten, ob das Ergebnis überlaufen könnte.
Dabei gilt z.B.: bei einer Addition kann die Anzahl der benötigten Bits für das Ergebnis maximal um 1 größer sein als die Anzahl der benötigten Bits für die größere der beiden addierten Zahlen:

Beispiel:
16383+32767 = 49150
(14bit) (15bit) (16bit) [15+1 = 16]

Bei Multiplikationen entspricht die maximal mögliche Bitbreite der resultierenden Zahl der addierten Bitbreiten der addierten Zahlen:

511*255 = 130305
(9) (8 ) (17) [9+8 = 17]

Die Anzahl der zur Darstellung einer Zahll benötigten Bits kann man über den Logarithmus dualis bestimmen (wobei man ld(N+1) benutzen sollte). Bei einer echten Implementierung ist es aber wohl sinnvoller zu testen, welches das höchstwertige gesetzte Bit ist (z.B. per Rausshiften).

 

[Noob4Life]

Wie test ich das ab?
zb

for(int i=0;i<=z;i++){
x=x1+x2;
x2=x1;
x1=x;
  if(x>(Math.pow(2,32)-1)){
    x=-1; 
    break;
  }
}     
return x;

funktioniert nicht, kommt trotzdem zu nem Überlauf.

 

[meez]

Sollte dein Beispiel oben (13!) , nicht eigentlich eine negative Zahl ergeben?

 

[0xdeadbeef]

Wie gesagt: vor der Addition/Multiplikation muß getestet werden, nicht danach, denn dann ist das Kind schon in den Brunnen gefallen. Wie man davor testet, habe ich ja ebenfalls beschrieben.

Alternativ könntest Du die Addition in diesem speziell Fall auch in "long" rechnen. Dann klappt auch der Test danach, solange das Ergebnis nicht > 63bit ist.

Math.pow(2,32) dürfte in dem Kontext übrigens eine reichlich teure Operation sein. Zudem ist der Zahlenwert falsch: int geht nur bis ((1<<31)-1). Warum nimmst Du nicht einfach long (( 1L << 31)-1) statt double?

 

[0xdeadbeef]

@meez:
Nein: 1932053504 ist exakt das Ergebnis, wenn man 6227020800 auf einen signed 32bit-Wert casted.
Ist ja nur eine Frage, wie stark der Überlauf ist, ob man im negativen oder postiven Zahlenbereich landet.

 

[Noob4Life]

@Meez
Nein, erst ab 17! gibt die Berechnung mit int manchmal negative Werte aus.

@0xdeadbeef
die 32 war en Tippfehler.
Und du sagst ich müsste die if-Abfrage vor x=x1+x2; machen und dann würds gehen?
Shift-Operatoren hab ich bisher seltenst benutzt, deshalb nicht an die Möglichkeit gedacht.
Alternativ könnt ich auch einfach 2147483647 benutzen.
Hab ichs jetzt verstanden? Ja, Nö? Du wirsts nie verstehen :bahnhof:

 

[0xdeadbeef]

Meine LD2-Ausführungen willst Du ja offensichtlich nicht wahrnehmen, bleiben wie also bei der einfacheren Lösung:
In diesem speziellen Fall wäre es am sinnvollsten, Du würdest temporär mit einer long-Variablen rechnen.
So in der Art

longt temp;

...
temp = (long)x1 + (long)x2;
if (temp > Integer.MAX_VALUE)
    x = Integer.MAX_VALUE; // OVERFLOW!!!
else
    x = (int)temp;

Nebenbei: einen Algorithmus für die Fakultät mit int zu implementieren, ist ziemlich für die Katz, wie Du ja auch schon gemerkt hast. Da wäre es einfacher, die paar Werte vorberechnet in ein Array abzulegen und dann gleich das Ergebnis auszulesen.

 

[Noob4Life]

Würde deine LD2-Ausführung schon wahrnehmen, wenn ich gut genug in Mathe wäre
Und jo, klar, int für Fakultäten zu benutzen ist schon recht unpraktisch, war auch mehr als Beispiel gedacht.
Geht mir ja eher darum, ne Vorrichtung für unbekannte Werte zu haben, so dass ich immer ein gescheites Ergebnis bekomme ohne dass ich von vornerein BI benutzen muss. Code wär zwar kürzer, aber mit 32bit Werten ists halt einfach schneller.

 

[Bleiglanz]

vergiss den logarithmus

die ganze idee ist doch schräg, du kannst mit int oder long alle "darstellbaren" fakultäten im voraus berechnen (so viele sinds nämlich nicht) und über ein array o.ä. zur Verfügung stellen

es gab früher mal Ideen für "überprüftes Rechnen", wo man a priori wissen wollte, obs einen Überlauf gibt oder nicht und je nach dem reagiert; wegen der unendlich aufwändigen Flusskontrolle und "Vorher-Wissen-Problematik" ist das alles gescheitert

Tipp: Wenn du mit Fakultäten sinnvoll rechnen willst, nimm gleich BigInteger (andernfalls ist dein programm auf winzigste Zahlen eingeschränkt)

 

[0xdeadbeef]

vergiss den logarithmus

die ganze idee ist doch schräg...

Die Idee ist so schräg nicht, wenn man sie wie beschrieben einsetzt. Beruflich überprüfe ich alle komplexen Integerberechnungen (Automotive-Zeugs) per ld2 auf Überläufe, weil das schlicht der einzige richtige Weg ist. Natürlich nicht zur Laufzeit, da benutzen wir (zumindest teils) entsprechende inline-Funktionen (C) , die den Überlauf per Cast auf den nächsthöheren Integertyp abtesten und dann auf den Maximalwert begrenzen.

, du kannst mit int oder long alle "darstellbaren" fakultäten im voraus berechnen (so viele sinds nämlich nicht) und über ein array o.ä. zur Verfügung stellen

Als sei das nicht bereits gesagt worden :roll:

es gab früher mal Ideen für "überprüftes Rechnen", wo man a priori wissen wollte, obs einen Überlauf gibt oder nicht und je nach dem reagiert; wegen der unendlich aufwändigen Flusskontrolle und "Vorher-Wissen-Problematik" ist das alles gescheitert

Es gibt Bereiche, in denen man Überläufe nicht hinnehmen kann. Dann muß man sich halt ein paar Gedanken machen.

Tipp: Wenn du mit Fakultäten sinnvoll rechnen willst, nimm gleich BigInteger (andernfalls ist dein programm auf winzigste Zahlen eingeschränkt)

Er schrieb bereits, daß das nur ein Beispiel ist. Davon abgesehen wurde auch BigInteger bereits mindestens zweimal erwähnt.

 

[Bleiglanz]

Die Idee ist so schräg nicht, wenn man sie wie beschrieben einsetzt. Beruflich überprüfe ich alle komplexen Integerberechnungen (Automotive-Zeugs) per ld2 auf Überläufe, weil das schlicht der einzige richtige Weg ist. Natürlich nicht zur Laufzeit, da benutzen wir (zumindest teils) entsprechende inline-Funktionen (C) , die den Überlauf per Cast auf den nächsthöheren Integertyp abtesten und dann auf den Maximalwert begrenzen.

oben hast du geschrieben, dass andere Möglichkeiten eventuell besser sind (shiften, ...); jetzt ist der aufwändige log_2 auf einmal "schlicht der einzige Weg"?

Es gibt Bereiche, in denen man Überläufe nicht hinnehmen kann. Dann muß man sich halt ein paar Gedanken machen.

Stimmt. Dann aber vor jeder Rechnung "einzeln, ad hoc", es gibt keine global richtige Lösung. Im Normalfall wird man doch immer den "maximalen" Typen wählen (in java etwa long)

Was aber tun, wenn die Rechnung nicht ausgeführt werden kann?

Kurze Idee mit longs ("einfach hinterher testen"):

e = a* b;
if(a = e/b && b=e/a){
// alles OK
}else
{
// ging nicht, weil...
}
Frage: ist dann im //alles OK zweig sicher, dass es keinen Überlauf gegeben hat - check ich jetzt nicht auf die Schnelle?

 

[0xdeadbeef]

oben hast du geschrieben, dass andere Möglichkeiten eventuell besser sind (shiften, ...); jetzt ist der aufwändige log_2 auf einmal "schlicht der einzige Weg"?

Entgegen Deinem Verständnis steck keinerlei Widerspruch in dieser Aussage. Log2 ist die mathematisch (!) richtige Lösung, der Shift-Logarithmus war ein Vorschlag für eine Implementierung (!) mit einigermaßen brauchbarer Performanz. Wenn man es denn zur Laufzeit testen will, von was ich aber immer abgeraten habe.

Stimmt. Dann aber vor jeder Rechnung "einzeln, ad hoc", es gibt keine global richtige Lösung. Im Normalfall wird man doch immer den "maximalen" Typen wählen (in java etwa long)

Solche Überlegungen sind stets Kompromisse zwischen Sicherheit und Perofrmance. Es gibt im allgemeinen Stellen, an denen man einen Überlauf ausschließt und auf Überprüfung verzichtet und andere, an denen man die Überprüfung zwingend braucht. Aber ja: eine global richtige Lösung bei der Implementierung (!) gibt es nicht. Habe ich allerdings auch nie behauptet.

Was aber tun, wenn die Rechnung nicht ausgeführt werden kann?

Man kann wie beschrieben saturieren. Eigentlich der übliche Weg. Im Einzefall kann aber eine andere Implementierung sinnvoller sein (Fehlerzustand/Notlauf oder dergleichen). Es sollte jedoch klar sein, daß man am besten Überläufe bereits vor der Implementierung bedenkt und dann die Zahlenbereiche/Auflösungen so wählt, daß in der Praxis keine Überläufe auftreten können. Denn auch eine Saturierung ist ein Fehlverhalten. Nur halt eines mit (zumeist) weniger katastrophaler Auswirkung als ein Überlauf.

Kurze Idee mit longs ("einfach hinterher testen"):

e = a* b;
if(a = e/b && b=e/a){
// alles OK
}else
{
// ging nicht, weil...
}
Frage: ist dann im //alles OK zweig sicher, dass es keinen Überlauf gegeben hat - check ich jetzt nicht auf die Schnelle?

Der Code ist ohnehin falsch ("=" statt "==") und behandelt ein ganz anderes Problem (Teilung ohne Rest). Zudem ist die Redundanz zwecklos. Bin mir daher nicht sicher, was Du mir damit sagen willst.

 

[Noob4Life]

@0xdeadbeef


Ich hab mich jetzt mal schlau gemacht, wie man den LD ausrechnet.
Hab als erstes mal ein kleines Testprogramm geschrieben, dass den LD berechnet.
Soweit hat auch noch alles gut funktioniert.
Dann hab ich versucht, die LD-Berechnung in mein anderes Testprogramm für Fakultäten einzubauen.
Und das hab ich leider bisher noch nicht geschafft.

So sah im Übrigen mein Code für den LD aus. Denke, dass er für positive ganzzahlige Zahlen stimmt

do {
	s=y1*y;// y=2, y1=y, calculates s
	y1=s;  // sets y1 to s
	x=x+1; // LD-Count
   }while (s<=n);

Könntest du mir mit Code sagen wie das mit dem LD innerhalb eines anderen Programms funktioniert?
Ich versteh zwar deine erste Erklärung so in etwa, aber ich weiss einfach nicht wie ich das umsetzen soll.

 

[Bleiglanz]

oben hast du geschrieben, dass andere Möglichkeiten eventuell besser sind (shiften, ...); jetzt ist der aufwändige log_2 auf einmal "schlicht der einzige Weg"?

Entgegen Deinem Verständnis steck keinerlei Widerspruch in dieser Aussage. Log2 ist die mathematisch (!) richtige Lösung, der Shift-Logarithmus war ein Vorschlag für eine Implementierung (!) mit einigermaßen brauchbarer Performanz. Wenn man es denn zur Laufzeit testen will, von was ich aber immer abgeraten habe.

Der log2 wird fast immer eine irrationale Zahl liefern und ist in der Berechnung aufwändig, die Lösung mit dem shiften liefert einfach viel schneller die gewünschte Info ("Anzahl der Stellen im 2er System")

Wir reden hier doch nur von Laufzeitproblemen, wenn du alles vorher ("Entwurfszeit") abfangen kannst, dann ist diese Diskussion doch für die Katz??

kurze Idee mit longs ("einfach hinterher testen"):
e = a* b;
if(a = e/b && b=e/a){
// alles OK
}else
{
// ging nicht, weil...
}
Frage: ist dann im //alles OK zweig sicher, dass es keinen Überlauf gegeben hat - check ich jetzt nicht auf die Schnelle?

Der Code ist ohnehin falsch ("=" statt "==") und behandelt ein ganz anderes Problem (Teilung ohne Rest). Zudem ist die Redundanz zwecklos. Bin mir daher nicht sicher, was Du mir damit sagen willst.

Wollte nur mal ein Beispiel geben, dass man den Überlauf nicht vorher abprüft, sondern einfach hinterher nochmal nachschaut (das ist nur als Alternative zu

a < Integer.MAXVALUE / b

gedacht. Bin mir aber nicht sicher, obs wirklich 100% funktioniert