optimization - resueltos - ¿Cuál es la forma más rápida de dividir un número entero por 3?
divisiones con decimales en el divisor (12)
int x = n / 3; // <-- make this faster
// for instance
int a = n * 3; // <-- normal integer multiplication
int b = (n << 1) + n; // <-- potentially faster multiplication
¿Qué pasa si realmente no quieres multiplicar o dividir? Aquí hay una aproximación que acabo de inventar. Funciona porque (x / 3) = (x / 4) + (x / 12). Pero como (x / 12) = (x / 4) / 3 solo tenemos que repetir el proceso hasta que sea lo suficientemente bueno.
#include <stdio.h>
void main()
{
int n = 1000;
int a,b;
a = n >> 2;
b = (a >> 2);
a += b;
b = (b >> 2);
a += b;
b = (b >> 2);
a += b;
b = (b >> 2);
a += b;
printf("a=%d/n", a);
}
El resultado es 330. Podría hacerse más preciso usando b = ((b + 2) >> 2); para explicar el redondeo.
Si se le permite multiplicar, simplemente elija una aproximación adecuada para (1/3), con un divisor de potencia de 2. Por ejemplo, n * (1/3) ~ = n * 43/128 = (n * 43) >> 7.
Esta técnica es muy útil en Indiana.
Computación fácil ... a lo sumo n iteraciones donde n es su número de bits:
uint8_t divideby3(uint8_t x)
{
uint8_t answer =0;
do
{
x>>=1;
answer+=x;
x=-x;
}while(x);
return answer;
}
Dependiendo de su plataforma y dependiendo de su compilador de C, una solución nativa como simplemente usar
y = x / 3
Puede ser rápido o puede ser terriblemente lento (incluso si la división se hace completamente en hardware, si se hace usando una instrucción DIV, esta instrucción es aproximadamente de 3 a 4 veces más lenta que una multiplicación en las CPU modernas). Muy buenos compiladores de C con indicadores de optimización activados pueden optimizar esta operación, pero si quiere estar seguro, es mejor que lo optimice usted mismo.
Para la optimización, es importante tener números enteros de un tamaño conocido. En C int no tiene un tamaño conocido (¡puede variar según la plataforma y el compilador!), Por lo que es mejor utilizar enteros de tamaño fijo C99. El código siguiente supone que desea dividir un entero de 32 bits sin signo entre tres y que su compilador C conoce números enteros de 64 bits ( NOTA: incluso en una arquitectura de CPU de 32 bits, la mayoría de los compiladores de C pueden manejar enteros de 64 bits ):
static inline uint32_t divby3 (
uint32_t divideMe
) {
return (uint32_t)(((uint64_t)0xAAAAAAABULL * divideMe) >> 33);
}
Por loco que suene, pero el método anterior sí lo divide por 3. Todo lo que necesita para hacerlo es una sola multiplicación de 64 bits y un cambio (como dije, las multiplicaciones pueden ser de 3 a 4 veces más rápidas que las divisiones en su CPU ) En una aplicación de 64 bits, este código será mucho más rápido que en una aplicación de 32 bits (en una aplicación de 32 bits que multiplica dos números de 64 bits toma 3 multiplicaciones y 3 agregaciones en valores de 32 bits); sin embargo, podría ser aún más rápido que división en una máquina de 32 bits.
Por otro lado, si tu compilador es muy bueno y conoce el truco de cómo optimizar la división de enteros por una constante (lo último de GCC, acabo de comprobar), generará el código anterior de todos modos (GCC creará exactamente este código para "/ 3" si habilita al menos el nivel de optimización 1). Para otros compiladores ... no puede confiar o esperar que use trucos como ese, aunque este método está muy bien documentado y mencionado en todo el Internet.
El problema es que solo funciona para números constantes, no para números variables. Siempre necesita saber el número mágico (aquí 0xAAAAAAAB) y las operaciones correctas después de la multiplicación (cambios y / o adiciones en la mayoría de los casos) y ambos son diferentes dependiendo del número que desea dividir y ambos toman demasiado tiempo de CPU para calcule sobre la marcha (eso sería más lento que la división de hardware). Sin embargo, es fácil para un compilador calcularlos durante el tiempo de compilación (donde un segundo más o menos tiempo de compilación apenas juega un papel).
El tipo que dijo "déjalo al compilador" tenía razón, pero no tengo la "reputación" para modificarlo o comentarlo. Le pedí a gcc que compilara la prueba int (int a) {return a / 3; } para un ix86 y luego desensamblado la salida. Solo por interés académico, lo que está haciendo es aproximadamente multiplicar por 0x55555556 y luego tomar los primeros 32 bits del resultado de 64 bits de eso. Puede demostrar esto a usted mismo con, por ejemplo:
$ ruby -e ''puts(60000 * 0x55555556 >> 32)'' 20000 $ ruby -e ''puts(72 * 0x55555556 >> 32)'' 24 $
La página de wikipedia en la división de Montgomery es difícil de leer, pero afortunadamente los chicos del compilador lo han hecho para que no sea necesario.
Este es el más rápido ya que el compilador lo optimizará si puede dependiendo del procesador de salida.
int a;
int b;
a = some value;
b = a / 3;
Hay una forma más rápida de hacerlo si conoce los rangos de los valores, por ejemplo, si divide un entero con signo por 3 y sabe que el rango del valor a dividir es de 0 a 768, puede multiplicarlo por un factor y cambiarlo a la izquierda por una potencia de 2 a ese factor dividido por 3.
p.ej.
Rango 0 -> 768
podrías usar el desplazamiento de 10 bits, que multiplicando por 1024, quieres dividir por 3, entonces tu multiplicador debería ser 1024/3 = 341,
entonces ahora puede usar (x * 341) >> 10
(Asegúrese de que el turno sea un turno firmado si usa enteros con signo), también asegúrese de que el turno sea en realidad un turno y no un poco ROLLO
Esto dividirá efectivamente el valor 3, y se ejecutará a aproximadamente 1.6 veces la velocidad como una división natural en 3 en una CPU estándar x86 / x64.
Por supuesto, la única razón por la que puede hacer esta optimización cuando el compilador no puede hacerlo es porque el compilador no conoce el rango máximo de X y, por lo tanto, no puede hacer esta determinación, pero usted como programador puede hacerlo.
En algún momento, puede ser más beneficioso mover el valor a un valor mayor y luego hacer lo mismo, es decir. si tiene un int de rango completo, puede convertirlo en un valor de 64 bits y luego multiplicar y desplazar en lugar de dividir por 3.
Tuve que hacer esto recientemente para acelerar el procesamiento de imágenes, necesitaba encontrar el promedio de 3 canales de color, cada canal de color con un rango de bytes (0 - 255). rojo verde y azul.
Al principio simplemente usé:
avg = (r + g + b) / 3;
(Entonces r + g + b tiene un máximo de 768 y un mínimo de 0, porque cada canal es un byte 0 - 255)
Después de millones de iteraciones, toda la operación tomó 36 milisegundos.
Cambié la línea a:
avg = (r + g + b) * 341 >> 10;
Y eso llevó a 22 milisegundos, es increíble lo que se puede hacer con un poco de ingenio.
Esta aceleración se produjo en C # aunque tuve las optimizaciones activadas y estaba ejecutando el programa de forma nativa sin depuración de información y no a través del IDE.
No sé si es más rápido, pero si desea usar un operador bit a bit para realizar una división binaria, puede usar el método de desplazamiento y sustracción que se describe en esta página :
- Establecer el cociente en 0
- Alinea los dígitos más a la izquierda en dividendo y divisor
- Repetir:
- Si esa parte del dividendo por encima del divisor es mayor o igual que el divisor:
- Luego reste el divisor de esa parte del dividendo y
- Concatete 1 al extremo derecho del cociente
- El otro concatena 0 al extremo derecho del cociente
- Cambia el divisor un lugar correcto
- Hasta que el dividendo sea menor que el divisor:
- el cociente es correcto, el dividendo es resto
- DETENER
Para números de 64 bits:
uint64_t divBy3(uint64_t x)
{
return x*12297829382473034411ULL;
}
Sin embargo, esta no es la división entera truncada que podría esperar. Funciona correctamente si el número ya es divisible por 3, pero devuelve un número enorme si no es así.
Por ejemplo, si lo ejecuta en, por ejemplo, 11, devuelve 6148914691236517209. Esto parece una basura, pero de hecho es la respuesta correcta: ¡multiplíquelo por 3 y recupera los 11!
Si está buscando la división truncada, simplemente use el operador /. Dudo mucho que puedas llegar mucho más rápido que eso.
Teoría:
La aritmética sin signo de 64 bits es una aritmética de módulo 2 ^ 64. Esto significa que para cada entero que es coprime con el módulo 2 ^ 64 (esencialmente todos los números impares) existe un inverso multiplicativo que puede usar para multiplicar con en lugar de división. Este número mágico puede obtenerse resolviendo la ecuación 3*x + 2^64*y = 1 usando el Algoritmo Euclidiano Extendido.
Para una división entera muy grande (por ejemplo, números mayores de 64 bits) puede representar su número como int [] y realizar división bastante rápido tomando dos dígitos a la vez y dividirlos por 3. El resto será parte de los siguientes dos dígitos Etcétera.
p.ej. 11004/3 dices
11/3 = 3, residuo = 2 (de 11-3 * 3)
20/3 = 6, resto = 2 (de 20-6 * 3)
20/3 = 6, resto = 2 (de 20-6 * 3)
24/3 = 8, resto = 0
de ahí el resultado 3668
internal static List<int> Div3(int[] a)
{
int remainder = 0;
var res = new List<int>();
for (int i = 0; i < a.Length; i++)
{
var val = remainder + a[i];
var div = val/3;
remainder = 10*(val%3);
if (div > 9)
{
res.Add(div/10);
res.Add(div%10);
}
else
res.Add(div);
}
if (res[0] == 0) res.RemoveAt(0);
return res;
}
Si realmente quieres ver este artículo sobre la división de enteros , pero solo tiene mérito académico ... sería una aplicación interesante que realmente se necesitaba para realizar y que se beneficiara de ese tipo de truco.
Un enfoque de tabla de búsqueda también sería más rápido en algunas arquitecturas.
uint8_t DivBy3LU(uint8_t u8Operand)
{
uint8_t ai8Div3 = [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ....];
return ai8Div3[u8Operand];
}