Non c'è alcuna alternativa all'utilizzo di % (modulo) in C/C++?
https://stackoverflow.com/questions/48053
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho letto da qualche parte una volta che l'operatore di modulo è inefficiente su piccoli dispositivi embedded come 8 bit micro-controllori che non hanno la divisione di interi istruzione.Forse qualcuno può confermare questo, ma ho pensato che la differenza è di 5-10 tempo più lento che con un intero operazione di divisione.
C'è un altro modo per fare questo altro che mantenere una variabile contatore e manualmente traboccante a 0 al mod punto?
const int FIZZ = 6;
for(int x = 0; x < MAXCOUNT; x++)
{
if(!(x % FIZZ)) print("Fizz\n"); // slow on some systems
}
vs:
Il modo in cui attualmente sto facendo:
const int FIZZ = 6;
int fizzcount = 1;
for(int x = 1; x < MAXCOUNT; x++)
{
if(fizzcount >= FIZZ)
{
print("Fizz\n");
fizzcount = 0;
}
}
Soluzione
Ah, le gioie di bit a bit aritmetica.Un effetto collaterale di molti routine di divisione è il modulo in modo che, in alcuni casi dovrebbe divisione effettivamente essere più veloce di modulo.Sono interessato a vedere la fonte hai preso questa informazione dal.I processori con moltiplicatori sono interessanti divisione routine utilizzando il moltiplicatore, ma si può ottenere da una divisione risultato per modulo con solo due passaggi (moltiplicazione e sottrazione) quindi è ancora paragonabile.Se il processore è dotato di una divisione di routine probabilmente vedrete fornisce anche il resto.
Ancora, c'è un piccolo ramo della teoria dei numeri dedicati a L'Aritmetica Modulare che richiede studio, se si vuole veramente capire come ottimizzare un modulo di funzionamento.Modulare arithmatic, per esempio, è molto utile per la generazione di quadrati magici.
Così, in questa prospettiva, ecco un molto basso il livello di look presso la matematica del modulo per un esempio di x, che deve dimostrare quanto è semplice esso può essere paragonato a divisione:
Forse un modo migliore di pensare al problema in termini di numero di basi e il modulo aritmetico.Per esempio, il vostro obiettivo è quello di calcolare il DOW mod 7, dove il DOW è a 16 bit rappresentazione del giorno del settimana.Si può scrivere come:
DOW = DOW_HI*256 + DOW_LO
DOW%7 = (DOW_HI*256 + DOW_LO) % 7
= ((DOW_HI*256)%7 + (DOW_LO % 7)) %7
= ((DOW_HI%7 * 256%7) + (DOW_LO%7)) %7
= ((DOW_HI%7 * 4) + (DOW_LO%7)) %7
Espresso in questo modo, è possibile calcolare separatamente il modulo 7 risultato per l'alta e bassa byte.Moltiplicare il risultato per l'alto da 4 e aggiungi il basso e poi, finalmente, risultati di calcolo modulo 7.
Calcolo mod 7 risultato di un numero a 8 bit può essere eseguita in un in un modo simile.È possibile scrivere un numero a 8 bit in ottale in questo modo:
X = a*64 + b*8 + c
Dove a, b, e c sono 3-bit di numeri.
X%7 = ((a%7)*(64%7) + (b%7)*(8%7) + c%7) % 7
= (a%7 + b%7 + c%7) % 7
= (a + b + c) % 7
dal 64%7 = 8%7 = 1
Naturalmente, a, b, e c sono
c = X & 7
b = (X>>3) & 7
a = (X>>6) & 7 // (actually, a is only 2-bits).
Il più grande valore per a+b+c è 7+7+3 = 17.Così, avrete bisogno di
uno più ottale passo.Il completo (non testato) C versione potrebbe essere
scritto come:
unsigned char Mod7Byte(unsigned char X)
{
X = (X&7) + ((X>>3)&7) + (X>>6);
X = (X&7) + (X>>3);
return X==7 ? 0 : X;
}
Ho trascorso un paio di momenti di scrivere un PIC versione.L'effettiva attuazione è leggermente diverso da quello descritto sopra
Mod7Byte:
movwf temp1 ;
andlw 7 ;W=c
movwf temp2 ;temp2=c
rlncf temp1,F ;
swapf temp1,W ;W= a*8+b
andlw 0x1F
addwf temp2,W ;W= a*8+b+c
movwf temp2 ;temp2 is now a 6-bit number
andlw 0x38 ;get the high 3 bits == a'
xorwf temp2,F ;temp2 now has the 3 low bits == b'
rlncf WREG,F ;shift the high bits right 4
swapf WREG,F ;
addwf temp2,W ;W = a' + b'
; at this point, W is between 0 and 10
addlw -7
bc Mod7Byte_L2
Mod7Byte_L1:
addlw 7
Mod7Byte_L2:
return
Ecco un po ' di routine per verificare l'algoritmo
clrf x
clrf count
TestLoop:
movf x,W
RCALL Mod7Byte
cpfseq count
bra fail
incf count,W
xorlw 7
skpz
xorlw 7
movwf count
incfsz x,F
bra TestLoop
passed:
Infine, per il 16-bit di risultato (che non ho testato), si potrebbe scrivere:
uint16 Mod7Word(uint16 X)
{
return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
}
Scott
Altri suggerimenti
Se si calcola un numero di mod di qualche potenza di due, è possibile utilizzare il bit-wise e operatore.Basta sottrarre uno dal secondo numero.Per esempio:
x % 8 == x & 7
x % 256 == x & 255
Alcune avvertenze:
- Questo funziona solo se il secondo numero è una potenza di due.
- E ' solo per equivalente, se il modulo è sempre positivo.Il C e il C++ standard non specificare il segno del modulo quando il primo numero è negativo (fino al C++11, che non la garanzia sarà negativo, che è quello che la maggior parte dei compilatori erano già facendo).Un po ' saggio e si sbarazza del bit di segno, in modo da essere sempre positiva, cioèè un vero e proprio modulo, non il resto).Sembra che quello che vuoi comunque anche se.
- Il compilatore probabilmente già fa quando può, nella maggior parte dei casi non vale la pena di farlo manualmente.
C'è un overhead la maggior parte del tempo in utilizzando il modulo che non sono potenze di 2.Questo è a prescindere dal processore (AFAIK) anche processori con modulo gli operatori sono un paio di cicli più lento per dividere anziché maschera di operazioni.
Per la maggior parte dei casi questo non è un'ottimizzazione che è degno di considerazione, e certamente non vale la pena di calcolare i vostri operazione di scelta rapida (soprattutto se si tratta pur sempre di dividere o moltiplicare).
Tuttavia, una regola empirica è quello di selezionare le dimensioni degli array, etc.per essere potenze di 2.
così, se il calcolo del giorno della settimana, potrebbe anche usare %7 prescindere se l'impostazione di un buffer circolare di circa 100 voci...perché non farlo 128.È quindi possibile scrivere % a 128 e la maggior parte (tutti) i compilatori, che farà di questo & 0x7F
A meno che non si ha realmente bisogno di elevate prestazioni su più piattaforme embedded, non cambiare come codice per motivi di prestazioni fino al profilo!!!
Il codice che è scritto goffamente per ottimizzare le prestazioni è difficile eseguire il debug e difficile da mantenere.Scrivere un test, e il profilo di sul vostro bersaglio.Una volta che si conosce il costo effettivo del modulo, quindi decidere se la soluzione alternativa è la pena di codifica.
@Matteo è giusto.Prova questo:
int main() {
int i;
for(i = 0; i<=1024; i++) {
if (!(i & 0xFF)) printf("& i = %d\n", i);
if (!(i % 0x100)) printf("mod i = %d\n", i);
}
}
x%y == (x-(x/y)*y)
Spero che questo aiuta.
Nel mondo embedded, il "modulo" le operazioni che devi fare sono spesso quelli che rompono ben in bit operazioni che si possono fare con '&' e '|' e a volte '>>'.
Non si ha accesso a qualsiasi hardware programmabile sul dispositivo embedded?Come contatori e simili?Se è così, si potrebbe essere in grado di scrivere un hardware basato mod unità, invece di utilizzare il simulato %.(L'ho fatto una volta in VHDL.Non so se ho ancora il codice però.)
Mente voi, avete detto che la divisione è 5-10 volte più veloce.Avete considerato la possibilità di fare una divisione, moltiplicazione e sottrazione per simulare il mod?(Edit:Frainteso il post originale.Mi ha fatto pensare che fosse strano che la divisione era più veloce di mod, sono la stessa operazione.)
Nel tuo caso specifico, però, si deve controllare che il mod di 6.6 = 2*3.Così si potrebbe FORSE ottenere alcuni piccoli guadagni se hai controllato se il bit meno significativo è stato uno 0.Qualcosa di simile a:
if((!(x & 1)) && (x % 3))
{
print("Fizz\n");
}
Se lo si fa, però, mi consiglia di confermare che si ottiene alcun vantaggio, yay per il profiler.E facendo un po ' di commenti.Mi sento male per il prossimo ragazzo che ha di guardare il codice altrimenti.
Si dovrebbe davvero controllare il dispositivo incorporato di cui hai bisogno.Tutto il linguaggio assembly che ho visto (x86, 68000) implementare il modulo utilizzando una divisione.
In realtà, la divisione assemblea operazione restituisce il risultato della divisione e i restanti in due registri diversi.
Non che questo sia necessariamente migliore, ma si potrebbe avere un ciclo interno che va sempre fino a FIZZ, e un ciclo esterno che si ripete in tutto un certo numero di volte.Hai forse preso per caso speciale finale a pochi passi se MAXCOUNT non è divisibile per FIZZ.
Detto questo, mi piacerebbe suggerisco di fare qualche ricerca e di analisi delle prestazioni sulla tua intenzione di piattaforme, per avere una chiara idea dei vincoli di prestazioni si sta sotto.Ci può essere molto più produttivo luoghi per trascorrere il vostro sforzo di ottimizzazione.
@Jeff V:Vedo un problema!(Al di là che il codice originale era alla ricerca di una mod 6 e ora si sono essenzialmente cercando un mod 8).Continui a fare un ulteriore +1!Speriamo che il tuo compilatore ottimizza via, ma perché non prova a 2 e vai a MAXCOUNT inclusive?Infine, si restituisce true ogni volta che (x+1) NON è divisibile per 8.È questo che vuoi?(Suppongo che sia, ma voglio solo confermare.)
Per il modulo 6 è possibile modificare il codice Python in C/C++:
def mod6(number):
while number > 7:
number = (number >> 3 << 1) + (number & 0x7)
if number > 5:
number -= 6
return number
L'istruzione print prendere gli ordini di grandezza più lungo che anche il più lento attuazione dell'operatore modulo.Quindi, fondamentalmente, il commento "lento su alcuni sistemi" dovrebbe essere "lento su tutti i sistemi".
Inoltre, i due frammenti di codice fornito non fare la stessa cosa.Nella seconda, la linea
if(fizzcount >= FIZZ)
è sempre false, in modo che "FIZZ " non viene mai stampato.
