re implementare modulo usando i bit shift?

Question

Sto scrivendo del codice per un sistema molto limitato in cui l'operatore mod è molto lento. Nel mio codice deve essere usato un modulo circa 180 volte al secondo e ho pensato che rimuoverlo il più possibile avrebbe aumentato significativamente la velocità del mio codice, dal momento che un ciclo del mio mainloop non viene eseguito in 1/60 di un secondo come dovrebbe Mi chiedevo se fosse possibile ri-implementare il modulo usando solo i bit shift come è possibile con la moltiplicazione e la divisione. Quindi qui è il mio codice finora in C++ (se posso eseguire un modulo utilizzando assembly sarebbe ancora meglio). Come posso rimuovere il modulo senza utilizzare la divisione o la moltiplicazione?

while(input > 0) 
{ 
    out = (out << 3) + (out << 1); 
    out += input % 10; 

    input = (input >> 8) + (input >> 1); 
} 

EDIT: In realtà mi sono reso conto che ho bisogno di farlo molto più di 180 volte al secondo. Visto che il valore di input può essere un numero molto grande fino a 40 cifre.

Answer 1

Che cosa si può fare con semplice operazioni bit a bit sta prendendo un modulo di potenza di due (divisore) del valore (dividendo) da parte di AND'ing con divisore-1. Alcuni esempi:

unsigned int val = 123; // initial value 
unsigned int rem; 

rem = val & 0x3; // remainder after value is divided by 4. 
       // Equivalent to 'val % 4' 
rem = val % 5; // remainder after value is divided by 5. 
       // Because 5 isn't power of two, we can't simply AND it with 5-1(=4). 

Perché funziona? Consideriamo un modello di bit per il valore 123 che è 1111011 e quindi il divisore 4, che ha lo schema di bit di 00000100. Come sappiamo ormai, il divisore deve essere power-of-two (come 4 è) e abbiamo bisogno di decrementarlo di uno (da 4 a 3 in decimale) che ci restituisce il bit pattern 00000011. Dopo aver applicato bit per bit-AND sia dell'originale 123 che di quello 3, il modello di bit risultante sarà 00000011. Questo risulta essere 3 in decimale. Il motivo per cui abbiamo bisogno di un divisore di potenza di due è che una volta decrementati di uno, otteniamo tutti i bit meno significativi impostati su 1 e il resto è 0. Una volta eseguito il bit-AND, esso "annulla" i bit più significativi dal valore originale e ci lascia semplicemente con il resto del valore originale diviso per il divisore. Tuttavia, applicare qualcosa di specifico come questo per i divisori arbitrari non funzionerà se non si conoscono i divisori in anticipo (al momento della compilazione, e anche in questo caso richiede codepath specifici del divisore) - risolverlo non è fattibile, specialmente non nel tuo caso in cui le prestazioni sono importanti.

Inoltre c'è a previous question related to the subject che probabilmente ha informazioni interessanti sull'argomento da diversi punti di vista.

Answer 2

Fare il modulo 10 con i cambi di bit sarà difficile e brutto, poiché i cambiamenti di bit sono intrinsecamente binari (su qualsiasi macchina su cui si sta lavorando oggi). Se ci pensate, i bit shift sono semplicemente moltiplicare o dividere per 2.

Ma c'è un ovvio scambio spazio-temporale che potreste fare qui: impostate una tabella di valori per out e out % 10 e cercatelo. Poi la linea diventa

out += tab[out] 

e con po 'di fortuna, che si rivelerà essere una 16-bit aggiungere e un'operazione di memorizzazione.

Answer 3

Se si desidera eseguire modulo 10 e turni, forse è possibile adattare double dabble algorithm alle proprie esigenze?

Questo algoritmo viene utilizzato per convertire numeri binari in decimali senza utilizzare modulo o divisione.

Answer 4

Ogni potenza di 16 termina in 6.Se rappresenti il ​​numero come una somma di poteri di 16 (cioè lo spezziamo in nybbles), allora ogni termine contribuisce all'ultima cifra nello stesso modo, eccetto il posto di uno.

0x481A % 10 = (0x4 * 6 + 0x8 * 6 + 0x1 * 6 + 0xA) % 10 

Nota che 6 = 5 + 1, e i 5 si annulleranno se ce ne sono un numero pari. Quindi somma i nybbles (tranne l'ultimo) e aggiungi 5 se il risultato è dispari.

0x481A % 10 = (0x4 + 0x8 + 0x1 /* sum = 13 */ 
       + 5 /* so add 5 */ + 0xA /* and the one's place */) % 10 
      = 28 % 10 

Questo riduce a 16 bit, 4 nybble modulo di un numero al massimo 0xF * 4 + 5 = 65. In binario, è fastidiosamente ancora 3 nybbles quindi è necessario ripetere l'algoritmo (anche se uno di questi non conta davvero).

Ma il 286 dovrebbe avere un'aggiunta di BCD ragionevolmente efficiente che è possibile utilizzare per eseguire la somma e ottenere il risultato in un passaggio. (Questo richiede la conversione manuale di ogni nybble in BCD, non so abbastanza sulla piattaforma per dire come ottimizzarlo o se è problematico.)

Answer 5

In realtà la divisione per costanti è un ottimizzazione ben nota per i compilatori e infatti, gcc lo sta già facendo.

Questo semplice frammento di codice:

int mod(int val) { 
    return val % 10; 
} 

genera il seguente codice sul mio piuttosto vecchio gcc con -O3:

_mod: 
     push ebp 
     mov  edx, 1717986919 
     mov  ebp, esp 
     mov  ecx, DWORD PTR [ebp+8] 
     pop  ebp 
     mov  eax, ecx 
     imul edx 
     mov  eax, ecx 
     sar  eax, 31 
     sar  edx, 2 
     sub  edx, eax 
     lea  eax, [edx+edx*4] 
     mov  edx, ecx 
     add  eax, eax 
     sub  edx, eax 
     mov  eax, edx 
     ret 

Se non rispetti la funzione epilogo/prologo, fondamentalmente due Muls (anzi su x86 siamo fortunati e possiamo usare lea per uno) e alcuni turni e aggiunge/sottotitoli. So che ho già spiegato da qualche parte la teoria alla base di questa ottimizzazione, quindi vedrò se riesco a trovare quel post prima di spiegarlo ancora una volta.

Ora su CPU moderne è sicuramente più veloce dell'accesso alla memoria (anche se si colpisce la cache), ma se è più veloce per la tua CPU ovviamente un po 'più antica è una domanda alla quale è possibile rispondere solo con benchmark (e anche assicurarsi il tuo compilatore sta facendo questa ottimizzazione, altrimenti puoi sempre "rubare" la versione di gcc qui;)). Soprattutto considerando che dipende da un mulh efficiente (cioè bit più alti di un'istruzione moltiplicata) per essere efficiente. Si noti che questo codice è non dimensioni indipendenti: per essere precisi il numero magico cambia (e forse anche le parti di add/shift), ma che può essere adattato.

Answer 6

Prendi una copia di "Writing Efficient Programs" di Jon Bentley (purtroppo esaurito, un riassunto è nel suo "Programming Pearls"). Discute su come (e quando!) Spremere l'ultima goccia di prestazioni dai programmi. Semplici cambiamenti come quello qui discusso sono fatti naturalmente dagli attuali compilatori, controllano il codice assemblatore di fonti alternative e mantengono tutto ciò che è più chiaro.