Modo veloce per calcolare n! mod m dove m è primo?

Question

Ero curioso di sapere se c'era un buon modo per farlo. Il mio codice attuale è qualcosa del tipo:

def factorialMod(n, modulus): 
    ans=1 
    for i in range(1,n+1): 
     ans = ans * i % modulus  
    return ans % modulus 

Ma sembra piuttosto lento!

Inoltre non riesco a calcolare n! e quindi applicare il modulo primario perché a volte n è così grande che n! è semplicemente non fattibile calcolare in modo esplicito.

Mi sono anche imbattuto nello http://en.wikipedia.org/wiki/Stirling%27s_approximation e mi chiedo se questo possa essere usato qui in qualche modo?

Oppure, come è possibile creare una funzione ricorsiva e memorizzata in C++?

Answer 1

Ampliare il mio commento ad una risposta:

Sì, ci sono modi più efficaci per farlo. Ma sono estremamente disordinati.

Quindi, a meno che non si abbia davvero bisogno di prestazioni extra, non suggerisco di provare a implementarle.

---

La chiave è da notare che il modulo (che è essenzialmente una divisione) sarà l'operazione collo di bottiglia. Fortunatamente, ci sono alcuni algoritmi molto veloci che ti permettono di eseguire più moduli sullo stesso numero molte volte.

• Division by Invariant Integers using Multiplication
• Montgomery Reduction

Questi metodi sono veloci perché sostanzialmente eliminare il modulo.

---

Questi metodi da soli dovrebbero darti una moderata accelerazione. Per essere veramente efficace, potrebbe essere necessario srotolare il ciclo per consentire una migliore IPC:

Qualcosa di simile a questo:

ans0 = 1 
ans1 = 1 
for i in range(1,(n+1)/2): 
    ans0 = ans0 * (2*i + 0) % modulus  
    ans1 = ans1 * (2*i + 1) % modulus  

return ans0 * ans1 % modulus 

ma tenendo conto di un # dispari di iterazioni e combinandolo con uno dei metodi che ho collegato sopra.

Alcuni potrebbero sostenere che il ciclo di srotolamento dovrebbe essere lasciato al compilatore. Contrasterò che i compilatori al momento non sono abbastanza intelligenti da srotolare questo particolare ciclo. Dai un'occhiata più da vicino e vedrai perché.

---

Si noti che sebbene la mia risposta sia indipendente dal linguaggio, è intesa principalmente per C o C++.

Answer 2

Partendo dal presupposto che l'operatore "mod" della vostra piattaforma scelta è sufficientemente veloce, il gioco è delimitato in primo luogo dalla velocità con cui è possibile calcolare n! e lo spazio che avete a disposizione per calcolare in.

Poi è essenzialmente un'operazione in 2 fasi:

1. Calcola n! (Ci sono un sacco di algoritmi veloci quindi non ripetere alcun qui)
2. Prendere la mod del risultato

Non c'è bisogno di complexify cose, soprattutto se la velocità è il componente fondamentale. In generale, esegui il minor numero possibile di operazioni all'interno del loop.

Se è necessario calcolare ripetutamente n! mod m, è possibile memorizzare i valori che escono dalla funzione eseguendo i calcoli. Come sempre, è il classico compromesso spazio/tempo, ma le tabelle di ricerca sono molto veloce.

Infine, è possibile combinare la memoizzazione con la ricorsione (e anche i trampolini se necessario) per ottenere rapidamente .

Answer 3

n può essere arbitrariamente grande

Beh, n non può essere arbitrariamente grande - se n >= m, quindi n! ≡ 0 (mod m)(perché m è uno dei fattori, dalla definizione di fattoriale).

---

Supponendo n << m ed è necessario un esatto valore , l'algoritmo non può andare più veloce, a mia conoscenza. Tuttavia, se n > m/2, è possibile utilizzare la seguente identità (Wilson's theorem - Grazie @Daniel Fischer!)

di limitare il numero di moltiplicazioni a circa 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) 

