c++ - numeros - Pruebas rápidas de divisibilidad(por 2,3,4,5,..., 16)

numeros divisibles por 2 ejemplos (16)

Antes que nada, les recuerdo que un número en el formato bn ... b2b1b0 en binario tiene valor:

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

Ahora, cuando dices el número% 3, tienes:

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

(Utilicé = 3 = para indicar congruencia módulo 3). Tenga en cuenta también que b1*2 =3= -b1*1

Ahora escribiré las 16 divisiones usando + y - y posiblemente multiplicación (tenga en cuenta que la multiplicación podría escribirse como shift o suma del mismo valor desplazado a diferentes ubicaciones. Por ejemplo, 5*x significa x+(x<<2) en el que compute x solo una vez)

Llamemos al número n y digamos que Divisible_by_i es un valor booleano. Como valor intermedio, imagine Congruence_by_i es un valor congruente con n modulo i .

Además, digamos que n0 significa bit cero de n, n1 significa bit 1, etc.

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

O cuando se factoriza:

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 estos valores terminan siendo negativos, agréguelos con i hasta que se vuelvan positivos.

Ahora lo que debes hacer es alimentar de forma recursiva estos valores a través del mismo proceso que acabamos de hacer hasta que Congruence_by_i sea menor que i (y obviamente >= 0 ). Esto es similar a lo que hacemos cuando queremos encontrar el resto de un número por 3 o 9, ¿recuerdas? Suma los dígitos, si tiene más de un dígito, sube los dígitos del resultado nuevamente hasta que obtengas solo un dígito.

Ahora para i = 1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16 :

Divisible_by_i = (Congruence_by_i == 0);

Y por el resto:

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;

Editar: Tenga en cuenta que algunas de las adiciones podrían evitarse desde el principio. Por ejemplo n0+2*n1+4*n2 es lo mismo que n&0x7 , similarmente n3+2*n4+4*n5 es (n>>3)&0x7 y por lo tanto con cada fórmula, no tiene que obtener cada bit individualmente, lo escribí así por el bien de la claridad y la similitud en la operación. Para optimizar cada una de las fórmulas, debe trabajar en ella usted mismo; operandos de grupo y operación de factorización.

¿Cuáles son las pruebas de divisibilidad más rápidas? Digamos, dada una arquitectura little-endian y un entero con signo de 32 bits: cómo calcular muy rápido que un número es divisible por 2,3,4,5, ... hasta 16?

ADVERTENCIA: el código dado es EJEMPLO solamente. ¡Cada línea es independiente! La única solución obvia que utiliza la operación de módulo es lenta en muchos procesadores, que no tienen hardware DIV (como muchos ARM). Algunos compiladores tampoco pueden realizar tales optimizaciones (por ejemplo, si divisor es el argumento de una función o depende de algo).

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();

y casos especiales:

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

Aquí hay algunos consejos que aún no he visto que sugiera nadie más:

Una idea es usar una instrucción switch o precomputar alguna matriz. Entonces, cualquier optimizador decente puede simplemente indexar cada caso directamente. Por ejemplo:

// tests for (2,3,4,5,6,7) switch (n % 8) { case 0: break; case 1: break; case 2: do(2); break; case 3: do(3); break; case 4: do(2); do(4) break; case 5: do(5); break; case 6: do(2); do(3); do(4); break; case 7: do(7); break; }

Su aplicación es un poco ambigua, pero tal vez solo necesite verificar números primos menores que n = 16. Esto se debe a que todos los números son factores de los números primos actuales o anteriores. Entonces, para n = 16, tal vez puedas salirte con solo verificar 2, 3, 5, 7, 11, 13 alguna manera. Solo un pensamiento.

Como mencionó @James , permita que el compilador lo simplifique por usted. Si n es una constante, cualquier compilador de descenso puede reconocer el patrón y cambiarlo a un equivalente más eficiente.

Por ejemplo, el código

#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; }

compilado con g ++ - 4.5 -O3, la parte relevante de x%3 == 0 se convertirá

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

que, traducido de nuevo al código C, significa

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

ninguna división involucrada aquí. (Tenga en cuenta que 0xaaaaaaaaaaaaaaab == 0x20000000000000001L/3 )

Editar:

La constante mágica 0xaaaaaaaaaaaaaaab se puede calcular en http://www.hackersdelight.org/magic.htm
Para los divisores de la forma 2 ⁿ - 1, consulte http://graphics.stanford.edu/~seander/bithacks.html#ModulusDivision

