große Zahlen bei Fakultätsberechnung

Michael E.

Nach ner Definition der ganzen Zahlen hat keiner gefragt. Aber um zu wissen, was ganze Zahlen im umgangssprachlichen Sinn sind, braucht man nicht "Mathe zu können".

Worauf ich hinaus will: Niemand sagt im Deutschen Integral für Ganzzahl.

Hacker, das mit der Formel hat der nur als Jux gemeint. Da steht auch nur 2*3*4*...*n

Michael E. schrieb:

Nach ner Definition der ganzen Zahlen hat keiner gefragt. Aber um zu wissen, was ganze Zahlen im umgangssprachlichen Sinn sind, braucht man nicht "Mathe zu können".

Zahlenmengen sind ja auch nur "Teilgebiet der Mathematik".
Egal, du hast Recht, aber ich will mich fachlich ausdrücken.

314159265358979 schrieb:

Hast du das selbst geschrieben seldon?

Ja, die Grundfassung ist aber lange her und hieß anders (read_type, wenn ich das richtig im Kopf habe). Du kannst das Ding gerne benutzen, wenn du es für irgendwas gebrauchen kannst. Ich habe für mich festgestellt, dass ich im Laufe der Zeit immer weniger Verwendung dafür hatte, aber eine Weile hat es mir gute Dienste geleistet (Performance ist ja an dieser Stelle von nachrangiger Bedeutung).

Michael E.

gastgast schrieb:

Hacker, das mit der Formel hat der nur als Jux gemeint. Da steht auch nur 2*3*4*...*n

Natürlich ist das dasselbe, sonst hätte ichs wohl nicht geschrieben. Aber es war kein Jux. Denn in vielen Fällen, hier auch, kann man mit dem Logarithmus der Fakultät rechnen, sodass man mit deutlich größeren Zahlen zurechtkommt.

PhilippHToner

Also eigentlich kann man bei den Binominalkoeffs numerisch sehr gut kürzen!

n über k = n! / ( k!*(n-k)!): mit n >= k

Für n > 2k ist der zweite Faktor im Nenner größer, ansonsten, der erste Faktor.

Und den größeren Faktor rechnest du sofort mit n! entgegen, dann sparst du dir schon mal 2*k, bzw 2*(n-k) Multiplikationen, weil du es sowohl für n! als auch für den größeren Faktor nicht berechnen musst.

Beispiel: 100 über 3

100! / (3! * (100-3)!) => n > 2k also über (100-3)! kürzen

100!/97! * 1/3! = 100*99*98 * 1/(1*2*3) = 161700
so kann man es sogar fast im Kopf rechnen.

Anders hat der numerische Wert von 100! 158 Stellen vor dem Komma
Da müsstest dann von Java BigInt benutzen !

@Michael: Die Idee ist prinzipiell nicht ganz blöde, aber man kann die Berechnung des Binomialkoeffizienten so aufziehen, dass kein Zwischenergebnis größer ist als das Endergebnis:

unsigned long bincoeff(int n, int k) {
  if(k > n - k) {
    return bincoeff(n, n - k);
  }

  unsigned long result = 1ul;
  for(int i = 1; i <= k; ++i) {
    if((n - k) % i == 0) {
      result *= (n - k) / i + 1;
    } else {
      result /= i;
      result *= n - k + i; // Merke: n - k + i > i
    }
  }

  return result;
}

...womit die Notwendigkeit für den Logarithmus-Trick verschwindet, denn wenn das Endergebnis nicht mehr in den Zieldatentyp passt, hat man noch ein ganz anderes Problem.

Michael E.

seldon schrieb:

man kann die Berechnung des Binomialkoeffizienten so aufziehen, dass kein Zwischenergebnis größer ist als das Endergebnis

Ich weiß. Aber Fakultäten braucht man nicht nur für Binomialkoeffizienten

Kentatschdis

Soweit ich weiss, kann man zu grosse Zahlen auch mit einer verkettetn Liste darstellen.
Erste Element ist die Einerstelle, zweites Element die Zehnerstelle usw. Man muss sich halt eine Klasse schreiben und die Operatoren für *, /, + usw mitprogrammieren.

Ist zwar ein wenig aufwendig, aber man hat das Problem der zu grossen Zahlen gelöst.
Ich könnte mir vorstellen, dass es eine LinkedList Bibliothek gibt, die man wahrscheinlich benutzen könnte. Wir haben die LinkedList damals komplett selber geschrieben, aber ich weiss auch nicht, wie fit du in C++ bist. Man muss sich mit Zeigern usw auskennen.

PhilippHToner

Kentatschdis schrieb:

Soweit ich weiss, kann man zu grosse Zahlen auch mit einer verkettetn Liste darstellen.
Erste Element ist die Einerstelle, zweites Element die Zehnerstelle usw. Man muss sich halt eine Klasse schreiben und die Operatoren für *, /, + usw mitprogrammieren.

Ist zwar ein wenig aufwendig, aber man hat das Problem der zu grossen Zahlen gelöst.
Ich könnte mir vorstellen, dass es eine LinkedList Bibliothek gibt, die man wahrscheinlich benutzen könnte. Wir haben die LinkedList damals komplett selber geschrieben, aber ich weiss auch nicht, wie fit du in C++ bist. Man muss sich mit Zeigern usw auskennen.

Das halte ich für Käse. Das ist ein absoluter Workaround der keinen Spass macht und völliger Unnütz. Wenn ich wirklich eine stabile Laufzeit haben will und bei großen Zahlen die Darstellung mit der Zeit eh sehr vage wird, kann ich gleich die diskrete Gammafunktion implementieren http://de.wikipedia.org/wiki/Gammafunktion.

Bignums implementiert man nicht dezimalstellenweise und erst recht nicht als verkettete Liste (verkettete Liste heißt Cache-Misses ohne Ende). Im Zweifel wird das ein Vektor von Integern, und gerechnet wird mit Radix 2^Breite.

Bibliotheken dafür gibt es eine ganze Reihe, beispielsweise GMP.