Tests de divisibilité rapides (par 2,3,4,5, .., 16)?

Question

Ce sont les plus rapides de divisibilité des tests? Dire, compte tenu d'un little-endian architecture et un entier signé 32 bits: comment calculer très vite qu'un nombre est divisible par 2,3,4,5,... jusqu'à 16 ans?

AVERTISSEMENT: compte tenu de code est un EXEMPLE seulement. Chaque ligne est indépendant! Juste la solution la plus évidente à l'aide modulo est lent sur de nombreux processeurs, qui n'ont pas de DIV matériel (comme beaucoup d'Armes). Certains compilateurs sont aussi ne peut pas faire de telles optimisations (par exemple, si le diviseur est une fonction de l'argument ou est dépendant de quelque chose).

Divisible_by_1 = do();
Divisible_by_2 = if (!(number & 1)) do();
Divisible_by_3 = ?
Divisible_by_4 = ?
Divisible_by_5 = ?
Divisible_by_6 = ?
Divisible_by_7 = ?
Divisible_by_8 = ?
Divisible_by_9 = ?
Divisible_by_10 = ?
Divisible_by_11 = ?
Divisible_by_12 = ?
Divisible_by_13 = ?
Divisible_by_14 = ?
Divisible_by_15 = ?
Divisible_by_16 = if(!number & 0x0000000F) do();

et cas particuliers:

Divisible_by_2k = if(number & (tk-1)) do();  //tk=2**k=(2*2*2*...) k times

Answer 1

Dans tous les cas (y compris divisible par 2):

 if (number % n == 0) do();
 

Anding avec un masque de bits de poids faible n'est que de l'obscurcissement, et avec un compilateur moderne ne sera pas plus rapide que d'écrire le code de manière lisible.

Si vous devez tester tous les cas, vous pouvez améliorer les performances en plaçant certains des cas dans if pour un autre: il est inutile de tester la divisibilité par 4 si la divisibilité par 2 a déjà échoué, par exemple exemple.

Answer 2

Ce n'est pas une mauvaise idée du TOUT à comprendre des solutions de rechange à la division des instructions (qui comprend modulo sur x86/x64) parce qu'ils sont très lents. Plus lent (ou même beaucoup plus lent) que la plupart des gens réalisent. Ceux qui suggèrent "% n", où n est une variable sont insensé de donner des conseils, car il va immanquablement conduire à l'utilisation de la division de l'instruction. Sur l'autre main "% c" (où c est une constante) permettra au compilateur de déterminer le meilleur algorithme disponible dans son répertoire. Parfois, il sera la division de l'instruction, mais la plupart du temps, il ne sera pas.

Dans ce document, Torbjörn Granlund montre que le ratio de cycles d'horloge nécessaires pour non signé de 32 bits multis:divs est de 4:26 (6,5 x) sur Sandybridge et 3:45 (15x) sur K10. pour la version 64 bits respectifs sont les formats 4:92 (23x) et 5:77 (14,4 x).

Le "L" colonnes désigner la latence. "T" colonnes de désigner le débit. Cela a à voir avec le processeur, capacité à gérer plusieurs instructions en parallèle. Sandybridge peut émettre une 32-bits de multiplication de chaque autre cycle ou un 64 bits de chaque cycle. Pour K10 le débit correspondant est inversé. Pour les divisions K10 doit remplir la totalité de la séquence avant de commencer un autre. Je soupçonne que c'est la même chose pour Sandybridge.

En utilisant le K10 comme un exemple, cela signifie que pendant les cycles requis pour un 32 bits division (45) le même nombre (45) de multiplications peuvent être émis et de l'avant-dernière et la dernière de ces effectueront un et deux cycles d'horloge après la division est terminée. BEAUCOUP de travail peut être effectué dans les 45 multiplications.

Il est également intéressant de noter que les divs sont devenus de moins en moins efficace avec l'évolution de K8-K9 à K10: de 39 à 45 et 71 à 77 cycles d'horloge pour 32 - et 64-bits.

Granlund de la page à gmplib.org et à l' Institut Royal de Technologie de Stockholm contenir plus de goodies, dont certaines ont été intégrées dans le compilateur gcc.

Answer 3

