Schneller Weg, um n zu berechnen! mod m wobei m prim ist?

n beliebig groß werden kann

Gut, n können nicht willkürlich großen - wenn n >= m, dann n! ≡ 0 (mod m) (weil m ist einer der Faktoren, durch die definition der Fakultät).

Vorausgesetzt n << m benötigen Sie genaue Wert, Ihren Algorithmus kann gar nicht schneller, meines Wissens nach. Allerdings, wenn n > m/2 können, verwenden Sie die folgende Identität (Wilson ' s theorem - Danke @Daniel Fischer!)

cap die Anzahl der Multiplikationen bei etwa m-n

(m-1)! ≡ -1 (mod m) 
1 * 2 * 3 * ... * (n-1) * n * (n+1) * ... * (m-2) * (m-1) ≡ -1 (mod m) 
n! * (n+1) * ... * (m-2) * (m-1) ≡ -1 (mod m) 
n! ≡ -[(n+1) * ... * (m-2) * (m-1)]-1 (mod m) 

Dies gibt uns eine einfache Möglichkeit zur Berechnung n! (mod m) im m-n-1 Multiplikationen, plus ein modulare inverse:

def factorialMod(n, E-Modul): 
ans=1 
wenn n <= E-Modul//2: 
#berechnen der Fakultät in der Regel (Rechte argument von range() ist exklusive) 
for i in range(1,n+1): 
ans = (ans * i) % E-Modul 
sonst: 
#Fancypants-Methode für große n 
for i in range(n+1,E-Modul): 
ans = (ans * i) % E-Modul 
ans = modinv(ans, E-Modul) 
ans = -1*ans + Modul 
Rückkehr ans - % - Modul 

Können wir umformulieren der obigen Gleichung auf eine andere Weise, die möglicherweise oder möglicherweise nicht ausführen etwas schneller. Anhand der folgenden Identität:

können wir formulieren die Gleichung

n! ≡ -[(n+1) * ... * (m-2) * (m-1)]-1 (mod m) 
n! ≡ -[(n+1-m) * ... * (m-2-m) * (m-1-m)]-1 (mod m) 
(umgekehrte Reihenfolge der Bedingungen) 
n! ≡ -[(-1) * (-2) * ... * -(m-n-2) * -(m-n-1)]-1 (mod m) 
n! ≡ -[(1) * (2) * ... * (m-n-2) * (m-n-1) * (-1)(m-n-1)]-1 (mod m) 
n! ≡ [(m-n-1)!]-1 * (-1)(m-n) (mod m) 

Dies kann in Python geschrieben wie folgt:

def factorialMod(n, E-Modul): 
ans=1 
wenn n <= E-Modul//2: 
#berechnen der Fakultät in der Regel (Rechte argument von range() ist exklusive) 
for i in range(1,n+1): 
ans = (ans * i) % E-Modul 
sonst: 
#Fancypants-Methode für große n 
for i in range(1,modulo-n): 
ans = (ans * i) % E-Modul 
ans = modinv(ans, E-Modul) 

#Da m eine ungerade Primzahl ist, (-1)^(m-n) = -1, falls n gerade ist, +1 wenn n ungerade 
if n % 2 == 0: 
ans = -1*ans + Modul 
Rückkehr ans - % - Modul 

Wenn Sie nicht brauchen, ein genaue Wert, wird das Leben ein bisschen leichter - Sie können Stirling ' s approximation zum berechnen einer ungefähren Wert in O(log n) Zeit (mit Potenzierung durch Quadratur).

Schließlich sollte ich erwähnen, dass, wenn diese zeitkritisch ist und du bist mit Python, versuchen Sie die Umstellung zu C++. Aus persönlicher Erfahrung, Sie sollten erwarten, dass etwa eine Größenordnung höhere Geschwindigkeit oder mehr, einfach deshalb, weil dies genau die Art von CPU-bound tight-Schleife, die nativ kompilierten code zeichnet sich bei (auch, aus welchem Grund auch immer, GMP scheint viel feiner abgestimmt als Python-Bignum).

InformationsquelleAutor der Antwort BlueRaja - Danny Pflughoeft

Wenn wir berechnen wollen M = a*(a+1) * ... * (b-1) * b (mod p) können wir den folgenden Ansatz, wenn wir annehmen, können wir addieren, subtrahieren und multiplizieren schnell (mod p), und erhalten eine Laufzeit Komplexität von O( sqrt(b-a) * polylog(b-a) ).

Zur Vereinfachung wird angenommen, dass (b-a+1) = k^2 ist ein Quadrat. Jetzt können wir teilen unser Produkt in k Teile, D. H. M = [a*..*(a+k-1)] *...* [(b-k+1)*..*b]. Jeder der Faktoren in diesem Produkt ist von der form p(x)=x*..*(x+k-1) für entsprechende x.

Durch die Verwendung eines schnellen Algorithmus zur Matrixmultiplikation von Polynomen, wie Schönhage–Strassen-Algorithmus, in einem divide & conquer Weise, kann man die Koeffizienten des Polynoms p(x) in O( k * polylog(k) ). Nun, offenbar gibt es einen Algorithmus für das ersetzen k Punkte im gleichen Maß-k Polynom in O( k * polylog(k) ), was bedeutet, können wir berechnen p(a), p(a+k), ..., p(b-k+1) schnell.

Dieser Algorithmus der Substitution viele Punkte in ein Polynom beschrieben wird in dem Buch "Primzahlen" von C. Pomerance und R. Crandall. Schließlich, wenn Sie diese k Werte, Sie können multiplizieren Sie Sie in O(k) und den gewünschten Wert.

Beachten Sie, dass alle unsere Operationen wurden (mod p).
Die genaue Laufzeit ist O(sqrt(b-a) * log(b-a)^2 * log(log(b-a))).

InformationsquelleAutor der Antwort ohad

Wenn n = (m - 1) für prime-m dann durch http://en.wikipedia.org/wiki/Wilson's_theorem n! mod m = (m - 1)

Auch, wie schon darauf hingewiesen, n! mod m = 0, wenn n > m

InformationsquelleAutor der Antwort Philip Riebold

Dieser Algorithmus hat O(n log log(n)) preprocessing-Zeit Komplexität (durch Sieb) und O(r(n)) Speicherplatz-Komplexität, wo r(n) ist die prime counting function. Nach der preprocessing -, Abfrage-x! wo x <= N ist O(r(x) * log(x)).

Leider wird dies nicht machbar für 10¹⁰ da r(1e9) ist 455,052,511 die fast 2GB Speicher zum speichern der Primzahlen. Für 10⁹ aber, wir brauchten nur rund 300MB Speicher.

Angenommen mod ist 1e9+7 um zu vermeiden, überlauf in C++, aber es kann alles sein.

Eine Art zu berechnen N! mod m schnell

Berechnen N! schnell, können wir zerlegen N in seine Primfaktoren. Es kann beobachtet werden, dass wenn p eine Primzahl Faktor von N!, p muss <= N, da N! ist ein Produkt der ganzen zahlen von 1 bis N. in Anbetracht dieser Tatsachen, können wir berechnen N! mit nur Primzahlen von 2 bis N (inklusive). Nach Wikipedia, es gibt 50,847,534 ungefähr (~5 * 10^7) Primzahlen kleiner oder gleich 10⁹. Dies wäre die Formel zu verwenden:

v_p(N!) ist die größte Zahl, so dass p^v_p(N!) teilt N!. Legendre-Formel berechnet v_p(N!) in O(log(N)) Zeit. Hier ist die Formel aus Wikipedia.

int factorial(int n) {
    int ans = 1;
    for (int i = 0; i < primes.size() && primes[i] <= n; i++) {
        int e = 0;
        for (int j = n; j > 0; ) {
            j /= primes[i];
            e += j;
        }
        ans = ((u64) ans * fast_power(primes[i], e)) % mod;
    }
    return ans;
}

fast_power(x, y) gibt x^y % mod O(log(y)) Zeit mit exponeniation durch Quadratur.

Generierung Von Primzahlen

Ich bin Generierung von Primzahlen mit Sieb des Eratosthenes. In meiner Implementierung des Sieb, ich bin mit bitset um Speicher zu sparen. Meine Umsetzung dauerte 16-18seconds zum generieren von Primzahlen bis zu 10^9 wenn ich kompiliert habe, mit -O3 flag mit einer 2. Gen i3 Prozessor. Ich bin sicher, es gibt bessere algorithmen/Implementierungen für die Generierung von Primzahlen.

const int LIMIT = 1e9;
bitset<LIMIT+1> sieve;
vector<int> primes;

void go_sieve() {
    primes.push_back(2);
    int i = 3;
    for (int i = 3; i * i <= LIMIT; i+=2) {
        if (!sieve.test(i)) {
            primes.push_back(i);
            for (int j = i * i; j <= LIMIT; j += i) {
                sieve.set(j);
            }
        }
    }
    while (i <= LIMIT) {
        if (!sieve.test(i)) primes.push_back(i);
        i+=2;
    }
}

Speicherverbrauch

Laut Wikipedia, es gibt 50,847,534 Primzahlen, die kleiner oder gleich 10^9. Da ein 32-bit-Ganzzahl aus 4 bytes, die prime-Vektor muss 203.39 MB (50,847,534 * 4 bytes). Das Sieb bitset Bedürfnisse (125 MB) 10^9 bits.

Leistung

War ich in der Lage zu berechnen 1,000,000,000! in 1,17 Sekunden nach der Verarbeitung.

Hinweis: ich hab den Algorithmus mit dem -O3 flag aktiviert.

InformationsquelleAutor der Antwort Mercado