Hohe Fakultät nicht möglich?

[Privateer3000]

Hallo,

für eine mathmatische Funktion
wollt ich die Fakultät errechnen lassen.
Festgestellt habe ich dabei dass dies nur
beschränkt möglich ist.
Mittels Integer * Fakultaet(Integer - 1) lässt sich nur
bis 30! ein Ergebnis erzielen, danach erscheint 0.
Mir ist klar das ein zu hoher Integer zum Überlauf
führen kann. Kann man dies nicht abfangen und
trotzdem ein Ergebnis erhalten?

Grüße
Privateer

[jfheins]

Du kannst einen Int64 benutztn, der kommt etwas höher (um genau zu sein: 2^32 mal höher) als der normale Integer ;)

Aber mit 32 Bit kannst du nur noch 12! darstellen, 13! geht über die Grenze des Cardinals ;)

[negaH]

Hier im Forum mal auf Suche gehen das Thema wurde schon sehr oft behandelt.

Zb. http://www.delphipraxis.net/internal...t%E4t&start=20

Gruß Hagen

[Privateer3000]

Danke Leute

[Privateer3000]

Wie stellt man das an
wenn ein Überlauf mit
zb 1.3456 E62 dargestellt werden soll?
Da blick ich noch nicht durch....

[jfheins]

Du könntest auch einfach nen Double nehmen, der kann extrem hohe Zahlen darstellen (zu Lasten der Genauigkeit ...)

[Nikolas]

für was brauchst du die hohen Fakultäten überhaupt? Kannst du sie nicht mit etwas Mathe umgehen?

[Privateer3000]

Danke Leute,
die hohen fakultäten sind
mitunter beim Binomialkoeffizienten notwendig.
Da ich im Bereich der Kombinatorik einige
Versuche machen will.
Sollte man den Koeffizienten anders berechnen
können... immer her damit ! :-)

Mit abgekürzten Zahlen wie 1,23456E+016 kann
man keine weiterführene Berechnungen anstellen.
Oder doch :?:


Grüße

[Nikolas]

Reicht dir den TBigInteger von Hagen da auch nicht aus?
Was willst du denn genau berechnen? Kannst du nicht eine andere Verteilung benutzen?

[jfheins]

Du kannst den Binominalkoeffizienten anders berechnen ;)

Denn hier: http://upload.wikimedia.org/math/a/e...f1e0981da8.png(1)
Kannst du die verschiedenen Fakultäten zumindest Teilweise gegeneinander kürzen ;)

Da müsste auch etwas Code irgendwo sein ... :gruebel:

Binomial :arrow: http://www.delphipraxis.net/internal...=303010#303010 ;)

(1) (c) Wikipedia, 3.9.2007

[negaH]

Das Binomial läasst sich genauso effizient berechnen wie die Fakultät.

Also zb.

10! = 1*2*3*4*5*6*7*8*9*10

nun wandeln wir die Zahlen in Potenzschreibweise um

2^1 * 3^1 * 2^2 * 5^1 * (2^1 * 3^1) * 7^1 * 2^3 * 3^2 * (2^1 * 5^1)

nun gruppieren wir das nach den Basen der Potenzen um

(2^1 * 2^2 * 2^1 * 2^3 * 2^1) * (3^1 * 3^1 * 3^2) * (5^1 * 5^1) * 7^1

nun fassen wir das zusammen

10! = 2^8 * 3^4 * 5^2 * 7^1


Wenn wir nun N über K haben und N = 10 und K = 6 dann also 10! / (6! * 4!) daraus wird

2^8 * 3^4 * 5^2 * 7^1
---------------------
2^4 * 3^2 * 5^1 * 2^2

gleich

2^8 * 3^4 * 5^2 * 7^1
---------------------
2^6 * 3^2 * 5^1

nun kürzen wir einfach über die Exponenten das ergibt

2^2 * 3^2 * 5^1 * 7^1 = (10 über 4)

