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