Satz von Lucas (Lucas Theorem) und beliebig große Binomialkoeffizienten

Neue Frage »

Hosenschlange Auf diesen Beitrag antworten »
Satz von Lucas (Lucas Theorem) und beliebig große Binomialkoeffizienten
Hallo,

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!)
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
def factorial(n):
 	f = 1
 	while n > 1:
 		f *= n
 		n -= 1
 	return f

def binomial(n, k):
 	return factorial(n) / (factorial(k) * factorial(n-k))

def binomialModPrime(n, k, p):
 	size = 0

	while p**size <= n:
 		size += 1
 	size -= 1
 	Npow = [0] * (size+1)
 	Kpow = [0] * (size+1)

 	while size:
 		q = n // p**size
 		Npow[size] = q
 		n -= q * p**size
 		q = k // p**size
 		Kpow[size] = q
 		k -= q * p**size
 		size -= 1

 	Npow[size] = n
 	Kpow[size] = k

 	size = 1
 	for i in range(0, len(Npow)):
 		size *= binomial(Npow[i], Kpow[i])

 	return size % p

#
N = 10**12
K = 10**9
P = 997
print binomialModPrime(N, K, P)
Hosenschlange Auf diesen Beitrag antworten »

Es geht natürlich nicht _nur_ ums Ergebnis, sondern auch um den richtigen Weg dorthin....
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?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Hosenschlange
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.

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) ? verwirrt
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.
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.
 
 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »