n über k - berechnen!?

[negaH]

Zitat:

(49*48*47*46*45*44) / (1*2*3*4*5*6)

Und das lässt sich nach A.Schönhage noch weiter kürzen.


49*48*47*46*45*44
----------------- =
1*2*3*4*5*6


7*7 * 2*2*2*2*3 * 47 * 2*23 * 2*2*11
------------------------------------ =
2*3*2*2*5*2*3

2^7 * 3^1 * 7^2 * 11 * 47
------------------------- =
2^4 * 3^2 * 5^1

nun Exponenten kürzen, also 2^7 / 2^4 = 2^(7-4) = 2^3

2^3 * 7^2 * 11^1 * 47^1
----------------------- =
3^1 * 5^1

bei der Berechnung dieses Bruches und der Potenzen kann man nun ebenfalls zwei Tricks anwenden:

1.) Potenzen ausmultiplizieren mit Hilfe der "Binary Powering" Methode.
Zb. 2^3 ist 2^011b wenn man die Potenz von 3 in binär darstellt -> 2^3 -> 2^2 * 2^1. 2^2 ist 2 zum Quadrat und man kann statt einfacher Multiplikation mit einem schnelleren Quadrierungs Algortihmus arbeiten. Die Quadrierung einer großen Zahl ist 1.5 mal schneller durchfüphrbar als die entsprechene Multipikatation.
Man nimmt nun die Potenz 3 binär -> 11b. Geht die Bits in einer Schleife von MSB-1 zu LSB durch und quadriert in jedem Schritt das Resultat. Wenn ein Bit im Exponenten gesetzt ist multipliziert man das Ergebnis noch mit der Basis.

2.) "Binary Splitting" dabei hat man eine ganze Liste von Zwischenprodukten die man ausmultiplizieren möchte. Zb. 2*3*4*5. Man teilt diese Liste in der Hälfte und rechnet rekursiv die Linke und Rechte Hälfte aus. Also (2*3) * (4*5). So stellt man sicher das die Zischenprodukte während der Multiplikationen immer möglichst gleich groß sind und somit deie höchtste Performance der verwendeten Multiplikationsalgorithmen erreicht.

Alle diese Tricks verwendet mein DECMath. Mal hier rein lesen http://www.delphipraxis.net/internal...orial&start=20
Das Binomial ist nichts anderes als die Division zweier Fakultäten. Also zerlegt man beide Fakultäten in deren Primzahlpotenzen und subtrahiert nun die Exponenten mit gleicher Basis voneinander. Übrig bleibt die Potenzschreibweise des gesuchten Binomials.


Gruß Hagen