Hohe Fakultät nicht möglich?

[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