Comme @James mentionné, permet au compilateur de le simplifier pour vous. Si n est une constante, toute descente compilateur est capable de reconnaître le modèle et de le modifier pour une efficacité équivalente.

Par exemple, le code

#include <stdio.h>

int main() {
    size_t x;
    scanf("%u\n", &x);
    __asm__ volatile ("nop;nop;nop;nop;nop;");
    const char* volatile foo = (x%3 == 0) ? "yes" : "no";
    __asm__ volatile ("nop;nop;nop;nop;nop;");
    printf("%s\n", foo);
    return 0;
}

compilé avec g++-4.5 -O3, la partie pertinente de l' x%3 == 0 deviendra

mov    rcx,QWORD PTR [rbp-0x8]   # rbp-0x8 = &x
mov    rdx,0xaaaaaaaaaaaaaaab
mov    rax,rcx
mul    rdx
lea    rax,"yes"
shr    rdx,1
lea    rdx,[rdx+rdx*2]
cmp    rcx,rdx
lea    rdx,"no"
cmovne rax,rdx
mov    QWORD PTR [rbp-0x10],rax

ce qui, traduit en code C, signifie

(hi64bit(x * 0xaaaaaaaaaaaaaaab) / 2) * 3 == x ? "yes" : "no"
// equivalatent to:                 x % 3 == 0 ? "yes" : "no"

