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

Question

In 32 bit integer matematica, operazioni matematiche di base di add e si moltiplicano sono calcolati in modo implicito mod 2 ^ 32, che significa i risultati saranno i più bassi bit di ordine del componente aggiuntivo o moltiplicare.

Se si vuole calcolare il risultato con un modulo diverso, è certamente possibile utilizzare qualsiasi numero di classi bigint in diverse lingue. E per i valori a, b, c <2 ^ 32 è possibile calcolare i valori intermedi di interi lunghi 64 bit e utilizzare costruito in operatori% per ridurre al answe destra

Ma mi è stato detto che ci sono trucchi speciali per il calcolo in modo efficiente a * b mod C quando C è della forma (2 ^ N) -1 o (2 ^ N) 1, che non utilizzare 64 po 'di matematica o una libreria BigInt e sono abbastanza efficienti, più che una valutazione modulo arbitrario, e anche calcolare correttamente i casi che normalmente sovraccaricare la a 32 bit int se si stesse includi la moltiplicazione intermedio.

Purtroppo, nonostante sentendo che tali casi particolari hanno un metodo di valutazione rapida, non ho effettivamente trovato una descrizione del metodo. "Non è che in Knuth?" "Non è che da qualche parte su Wikipedia?" sono le mumblings che ho sentito.

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

Quindi mi chiedo agli esperti. Che cos'è questo caso particolare intelligente moltiplicano-con-mod metodo che non riesco a trovare alcuna discussione di?

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 si 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

Dal x * 10000 ≡ x (mod 10000-1) [1], i primi e gli ultimi termini diventano 648 + 1088. Il secondo e terzo termini sono dove il 'trucco' venuto nella nota che:.

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

Questo è essenzialmente uno spostamento circolare. Dare i risultati di 648 + 3618 + 8403 + 1088. E nota anche che in tutti i casi, i numeri sono moltiplicate <10000 (dal momento che un <100 e b <100), quindi questo è calcolabile se voi solo potessi multipla 2 numeri a due cifre insieme , e aggiungerli.

In binario, che sta andando a lavorare in modo simile.

Inizia con A e B, entrambi sono 32 bit. Si supponga di voler moltiplicare loro mod 2 ^ 31-1, ma hai solo un moltiplicatore a 16 bit (32 bit dare). 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 è giusto però. Qualcuno si sente libero di modificarla per renderla di destra.

Unrolled, questo è abbastanza veloce, così, che è quello che l'uso PRNG, sto cercando di indovinare.

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

Answer 2

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

Poi 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 v'è alcuna divisione per 2^N-1 o 2^N+1.

Answer 3

Una rapida ricerca alzato questo: http: //home.pipeline .com / ~ hbaker1 / AB-mod-N.pdf . Purtroppo, è troppo tardi per me fare abbastanza senso di che scrivere solo nella formula semplificata, ma è probabilmente che la carta da qualche parte.

Answer 4

Piuttosto che fare la riduzione modulare ad ogni passo, è possibile utilizzare Montgomery riduzione (ci sono altri ) per ridurre il costo di calcolo moltiplicazione modulare. Questo ancora non usa le proprietà di N è 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" "numeri primi: una prospettiva computazionale" di Richard Crandall e Carl Pomerance. Oltre teoria, contiene pseudocodice per un algoritmo di attuazione la relazione di cui sopra.

Answer 6

Ho trovato un piuttosto estesa pagina su questo argomento, non discutere solo l'algoritmo, ma anche la specifica storia del problema e la soluzione e il modo persone hanno utilizzato la soluzione.