El LCM de estos números parece ser 720720. Es bastante pequeño, por lo que puede realizar una única operación de módulo y usar el resto como índice en la LUT precalculada.

En todos los casos (incluso divisible por 2):

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

Anding con una máscara de bits de bajo orden es solo ofuscación, y con un compilador moderno no será más rápido que escribir el código de una manera legible.

Si tiene que probar todos los casos, puede mejorar el rendimiento colocando algunos de los casos en el if para otro: no tiene sentido que pruebe la divisibilidad en 4 si la divisibilidad en 2 ya ha fallado, por ejemplo.

En una pregunta anterior , mostré un algoritmo rápido para verificar en la base N los divisores que son factores de N-1. Las transformaciones de bases entre diferentes potencias de 2 son triviales; eso es solo un poco agrupamiento.

Por lo tanto, verificar 3 es fácil en la base 4; verificar 5 es fácil en la base 16, y verificar 7 (y 9) es fácil en la base 64.

Los divisores no primos son triviales, por lo que solo 11 y 13 son casos difíciles. Para 11, puede usar la base 1024, pero en ese punto no es realmente eficiente para enteros pequeños.

Las pruebas rápidas de divisibilidad dependen en gran medida de la base en la que se representa el número. En caso de que cuando base sea 2, creo que solo puedes hacer "pruebas rápidas" de divisibilidad por potencias de 2. Un número binario es divisible por 2 ⁿ si los últimos n dígitos binarios de ese número son 0. Para otras pruebas, no lo hago. Creo que generalmente puede encontrar algo más rápido que % .

No es una mala idea EN TOTAL encontrar alternativas a las instrucciones de división (que incluyen módulo en x86 / x64) porque son muy lentas. Más lento (o incluso mucho más lento) que la mayoría de las personas se dan cuenta. Aquellos que sugieren "% n", donde n es una variable, están dando consejos tontos porque invariablemente llevarán al uso de la instrucción de división. Por otro lado, "% c" (donde c es una constante) permitirá al compilador determinar el mejor algoritmo disponible en su repertorio. A veces será la instrucción de división pero muchas veces no lo hará.

En este documento, Torbjörn Granlund muestra que la proporción de ciclos de reloj requerida para mults de 32 bits sin signo: divs es 4:26 (6.5x) en Sandybridge y 3:45 (15x) en K10. para 64 bits las proporciones respectivas son 4:92 (23x) y 5:77 (14.4x).

Las columnas "L" denotan latencia. Las columnas "T" denotan el rendimiento. Esto tiene que ver con la capacidad del procesador para manejar múltiples instrucciones en paralelo. Sandybridge puede emitir una multiplicación de 32 bits cada dos ciclos o uno de 64 bits en cada ciclo. Para K10, el rendimiento correspondiente se invierte. Para las divisiones, el K10 necesita completar la secuencia completa antes de que pueda comenzar otra. Sospecho que es lo mismo para Sandybridge.

Usando el K10 como ejemplo, significa que durante los ciclos requeridos para una división de 32 bits (45) se puede emitir el mismo número (45) de multiplicaciones y el penúltimo y último de estos completarán uno y dos reloj ciclos después de que la división se haya completado. MUCHO trabajo se puede realizar en 45 multiplicaciones.

También es interesante observar que los divs se han vuelto menos eficientes con la evolución de K8-K9 a K10: de 39 a 45 y de 71 a 77 ciclos de reloj para 32 y 64 bits.

La page de Granlund en gmplib.org y en el Instituto Real de Tecnología en Estocolmo contiene más objetos, algunos de los cuales han sido incorporados en el compilador de gcc.

Probablemente esto no te ayude en el código, pero hay un truco muy bueno que puede ayudarte a hacer esto en tu cabeza en algunos casos:

Para dividir por 3: para un número representado en decimal, puede sumar todos los dígitos y verificar si la suma es divisible entre 3.

Ejemplo: 12345 => 1+2+3+4+5 = 15 => 1+5 = 6 , que es divisible por 3 (3 x 4115 = 12345) .

Más interesante es que la misma técnica funciona para todos los factores de X-1, donde X es la base en la que se representa el número. Por lo tanto, para el número decimal, puede marcar dividir entre 3 o 9. Para el hexágono, puede verificar dividir entre 3,5 o 15. Y para los números octales, puede marcar dividir entre 7.