Wenn wir das nun effizient ausrechnen möchten dann betrachten wir mal die binäre Darstellung der Exponenten. Das ist hier ein sehr kleines Beispiel, bei großem N und K wird das noch deutlicher.

2^010 * 3^010 * 5^001 * 7^001 (Exponenten sind binär)

nun schreiben wir das mal um

2^010
3^010
5^001
7^001

Nun gehen wir die Binären Spalten von links nach rechts durch und schreiben

(2*3)^2 * (da bei diesen die erste 1 in deren Spalten steht)
(5*7)

10 über 4 = (2*3)^2 * (5*7)

Beispiel mal 100! =
(((((3)^2 *
3*5*7)^2 *
5*11)^2 *
13*17*19*23)^2 *
13*29*31*37*41*43*47)^2 *
11*13*17*19*29*31*53*59*61*67*71*73*79*83*89*97 * 2^97


Damit haben wir eine sehr effiziente Rechenvorschrift die nach Arnold Schönhage den effizientesten bekannten Berechnungsalgorithmus für die Fakultäten, Binomiale usw. ergibt.

Jede Muliplikation der einzelnen Zahlenbasen führen wir per Binary Splitting durch, das ist ein Divide and Conquer Verfahren (Teile und Herrsche). Zb. die Multiplikationen von

11*13*17*19*29*31*53*59*61*67*71*73*79*83*89*97

wir teilen diese Menge in der Mitte

(11*13*17*19*29*31*53*59) * (61*67*71*73*79*83*89*97)

und rufen rekursiv wieder eine Teilung der linken und rechten Hälfte auf

((11*13*17*19) * (29*31*53*59)) * ((61*67*71*73) * (79*83*89*97))

und das nochmal

(((11*13) * (17*19)) * ((29*31) * (53*59))) * (((61*67) * (71*73)) * ((79*83) * (89*97)))

und berechnen nun die Produkte so wie sie in Klammern stehen rekursiv aus. Damit multiplizieren wir immer 2 Zahlen (links und rechts) die in ihrer Größe annähernd gleichgroß sind.

Wollten wir sehr große Zahlen, eg. Fakultäten berechnen so sind diese Sets sehr sehr groß und es entstehen in den Teilprodukten sehr schnell sehr große Zahlen. Da wir immer zwei Produkte die annäherend gleichgroß sind (in ihrer binären Größe) erreichen wir mit jedem bekannten Multiplikationsverfahren den höchsten Datendurchsatz. Zb. gerade bei den Multiplikatonen per FFT=Fast Fourier Transformationen, zb. Modulare Fermat FFT nach A. Schönhage und S. Strassen, ist dieser Punkt der gleichgewichteten Multiplikanten enorm wichtig.

Oben haben wir eine Form der Binären Exponentation angewendet. Wir haben die Exponenten in ihrer binären Darstellung betrachtet und gehen diese binären Exponenten quasi Spaltenweise durch. Damit wandeln wir die normale Multiplikation in Quadrierungen um, wir schreiben quasi die die aus Multiplikationen bestehnde Formel in eine Formel um die maximal mögliche Anzahl an Quadrierungen benutzt. Nun eine Quadrierung ist 1.5 mal schneller ausführbar als eine vergleichbare Multiplikation. Dh. man kann eine Quadrierung nach heutigem Wissen per Software nicht schneller ausrechnen als 1.5mal schneller als eine vergleichbare Multipliaktion. Diesen Faktor habe ich in meiner Library verifizieren können.

Falls du tiefgehenderes Interesse hast so solltest du dir mein DECMath downloaden http://www.michael-puff.de/Developer...agen_Reddmann/
und darin die Unit NCombi.pas genauer anschauen. Darin enthalten sind alle oben angesprochene Tricks. Also Binäre Expansion um Quadrierungen statt Multiplikationen zu benutzen, das Kürzen beim Binomial und das direkte Ausrechnen der Potenzdarstellung der Fakultät.

Um also von 10! auf 2^8 * 3^4 * 5^2 * 7^1 zu kommen geht man so vor

