¿Algoritmo rápido de módulo 3 o división?

hay un algoritmo rápido, similar a la potencia de 2, que se puede usar con 3, es decir, n% 3. Tal vez algo que utiliza el hecho de que si la suma de dígitos es divisible por tres, entonces el número también es divisible.¿Algoritmo rápido de módulo 3 o división?

Esto lleva a la siguiente pregunta. ¿Cuál es la forma más rápida de agregar dígitos en un número? Es decir. 37 -> 3 7 -> 10 Busco algo que no tiene condicionales como aquellos que tienden a inhibir la vectorización

gracias

Fuente

2009-11-08 Anycorn

Agregar dígitos no funcionará en este caso porque tendría que convertir el número primero a un número decimal que demora _mucho_ más que solo dividir. –

¿Qué estás tratando de lograr? A menos que sea una curiosidad teórica, dudo que este problema específico que tiene sea el cuello de botella de una aplicación del mundo real ... –

es práctico y teórico. la pregunta surge al tratar de distribuir múltiples bucles anidados sobre centros cartesianos entre hilos (específicamente Cuda, pero no es importante). Ya resolví el problema de otra manera, pero aún me gustaría saber si hay alguna manera. Este es un verdadero cuello de botella ya que la división y el módulo enteros son mucho más caros que las operaciones reales de coma flotante que intento hacer en paralelo. – Anycorn

4 % 3 == 1, entonces (4^k * a + b) % 3 == (a + b) % 3. Se puede utilizar este hecho para evaluar x 3% para los de 32 bits x:

x = (x >> 16) + (x & 0xffff); 
x = (x >> 10) + (x & 0x3ff); 
x = (x >> 6) + (x & 0x3f); 
x = (x >> 4) + (x & 0xf); 
x = (x >> 2) + (x & 0x3); 
x = (x >> 2) + (x & 0x3); 
x = (x >> 2) + (x & 0x3); 
if (x == 3) x = 0;

(. No comprobado - Puede que necesite un poco más reducciones) es más rápido que el hardware puede hacer x 3%? Si es así, probablemente no sea por mucho.

Fuente

2009-11-08 18:22:39

¿Es esto realmente más rápido que 'x% 3'? Ver https://godbolt.org/g/aRbqrW – plasmacel

No está seguro de su primera pregunta, pero para la segunda, se puede tomar ventaja de la división % operador y número entero:

int num = 12345; 
int sum = 0; 
while (num) { 
    sum += num % 10; 
    num /= 10; 
}

Esto funciona porque 12345 % 10 = 5, 12345/10 = 1234 y seguir adelante hasta num == 0

Fuente

2009-11-08 18:14:57

+1 Niza # 2. solución. –

sí, es esa solución obvia. Sin embargo, división y módulo son operaciones muy caras, del orden de cientos de ciclos en mi plataforma. Estoy más interesado en algo que no incluye esos. Tengo que decir que esta es una pregunta puramente curiosa. – Anycorn

Este comp.compilers item tiene una recomendación específica para el cálculo de modulo 3.

Una alternativa, especialmente si el tamaño maximium del dividendo es modesta, es multiplicar por el recíproco de 3 como un valor de punto fijo, con suficiente bits de precisión para manejar el dividendo de tamaño máximo para calcular el cociente, y luego restar 3 * cociente del dividendo para obtener el resto. Todas estas multiplicaciones se pueden implementar con una secuencia fija de turnos y adiciones. El número de instrucciones dependerá del patrón de bits del recíproco. Esto funciona bastante bien cuando el dividendo máximo es de tamaño modesto.

En cuanto a la adición de dígitos en el número ... si desea agregar los dígitos decimales, terminará haciendo lo que equivale a una conversión de número a decimal, que implica dividir por 10 en algún lugar . Si está dispuesto a conformarse con sumar los dígitos en base2, puede hacerlo con un shift-right fácil y agregar un bucle. Se pueden usar varios trucos ingeniosos para hacer esto en trozos de N bits para acelerarlo aún más.

Fuente

2009-11-08 18:55:35

¿Algoritmo rápido de módulo 3 o división?

Respuesta

Cuestiones relacionadas