¿Cuál es la forma más rápida de dividir un número entero por 3?

StackOverflow https://stackoverflow.com/questions/171301

Pregunta 

int x = n / 3;  // <-- make this faster

// for instance

int a = n * 3; // <-- normal integer multiplication

int b = (n << 1) + n; // <-- potentially faster multiplication
¿Fue útil?

Solución

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;

Otros consejos

El tipo que dijo "déjalo en el compilador" Estaba en lo cierto, pero no tengo la "reputación" Para modificarlo o comentarlo. Le pedí a gcc que compile int test (int a) {return a / 3; } para un ix86 y luego desensambla la salida. Solo por interés académico, lo que está haciendo es aproximadamente multiplicando por 0x55555556 y luego tomando los 32 bits superiores del resultado de 64 bits. Puedes demostrar esto a ti mismo con, por ejemplo: 

$ ruby -e 'puts(60000 * 0x55555556 >> 32)'
20000
$ ruby -e 'puts(72 * 0x55555556 >> 32)'
24
$

La página de wikipedia en división de Montgomery es difícil de leer, pero afortunadamente los compiladores lo han hecho para que no tengas que hacerlo.

Hay una forma más rápida de hacerlo si conoce los rangos de los valores, por ejemplo, si está dividiendo un entero con signo entre 3 y sabe que el rango del valor a dividir es de 0 a 768, entonces puede multiplicarlo por un factor y desplazarlo hacia la izquierda por una potencia de 2 a ese factor dividido por 3.

por ejemplo.

Rango 0 - > 768

puede usar el desplazamiento de 10 bits, que multiplicando por 1024, quiere dividir por 3, por lo que su multiplicador debería ser 1024/3 = 341,

para que ahora puedas usar (x * 341) > > 10
(Asegúrese de que el cambio sea un cambio con signo si usa enteros con signo), también asegúrese de que el cambio sea realmente un cambio y no un poco ROLLAR

Esto dividirá efectivamente el valor 3, y se ejecutará aproximadamente 1,6 veces la velocidad como una división natural entre 3 en una CPU x86 / x64 estándar.

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 el programador puede.

En algún momento, incluso 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 hacer la multiplicación y el cambio en lugar de dividir por 3.

Hace poco tuve que hacer esto 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;

(Así que 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, la operación completa tomó 36 milisegundos.

Cambié la línea a:

avg = (r + g + b) * 341 > > 10;

Y eso lo 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 tenía activadas las optimizaciones y estaba ejecutando el programa de forma nativa sin información de depuración y no a través del IDE.

Consulte Cómo dividir por 3 para una discusión más amplia de más dividiendo eficientemente por 3, enfocado en hacer operaciones aritméticas de FPGA.

También relevante:

Dependiendo de su plataforma y 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 realiza completamente en hardware, si se hace usando una instrucción DIV, esta instrucción es aproximadamente 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 quieres estar seguro, es mejor que lo optimices tú mismo.

Para la optimización, es importante tener números enteros de un tamaño conocido. En C int no se conoce el tamaño (¡puede variar según la plataforma y el compilador!), Por lo que es mejor utilizar enteros de tamaño fijo C99. El código a continuación asume que usted desea dividir un entero de 32 bits sin firmar por tres y que el compilador de C conoce alrededor de números de 64 bits ( NOTA: Incluso en una arquitectura de CPU de 32 bits, la mayoría de los compiladores de C pueden manejar números enteros de 64 bits) bien ): 

static inline uint32_t divby3 (
    uint32_t divideMe
) {
    return (uint32_t)(((uint64_t)0xAAAAAAABULL * divideMe) >> 33);
}

Tan loco como puede sonar, pero el método anterior en realidad se 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, la multiplicación de dos números de 64 bits requiere 3 multiplicaciones y 3 adiciones 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 otra parte, si su compilador es muy bueno y sabe el truco de cómo optimizar la división de enteros por una constante (el último GCC lo hace, lo acabo de marcar), 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 puedes confiar o esperar que use trucos como esos, a pesar de que este método está muy bien documentado y se menciona en todas partes en Internet.

El problema es que solo funciona con números constantes, no con 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 requieren demasiado tiempo de CPU para calcularlos sobre la marcha (que 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 el tiempo de compilación no juega un papel importante).

¿Qué sucede si usted realmente no quiere 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. Se podría hacer más preciso utilizando b = ((b + 2) > > 2); para tener en cuenta el redondeo.

Si tiene permitido 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 más útil en Indiana.

No sé si es más rápido, pero si desea utilizar un operador bitwise para realizar la división binaria, puede usar el método de cambio y resta descrito en esta página :

  
      
  • Establezca el cociente en 0
    •   
  • Alinear los dígitos del extremo izquierdo en dividendo y divisor
    •   
  • repetir:      
        
    • Si esa parte del dividendo sobre el divisor es mayor o igual que el divisor:      
          
      • Luego reste el divisor de esa parte del dividendo y
        •   
      • Concatene 1 al extremo derecho del cociente
        •   
      • De lo contrario, concatene 0 en el extremo derecho del cociente
        •   
      •   
    • Desplazar el divisor un lugar a la derecha
      •   
    •   
  • Hasta que el dividendo sea menor que el divisor:
    •   
  • el cociente es correcto, el dividendo es el resto
    •   
  • PARAR
    •   

Para números de 64 bits: 

uint64_t divBy3(uint64_t x)
{
    return x*12297829382473034411ULL;
}

Sin embargo, esta no es la división de enteros truncado que podría esperar. Funciona correctamente si el número ya es divisible por 3, pero devuelve un gran número si no lo es.

Por ejemplo, si lo ejecutas en el ejemplo 11, devuelve 6148914691236517209. Esto parece una basura, pero en realidad es la respuesta correcta: multiplícalo por 3 y recuperas el 11!

Si está buscando la división de truncamiento, solo 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 puedes usar para multiplicar con en lugar de división. Este número mágico se puede obtener resolviendo la ecuación 3 * x + 2 ^ 64 * y = 1 utilizando el algoritmo euclidiano extendido.

Si realmente quieres ver este artículo en división entera , pero solo tiene mérito académico ... sería una aplicación interesante que realmente se necesitaba para realizar que se benefició de ese tipo de truco.

Para una división de enteros realmente grande (p. ej., números mayores a 64 bits) puede representar su número como un int [] y realizar la división bastante rápido al tomar dos dígitos a la vez y dividirlos por 3. El resto formará parte de próximos dos dígitos y así sucesivamente.

por ejemplo. 11004/3 que dices

11/3 = 3, permaneciendo = 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;
}

Cómputo fácil ... como máximo 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;
}

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];
}
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top