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

Question

int x = n / 3;  // <-- make this faster

// for instance

int a = n * 3; // <-- normal integer multiplication

int b = (n << 1) + n; // <-- potentially faster multiplication

Answer 1

Questo è il più veloce in quanto il compilatore lo ottimizzerà se possibile a seconda del processore di output.

int a;
int b;

a = some value;
b = a / 3;

Answer 2

Il tizio che ha detto "lascialo al compilatore" aveva ragione, ma non ho la "reputazione" per modificarlo o commentarlo. 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 moltiplicarsi per 0x55555556 e quindi prendere 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 su Divisione Montgomery è difficile da leggere ma fortunatamente i compilatori l'hanno fatto quindi non è necessario.

Answer 3

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

ad es.

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,

così ora puoi usare (x * 341) > > 10
(Assicurati che il turno sia un turno con segno se usi numeri interi con segno), assicurati anche che il turno sia un turno reale e non un po 'ROTTO

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

Ovviamente l'unica ragione per cui puoi fare questa ottimizzazione quando il compilatore non può essere perché il compilatore non conosce la gamma massima di X e quindi non può fare questa determinazione, ma tu come il programmatore puoi.

A volte potrebbe persino essere più vantaggioso spostare il valore in un valore più grande e quindi fare la stessa cosa, ad es. se hai un int di intervallo completo puoi renderlo un valore di 64 bit e quindi fare il moltiplicare e spostare invece di dividere per 3.

Di recente ho dovuto farlo per accelerare l'elaborazione delle immagini, dovevo 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, poiché ogni canale è un byte 0 - 255)

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

Ho cambiato la linea in:

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

E questo ha portato a 22 millisecondi, è incredibile cosa si può fare con un po 'di ingegnosità.

Questa accelerazione si è verificata in C # anche se avevo attivato le ottimizzazioni e eseguivo il programma in modo nativo senza informazioni di debug e non tramite l'IDE.

Answer 4

Vedi How To Divide By 3 per una discussione estesa di più divisione efficiente per 3, incentrata sull'esecuzione di operazioni aritmetiche FPGA.

Anche rilevante:

• Ottimizzazione delle divisioni intere con lo spostamento multiplo in C #

Answer 5

A seconda della piattaforma e in base al compilatore C, una soluzione nativa come usare semplicemente

y = x / 3

Può essere veloce o può essere terribilmente lento (anche se la divisione viene eseguita interamente nell'hardware, se viene eseguita utilizzando un'istruzione DIV, questa istruzione è circa 3-4 volte più lenta di una moltiplicazione su CPU moderne). Ottimi compilatori C con flag di ottimizzazione attivati ??possono ottimizzare questa operazione, ma se vuoi essere sicuro, è meglio ottimizzarla tu stesso.

Per l'ottimizzazione è importante disporre di numeri interi di dimensioni note. In C int non ha dimensioni note (può variare in base alla piattaforma e al compilatore!), Quindi è meglio usare numeri interi di dimensioni fisse C99. Il codice seguente presuppone che si desideri dividere un numero intero a 32 bit senza segno per tre e che il compilatore C sia a conoscenza dei numeri interi a 64 bit ( NOTA: anche su un'architettura CPU a 32 bit la maggior parte dei compilatori C può gestire numeri interi a 64 bit solo multa ):

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

Per quanto folle possa sembrare, ma il metodo sopra in effetti si divide per 3. Tutto ciò che serve per farlo è una singola moltiplicazione a 64 bit e uno spostamento (come ho detto, le moltiplicazioni potrebbero essere 3-4 volte più veloci delle divisioni sulla tua CPU). In un'applicazione a 64 bit questo codice sarà molto più veloce che in un'applicazione a 32 bit (in un'applicazione a 32 bit la moltiplicazione di due numeri a 64 bit richiede 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 conosce il trucco come ottimizzare la divisione di numeri interi di una costante (l'ultimo GCC fa, ho appena controllato), genererà comunque il codice sopra (GCC creerà esattamente questo codice per " / 3 " se abiliti almeno il livello di ottimizzazione 1). Per altri compilatori ... non puoi fare affidamento o aspettarti che utilizzerà trucchi del genere, anche se questo metodo è ben documentato e menzionato ovunque su Internet.

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

Answer 6

Che cosa succede se davvero non vuoi 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 non ci resta che ripetere il processo fino a quando non è abbastanza buono.

#include <stdio.h>

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 è consentito moltiplicare, seleziona 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.

Answer 7

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

  

  
• Imposta il quoziente su 0
  
• Allinea le cifre più a sinistra in dividendo e divisore
  
• Ripeti:      
    
  • Se quella parte del dividendo sopra il divisore è maggiore o uguale al divisore:      
      
    • Quindi sottrai il divisore da quella parte del dividendo e
      
    • Concatena 1 all'estremità destra del quoziente
      
    • Altrimenti concatentate 0 all'estremità destra del quoziente
      
    
  • Sposta il divisore di un posto a destra
    
  
• Fino a quando il dividendo è inferiore al divisore:
  
• il quoziente è corretto, il dividendo è il resto
  
• STOP
  

Answer 8

Per numeri a 64 bit:

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

Tuttavia, questa non è la divisione del numero intero troncante che ci si potrebbe aspettare. Funziona correttamente se il numero è già divisibile per 3, ma restituisce un numero enorme se non lo è.

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

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

Theory:

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

Answer 9

Se vuoi davvero vedere questo articolo sulla divisione integer , ma ha solo merito accademico ... sarebbe un'applicazione interessante che in realtà aveva bisogno di eseguire ciò che beneficiava di quel tipo di trucco.

Answer 10

Per una divisione di numeri interi veramente grandi (ad es. numeri più grandi di 64 bit) puoi rappresentare il tuo numero come un int [] ed eseguire una divisione abbastanza velocemente prendendo due cifre alla volta e dividerle per 3. Il resto sarà parte del le prossime due cifre e così via.

ad es. 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

quindi il risultato 3668

internal static List<int> Div3(int[] a)
{
  int remainder = 0;
  var res = new List<int>();
  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;
}

Answer 11

Calcolo semplice ... al massimo n iterazioni in cui n è il numero di bit:

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

Answer 12

Un approccio di 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];
}