Questo ci dà un modo semplice per calcolare n! (mod m) in m-n-1 moltiplicazioni, oltre a un modular inverse:

 
def factorialMod(n, modulus): 
    ans=1 
    if n <= modulus//2: 
     #calculate the factorial normally (right argument of range() is exclusive) 
     for i in range(1,n+1): 
      ans = (ans * i) % modulus 
    else: 
     #Fancypants method for large n 
     for i in range(n+1,modulus): 
      ans = (ans * i) % modulus 
     ans = modinv(ans, modulus) 
     ans = -1*ans + modulus 
    return ans % modulus 

---

Possiamo riformulare l'equazione di cui sopra in un altro modo, che potrebbe o meno eseguire leggermente più velocemente. Utilizzando la seguente identità:

possiamo riformulare l'equazione come

 
n! ≡ -[(n+1) * ... * (m-2) * (m-1)]-1 (mod m) 
n! ≡ -[(n+1-m) * ... * (m-2-m) * (m-1-m)]-1 (mod m) 
     (reverse order of terms) 
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) 

Questo può essere scritto in Python come segue:

 
def factorialMod(n, modulus): 
    ans=1 
    if n <= modulus//2: 
     #calculate the factorial normally (right argument of range() is exclusive) 
     for i in range(1,n+1): 
      ans = (ans * i) % modulus 
    else: 
     #Fancypants method for large n 
     for i in range(1,modulus-n): 
      ans = (ans * i) % modulus 
     ans = modinv(ans, modulus) 

     #Since m is an odd-prime, (-1)^(m-n) = -1 if n is even, +1 if n is odd 
     if n % 2 == 0: 
      ans = -1*ans + modulus 
    return ans % modulus 

---

Se don' t necessario un valore esatto , lif e diventa un po 'più facile - è possibile utilizzare Stirling's approximation per calcolare un valore approssimativo nel tempo O(log n)(utilizzando exponentiation by squaring).

---

Infine, dovrei dire che se questo è time-critical e stai usando Python, prova a passare a C++. Dall'esperienza personale, dovresti aspettarti un aumento di velocità dell'ordine o maggiore, semplicemente perché questo è esattamente il tipo di limite stretto della CPU che il codice compilato in origine eccelle allo (anche, per qualsiasi motivo , GMP sembra molto più finemente accordato rispetto a Bignum di Python).

Answer 4

Ampliando il mio commento, questo richiede circa il 50% del tempo per ogni n in [100, 100007] dove m = (117 | 1117):

Function facmod(n As Integer, m As Integer) As Integer 
    Dim f As Integer = 1 
    For i As Integer = 2 To n 
     f = f * i 
     If f > m Then 
      f = f Mod m 
     End If 
    Next 
    Return f 
End Function 

Answer 5

n! mod m può essere calcolato in O (n ^{1/2 + & epsilon;}) anziché in O (n). Ciò richiede l'uso della moltiplicazione polinomiale FFT e vale solo per n molto grandi, ad es. n> 10 .

Cenni dell'algoritmo e alcuni tempi può essere visto qui: http://fredrikj.net/blog/2012/03/factorials-mod-n-and-wilsons-theorem/

Answer 6

Se vogliamo calcolare M = a*(a+1) * ... * (b-1) * b (mod p), possiamo utilizzare il seguente approccio, se assumiamo possiamo aggiungere, sottrarre e moltiplicare veloce (mod p), e ottenere una complessità del tempo di esecuzione di O(sqrt(b-a) * polylog(b-a)).

Per semplicità, supporre (b-a+1) = k^2, è un quadrato. Ora, possiamo dividere il nostro prodotto in k parti, ad esempio M = [a*..*(a+k-1)] *...* [(b-k+1)*..*b]. Ciascuno dei fattori in questo prodotto è nella forma p(x)=x*..*(x+k-1), per l'appropriato x.

Utilizzando un algoritmo rapida moltiplicazione di polinomi, come Schönhage–Strassen algorithm, in un gap & conquista modo, si possono trovare i coefficienti del polinomio p(x) in O(k * polylog(k)). Ora, a quanto pare, esiste un algoritmo per sostituire i punti k nello stesso polinomio di grado-k in O(k * polylog(k)), il che significa che possiamo calcolare velocemente p(a), p(a+k), ..., p(b-k+1).