Puedes reemplazar la división por una constante que no sea potencia de dos por una multiplicación, esencialmente multiplicando por el recíproco de tu divisor. Los detalles para obtener el resultado exacto con este método son complicados.

Hacker''s Delight lo analiza extensamente en el capítulo 10 (desafortunadamente no está disponible en línea).

Del cociente puede obtener el módulo mediante otra multiplicación y una resta.

Solo debe usar (i% N) == 0 como prueba.

Mi compilador (una versión bastante antigua de gcc) generó un buen código para todos los casos que probé. Donde las pruebas de bits fueron apropiadas, lo hizo. Donde N era una constante, no generaba la "división" obvia para ningún caso, siempre usaba algún "truco".

Simplemente permita que el compilador genere el código para usted, seguramente sabrá más acerca de la arquitectura de la máquina que usted :). Y estas son optimizaciones fáciles donde es poco probable que piense algo mejor que el compilador.

Sin embargo, es una pregunta interesante. No puedo enumerar los trucos utilizados por el compilador para cada constante ya que tengo que compilar en una computadora diferente. Pero actualizaré esta respuesta más adelante si nadie me gana :)

Supongamos que el number unsigned está unsigned (32 bits). A continuación, las siguientes son formas muy rápidas de calcular la divisibilidad hasta 16. (No he medido, pero el código de ensamblaje lo indica).

bool divisible_by_2 = number % 2 == 0; bool divisible_by_3 = number * 2863311531u <= 1431655765u; bool divisible_by_4 = number % 4 == 0; bool divisible_by_5 = number * 3435973837u <= 858993459u; bool divisible_by_6 = divisible_by_2 && divisible_by_3; bool divisible_by_7 = number * 3067833783u <= 613566756u; bool divisible_by_8 = number % 8 == 0; bool divisible_by_9 = number * 954437177u <= 477218588u; bool divisible_by_10 = divisible_by_2 && divisible_by_5; bool divisible_by_11 = number * 3123612579u <= 390451572u; bool divisible_by_12 = divisible_by_3 && divisible_by_4; bool divisible_by_13 = number * 3303820997u <= 330382099u; bool divisible_by_14 = divisible_by_2 && divisible_by_7; bool divisible_by_15 = number * 4008636143u <= 286331153u; bool divisible_by_16 = number % 16 == 0;

En cuanto a la divisibilidad por d las siguientes reglas son válidas:

Cuando d es un poder de 2:
Como señaló , puede usar is_divisible_by_d = (number % d == 0) . Los compiladores son lo suficientemente astutos como para reemplazar esto con (number & (d - 1)) == 0 que es más eficiente pero también ofuscado.
Sin embargo, cuando d no es una potencia de 2, parece que la ofuscación que se muestra arriba es más eficiente que lo que hacen los compiladores actuales. (Más sobre eso más adelante).
Cuando d es impar:
La técnica toma la forma is_divisible_by_d = number * a <= b donde a y b son constantes ingeniosamente obtenidas . Tenga en cuenta que todo lo que necesitamos es 1 multiplicación y 1 comparación:
Cuando d es par, pero no tiene una potencia de 2:
Luego, escribe d = p * q donde p es una potencia de 2 y q es impar y usa la "lengua en la mejilla" sugerida por , es decir, is_divisible_by_d = is_divisible_by_p && is_divisible_by_q . De nuevo, solo se realiza 1 multiplicación (en el cálculo de is_divisible_by_q ).

Muchos compiladores (he probado clang 5.0.0, gcc 7.3, icc 18 y msvc 19 usando godbolt ) reemplazan el number % d == 0 por (number / d) * d == number . Utilizan una técnica inteligente (ver referencias en la answer Olof Forshell ) para reemplazar la división por una multiplicación y un cambio de bit. Terminan haciendo 2 multiplicaciones. En contraste con las técnicas anteriores, realice solo 1 multiplicación.

Un método que puede ayudar a la reducción del módulo de todos los valores enteros usa el corte de bits y la cuenta de números.

mod3 = pop(x & 0x55555555) + pop(x & 0xaaaaaaaa) << 1; // <- one term is shared! mod5 = pop(x & 0x99999999) + pop(x & 0xaaaaaaaa) << 1 + pop(x & 0x44444444) << 2; mod7 = pop(x & 0x49249249) + pop(x & 0x92492492) << 1 + pop(x & 0x24924924) << 2; modB = pop(x & 0x5d1745d1) + pop(x & 0xba2e8ba2) << 1 + pop(x & 0x294a5294) << 2 + pop(x & 0x0681a068) << 3; modD = pop(x & 0x91b91b91) + pop(x & 0xb2cb2cb2) << 1 + pop(x & 0x64a64a64) << 2 + pop(x & 0xc85c85c8) << 3;