10/2 = 5 -> +5
5/2 = 2 -> +2
2/2 = 1 -> +1

+5 +2 +1 = 8, ergo in 10! kommt der Term 2^8 vor.

10/3 = 3 -> +3
3/3 = 1 -> +1

in 10! kommt 3^4 vor

10/5 = 2 -> +2

in 10! kommt 5^2 vor.

10/7 = +1, 10! enthält 7^1

Die Überprüfung zur Basis 2 geht aber nochmal schneller, 10 - BitCount(10) = 8. Also einfach die Anzahl der 1'er Bit in N ausrechnen und das von N selber subtrahieren, ergibt die Anzahl der trailing Nullen wenn man N! als Binärzahl ausrechnen würde, bzw. eben den Exponenten zur Basis 2.

Gruß Hagen

[negaH]

Wollten wir nun die Exponenten schon gekürzt für 10! / (6! - 4!) errechnen also direkt auf 2^2 * 3^2 * 5^1 * 7^1 kommen dann geht das so

Delphi-Quellcode:

  function FindEP(K,L,N,P: Cardinal): Cardinal;
  // extract exponents to base P, where P is prime
  var
    E: Cardinal;
  begin
    E := 0;
    while K >= P do
    begin
      N := N div P;
      L := L div P;
      K := K div P;
      Inc(E, N - L - K);
    end;
    while L >= P do
    begin
      N := N div P;
      L := L div P;
      Inc(E, N - L);
    end;
    while N >= P do
    begin
      N := N div P;
      Inc(E, N);
    end;
    Result := E;
  end;

P ist unsere Primzahlbasis,
N dann 10
L dann 6
K dann 4


nun rufen wir für die Primzahlen 3,5,7 obige Funktion auf und bekommen

3^2 * 5^1 * 7^1 * 2^((N - L - K) - (BitCount(N) - BitCount(L) - BitCount(K)) <- ergibt 2^2

Man kann also mit 32 Bit Operationen sehr effizient und auf direktem Wege die Potenzschreibweise des Binomials ausrechnen und erreicht somit den mathematisch kürzesten Weg um das Binomial auszurechnen. Es gibt kein mir bekanntes Verfahren das effizienter und schneller zu berechnen wäre. Besoinderst wenn es sich um sehr große Binomiale, Fakultäten, das Produkt oder die Permutation handelt.

Übrigens mit obiger Funktion kann man auch zb. die Frage beantworten wieviele 0 Stellen am Ende der Fakultät,Binomial,Produkt,Permutation zu einer Basis diese haben.
Möchte man zb. wissen wie oft 10! durch zb. 2 oder 5 oder 10 (2*5) teilbar ohne Rest ist so kann man obige Funktion benutzen.

Man kann damit zb. die Potenzschreibweise von bis zu 4294967295! ausrechnen dazu benötigen wir nur die Primzahlen bis 4294967295.

Gruß Hagen

[Privateer3000]

Vielen Dank für diese ausführliche Beschreibung.
Ich werd das alles stückchenweise mal durchgehen
um den Lösungsweg zu verstehen.
Da auf unserem Dorfgymnasium das Hauptfach Entenfüttern
war, kannte ich diese Lösung garnicht ;-)

Vielen Dank

[negaH]

Das ist nicht so schlimm, die meisten kennen diesen Weg nicht. Selbst ich war davon überrascht, besonders weil er eigentlich trivial ist. Das Besondere ist aber das man mit diesem Beispiel der Mathematik die Zahlentheorie als Forschungsfeld der Mathematik besser verstehen lernt und Feuer fangen kann ;)

Gruß Hagen

[Privateer3000]

Na was ein echter Thüringer ist ;-) der fängt doch immer gleich Feuer
Tatsache ist, das ich mich ebenfalls für die Mathematik, insbesondere
Statistik und Kombinatorik interessiere weil es mich fesselt.

In diesem Sinne
ein tolles WE

Privateer

[negaH]

gerade heute Abend mal wieder tolle Soße in Kartoffeln geknescht ;)

Gruß Hagen