Questo algoritmo di sostituzione di molti punti in un polinomio è descritto nel libro "Numeri primi" di C. Pomerance e R. Crandall. Alla fine, quando disponi di questi valori k, puoi moltiplicarli in O(k) e ottenere il valore desiderato.

Si noti che tutte le nostre operazioni sono state prese (mod p). L'ora esatta è O(sqrt(b-a) * log(b-a)^2 * log(log(b-a))).

Answer 7

Se n = (m - 1) per primo m poi per http://en.wikipedia.org/wiki/Wilson 's_theorem n! mod m = (m - 1)

Anche come è già stato sottolineato n!mod m = 0 se n> m

Answer 8

Ho trovato questa seguente funzione su quora:
Con f (n, m) = n! mod m;

function f(n,m:int64):int64; 
     begin 
       if n = 1 then f:= 1 
       else f:= ((n mod m)*(f(n-1,m) mod m)) mod m; 
     end; 

Probabilmente batti utilizzando un ciclo che richiede tempo e moltiplicando il numero grande memorizzato nella stringa. Inoltre, è applicabile a qualsiasi numero intero m.
Il link dove ho trovato questa funzione: https://www.quora.com/How-do-you-calculate-n-mod-m-where-n-is-in-the-1000s-and-m-is-a-very-large-prime-number-eg-n-1000-m-10-9+7

Answer 9

Questo algoritmo ha O(n log log(n)) tempo di pre-elaborazione della complessità (a causa del setaccio) e O (r (n)) la complessità spazio dove r(n) è il prime counting function. Dopo la pre-elaborazione, interrogando x! dove x <= N è O(r(x) * log(x)).

Sfortunatamente questo non è fattibile per 10 poiché r (1e9) è 455.052.511 che richiedono quasi 2 GB di memoria per memorizzare gli interi primi. Tuttavia, per il 10 , avevamo solo bisogno di circa 300 MB di memoria.

Supponiamo che mod sia 1e9 + 7 per evitare l'overflow in C++, ma può essere qualsiasi cosa.

Un modo per calcolare N! mod m fast

Per calcolare N! veloce, possiamo decomporre N ai suoi fattori primi. Si può osservare che se p è un fattore primo di N !, p deve essere < = N poiché N! è un prodotto degli interi da 1 a N. Dati questi fatti, possiamo calcolare N! utilizzando solo numeri primi tra 2 e N (inclusi). Secondo Wikipedia, ci sono 50.847.534 numeri primi (~ 5 * 10^7) inferiori o uguali a 10 . Questa sarebbe la formula da utilizzare:

v _{p (! N)} è il maggior numero tale che p ^{v _p (! N)} divide N !. Legendre's formula calcoli v _p (N!) Nel tempo O (log (N)). Ecco la formula da 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) rendimenti x ^y% mod in O (log (y)) tempo utilizzando exponeniation by squaring.

Generazione Primes

sto generando numeri primi utilizzando Sieve of Eratosthenes. Nella mia implementazione del setaccio, sto usando bitset per risparmiare memoria. La mia applicazione ha preso 16-18seconds per generare numeri primi fino a 10^9 quando ho compilato con -O3 bandiera con 2nd Generation processore i3 . Sono sicuro che ci sono migliori algoritmi/implementazioni per la generazione di numeri primi.

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; 
    } 
} 

consumo di memoria

Secondo Wikipedia, ci sono 50,847,534 numeri primi che sono inferiori o uguali a 10^9. Poiché un numero intero a 32 bit è 4 byte, il vettore principale richiede 203,39 MB (50,847,534 * 4 byte). Il setaccio setaccio ha bisogno di (125 MB) 10^9 bit.

prestazioni

sono stato in grado di calcolare miliardo! in 1,17 secondi dopo l'elaborazione.

Nota: ho eseguito l'algoritmo con il flag -O3 abilitato.