Diviser par 10 à l'aide de bits des changements?

Est-il possible de diviser un entier non-signé par 10 par le biais de la pure bits quarts de travail, l'addition, la soustraction et peut-être se multiplier? À l'aide d'un processeur avec des ressources très limitées et lent diviser.

  • Il est possible (soustraction répétée de la division), mais la question est de savoir si c'est plus vite que la lenteur de la division.
  • Désolé, je ne peux pas vous comprendre. Parlez-vous dans la base de 17 ou de la base de 22?
  • De la Base de deux. Décalage à droite divise par 2^n qui permettrait de résoudre votre question si par "10", tu veux dire 16 décimal ou 10h.
  • Êtes-vous disputer avec moi? Je suis en train d'essayer d'admettre que je n'ai pas parler de ma réponse n'était pas pour les décimales.... Peut-être un peu obscur, mais que c'était mon intention.
  • O - voir mon commentaire. Je n'ai pas remarqué un upvote....
  • Oui, je crois que je discutais avec vous, sur l'interprétation de l'10(base 10) 10(base 16). Je pense qu'une telle interprétation par défaut est rare, au mieux.
  • Connexes: Pourquoi ne GCC utilisent la multiplication par un nombre étrange dans la mise en œuvre de division entière?: Si vous avez un rapide se multiplient, vous pouvez diviser par des constantes de compilation avec juste une multiplication et une maj de la moitié haute, obtenir le résultat correct pour chaque dividende (à la différence de la accepté de répondre).