Los valores máximos para estas variables son 48, 80, 73, 168 y 203, que se ajustan a las variables de 8 bits. La segunda ronda se puede llevar en paralelo (o se puede aplicar algún método LUT)

mod3 mod3 mod5 mod5 mod5 mod7 mod7 mod7 modB modB modB modB modD modD modD modD mask 0x55 0xaa 0x99 0xaa 0x44 0x49 0x92 0x24 0xd1 0xa2 0x94 0x68 0x91 0xb2 0x64 0xc8 shift *1 *2 *1 *2 *4 *1 *2 *4 *1 *2 *4 *8 *1 *2 *4 *8 sum <-------> <------------> <-----------> <-----------------> <----------------->

Un poco de pernicioso y ofuscado juego de palabras te puede hacer divisar por 15.

Para un número sin firmar de 32 bits:

def mod_15ish(unsigned int x) { // returns a number between 0 and 21 that is either x % 15 // or 15 + (x % 15), and returns 0 only for x == 0 x = (x & 0xF0F0F0F) + ((x >> 4) & 0xF0F0F0F); x = (x & 0xFF00FF) + ((x >> 8) & 0xFF00FF); x = (x & 0xFFFF) + ((x >> 16) & 0xFFFF); // *1 x = (x & 0xF) + ((x >> 4) & 0xF); return x; } def Divisible_by_15(unsigned int x) { return ((x == 0) || (mod_15ish(x) == 15)); }

Puede crear rutinas de divisibilidad similares para 3 y 5 basadas en mod_15ish .

Si tiene que tratar con enteros sin firmar de 64 bits, extienda cada constante sobre la línea *1 de la manera obvia, y agregue una línea sobre la línea *1 para hacer un desplazamiento a la derecha en 32 bits con una máscara de 0xFFFFFFFF . (Las dos últimas líneas pueden permanecer iguales) mod_15ish obedece al mismo contrato básico, pero el valor de retorno ahora está entre 0 y 31 . ( mod_15ish(x) % 15 lo que se mantiene es que x % 15 == mod_15ish(x) % 15 )

Un poco la lengua en la mejilla, pero suponiendo que obtengas el resto de las respuestas:

Una cosa a tener en cuenta: dado que solo te importa la divisibilidad hasta 16, solo necesitas verificar la divisibilidad por los números primos hasta 16. Estos son 2, 3, 5, 7, 11 y 13.

Divida su número por cada uno de los números primos, haciendo un seguimiento con un booleano (como div2 = verdadero). Los números dos y tres son casos especiales. Si div3 es verdadero, intente dividir por 3 nuevamente, estableciendo div9. Dos y sus poderes son muy simples (nota: ''&'' es una de las cosas más rápidas que un procesador puede hacer):

if n & 1 == 0: div2 = true if n & 3 == 0: div4 = true if n & 7 == 0: div8 = true if n & 15 == 0: div16 = true

Ahora tiene los booleanos div2, div3, div4, div5, div7, div8, div9, div11, div13 y div16. Todos los demás números son combinaciones; por ejemplo div6 es lo mismo que (div2 && div3)

Por lo tanto, solo necesita hacer 5 o 6 divisiones reales (6 solo si su número es divisible por 3).

Para mí, probablemente usaría bits en un solo registro para mis booleanos; por ejemplo, bit_0 significa div2. Entonces puedo usar máscaras:

if (flags & (div2+div3)) == (div2 + div3): do_6()

tenga en cuenta que div2 + div3 puede ser una constante precalculada. Si div2 es bit0 y div3 es bit1, entonces div2 + div3 == 3. Esto hace que el anterior ''if'' se optimice para:

if (flags & 3) == 3: do_6()

Entonces ahora ... mod sin una división:

def mod(n,m): i = 0 while m < n: m <<= 1 i += 1 while i > 0: m >>= 1 if m <= n: n -= m i -= 1 return n div3 = mod(n,3) == 0 ...

Por cierto: el peor caso para el código anterior es 31 veces a través de cualquier bucle para un número de 32 bits

FYI: Acabo de mirar la publicación de Msalter, arriba. Su técnica se puede usar en lugar de mod (...) para algunos de los números primos.