Question

J'écris du code pour un microprocesseur avec une arithmétique entière rapide et une arithmétique float pas si rapide . Je dois diviser un entier par un nombre de 1 à 9 et reconvertir le résultat en entier.

J'ai créé un tableau float avec des membres tels que 0, 1, 0.5, 0.3333, etc. Mais je pense qu’il existe des constantes MAGIC (comme 0x55555556) pour un nombre sauf (1/3).

Quels sont ces chiffres?

Était-ce utile?

La solution

Si l’instruction de division sur votre microcontrôleur est suffisamment rapide, utilisez-la. Si vous avez besoin de la partie décimale du résultat, vous pourrez peut-être 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 l’est, vous pouvez utiliser la technique suivante (et vous aurez l’impression que c’est 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 importante est stockée dans un registre et la moitié moins importante dans l’autre. Vous pouvez l'exploiter en réalisant que la division par un nombre n équivaut à multiplier par (2 ^ 32) / n, puis en prenant les 32 bits les plus significatifs du résultat. En d'autres termes, si vous souhaitez diviser par 3, vous pouvez 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 en virgule fixe. Consultez l'article dans Wikipedia pour plus d'informations.

Autres conseils

Une division d'un entier par une constante entière peut être remplacée par la combinaison d'un décalage et d'une multiplication. Voir ce guide d'optimisation pour plus de détails. Bien sûr, cela est utile s’il est effectivement plus rapide sur la puce d’intérêt.

Je suppose que, sur la base de la balise micro-contrôleur, vous n’avez pas de division en nombre entier rapide. Ma réponse concerne également les valeurs non signées - cela fonctionnera pour les valeurs signées, il vous suffit de limiter les nombres utilisés dans la partie délicate ci-dessous.

Un bon début consiste à diviser par 2, 4 et 8. Ceci peut être fait avec des décalages à droite de 1, 2 et 3 bits respectivement, en supposant que votre CPU dispose d'une instruction logique de décalage à droite.

Deuxièmement, diviser par 1 revient à garder le nombre tel quel. Il ne reste que 3, 5, 6, 7 et 9.

Le point délicat commence ici:

Pour les autres nombres, vous pouvez utiliser le fait qu’une division peut être remplacée par une multiplication et un décalage.

Disons que vous avez un processeur 16 bits. Pour diviser par N, il faut multiplier par 256 / N et décaler à 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 / 5. Multipliez 72 par 51 pour obtenir 3672, puis passez de 8 bits à droite à 14.

Pour que cela fonctionne, les numéros que vous utilisez ne doivent pas dépasser les 16 bits. Dans le pire des cas, multiplié par 85, vous pouvez gérer des nombres allant jusqu'à 771.

Cela fonctionne parce qu’un décalage à droite de 8 bits équivaut à une division par 256 et que: 

  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 changent quelque peu, puisqu'il s'agit de 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, choisissons le nombre aléatoire 20 000/7: 20 000 multiplié par 9 363, ce qui correspond à 187 260 000. Lorsque vous décalez le décalage à droite sur 16 bits, vous obtenez 2 857 (le résultat réel est 2 857).

Le programme de test suivant en C indique les valeurs de précision pour les valeurs données. Il utilise des valeurs signées et n’est 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;
}

Cette sortie: 

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
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top