Diviser par 10 en utilisant des décalages de bits ?

Question

Est-il possible de diviser un nombre entier non signé par 10 en utilisant des décalages de bits purs, des additions, des soustractions et des opérations d'écriture ? peut-être se multiplier ? En utilisant un processeur aux ressources très limitées et à la division lente.

Answer 1

Note de l'éditeur : c'est no ce que font réellement les compilateurs, et donne une mauvaise réponse pour les grands nombres entiers positifs se terminant par 9, en commençant par div10(1073741829) = 107374183 pas 107374182. Il est exact pour les entrées plus petites, cependant, ce qui peut être suffisant pour certaines utilisations.

Les compilateurs (y compris MSVC) utilisent des inverses multiplicatives en virgule fixe pour les diviseurs constants, mais ils utilisent une constante magique différente et un décalage sur le résultat de la moitié supérieure pour obtenir un résultat exact pour toutes les entrées possibles, ce qui correspond à ce que la machine abstraite C exige. Voir Article de Granlund & Montgomery sur l'algorithme.

Ver Pourquoi GCC utilise-t-il la multiplication par un nombre étrange pour implémenter la division d'un nombre entier ? pour des exemples de l'asm x86 que font gcc, clang, MSVC, ICC et d'autres compilateurs modernes.

---

Il s'agit d'une approximation rapide qui est inexacte pour les entrées importantes.

C'est même plus rapide que la division exacte via multiplier + décalage à droite que les compilateurs utilisent.

Vous pouvez utiliser la moitié supérieure du résultat d'une multiplication pour les divisions par de petites constantes intégrales. Supposons une machine 32 bits (le code peut être adapté en conséquence) :

int32_t div10(int32_t dividend)
{
    int64_t invDivisor = 0x1999999A;
    return (int32_t) ((invDivisor * dividend) >> 32);
}

Ce qui se passe ici, c'est que nous multiplions par une approximation proche de 1/10 * 2^32 et ensuite nous enlevons les 2^32. Cette approche peut être adaptée à différents diviseurs et différentes largeurs de bits.

Cela fonctionne très bien pour l'architecture ia32, puisque son instruction IMUL placera le produit 64 bits dans edx:eax, et la valeur de edx sera la valeur voulue. Viz (en supposant que le dividende est passé dans eax et le quotient retourné dans eax)

div10 proc 
    mov    edx,1999999Ah    ; load 1/10 * 2^32
    imul   eax              ; edx:eax = dividend / 10 * 2 ^32
    mov    eax,edx          ; eax = dividend / 10
    ret
    endp

Même sur une machine avec une instruction de multiplication lente, cela sera plus rapide qu'une division logicielle ou même matérielle.

Answer 2

Bien que les réponses données jusqu'à présent correspondent à la question réelle, elles ne correspondent pas au titre. Voici donc une solution fortement inspirée par Le plaisir du hacker qui n'utilise que des décalages de bits.

unsigned divu10(unsigned n) {
    unsigned q, r;
    q = (n >> 1) + (n >> 2);
    q = q + (q >> 4);
    q = q + (q >> 8);
    q = q + (q >> 16);
    q = q >> 3;
    r = n - (((q << 2) + q) << 1);
    return q + (r > 9);
}

Je pense que c'est la meilleure solution pour les architectures qui ne disposent pas d'une instruction de multiplication.

Answer 3

Bien sûr, vous pouvez le faire si vous pouvez vivre avec une certaine perte de précision. Si vous connaissez la plage de valeurs de vos valeurs d'entrée, vous pouvez proposer un décalage de bits et une multiplication qui sont exacts. Voici quelques exemples de la façon dont vous pouvez diviser par 10, 60, ... comme cela est décrit dans ce blog pour mettre en forme le temps le plus rapide possible.

temp = (ms * 205) >> 11;  // 205/2048 is nearly the same as /10

Answer 4

Pour développer un peu la réponse d'Alois, nous pouvons développer la proposition de y = (x * 205) >> 11 pour quelques multiples/shifts de plus :

