Problem: Fakultät -> großes Ergebnis

[mo_greene]

Hallo,

ich habe ein kleines Tool programmiert, welches mir die Binomialverteilung zu einem Bernoulli-Experiement berechnet und ausgibt.

Nun mein Problem:

Wenn ich ein Bernoulli Experiment mit der Länge n = 40, p = 0,4 und k = 15 habe, dann muss ich ja um den Binomialkoeffizienten auszurechnen die Fakultät von 40 berechnen lassen. Leider ist dies eine sehr große Zahl, womit Delphi scheinbar Probleme hat, da das Ergebnis nicht stimmt (z.T. negativ oder auch manchmal 0). Das richtige Ergebnis wäre ungefähr 8.16*10^47.

Wie kann ich solch große Zahlen berechnen lassen?


Vielen Dank,

David

[mkinzler]

BigInt

[Apollonius]

Der Typ Integer fasst nur Zahlen bis 2^31 - 1. Du kannst entweder ein Konstrukt nehmen, welches einen größeren Bereich unterstützt oder den Binomialkoeffizienten auf geschicktere Art berechnen. Beispielsweise kannst für 49 über 6 einfach 49*48*47*46*45*44/(2*3*4*5*6) nehmen und erhältst damit keine sehr großen Zwischenergebnisse.

[mo_greene]

Ist ja eine gute Idee, aber wenn ich habe 99 über 97, dann kommt doch für den Zähler des Binomialkoeffizienten auch schonmal etwas sehr großes heraus. Also muss ich dann auf ein von dir so genanntes Konstruk zurückgreifen!?

[Medium]

Es würde jedoch noch locker passen, wenn ich nicht irre. Du solltest dir evtl. mal diesen Abschnitt zu Binomialkoeffizienten in der Wikipedia auf der Zunge zergehen lassen.

[alzaimar]

Vergiss bitte nicht die normalen Datentypen Double und Extended. Dort wird die Fakultät zwar nicht bis auf die letzte Stelle ausgerechnet, aber die Genauigkeit dürfte dennoch ausreichen, immerhin rechen diese Datentypen auf 15-20 Stellen genau. Das Zwischenergebnis wäre zwar ungenau, aber im Endeffekt dürfte das keine große Rolle spielen.

Weiterhin gibt es für große N auch Näherungsformeln für N! (Sterlingformel, wenn ich mich nicht irre).

[Horst_]

Hallo,

Zum Beispiel auf http://www.developia.de/forum/viewto...793&highlight= mein Programm N über k (müßte wohl eher Bernoulli heißen ;-) ) berechnet die Werte logarithmisch, weil Multiplikation/Division dann zur Addition/Subtraktion werden und riesige Zahlen verarbeitbar werden.

Gruß Horst

[negaH]

Hatten wir alles schonmal siehe hier http://www.delphipraxis.net/internal...342&highlight=
Folge auch den Links innerhab dieses Postings, dort wurde alles schonmal erklärt und Sourcen gibts auch.
Man sollte erstmal hier in der DP nach zb. "Fakultät" suchen bevor man ständig nach Wikipedia oder extern verlinkt, denn sehr sehr vieles ist in der DP schon gesammelt worden.

Du kannst im Binomial kürzen, so das du mit normalen Integer den Wertebereich stark vergrößerst.

Gruß Hagen

[Medium]

Zitat:

Zitat von negaH

Man sollte erstmal hier in der DP nach zb. "Fakultät" suchen [...]

Wenn ich mich nicht irre, sollte diese Möglichkeit bereits vom TE ausgeschöpft werden bevor er die Frage stellt ;)

[sx2008]

Zitat:

Zitat von negaH

Du kannst im Binomial kürzen, so das du mit normalen Integer den Wertebereich stark vergrößerst.

Ja, das geschickte Kürzen ist der Knackpunkt.
Habe da eine gute Implementierung im der Bibliothek ESBMaths von ESBConsult gefunden:

Delphi-Quellcode:

{:
   ESBMaths 3.2.1 - contains useful Mathematical routines for Delphi 4, 5 & 6.
   Copyright ©1997-2001 ESB Consultancy



   ESB Consultancy retains full copyright.



   ESB Consultancy grants users of this code royalty free rights
   to do with this code as they wish.

 }
function BinomialCoeff (N, R: LongWord): Extended;
var
   I: Integer;
   K: LongWord;
begin
   if (N = 0) or (R > N) or (N > 1754) then
   begin
      Result := 0.0;
      Exit;
   end;
   Result := 1.0;
   if (R = 0) or (R = N) then
      Exit;
   if R > N div 2 then
      R := N - R;
   K := 2;
   try
      for I := N - R + 1 to N do
      begin
         Result := Result * I;
         if K <= R then
         begin
            Result := Result / K;
            Inc (K);
         end;
      end;
      Result := Int (Result + 0.5);
   except
      Result := -1.0
   end;
end;