Quel est le moyen le plus rapide de diviser un entier par 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

C’est le plus rapide, car le compilateur l’optimisera s’il le peut en fonction du processeur de sortie.

int a;
int b;

a = some value;
b = a / 3;

Answer 2

Le gars qui a dit "laissez cela au compilateur" avait raison, mais je n'ai pas la "réputation" pour le modifier ou commenter. J'ai demandé à gcc de compiler int test (int a) {return a / 3; } pour un ix86 et ensuite démonter la sortie. Juste pour l’intérêt académique, cela consiste à approximativement multiplier par 0x55555556, puis à prendre les 32 premiers bits du résultat 64 bits. Vous pouvez le démontrer à vous-même, par exemple:

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

La page wikipedia sur la division de Montgomery est difficile à lire, mais heureusement, les compilateurs l'ont fait. afin que vous n'ayez pas à le faire.

Answer 3

Il existe un moyen plus rapide de le faire si vous connaissez les plages des valeurs, par exemple, si vous divisez un entier signé par 3 et que la plage de la valeur à diviser est comprise entre 0 et 768, puis vous peut le multiplier par un facteur et le déplacer vers la gauche par une puissance de 2 à ce facteur divisé par 3.

par exemple.

Plage 0 - > 768

vous pouvez utiliser le décalage de 10 bits, ce qui multiplie par 1024, vous voulez diviser par 3 afin que votre multiplicateur devrait être 1024/3 = 341,

afin que vous puissiez maintenant utiliser (x * 341) > > 10
(Assurez-vous que le décalage est un décalage signé si vous utilisez des entiers signés), assurez-vous également que le décalage est un décalage et non un bit ROLL

Ceci divisera effectivement la valeur 3 et fonctionnera environ 1,6 fois plus vite que la division naturelle par 3 sur un processeur standard x86 / x64.

Bien sûr, la seule raison pour laquelle vous pouvez effectuer cette optimisation lorsque le compilateur est incliné est que le compilateur ne connaît pas la plage maximale de X et ne peut donc pas prendre cette décision, mais vous, en tant que programmeur, pouvez le faire.

Parfois, il peut même être plus avantageux de déplacer la valeur dans une valeur plus grande et de faire la même chose, c.-à-d. si vous avez un int de gamme complète, vous pouvez en faire une valeur de 64 bits, puis multiplier et déplacer au lieu de diviser par 3.

Je devais faire cela récemment pour accélérer le traitement des images. Il me fallait trouver la moyenne de 3 canaux de couleur, chaque canal de couleur avec une plage d'octets (0 - 255). rouge vert et bleu.

Au début, j'ai simplement utilisé:

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

(Donc, r + g + b a un maximum de 768 et un minimum de 0, car chaque canal correspond à un octet compris entre 0 et 255)

Après des millions d'itérations, l'opération entière a pris 36 millisecondes.

J'ai changé la ligne en:

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

Et cela l'a ramené à 22 millisecondes, c'est étonnant ce qu'on peut faire avec un peu d'ingéniosité.

Cette accélération s'est produite en C # même si les optimisations étaient activées et que le programme était exécuté en mode natif sans informations de débogage et non via l'EDI.

Answer 4

Voir Comment diviser par 3 pour une discussion plus approfondie divisant efficacement par 3, axé sur les opérations arithmétiques FPGA.

Également pertinent:

• Optimisation des divisions entières avec décalage multiple en C #

Answer 5

En fonction de votre plate-forme et de votre compilateur C, une solution native similaire à l'utilisation de

y = x / 3