y = (ms *        1) >>  3 // first error 8
y = (ms *        2) >>  4 // 8
y = (ms *        4) >>  5 // 8
y = (ms *        7) >>  6 // 19
y = (ms *       13) >>  7 // 69
y = (ms *       26) >>  8 // 69
y = (ms *       52) >>  9 // 69
y = (ms *      103) >> 10 // 179
y = (ms *      205) >> 11 // 1029
y = (ms *      410) >> 12 // 1029
y = (ms *      820) >> 13 // 1029
y = (ms *     1639) >> 14 // 2739
y = (ms *     3277) >> 15 // 16389
y = (ms *     6554) >> 16 // 16389
y = (ms *    13108) >> 17 // 16389
y = (ms *    26215) >> 18 // 43699
y = (ms *    52429) >> 19 // 262149
y = (ms *   104858) >> 20 // 262149
y = (ms *   209716) >> 21 // 262149
y = (ms *   419431) >> 22 // 699059
y = (ms *   838861) >> 23 // 4194309
y = (ms *  1677722) >> 24 // 4194309
y = (ms *  3355444) >> 25 // 4194309
y = (ms *  6710887) >> 26 // 11184819
y = (ms * 13421773) >> 27 // 67108869

chaque ligne est un calcul unique et indépendant, et vous verrez votre premier résultat "erroné"/incorrect à la valeur indiquée dans le commentaire. il est généralement préférable de prendre le plus petit décalage pour une valeur d'erreur donnée car cela minimisera les bits supplémentaires nécessaires pour stocker la valeur intermédiaire dans le calcul, par ex. (x * 13) >> 7 est "meilleur" que (x * 52) >> 9 car il nécessite deux bits de moins d'overhead, tandis que les deux commencent à donner des réponses erronées au-dessus de 68.

Si vous voulez en calculer davantage, le code suivant (Python) peut être utilisé :

def mul_from_shift(shift):
    mid = 2**shift + 5.
    return int(round(mid / 10.))

et j'ai fait la chose la plus évidente pour calculer quand cette approximation commence à se tromper avec :

def first_err(mul, shift):
    i = 1
    while True:
        y = (i * mul) >> shift
        if y != i // 10:
            return i
        i += 1

(notez que // est utilisé pour la division "entière", c'est-à-dire qu'il tronque/arrondit vers zéro)

la raison du schéma d'erreurs "3/1" (c'est-à-dire que 8 se répète 3 fois suivi de 9) semble être due au changement de bases, c'est-à-dire que les erreurs de base ne sont pas les mêmes. log2(10) est ~3.32. Si nous traçons les erreurs, nous obtenons ce qui suit :

où l'erreur relative est donnée par : mul_from_shift(shift) / (1<<shift) - 0.1

Answer 5

Vu la réponse de Kuba Ober, il y en a une autre dans la même veine. Elle utilise une approximation itérative du résultat, mais je ne m'attendrais pas à des performances surprenantes.

Disons que nous devons trouver x donde x = v / 10 .

Nous allons utiliser l'opération inverse v = x * 10 parce qu'il a la propriété agréable que lorsque x = a + b entonces x * 10 = a * 10 + b * 10 .

Laissez-nous utiliser x comme variable détenant la meilleure approximation du résultat jusqu'à présent. Lorsque la recherche se termine, x Tiendra le résultat. On va mettre chaque bit b de x du plus significatif au moins significatif, un par un, pour finir de comparer. (x + b) * 10 avec v . Si elle est inférieure ou égale à v alors le bit b est fixé dans x . Pour tester le bit suivant, il suffit de déplacer b d'une position vers la droite (diviser par deux).

Nous pouvons éviter la multiplication par 10 en maintenant x * 10 y b * 10 dans d'autres variables.

Cela donne l'algorithme suivant pour diviser v par 10.

uin16_t x = 0, x10 = 0, b = 0x1000, b10 = 0xA000;
while (b != 0) {
    uint16_t t = x10 + b10;
    if (t <= v) {
        x10 = t;
        x |= b;
    }
    b10 >>= 1;
    b >>= 1;
}
// x = v / 10

Editar: pour obtenir l'algorithme de Kuba Ober qui évite le besoin de variable x10 on peut soustraire b10 de v y v10 à la place. Dans ce cas x10 n'est plus nécessaire. L'algorithme devient

uin16_t x = 0, b = 0x1000, b10 = 0xA000;
while (b != 0) {
    if (b10 <= v) {
        v -= b10;
        x |= b;
    }
    b10 >>= 1;
    b >>= 1;
}
// x = v / 10

La boucle peut être déroulée et les différentes valeurs de b y b10 peuvent être précalculés comme des constantes.