Satz von Lucas (Lucas Theorem) und beliebig große Binomialkoeffizienten |
30.11.2016, 20:31 | Hosenschlange | Auf diesen Beitrag antworten » | |||||
Satz von Lucas (Lucas Theorem) und beliebig große Binomialkoeffizienten ich habe versucht, den Satz von Lucas (Lucas's Theorem) umzusetzen. Es geht hierbei um den Rest aus der Division (n über k) mod p, p ist prim. Das Prinzip hab ich mir von der englischen Wikipedia-Seite hergeleitet, zu der es leider keine deutsche Übersetzung gibt. Ich hab das ganze mit billigstem Quelltext in Python2 probiert. Für das folgende Beispiel mit n = 10^12, k = 10^9, p = 997 erhalte ich als Ergebnis 39. Kann das jemand bestätigen? (Der Quelltext ist einfach nur schnell zusammengebastelt - ohne jegliche Optimierung. Es geht nur ums Ergebnis!)
|
|||||||
30.11.2016, 22:02 | Hosenschlange | Auf diesen Beitrag antworten » | |||||
Es geht natürlich nicht _nur_ ums Ergebnis, sondern auch um den richtigen Weg dorthin.... |
|||||||
04.12.2016, 19:39 | Hosenschlange | Auf diesen Beitrag antworten » | |||||
Ich habe das Programm auch mit anderen Zahlen laufen lassen und feststellen müssen, dass für bestimmte Primzahlen P bzw. Werte N und K die Routine falsche Ergebnisse auswirft. Könnte mir evtl jemand weiterhelfen, was in dem Code falsch ist? |
|||||||
04.12.2016, 22:58 | HAL 9000 | Auf diesen Beitrag antworten » | |||||
Welche Programmiersprache nutzt du da? D.h., bist du dir wirklich sicher, dass deine Variablen beliebige Genauigkeit haben, und nicht etwa limitiert sind (bei vorzeichenbehafteten 64Bit-Integerzahlen nach oben durch 2^63-1 = 9223372036854775807) ? |
|||||||
05.12.2016, 07:08 | Hosenschlange | Auf diesen Beitrag antworten » | |||||
Das ist Python. Ich habe extra diese Sprache gewählt, um genau diesem Problem aus dem Weg zu gehen. Die Fehler scheinen auch nur in bestimmten Fällen aufzutreten, beispielsweise bei P = 5. |
|||||||
06.12.2016, 17:45 | Hosenschlange | Auf diesen Beitrag antworten » | |||||
Fehler gefunden. Ich musste den Algorithmus für den Binomialkoeffizienten umformulieren und den Fall k > n beachten, danach ging's. |
|||||||
Anzeige | |||||||
|
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|