pas de division en cause ici. (À noter qu' 0xaaaaaaaaaaaaaaab == 0x20000000000000001L/3)

---

Edit:

• La magie de la constante 0xaaaaaaaaaaaaaaab peut être calculé en http://www.hackersdelight.org/magic.htm
• Pour les diviseurs de la forme 2ⁿ - 1, chèque http://graphics.stanford.edu/~seander/bithacks.html#ModulusDivision

Answer 4

Un peu ironique, mais en supposant que vous obtenez le reste des réponses:

 Divisible_by_6  = Divisible_by_3 && Divisible_by_2;
Divisible_by_10 = Divisible_by_5 && Divisible_by_2;
Divisible_by_12 = Divisible_by_4 && Divisible_by_3;
Divisible_by_14 = Divisible_by_7 && Divisible_by_2;
Divisible_by_15 = Divisible_by_5 && Divisible_by_3;
 

Answer 5

Tout d'abord, je vous rappelle qu'un certain nombre de la forme bn...b2b1b0 en binaire a de la valeur:

number = bn*2^n+...+b2*4+b1*2+b0

Maintenant, quand vous dites que nombre%3, vous avez:

number%3 =3= bn*(2^n % 3)+...+b2*1+b1*2+b0

(J'ai utilisé =3= pour indiquer la congruence modulo 3). Notez également qu' b1*2 =3= -b1*1

Maintenant, je vais écrire tous les 16 divisions à l'aide de + et - et, éventuellement, de multiplication (à noter que la multiplication peut être écrit comme la touche maj ou la somme de la même valeur déplacé à différents endroits. Par exemple 5*x moyen x+(x<<2) dans lequel vous calculez x qu'une seule fois)

Appelons-le nombre n et disons - Divisible_by_i est une valeur booléenne. Comme une valeur intermédiaire, imaginez Congruence_by_i est une valeur conforme à l' n modulo i.

Aussi, disons n0 signifie zéro bit de n, n1 signifie que le bit 1 etc, c'est

ni = (n >> i) & 1;

Congruence_by_1 = 0
Congruence_by_2 = n&0x1
Congruence_by_3 = n0-n1+n2-n3+n4-n5+n6-n7+n8-n9+n10-n11+n12-n13+n14-n15+n16-n17+n18-n19+n20-n21+n22-n23+n24-n25+n26-n27+n28-n29+n30-n31
Congruence_by_4 = n&0x3
Congruence_by_5 = n0+2*n1-n2-2*n3+n4+2*n5-n6-2*n7+n8+2*n9-n10-2*n11+n12+2*n13-n14-2*n15+n16+2*n17-n18-2*n19+n20+2*n21-n22-2*n23+n24+2*n25-n26-2*n27+n28+2*n29-n30-2*n31
Congruence_by_7 = n0+2*n1+4*n2+n3+2*n4+4*n5+n6+2*n7+4*n8+n9+2*n10+4*n11+n12+2*n13+4*n14+n15+2*n16+4*n17+n18+2*n19+4*n20+n21+2*n22+4*n23+n24+2*n25+4*n26+n27+2*n28+4*n29+n30+2*n31
Congruence_by_8 = n&0x7
Congruence_by_9 = n0+2*n1+4*n2-n3-2*n4-4*n5+n6+2*n7+4*n8-n9-2*n10-4*n11+n12+2*n13+4*n14-n15-2*n16-4*n17+n18+2*n19+4*n20-n21-2*n22-4*n23+n24+2*n25+4*n26-n27-2*n28-4*n29+n30+2*n31
Congruence_by_11 = n0+2*n1+4*n2+8*n3+5*n4-n5-2*n6-4*n7-8*n8-5*n9+n10+2*n11+4*n12+8*n13+5*n14-n15-2*n16-4*n17-8*n18-5*n19+n20+2*n21+4*n22+8*n23+5*n24-n25-2*n26-4*n27-8*n28-5*n29+n30+2*n31
Congruence_by_13 = n0+2*n1+4*n2+8*n3+3*n4+6*n5-n6-2*n7-4*n8-8*n9-3*n10-6*n11+n12+2*n13+4*n14+8*n15+3*n16+6*n17-n18-2*n19-4*n20-8*n21-3*n22-6*n3+n24+2*n25+4*n26+8*n27+3*n28+6*n29-n30-2*n31
Congruence_by_16 = n&0xF

Ou quand factorisée:

Congruence_by_1 = 0
Congruence_by_2 = n&0x1
Congruence_by_3 = (n0+n2+n4+n6+n8+n10+n12+n14+n16+n18+n20+n22+n24+n26+n28+n30)-(n1+n3+n5+n7+n9+n11+n13+n15+n17+n19+n21+n23+n25+n27+n29+n31)
Congruence_by_4 = n&0x3
Congruence_by_5 = n0+n4+n8+n12+n16+n20+n24+n28-(n2+n6+n10+n14+n18+n22+n26+n30)+2*(n1+n5+n9+n13+n17+n21+n25+n29-(n3+n7+n11+n15+n19+n23+n27+n31))
Congruence_by_7 = n0+n3+n6+n9+n12+n15+n18+n21+n24+n27+n30+2*(n1+n4+n7+n10+n13+n16+n19+n22+n25+n28+n31)+4*(n2+n5+n8+n11+n14+n17+n20+n23+n26+n29)
Congruence_by_8 = n&0x7
Congruence_by_9 = n0+n6+n12+n18+n24+n30-(n3+n9+n15+n21+n27)+2*(n1+n7+n13+n19+n25+n31-(n4+n10+n16+n22+n28))+4*(n2+n8+n14+n20+n26-(n5+n11+n17+n23+n29))
// and so on

Si ces valeurs étant négatif, l'ajouter avec i jusqu'à ce qu'ils deviennent positifs.

Maintenant, ce que vous devez faire est de manière récursive la nourriture de ces valeurs à travers le même processus que nous a juste fait jusqu' Congruence_by_i devient de moins de i (et évidemment >= 0). Ceci est similaire à ce que nous faisons lorsque nous voulons trouver le reste d'un nombre par 3 ou 9, vous vous souvenez? La somme des chiffres, si elle avait plus d'un chiffre, des chiffres du résultat de nouveau jusqu'à obtenir un seul chiffre.

Maintenant, pour i = 1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16:

Divisible_by_i = (Congruence_by_i == 0);

Et pour le reste:

Divisible_by_6 = Divisible_by_3 && Divisible_by_2;
Divisible_by_10 = Divisible_by_5 && Divisible_by_2;
Divisible_by_12 = Divisible_by_4 && Divisible_by_3;
Divisible_by_14 = Divisible_by_7 && Divisible_by_2;
Divisible_by_15 = Divisible_by_5 && Divisible_by_3;

Edit: Notez que certains de ces ajouts pourraient être évités dès le début. Par exemple n0+2*n1+4*n2 est le même que n&0x7, de même n3+2*n4+4*n5 est (n>>3)&0x7 et donc avec chaque formule, vous n'avez pas à obtenir chaque bit individuellement, je l'ai écrit comme ça, pour la clarté et la similarité de fonctionnement. Pour optimiser chacune des formules, vous devez travailler sur vous-même; groupe des opérandes et factoriser l'opération.