Peut être rapide ou terriblement lent (même si la division est entièrement réalisée de manière matérielle, si elle est réalisée à l'aide d'une instruction DIV, cette instruction est environ 3 à 4 fois plus lente qu'une multiplication sur des CPU modernes). De très bons compilateurs C avec des indicateurs d'optimisation activés peuvent optimiser cette opération, mais si vous voulez en être sûr, vous feriez mieux de l'optimiser vous-même.

Pour l'optimisation, il est important de disposer de nombres entiers de taille connue. En C int n'a pas de taille connue (elle peut varier en fonction de la plate-forme et du compilateur!), Il est donc préférable d'utiliser des entiers de taille fixe C99. Le code ci-dessous suppose que vous souhaitez diviser un entier 32 bits non signé par trois et que le compilateur C connaisse les nombres entiers de 64 bits (). NOTE: Même sur une architecture de processeur 32 bits, la plupart des compilateurs C peuvent gérer des entiers 64 bits uniquement. bien ):

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

Aussi fou que cela puisse paraître, mais la méthode ci-dessus divise effectivement par 3. Tout ce dont elle a besoin est une simple multiplication de 64 bits et un décalage (comme je l'ai dit, les multiplications pourraient être 3 à 4 fois plus rapides que les divisions sur votre CPU). Dans une application 64 bits, ce code sera beaucoup plus rapide que dans une application 32 bits (dans une application 32 bits, multiplier deux nombres de 64 bits nécessite trois multiplications et trois additions sur des valeurs de 32 bits). Cependant, il peut être encore plus rapide division sur une machine 32 bits.

D’autre part, si votre compilateur est très bon et connait bien l’opportunité d’optimiser la division d’entiers par une constante (le dernier GCC le fait, je viens de le vérifier), il générera quand même le code ci-dessus (GCC créera exactement ce code pour "/ 3" si vous activez au moins le niveau d'optimisation 1). Pour les autres compilateurs ... vous ne pouvez pas compter ou espérer qu'il utilisera de telles astuces, même si cette méthode est très bien documentée et mentionnée partout sur Internet.

Le problème est que cela ne fonctionne que pour des nombres constants, pas pour des nombres variables. Vous devez toujours connaître le nombre magique (ici 0xAAAAAAAB) et les opérations correctes après la multiplication (décalages et / ou ajouts dans la plupart des cas). Les deux sont différents en fonction du nombre que vous souhaitez diviser et les deux prennent trop de temps de calcul. calculez-les à la volée (ce serait plus lent que la division du matériel). Cependant, il est facile pour un compilateur de les calculer pendant le temps de compilation (où une seconde de temps de compilation en plus ou moins joue à peine un rôle).

Answer 6

Et si vous vraiment ne voulez pas multiplier ou diviser? Voici une approximation que je viens d'inventer. Cela fonctionne parce que (x / 3) = (x / 4) + (x / 12). Mais puisque (x / 12) = (x / 4) / 3, il suffit de répéter le processus jusqu’à ce que cela soit suffisant.

#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);
}

Le résultat est 330. Il pourrait être plus précis en utilisant b = ((b + 2) > > 2); pour tenir compte de l'arrondissement.

Si vous êtes autorisé à vous multiplier, il vous suffit de choisir une approximation appropriée pour (1/3), avec un diviseur égal à 2. Par exemple, n * (1/3) ~ = n * 43/128 = (n * 43) > > 7.

Cette technique est particulièrement utile dans dans l'Indiana.

Answer 7

Je ne sais pas si c'est plus rapide, mais si vous souhaitez utiliser un opérateur au niveau des bits pour effectuer une division binaire, vous pouvez utiliser la méthode shift et soustraction décrite dans cette page :

  

  
• Définissez le quotient sur 0
  
• Aligner les chiffres les plus à gauche du dividende et du diviseur
  
• Répéter:      
    
  • Si la partie du dividende supérieure au diviseur est supérieure ou égale au diviseur:      
      
    • Ensuite, soustrayez le diviseur de cette partie du dividende et
      
    • Concatentez 1 à l'extrémité droite du quotient
      
    • Sinon concatentez 0 à l'extrémité droite du quotient
      
    
  • Déplacez le diviseur d'une place à droite
    
  
• Jusqu'à ce que le dividende soit inférieur au diviseur:
  
• le quotient est correct, le dividende est le reste
  
• STOP
  

Answer 8

Pour les nombres 64 bits:

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

Cependant, ce n’est pas la division entière tronquante à laquelle on pourrait s’attendre. Cela fonctionne correctement si le nombre est déjà divisible par 3, mais renvoie un nombre énorme s'il ne l'est pas.

Par exemple, si vous l'exécutez sur l'exemple 11, le code retourne 6148914691236517209. Cela ressemble à une foutaise, mais c'est en fait la bonne réponse: multipliez-le par 3 et vous récupérez le 11!

Si vous recherchez la division tronquée, utilisez simplement l'opérateur /. Je doute fort que vous puissiez obtenir beaucoup plus rapidement que cela.

Théorie:

L'arithmétique non signée sur 64 bits est une arithmétique modulo 2 ^ 64. Cela signifie que pour chaque entier coprime avec le module 2 ^ 64 (essentiellement tous les nombres impairs), il existe un inverse multiplicatif que vous pouvez utiliser pour multiplier au lieu de division. Ce nombre magique peut être obtenu en résolvant l'équation 3 * x + 2 ^ 64 * y = 1 à l'aide de l'algorithme euclidien étendu.

Answer 9

Si vous souhaitez vraiment voir cet article dans la division entière , mais il n’a qu’un mérite académique ... ce serait une application intéressante qui aurait en fait besoin de performer et qui bénéficie de ce genre d’astuce.

Answer 10

Pour une division entière très grande (par exemple, les nombres supérieurs à 64 bits), vous pouvez représenter votre nombre sous forme d'int [] et effectuer la division assez rapidement en prenant deux chiffres à la fois et en les divisant par 3. Le reste fera partie de la deux chiffres suivants et ainsi de suite.

par exemple. 11004/3 vous dites

11/3 = 3, restant = 2 (de 11-3 * 3)

20/3 = 6, reste = 2 (de 20-6 * 3)

20/3 = 6, reste = 2 (de 20-6 * 3)

24/3 = 8, reste = 0

d'où le résultat 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

Calcul facile ... au plus n itérations où n est votre nombre de bits:

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

Answer 12

Une approche de table de consultation serait également plus rapide dans certaines architectures.

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];
}