Calcolo (a * b) mod c velocemente per c = 2^N + -1

Question

In matematica a 32 bit, le operazioni matematiche di base di addizione e moltiplicazione vengono calcolate implicitamente mod 2^32, il che significa che i risultati saranno l'ordine più basso bit dell'aggiunta o della moltiplicazione.

Se si desidera calcolare il risultato con un modulo diverso, è possibile utilizzare qualsiasi numero di classi BigInt in diverse lingue. E per i valori a, b, c < 2^32 è possibile calcolare i valori intermedi in 64 bit di lunghezza e utilizzare% di operatori integrati per ridurre a destra la risposta

Ma mi è stato detto che ci sono trucchi speciali per il calcolo efficiente di un * b mod C quando C è del formato (2^N) -1 o (2^N) +1, che non usano la matematica a 64 bit o una libreria BigInt e sono abbastanza efficienti, più che una valutazione arbitraria del modulo, e anche calcolare correttamente i casi che normalmente sovrasfrutterebbero un int a 32 bit se si stesse includendo la moltiplicazione intermedia.

Sfortunatamente, nonostante abbia sentito che questi casi speciali hanno un metodo di valutazione veloce, non ho in realtà trovato una descrizione del metodo. "Non è quello a Knuth?" "Non è da qualche parte su Wikipedia?" sono i mormorii che ho sentito.

Apparentemente è una tecnica comune in generatori di numeri casuali che stanno facendo moltiplicazioni di un * b mod 2147483647, poiché 2147483647 è un numero primo uguale a 2^31 -1.

Quindi chiederò agli esperti. Cos'è questo astuto metodo speciale multiply-with-mod di cui non riesco a trovare nessuna discussione?

Answer 1

Credo che il trucco è il seguente (ho intenzione di farlo in base 10, perché è più facile, ma il principio dovrebbe tenere)

Supponiamo che stanno moltiplicando a*b mod 10000-1, e

a = 1234 = 12 * 100 + 34 
b = 5432 = 54 * 100 + 32 

ora a*b = 12 * 54 * 10000 + 34 * 54 * 100 + 12 * 32 * 100 + 34 * 32

12 * 54 * 10000 = 648 * 10000 
34 * 54 * 100 = 1836 * 100 
12 * 32 * 100 = 384 * 100 
34 * 32   = 1088 

Da x * 10000 ≡ x (mod 10000-1) [1], t il primo e l'ultimo termine diventano 648 + 1088. Il secondo e il terzo termine sono i punti in cui il "trucco" entra in gioco.Si noti che:

1836 = 18 * 100 + 36 
1836 * 100 ≡ 18 * 10000 + 3600 ≡ 3618 (mod 10000-1). 

Questo è essenzialmente uno spostamento circolare. Dando i risultati di 648 + 3618 + 8403 + 1088. E anche notare che in tutti i casi, i numeri moltiplicati sono < 10000 (dal momento che un < 100 e b < 100), quindi questo è calcolabile se si potessero più numeri a 2 cifre insieme e aggiungili.

In binario, funzionerà allo stesso modo.

Inizia con aeb, entrambi sono a 32 bit. Supponiamo che tu voglia moltiplicarli mod 2^31 - 1, ma hai solo un moltiplicatore a 16 bit (che dà 32 bit). L'algoritmo sarebbe qualcosa di simile a questo:

a = 0x12345678 
b = 0xfedbca98 
accumulator = 0 
for (x = 0; x < 32; x += 16) 
    for (y = 0; y < 32; y += 16) 
     // do the multiplication, 16-bit * 16-bit = 32-bit 
     temp = ((a >> x) & 0xFFFF) * ((b >> y) & 0xFFFF) 

     // add the bits to the accumulator, shifting over the right amount 
     total_bits_shifted = x + y 
     for (bits = 0; bits < total_bits_shifted + 32; bits += 31) 
      accumulator += (temp >> (bits - total_bits_shifted)) & 0x7FFFFFFF 

     // do modulus if it overflows 
     if (accumulator > 0x7FFFFFFFF) 
      accumulator = (accumulator >> 31) + (accumulator & 0x7FFFFFFF); 

E 'tardi, così la parte accumulatore che probabilmente non funzionerà. Penso che in linea di principio sia giusto comunque. Qualcuno si senta libero di modificarlo per farlo bene.

Srotolato, anche questo è abbastanza veloce, che è quello che usa il PRNG, immagino.

[1]: x*10000 ≡ x*(9999+1) ≡ 9999*x + x ≡ x (mod 9999)

Answer 2

Una ricerca rapida ha visualizzato questo: http://home.pipeline.com/~hbaker1/AB-mod-N.pdf. Sfortunatamente, è troppo tardi per me avere abbastanza senso da scrivere semplicemente nella formula semplificata, ma probabilmente è su quel foglio da qualche parte.

Answer 3

Supponiamo di poter calcolare a * b come p*2^N+q. Questo può richiedere calcoli a 64 bit, oppure è possibile dividere a e b in parti a 16 bit e calcolare su 32 bit.

Quindi a*b mod 2^N-1 = p+q mod 2^N-1 dal 2^N mod 2^N-1 = 1.

E a*b mod 2^N+1 = -p+q mod 2^N+1 dal 2^N mod 2^N+1 = -1.

In entrambi i casi, non esiste alcuna divisione per 2^N-1 o 2^N+1.

Answer 4

Anziché eseguire una riduzione modulare ad ogni passaggio, è possibile utilizzare Montgomery reduction (ce ne sono altri descriptions) per ridurre il costo del calcolo della moltiplicazione modulare. Questo comunque non usa le proprietà di N essendo più/meno una potenza di due, però.

Answer 5

L'identità che stai cercando è x mod N = (x mod 2^q)- c*floor(x/2^q), dato che N = 2^q + c e c è qualsiasi numero intero (ma in genere ± 1).

Si consiglia di leggere sezione 9.2.3: "Moduli di forma speciale" in "numeri primi: una prospettiva computazionale" di Richard Crandall e Carl Pomerance. Oltre alla teoria, contiene pseudocodice per un algoritmo che implementa la relazione di cui sopra.

Answer 6

Ho trovato una rather extensive page su questo argomento, discutendo non solo l'algoritmo, ma anche la specifica storia del problema e la soluzione e il modo le persone hanno utilizzato la soluzione.