InformationsquelleAutor Thomas O | 2011-04-05
  1. 55

    Voici ce que le compilateur de Microsoft n'lors de la compilation de divisions par de petites intégrale des constantes. Supposons qu'une machine 32 bits (code peut être ajustée en conséquence):

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

    Ce qu'il se passe ici, c'est que nous sommes en multipliant par une approximation proche de 1/10 * 2^32, puis en supprimant les 2^32. Cette approche peut être adaptée à différents diviseurs et de bits différents largeurs.

    Cela fonctionne très bien pour l'architecture ia32, depuis sa IMUL instruction de mettre le produit 64 bits dans edx:eax, et l'objectif de valeur sera la valeur requise. 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 lente multiplier instruction, ce sera plus rapide que d'un logiciel de fracture.

    • +1, et je tiens à souligner que le compilateur va le faire automatiquement pour vous lorsque vous écrivez "x/10"
    • hmm, n'est-ce pas là numériques inexactitude ici?
    • Vous allez toujours avoir numériques inexactitude lorsque vous faites entier divise: Que pensez-vous que vous obtenez lorsque vous divisez 28 par 10 à l'aide de nombres entiers? Réponse: 2.
    • Il n'y a pas de numérique à l'inexactitude dans la division entière, le résultat est exactement spécifié. Toutefois, la formule ci-dessus n'est exacte pour certains diviseurs. Même 10 est inexacte si vous voulez faire unsigned arithmétique: 4294967219 / 10 = 429496721, mais 4294967219 * div >> 32 = 429496722 Pour les plus grands diviseurs, la version signée seront inexactes ainsi.
    • Non, compilateurs, y compris MSVC compiler x/10 un point fixe inverse multiplicatif (et de faire un code supplémentaire pour gérer les négatifs des entrées pour la signature de division), à donner la bonne réponse pour tous les 32 bits d'entrées. Non signés, la division par 10, MSVC (et d'autres compilateurs) (godbolt.org/g/aAq7jx) permet de multiplier par 0xcccccccd et le déplacement à droite dans la moitié haute de 3.
    • J'ai écrit un programme de test pour ce, en comparant les résultats contre i/10. Il est mauvais pour les grands nombres entiers positifs se terminant par 9, en commençant par div10(1073741829) = 107374183. Correct = 107374182. C'est aussi mauvais pour la plupart (tous?) les entiers négatifs, par exemple div10(-1) = -1. Correct = 0. @JasonS est correct de dire que ce n'est pas de mettre en œuvre le C sémantique de x / 10.
    • il y a une jolie vidéo de Matt Godbolt qui touche à ce que le compilateur ne la division; parfois, il utilise la multiplication. voir youtube.com/watch?v=bSkpMdDe4g4

    InformationsquelleAutor John Källén
  2. 30

    Bien que les réponses apportées jusqu'à présent correspondre à la réelle question, ils ne correspondent pas au titre. Voici donc une solution fortement inspiré par Hacker Plaisir que vraiment utilise que peu les quarts de travail.

    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 multiplier instruction.

    InformationsquelleAutor realtime
  3. 15

    Bien sûr, vous pouvez si vous pouvez vivre avec une perte de précision. Si vous connaissez la plage de valeur de vos valeurs d'entrée, vous pouvez venir avec un décalage de bits et d'une multiplication qui est exact.
    Quelques exemples de comment vous pouvez diviser par 10, 60, ... comme il est décrit dans ce blog pour format le temps de la façon la plus rapide possible.

    temp = (ms * 205) >> 11;  //205/2048 is nearly the same as /10
    • Vous devez être conscient du fait que la valeur intermédiaire (ms * 205) risque de déborder.
    • Si vous ne l'int ms = 205 * (i >> 11); vous obtiendrez des valeurs erronées si les chiffres sont petits. Vous avez besoin d'une suite de tests pour s'assurer que, dans une gamme de valeur les résultats sont corrects.
    • c'est précis pour ms = 0..1028
    • Pourquoi 205 en particulier?
    • 11 est une division de 2048. Lorsque vous souhaitez diviser par dix, vous devez diviser par 2048/10 qui est 204,8 ou 205 comme le plus proche nombre entier.
    • J'adore la simplicité, c'est vraiment une excellente idée
    • C'est exactement le même pour 0 <= ms < 1029.

    InformationsquelleAutor Alois Kraus
  4. 3

    Considérant Kuba Ober réponse, il y en a une autre dans la même veine.
    Il utilise itératif rapprochement du résultat, mais je n'en attendait pas surprenant performances.

    Laisser dire que nous devons trouver x où x = v /10.

    Nous allons utiliser l'opération inverse v = x * 10, car il a la propriété que lorsque x = a + b, puis x * 10 = a * 10 + b * 10.

    Laisser utiliser x comme variable contenant la meilleure approximation de résultat à ce jour. Lorsque la recherche se termine, x Va contenir le résultat. Nous allons définir chaque bit b de x de la plus importante à la moins importante, un par un, à la fin de comparer (x + b) * 10 avec v. Si sa plus petite ou égale à v, alors le bit b est situé dans x. Pour tester le bit suivant, nous avons simplement shift b d'une position vers la droite (division par deux).

    Nous pouvons éviter la multiplication par 10 en tenant x * 10 et 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

    Edit: pour obtenir l'algorithme de Kuba Ober, ce qui évite de variable x10 , nous pouvons soustraire b10 de v et 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 unwinded et les différentes valeurs de b et b10 peuvent être précalculées comme des constantes.

    InformationsquelleAutor chmike
  5. 2

    Bien de la division est de la soustraction, donc oui. Décalage à droite d'ici le 1er (division par 2). Maintenant soustraire 5 de la suite, en comptant le nombre de fois que vous faites la soustraction jusqu'à ce que la valeur est inférieure à 5. Le résultat est le nombre de soustractions vous l'avez fait. Oh, et en divisant va probablement être plus rapide.

    Une stratégie hybride de décalage à droite, puis diviser par 5 à l'aide de la répartition normale peut vous permettre une amélioration de la performance si la logique dans le diviseur n'est pas déjà le faire pour vous.

    InformationsquelleAutor tvanfosson
  6. 2

    Sur les architectures qui ne peut prendre la place à un moment, une série de comparaisons explicites contre la diminution des puissances de deux, multiplié par 10 pourrait mieux fonctionner que la solution du hacker plaisir. En supposant un 16 bits dividende:

    uint16_t div10(uint16_t dividend) {
  uint16_t quotient = 0;
  #define div10_step(n) \
    do { if (dividend >= (n*10)) { quotient += n; dividend -= n*10; } } while (0)
  div10_step(0x1000);
  div10_step(0x0800);
  div10_step(0x0400);
  div10_step(0x0200);
  div10_step(0x0100);
  div10_step(0x0080);
  div10_step(0x0040);
  div10_step(0x0020);
  div10_step(0x0010);
  div10_step(0x0008);
  div10_step(0x0004);
  div10_step(0x0002);
  div10_step(0x0001);
  #undef div10_step
  if (dividend >= 5) ++quotient; //round the result (optional)
  return quotient;
}
    • Votre code effectue 16 multiplication par 10. Pourquoi pensez-vous que votre code est plus rapide que de hacker le plaisir ?
    • Il n'a pas d'importance ce que je pense. Ce qui importe est de savoir si à la plate-forme, il est plus rapide. Essayez vous-même! Il n'y a pas universellement solution la plus rapide ici. Chaque solution a une certaine plate-forme à l'esprit, et qui fonctionnera le mieux sur cette plate-forme, peut-être mieux que toute autre solution.
    • Je n'ai pas remarqué ce n*10 est constante. Il va donc être précalculées par le compilateur. J'ai fourni un algorithme alternatif dans une réponse. Notre algorithme sont équivalentes sauf pour une différence. Vous soustrayez b*10 à partir de v et je l'ajouter à x*10. Votre algorithme n'a pas besoin de garder une trace de x*10, qui enregistre une variable. Le code vous montrer déroule le ma boucle while.
    • Sur une machine sans matériel multiplier, n*10 est encore bon marché: (n<<3) + (n<<1). Petite maj des réponses pourrait peut-être être utile sur des machines avec de lents ou inexistants HW se multiplient, et seulement un décalage de 1. Sinon un point fixe inverse est beaucoup mieux pour compiler constante de temps de diviseurs (comme les compilateurs modernes faire pour x/10).
    InformationsquelleAutor Kuba Ober
  7. 1

    pour développer Alois réponse un peu, nous pouvons étendre le suggère y = (x * 205) >> 11 pour un peu plus des multiples/postes:

    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 une seule, indépendante, de calcul, et vous verrez que votre premier "erreur"/résultat incorrect à la valeur indiquée dans le commentaire. vous êtes généralement mieux de prendre la plus petite maj pour une valeur d'erreur que cela permettra de minimiser la des bits supplémentaires nécessaires pour stocker de la valeur intermédiaire dans le calcul, par exemple (x * 13) >> 7 est "meilleure" que la (x * 52) >> 9 comme il a besoin de deux moins de bits de frais généraux, tandis que les deux commencent à donner de mauvaises réponses ci-dessus 68.

    si vous voulez calculer plus de ceux-ci, les (Python) code 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 le calcul lorsque ce rapprochement commence à aller mal 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 "entier" de la division, c'est à dire qu'il tronque/tours vers zéro)

    la raison de la "3/1" modèle à erreurs (c'est à dire 8 répète 3 fois suivi par 9) semble être due au changement de bases, c'est à dire log2(10) est ~3.32. si nous intrigue, les erreurs que nous obtenez le résultat suivant:

    Diviser par 10 à l'aide de bits des changements?

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

    InformationsquelleAutor Sam Mason