Überlauf Fakultät

[vbtricks]

Salut,

ich schaue mir zur Zeit Java an, habe bis jetzt vornehmlich mit C# gearbeitet. Dabei gibt es einige Gemeinsamkeiten aber natürlich auch Unterschiede. Mit folgender Funktion will ich die Fakultät berechnen:

  private static int Faculty(int Number)
  {
  	int product = 1;
  	for(int i = 1; i <= Number; i++)
  	{
  		product *= i;
  	}
  	return product;
  }

Das gibt selbstverständlich einen Überlauf, bloß bekomme ich leider keine Exception, sondern einfach nur falsche Ergebnisse. Wie behandle ich das denn am besten?

Dann möchte ich noch eine eher theoretische Frage anschließen:
Ich könnte das ganze ja auch rekursiv programmieren. Gehe ich aber richtig in der Annahme, dass das nicht so sinnvoll ist, da für jeden rekursiven Aufruf entsprechend Platz für die Variablen reserviert werden muss, und das ganze somit langsamer wird?


Stefan

 

[Leroy42]

Der zusätzliche Zeitaufwand bei rekursiver Berechnung
der Fakultäten macht sich erst dann bemerkbar, wenn du
einige 100 000 mal Fakultäten berechnest. Bei einer so
einfachen Umwandlung in eine iterative Methode würde
ich die Fakultät dennoch iterativ berechnen.

Überlauf festzustellen ist schon umständlicher. Du müsstest vor
jeder Multiplikation auf einen Überlauf testen, etwa so

if (Integer.MAX_VALUE / i > product)
  throw new Exception(...)

Wenn du long statt int benutzst, kannst du entsprechend
größere Fakultäten berechnen. Wenn du aber beliebig
große Fakultäten berechnen willst, bleibt dir nur der Weg
über BigInteger:

BigInteger faculty(int n) {
  return n == 0 ? BigInteger.ONE : new BigInteger(n).multiply(faculty(n-1));
}

 

[Zunera]

Hi,

Leroy42 hat eigentlich schon alles gesagt. Außer das der mathematische Begriff "Fakultät" im englischen "factorial" heißt - "faculty" klingt ähnlich, hat aber nix mit der mathematischen Operation zu tun... :noe:

PS: Die Exception könnte man auch einfach mit

if(product <= 0) throw new RuntimeException("Result out of range!");

werfen.

 

[vbtricks]

Salut,

danke für die Antworten, hat mir weitergeholfen.

PS: Die Exception könnte man auch einfach mit

if(product <= 0) throw new RuntimeException("Result out of range!");

werfen

Woher kann ich mir sicher sein, dass du falsche Wert Nicht-Positiv ist? Ist das immer so, oder funktioniert das nur bei dem Beispiel? Hatte ich beim Debuggen zwar auch gesehen, wollte da aber keine voreiligen Rückschlüsse ziehen.


Stefan

 

[byte]

Das "letzte" Bit wird jeweils als Vorzeichen interpretiert. Das heisst, irgendwann ist das Produkt größer als 2^31 - 1 und somit negativ.

Wenn Du aber weiterrechnen würdest, dann würde das Produkt irgendwann natürlich auch wieder positiv werden, nämlich bei MAX_VALUE * MAX_VALUE.