Qual è il modo più veloce per dividere un intero per 3?

int x = n / 3; // <-- make this faster // for instance int a = n * 3; // <-- normal integer multiplication int b = (n << 1) + n; // <-- potentially faster multiplication 

Questo è il più veloce in quanto il compilatore lo ottimizzerà se può dipendere dal processore di output.

 int a; int b; a = some value; b = a / 3; 

Il tizio che ha detto “lascia fare al compilatore” aveva ragione, ma non ho la “reputazione” per modificarlo o commentare. Ho chiesto a gcc di compilare int test (int a) {return a / 3; } per un ix86 e quindi disassemblato l’output. Solo per interesse accademico, ciò che sta facendo è approssimativamente moltiplicato per 0x55555556 e poi prendendo i primi 32 bit del risultato a 64 bit di quello. Puoi dimostrarlo a te stesso ad esempio:

 $ ruby ​​-e 'puts (60000 * 0x55555556 >> 32)'
 20000
 $ ruby ​​-e 'puts (72 * 0x55555556 >> 32)'
 24
 $ 

La pagina di Wikipedia sulla divisione Montgomery è difficile da leggere ma per fortuna i compilatori lo hanno fatto in modo da non doverlo fare.

C’è un modo più veloce per farlo se si conoscono gli intervalli dei valori, ad esempio se si divide un intero con segno per 3 e si conosce che l’intervallo del valore da dividere è compreso tra 0 e 768, quindi è ansible moltiplicarlo di un fattore e spostarlo a sinistra di una potenza di 2 a quel fattore diviso per 3.

per esempio.

Intervallo 0 -> 768

potresti usare lo spostamento di 10 bit, che moltiplicando per 1024, vuoi dividere per 3 quindi il tuo moltiplicatore dovrebbe essere 1024/3 = 341,

quindi ora puoi usare (x * 341) >> 10
(Assicurati che lo spostamento sia un turno firmato se usi interi con segno), assicurati anche che lo spostamento sia effettivamente uno spostamento e non un po ‘ROLL

Questo dividerà efficacemente il valore 3, e funzionerà a circa 1,6 volte la velocità come una divisione naturale per 3 su una CPU x86 / x64 standard.

Ovviamente l’unico motivo per cui è ansible fare questa ottimizzazione quando il compilatore non riesce è perché il compilatore non conosce l’intervallo massimo di X e quindi non può effettuare questa determinazione, ma tu come il programmatore.

A volte può essere anche più vantaggioso spostare il valore in un valore più grande e quindi fare la stessa cosa, cioè. se hai una int dell’intervallo completo potresti renderlo un valore a 64 bit e quindi moltiplicare e spostare invece di dividere per 3.

Ho dovuto farlo di recente per accelerare l’elaborazione delle immagini, avevo bisogno di trovare la media di 3 canali di colore, ogni canale di colore con un intervallo di byte (0 – 255). rosso verde e blu.

All’inizio ho semplicemente usato:

avg = (r + g + b) / 3;

(Quindi r + g + b ha un massimo di 768 e un minimo di 0, perché ogni canale è un byte 0 – 255)

Dopo milioni di iterazioni, l’intera operazione ha richiesto 36 millisecondi.

Ho cambiato la riga per:

avg = (r + g + b) * 341 >> 10;

E questo lo portò giù a 22 millisecondi, è sorprendente quello che si può fare con un po ‘di ingegno.

Questa accelerazione si è verificata in C # anche se ho triggersto le ottimizzazioni ed eseguivo il programma in modo nativo senza eseguire il debug delle informazioni e non tramite l’IDE.

Vedi Come dividere per 3 per una discussione estesa su come dividere in modo più efficiente per 3, focalizzata sul fare operazioni aritmetiche FPGA.

Anche rilevante:

  • Ottimizzazione delle divisioni in interi con Multiply Shift in C #

A seconda della piattaforma e in base al compilatore C, una soluzione nativa come il semplice utilizzo

 y = x / 3 

Può essere veloce o può essere terribilmente lento (anche se la divisione viene eseguita interamente in hardware, se viene eseguita utilizzando un’istruzione DIV, questa istruzione è da 3 a 4 volte più lenta di una moltiplicazione sulle CPU moderne). Molto buoni compilatori C con flag di ottimizzazione triggersti ​​possono ottimizzare questa operazione, ma se si vuole essere sicuri, è meglio ottimizzarlo da soli.

Per l’ottimizzazione è importante avere numeri interi di una dimensione nota. In C int non ha dimensioni conosciute (può variare a seconda della piattaforma e del compilatore!), Quindi è meglio usare interi C99 a dimensione fissa. Il codice seguente presuppone che si desideri dividere un intero a 32 bit senza segno per tre e che il compilatore C conosce i numeri interi a 64 bit ( NOTA: anche su un’architettura CPU a 32 bit la maggior parte dei compilatori C è in grado di gestire interi a 64 bit ):

 static inline uint32_t divby3 ( uint32_t divideMe ) { return (uint32_t)(((uint64_t)0xAAAAAAABULL * divideMe) >> 33); } 

Per quanto possa sembrare assurdo, il metodo sopra descritto dividerà per 3. Tutto ciò che serve per farlo è una singola moltiplicazione a 64 bit e uno spostamento (come ho detto, le moltiplicazioni potrebbero essere da 3 a 4 volte più veloci delle divisioni sulla CPU ). In un’applicazione a 64 bit questo codice sarà molto più veloce rispetto a un’applicazione a 32 bit (in un’applicazione a 32 bit moltiplicando due numeri a 64 bit occorrono 3 moltiplicazioni e 3 aggiunte su valori a 32 bit) – tuttavia, potrebbe essere ancora più veloce di un divisione su una macchina a 32 bit.

