Il modo più veloce per ottenere un modulo positivo in C/C++

Question

Spesso nei miei loop interni ho bisogno di indicizzare un array in un modo "wrap-around", in modo che se la dimensione dell'array è 100 e il mio codice richiede l'elemento -2 , dovrebbe essere fornito l'elemento 98. In molti linguaggi di alto livello come Python, si può fare semplicemente con my_array[index % array_size], ma per qualche motivo l'intero aritmetico di C (di solito) arrotonda verso zero invece di arrotondare costantemente verso il basso, e di conseguenza il suo operatore modulo ritorna un risultato negativo quando viene dato un primo argomento negativo.

Spesso so che lo index non sarà inferiore a -array_size e in questi casi faccio solo my_array[(index + array_size) % array_size]. Tuttavia, a volte questo non può essere garantito, e per quei casi mi piacerebbe sapere il modo più veloce per implementare una funzione modulo sempre positiva. Ci sono diversi modi "intelligenti" per farlo senza ramificazione, come

inline int positive_modulo(int i, int n) { 
    return (n + (i % n)) % n 
} 

o

inline int positive_modulo(int i, int n) { 
    return (i % n) + (n * (i < 0)) 
} 

Certo che posso profilo questi per scoprire quale è il più veloce sul mio sistema, ma posso Aiutatemi a preoccuparmi che possa essermi perso uno migliore, o che quello che è veloce sulla mia macchina potrebbe essere lento su uno diverso.

Quindi c'è un modo standard per fare questo, o qualche trucco intelligente che ho perso che è probabile che sia il modo più veloce possibile?

Inoltre, so che probabilmente è un pio desiderio, ma se c'è un modo per farlo che può essere auto-vettorializzato, sarebbe fantastico.

Answer 1

Modulo una potenza di due, le seguenti opere (due a due assumendo completano la rappresentazione):

return i & (n-1); 

Answer 2

Il metodo standard che ho imparato è

inline int positive_modulo(int i, int n) { 
    return (i % n + n) % n; 
} 

Questa funzione è essenzialmente la vostra prima variante senza la abs (che, di fatto, fa ritornare il risultato sbagliato). Non sarei sorpreso se un compilatore ottimizzante potesse riconoscere questo modello e compilarlo al codice macchina che calcola un "modulo senza segno".

Edit:

Passando alla seconda variante: Prima di tutto, contiene un bug, anche - il n < 0 dovrebbe essere i < 0.

Questa variante potrebbe non sembrare una diramazione, ma su molte architetture, lo i < 0 verrà compilato in un salto condizionato. In ogni caso, sarà altrettanto rapido sostituire (n * (i < 0)) con i < 0? n: 0, che evita la moltiplicazione; inoltre, è "più pulito" perché evita di reinterpretare il bool come int.

Per quanto riguarda quale di queste due varianti è più veloce, ciò dipende probabilmente dal compilatore e dall'architettura del processore: tempo le due varianti e vedere. Non penso che ci sia un modo più veloce di una di queste due varianti, però.

Answer 3

Si può anche fare array[(i+array_size*N) % array_size], dove N è un numero intero abbastanza grande da garantire argomenti positivi, ma abbastanza piccolo da non eccedere.

Quando array_size è costante, esistono tecniche per calcolare il modulo senza divisione.Oltre alla potenza di due approcci, è possibile calcolare una somma ponderata di gruppi di bit moltiplicata per 2^i% n, dove i è il bit meno significativo in ciascun gruppo:

, ad es. Intero a 32 bit 0xaabbccdd% 100 = dd + cc * [2] 56 + bb * [655] 36 + aa * [167772] 16, con l'intervallo massimo di (1 + 56 + 36 + 16) * 255 = 27795. Con applicazioni ripetute e suddivisioni diverse si può ridurre l'operazione a poche sottrazioni condizionali.

Le pratiche comuni includono anche l'approssimazione della divisione con reciproco di 2^32/n, che di solito può gestire un intervallo di argomenti ragionevolmente ampio.

i - ((i * 655)>>16)*100; // (gives 100*n % 100 == 100 requiring adjusting...) 

Answer 4

Un modo vecchia scuola per ottenere l'addendo opzionale utilizzando complemento a due sign-bit propagazione:

int positive_mod(int i, int n) 
{ 
    /* constexpr */ int shift = CHAR_BIT*sizeof i - 1; 
    int m = i%n; 
    return m+ (m>>shift & n); 
} 

Answer 5

Il secondo esempio è migliore del primo. Una moltiplicazione è un'operazione più complessa di un'operazione if/else, quindi usa:

inline int positive_modulo(int i, int n) { 
    int tmp = i % n; 
    return tmp ? i >= 0 ? tmp : tmp + n : 0; 
}