Multiplication rapide

Question

J'écris du code pour un microprocesseur avec l'arithmétique d'entier rapide et pas si vite l'arithmétique flottante. Je dois diviser un entier par un nombre de 1 à 9 et convertir le résultat en nombre entier.

J'ai fait un tableau flottant avec des membres comme 0, 1, 0.5, 0.3333 etc. Mais je pense qu'il y a des constantes MAGIC (comme 0x55555556) pour un nombre sauf (1/3).

Quels sont ces chiffres?

Answer 1

Si l'instruction de la division sur votre micro-contrôleur est assez rapide, utiliser. Si vous avez besoin de la partie fractionnaire du résultat, vous pouvez utiliser le reste; Sur la plupart des architectures, l'instruction de division place le quotient dans un registre et le reste dans un autre.

Si votre instruction de division n'est pas assez rapide mais que l'instruction de multiplication est, vous pouvez utiliser la technique suivante (et cela semble être la technique que vous recherchez). Sur la plupart des architectures, multiplier un nombre de 32 bits par un autre nombre de 32 bits donne un résultat de 64 bits; la moitié la plus significative est stockée dans un registre et la moitié la moins significative est stockée dans l'autre. Vous pouvez exploiter ceci en réalisant que la division par un nombre n est la même que la multiplication par (2^32)/n, puis en prenant les 32 bits les plus significatifs du résultat. En d'autres termes, si vous voulez diviser par 3, vous pouvez plutôt multiplier par 0x100000000/3 = 0x55555555, puis prendre les 32 bits les plus significatifs du résultat.

Ce que vous faites ici est vraiment une forme d'arithmétique à virgule fixe. Jetez un oeil à la Wikipedia article pour plus d'informations.

Answer 2

Je suppose, basé sur l'étiquette de micro-contrôleur, que vous n'avez pas une division d'entier rapide. Ma réponse est également pour les valeurs non signées - cela fonctionnera pour les valeurs signées, il vous suffit de limiter les nombres utilisés dans le bit délicat ci-dessous. Un bon départ est de diviser par 2, 4 et 8. Cela peut être fait avec des décalages de 1, 2 et 3 bits respectivement, en supposant que votre CPU a une instruction de décalage vers la droite logique.

Deuxièmement, diviser par 1 ne fait que maintenir le nombre tel quel. Cela laisse simplement, 3, 5, 6, 7 et 9.

peu Tricky commence ici:

Pour les autres numéros, vous pouvez utiliser le fait qu'une fracture peut être remplacée par une multiplication et changement .

Disons que vous avez un processeur 16 bits. Pour diviser par N, vous multipliez par 256/N et décalage vers la droite 8 bits:

N = 3, multiply by 85 
N = 5, multiply by 51 
N = 6, multiply by 43 
N = 7, multiply by 37 
N = 9, multiply by 28 

Prenons l'exemple aléatoire de 72/72 5. Multiplier par 51 pour obtenir 3672 puis passer à droite 8 bits pour obtenir 14.

Pour que cela fonctionne, vos numéros que vous utilisez ne doivent pas déborder les 16 bits. Étant donné que votre pire des cas se multiplient par 85, vous pouvez manipuler des nombres jusqu'à 771.

La raison pour laquelle cela fonctionne est parce qu'un décalage à droite de 8 bits est le même que la division par 256, et:

m * (256/n)/256 
= m/(n/256)/256 
= m/n * 256/256 
= m/n * (256/256) 
= m/n 

Si vous avez un processeur 32 bits, les valeurs et les plages changer quelque peu, car il est 65536/N:

N = 3, multiply by 21,846, right shift 16 bits, max value roughly 196,600. 
N = 5, multiply by 13,108. 
N = 6, multiply by 10,923. 
N = 7, multiply by 9,363. 
N = 9, multiply by 7,282. 

Encore une fois, nous allons choisir le 20 000/7 au hasard: 20 000 multiplié par 9363 est 187.260.000 et, quand vous faites un décalage de 16 bits, vous obtenez 2 857 - le résultat réel est de 2 857.

Le programme de test suivant en C montre les chiffres de précision pour les valeurs données. Il utilise des valeurs signées, il n'est donc bon que jusqu'à environ 98 000 mais vous pouvez voir que la plus grande erreur est 1 et qu'elle se produit au point bas de 13 110 (seulement 0,008% d'erreur).

#include <stdio.h> 
int res[5] = {0}; 
int low[5] = {-1,-1,-1,-1,-1}; 
int da[] = {3,5,6,7,9}; 
int ma[] = {21846,13108,10923,9363,7282}; 
int main (void) { 
    int n, i; 
    for (n = 0; n < 98000; n++) { 
     for (i = 0; i < sizeof(da)/sizeof(da[0]); i++) { 
      int r1 = n/da[i]; 
      int r2 = (n * ma[i])>>16; 
      int dif = abs (r1-r2); 
      if (dif >= 5) { 
       printf ("%d/%d gives %d and %d\n", n, da[i], r1, r2); 
       return 1; 
      } 
      res[dif]++; 
      if (low[dif] == -1) { 
       low[dif] = n; 
      } 
     } 
    } 
    for (i = 0; i < sizeof(res)/sizeof(res[0]); i++) { 
     printf ("Difference of %d: %6d, lowest value was %6d\n", i, res[i], low[i]); 
    } 
    return 0; 
} 

Ce sorties:

Difference of 0: 335874, lowest value was  0 
Difference of 1: 154126, lowest value was 13110 
Difference of 2:  0, lowest value was  -1 
Difference of 3:  0, lowest value was  -1 
Difference of 4:  0, lowest value was  -1 

Answer 3

Une division d'un entier par une constante entière peut être remplacée par une combinaison d'un décalage et d'une multiplication. Voir this optimization guide pour plus de détails. De toute évidence c'est utile si c'est actully plus rapide sur la puce d'intérêt.