Il codice IDEA utilizza la moltiplicazione modulo 2^16 + 1
. Esiste un algoritmo per eseguire questa operazione senza operatore modulo generale (solo modulo 2^16
(troncamento))? Nel contesto di IDEA, zero viene interpretato come 2^16
(significa che zero non è un argomento della nostra moltiplicazione e non può essere il risultato, quindi possiamo salvare un bit e memorizzare il valore 2^16
come bit pattern 0000000000000000
). Mi chiedo come implementarlo in modo efficiente (o se è possibile) senza utilizzare l'operatore modulo standard.Modulo di moltiplicazione veloce 2^16 + 1
risposta
È possibile utilizzare il fatto che (N-1)% N == -1.
Pertanto, (65536 * a)% 65537 == -a% 65537.
Inoltre, -a% 65537 == -a + 1 (mod 65536), quando viene interpretato come 0 65536
uint16_t fastmod65537(uint16_t a, uint16_t b)
{
uint32_t c;
uint16_t hi, lo;
if (a == 0)
return -b + 1;
if (b == 0)
return -a + 1;
c = (uint32_t)a * (uint32_t)b;
hi = c >> 16;
lo = c;
if (lo > hi)
return lo-hi;
return lo-hi+1;
}
l'unico problema qui è se hi == lo
, il risultato sarebbe 0. Per fortuna una suite di test conferma, che in realtà non può essere ...
int main()
{
uint64_t a, b;
for (a = 1; a <= 65536; a++)
for (b = 1; b <= 65536; b++)
{
uint64_t c = a*b;
uint32_t d = (c % 65537) & 65535;
uint32_t e = m(a & 65535, b & 65535);
if (d != e)
printf("a * b % 65537 != m(%d, %d) real=%d m()=%d\n",
(uint32_t)a, (uint32_t)b, d, e);
}
}
uscita: nessuno
ps. L'esecuzione della suite nel core i5 ha dimostrato più rapidamente il metodo% 65537. –
Ancora non capisco come funzionino le ultime 5 righe. Suppongo che sia più lento a causa di quel due if o compilatore sta facendo un po 'di magia sotto il cofano. – ciechowoj
Ok, vedo che questo spostamento è solo div e il troncamento è mod. – ciechowoj
In primo luogo, il caso in cui sia a
o b
è zero. In tal caso, viene interpretato come avente il valore 2^16, quindi elementare modulo aritmetica ci dice che:
result = -a - b + 1;
, perché (nel contesto IDEA) l'inverso moltiplicativo di 2^16 è ancora 2^16 e i suoi 16 bit più bassi sono tutti zero.
Il caso generale è molto più facile di quello che sembra, ora che abbiamo preso cura della "0" caso speciale (2^16 + 1 è 0x10001):
/* This operation can overflow: */
unsigned result = (product & 0xFFFF) - (product >> 16);
/* ..so account for cases of overflow: */
result -= result >> 16;
Mettere insieme:
/* All types must be sufficiently wide unsigned, e.g. uint32_t: */
unsigned long long product = a * b;
if (product == 0) {
return -a - b + 1;
} else {
result = (product & 0xFFFF) - (product >> 16);
result -= result >> 16;
return result & 0xFFFF;
}
- 1. moltiplicazione matrice sparse veloce
- 2. Moltiplicazione modulo (in C)
- 3. Moltiplicazione veloce di interi molto grandi
- 4. più veloce moltiplicazione Fixnum in rubino?
- 5. PHP strano risultato della moltiplicazione per -1
- 6. Moltiplicazione
- 7. Ottimizzazione moltiplicazione modulo un piccolo primo
- 8. ottimizzata 2x2 moltiplicazione matriciale: assemblaggio lenta rispetto SIMD veloce
- 9. Divisione veloce 1/X (reciproco)
- 10. Limitazione modulo riproduzione 1
- 11. Moltiplicazione di matrice parallela
- 12. MySQL moltiplicazione di matrici
- 13. Moltiplicazione memorizzabile
- 14. Moltiplicazione di due polinomi
- 15. moltiplicazione di due numeri
- 16. java matrix-moltiplicazione (FAST)
- 17. Perché la moltiplicazione della matrice è più veloce con numpy che con ctypes in Python?
- 18. Matrix moltiplicazione sequenze di matrici
- 19. Perché la comprensione degli elenchi è molto più veloce di numpy per la moltiplicazione degli array?
- 20. Algoritmo veloce modulo 3 o divisione?
- 21. Perché chiamare vector.reserve (richiesto + 1) più veloce di vector.reserve (richiesto)?
- 22. Perché `-1 * x` più veloce di` -x` e perché?
- 23. Perché i = i + 1 è più veloce di i ++?
- 24. Perché selezionare 1 più veloce di Select count (*)?
- 25. Lista moltiplicazione
- 26. Come calcolare esecuzione Moltiplicazione
- 27. Java moltiplicazione strano comportamento
- 28. CSR Matrix - Matrix moltiplicazione
- 29. tempo Moltiplicazione in BigInteger
- 30. L'utilizzo di RSA per la moltiplicazione modulo porta all'errore su Java Card
Ho aggiunto qualche chiarimento. – ciechowoj