D’altra parte, se il tuo compilatore è molto buono e sa come ottimizzare la divisione intera di una costante (l’ultimo GCC lo fa, ho appena controllato), genererà comunque il codice sopra (GCC creerà esattamente questo codice per “/ 3” se si abilita almeno il livello di ottimizzazione 1). Per altri compilatori … non puoi fare affidamento o aspettarti che utilizzi trucchi del genere, anche se questo metodo è molto ben documentato e menzionato ovunque su Internet.

Il problema è che funziona solo per numeri costanti, non per quelli variabili. Hai sempre bisogno di conoscere il numero magico (qui 0xAAAAAAAB) e le operazioni corrette dopo la moltiplicazione (spostamenti e / o aggiunte nella maggior parte dei casi) ed entrambi sono diversi a seconda del numero che vuoi dividere ed entrambi richiedono troppo tempo CPU per calcolarli al volo (che sarebbe più lento della divisione hardware). Tuttavia, è facile per un compilatore calcolarli durante il tempo di compilazione (dove un secondo più o meno tempo di compilazione gioca a malapena un ruolo).

E se davvero non volessi moltiplicare o dividere? Ecco è un’approssimazione che ho appena inventato. Funziona perché (x / 3) = (x / 4) + (x / 12). Ma poiché (x / 12) = (x / 4) / 3 dobbiamo solo ripetere il processo fino a quando non è abbastanza buono.

 #include  void main() { int n = 1000; int a,b; a = n >> 2; b = (a >> 2); a += b; b = (b >> 2); a += b; b = (b >> 2); a += b; b = (b >> 2); a += b; printf("a=%d\n", a); } 

Il risultato è 330. Potrebbe essere reso più preciso usando b = ((b + 2) >> 2); per tenere conto dell’arrotondamento.

Se ti è permesso moltiplicare, scegli un’approssimazione adatta per (1/3), con un divisore di potenza di 2. Ad esempio, n * (1/3) ~ = n * 43/128 = (n * 43) >> 7.

Questa tecnica è molto utile in Indiana.

Non so se è più veloce, ma se si desidera utilizzare un operatore bit a bit per eseguire la divisione binaria, è ansible utilizzare il metodo di spostamento e sottrazione descritto in questa pagina :

  • Imposta il quoziente su 0
  • Allinea le cifre più a sinistra in dividendo e divisore
  • Ripetere:
    • Se quella porzione del dividendo sopra il divisore è maggiore o uguale al divisore:
      • Quindi sottrarre il divisore da quella parte del dividendo e
      • Concatenare 1 all’estremità destra del quoziente
      • Altrimenti concatenare 0 all’estremità destra del quoziente
    • Sposta il divisore in un punto a destra
  • Fino a quando il dividendo è inferiore al divisore:
  • il quoziente è corretto, il dividendo è il resto
  • STOP

Se vuoi davvero vedere questo articolo sulla divisione dei numeri interi , ma ha solo un merito accademico … sarebbe un’applicazione interessante che effettivamente ha bisogno di eseguire ciò che ha beneficiato di questo tipo di trucco.

Per una divisione intera molto grande (ad es. Numeri maggiori di 64 bit) puoi rappresentare il tuo numero come un int [] ed eseguire la divisione abbastanza velocemente prendendo due cifre alla volta e dividendole per 3. Il resto farà parte delle due cifre successive e così via.

per esempio. 11004/3 dici

11/3 = 3, rimanente = 2 (da 11-3 * 3)

20/3 = 6, resto = 2 (da 20-6 * 3)

20/3 = 6, resto = 2 (da 20-6 * 3)

24/3 = 8, resto = 0

da qui il risultato 3668

 internal static List Div3(int[] a) { int remainder = 0; var res = new List(); for (int i = 0; i < a.Length; i++) { var val = remainder + a[i]; var div = val/3; remainder = 10*(val%3); if (div > 9) { res.Add(div/10); res.Add(div%10); } else res.Add(div); } if (res[0] == 0) res.RemoveAt(0); return res; } 

Per numeri a 64 bit:

 uint64_t divBy3(uint64_t x) { return x*12297829382473034411ULL; } 

Tuttavia questa non è la divisione troncante di interi che potreste aspettarvi. Funziona correttamente se il numero è già divisibile per 3, ma restituisce un numero enorme se non lo è.

Ad esempio, se lo esegui per l’esempio 11, restituisce 6148914691236517209. Sembra una spazzatura ma in realtà è la risposta corretta: moltiplicala per 3 e ottieni 11!

Se stai cercando la divisione troncante, usa semplicemente l’operatore /. Dubito fortemente che tu possa ottenere molto più velocemente di così.

Teoria:

L’aritmetica senza segno a 64 bit è un aritmetico modulo 2 ^ 64. Ciò significa che per ogni numero intero che è coprimo con il modulo 2 ^ 64 (essenzialmente tutti i numeri dispari) esiste un inverso moltiplicativo che è ansible utilizzare per moltiplicare anziché per divisione. Questo numero magico può essere ottenuto risolvendo l’equazione 3*x + 2^64*y = 1 usando l’algoritmo euclideo esteso.

Computazione facile … al massimo n iterazioni in cui n è il tuo numero di bit:

 uint8_t divideby3(uint8_t x) { uint8_t answer =0; do { x>>=1; answer+=x; x=-x; }while(x); return answer; } 

Un approccio alla tabella di ricerca sarebbe anche più veloce in alcune architetture.

 uint8_t DivBy3LU(uint8_t u8Operand) { uint8_t ai8Div3 = [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ....]; return ai8Div3[u8Operand]; }