c++ - numeros - ¿Cómo comprobar si el número dado es divisible de 15 de la manera más rápida?

divisibilidad por 7 y 11

Question

La división en el procesador lleva mucho tiempo, por lo que quiero preguntar cómo verificar de la manera más rápida si el número es divisible de algún otro número, en mi caso necesito verificar si el número es divisible por 15.

También he estado buscando en la web y encontré formas divertidas de verificar si el número es divisible de algún número, pero estoy buscando una opción rápida.

NOTA: como la división lleva mucho tiempo, estoy buscando una respuesta sin / y % .

Answer 1

Aquí hay otro enfoque, que probablemente sea más lento que otros, pero usa solo la suma, el modo de bits y el desplazamiento:

int divisible15(unsigned int x) {
        if (x==0) return 1;
        x = (x & 0x0f0f0f0f) + ((x&0xf0f0f0f0)>>4);
        x = (x & 0x00ff00ff) + ((x&0xff00ff00)>>8);
        x = (x & 0x0000ffff) + ((x&0xffff0000)>>16);
        x = (x & 0x0f) + ((x&0xf0)>>4);
        return x==15;
}

La idea es que la divisibilidad por 15, en la base 16, es como la divisibilidad por 9 en la base 10; la suma de los dígitos debe ser divisible por 15.
Por lo tanto, el código resume todos los dígitos hexadecimales (de manera similar a la forma en que se cuentan los bits), y la suma debe ser igual a 15 (excepto para 0).

Answer 2

Bueno, es muy fácil de hacer en tu cabeza si tienes la representación hexadecimal. Solo suma todos los dígitos, hasta que tengas un solo dígito. Si la respuesta es ''0xf'', es divisible por 15.

Ejemplo 0x3a98 : 3 + 0xa + 9 + 8 = 0x1e = 1 + 0xe = 0xf, entonces eso es divisible por 15.

Esto funciona para todos los factores en X-1, donde X es la base utilizada para representar el número. (Para factores más pequeños, el dígito final debe ser divisible por el factor).

Sin embargo, no esperes que esto sea rápido en código.

Answer 3

En un proceso razonablemente moderno, dividir por 15 no debería ser tan terrible. La guía de optimización de AMD lo define en función del cociente (el valor que se está dividiendo), y toma la posición de 8 + bits del bit más significativo del cociente. Entonces, si sus números tienen el 63. ° bit establecido, terminará con 71 ciclos, lo cual es una instrucción bastante larga, por supuesto. Pero para un número de 32 bits con unos pocos ceros en los bits superiores, estamos hablando de 30-40 ciclos. Si el número se ajusta a un valor de 16 bits, el máximo es de 23 ciclos.

Para obtener el resto es un ciclo de reloj más por encima de eso.

Si estás haciendo esto TODO el tiempo, por supuesto, puedes encontrar que este tiempo es bastante largo, pero no estoy seguro de que haya una manera trivial de evitarlo.

Como han dicho otros, el compilador puede ser capaz de reemplazarlo con algo mejor. Pero 15 no tiene, por lo que sé, tiene una solución rápida obvia (si tienes 16 en lugar de 15, entonces podemos usar el truco de x & 15 ).

Si se trata de un rango limitado, podría crear una tabla [ vector<bool> por ejemplo, que almacenará 1 bit por entrada], pero pronto se encontrará con el problema de que el acceso a la memoria no almacenada en caché toma tanto tiempo como una operación de división ...

Hay algunas formas interesantes de averiguar si un número se divide por 3, 5 y así sucesivamente sumando los dígitos, pero desafortunadamente, estos solo funcionan en base a dígitos decimales, lo que implica una larga secuencia de divisiones.

Answer 4

La multiplicación toma menos tiempo que la división, así que puedes intentar esto:

inline bool divisible15(unsigned int x)
{
    //286331153 = (2^32 - 1) / 15
    //4008636143 = (2^32) - 286331153
    return x * 4008636143u <= 286331153u;
}

Esta forma funciona porque 2^32-1 (valor máximo de 32 bits) es divisible de 15, sin embargo, si toma, por ejemplo, 7, parecería funcionar, pero no funcionaría en todos los casos.

EDITAR: Vea this , demuestra que esta solución ( en algunos compiladores ) es más rápida que el módulo.

EDIT: Here está la explicación y la generalización.

Answer 5

Respuesta obligatoria para otros estudiantes que puedan venir en busca de una respuesta.

if (number % n == 0)

En la mayoría de los casos, siempre puede hacer esto, confiando en los compiladores modernos e inteligentes.

Sin embargo, esto no significa que te desanimes a aprender maneras divertidas. Echa un vistazo a estos enlaces.

Pruebas de divisibilidad rápida (por 2,3,4,5, .., 16)?

Trucos de Bit Twiddling

Answer 6

Solo usa i % 15 == 0

1. Dado que el compilador puede ver fácilmente que 15 nunca cambiará, puede sentirse libre de realizar cualquier optimización que desee en la operación de modificación. Es un trabajo de compilación de escritores hacer este tipo de optimización si no han pensado en una mejor manera de hacerlo, no lo harás.

2. Por ejemplo, es muy fácil verificar si un número es divisible entre 2 porque simplemente marca el primer bit. Los escritores de compiladores saben esto y usted podría escribir el código usted mismo para verificar el primer bit, pero especialmente un compilador maduro hará que la gente piense y trabaje en estas cosas durante años. Este tipo de optimización es muy sencillo de realizar, ya que solo requiere cambiar una instrucción o 2, las optimizaciones como una mejor asignación de registros son mucho más difíciles de lograr

3. Una cosa más a considerar es que su compilador fue escrito para el sistema en el que está encendido, su código por otro lado es el mismo en todas partes, si escribe un código extraño que puede ser igual de rápido en un sistema (probablemente todavía no sea más rápido) ) pero en otro sistema que tiene una optimización de hardware especial, su código puede perder en un orden de magnitud. Dado que escribió algún código esotérico para verificar la divisibilidad, es improbable que el compilador se dé cuenta de que puede optimizar a una sola operación de hardware, escribir lo obvio hace que la vida sea mejor para usted y más fácil para el compilador.

4. Ya que realmente no has comprobado que la velocidad sea importante al escribir el código, la forma extraña hará que el código sea muy difícil de leer para la siguiente persona y que sea más propenso a errores ( la optimización prematura es la raíz de todo mal )

5. Todavía funciona si la entrada es de 16, 32 o 64 bits, ya que no se basa en una manipulación de bits.

6. Incluso si el escritor del compilador no lo ha implementado, es claramente posible que alguien lo implemente (incluso usted mismo)