Multiplicación Rápida

Question

Estoy escribiendo código para un microprocesador con aritmética de enteros rápidos y aritmética flotante no tan rápida . Necesito dividir un número entero por un número del 1 al 9 y convertir el resultado nuevamente a entero.

Hice una matriz flotante con miembros como 0, 1, 0.5, 0.3333, etc. Pero creo que hay constantes MÁGICAS (como 0x55555556) para un número excepto (1/3).

¿Qué son estos números?

Answer 1

Si la instrucción de división en tu microcontrolador es lo suficientemente rápida, úsala. Si necesita la parte fraccionaria del resultado, puede utilizar el resto; en la mayoría de las arquitecturas, la instrucción de división coloca el cociente en un registro y el resto en otro.

Si su instrucción de división no es lo suficientemente rápida pero la instrucción de multiplicación sí, puede usar la siguiente técnica (y suena como si esta fuera la técnica que busca). En la mayoría de las arquitecturas, multiplicar un número de 32 bits por otro número de 32 bits da como resultado un resultado de 64 bits; la mitad más significativa se almacena en un registro y la mitad menos significativa se almacena en el otro registro. Puede explotar esto al darse cuenta de que la división por un número n es lo mismo que multiplicar por (2 ^ 32) / n, luego tomar los 32 bits más significativos del resultado. En otras palabras, si desea dividir entre 3, puede multiplicar por 0x100000000 / 3 = 0x55555555, luego tomar los 32 bits más significativos del resultado.

Lo que estás haciendo aquí es realmente una forma de aritmética de punto fijo. Consulte el artículo de Wikipedia para obtener más información.

Answer 2

Una división de un entero por una constante entera se puede reemplazar con una combinación de un cambio y una multiplicación. Consulte esta guía de optimización para obtener más información. Por supuesto, esto es útil si es realmente más rápido en el chip de interés.

Answer 3

Supongo que, según la etiqueta del microcontrolador, no tiene una división rápida de enteros. Mi respuesta también es para los valores sin firmar: funcionará para los valores firmados, solo tienes que limitar los números que se usan en la parte difícil a continuación.

Un buen comienzo es dividir por 2, 4 y 8. Esto se puede hacer con cambios a la derecha de 1, 2 y 3 bits respectivamente, asumiendo que su CPU tiene una instrucción lógica de cambio a la derecha.

En segundo lugar, dividir por 1 es mantener el número tal como está. Eso solo deja 3, 5, 6, 7 y 9.

El bit complicado comienza aquí:

Para los otros números, puedes usar el hecho de que una división puede ser reemplazada por una multiplicación y cambio.

Digamos que tiene un procesador de 16 bits. Para dividir por N, multiplica por 256 / N y desplaza 8 bits a la derecha:

N = 3, multiply by 85
N = 5, multiply by 51
N = 6, multiply by 43
N = 7, multiply by 37
N = 9, multiply by 28

Toma el ejemplo aleatorio de 72 / 5. Multiplica 72 por 51 para obtener 3672, luego cambia a la derecha 8 bits para obtener 14.

Para que esto funcione, los números que está utilizando no deben desbordar los 16 bits. Como su peor caso es multiplicar por 85, puede manejar números de hasta 771.

La razón por la que esto funciona es porque un desplazamiento a la derecha de 8 bits es lo mismo que dividir por 256, y:

  m * (256 /  n) / 256
= m / (n /  256) / 256
= m /  n *  256  / 256
= m /  n * (256  / 256)
= m /  n

Si tiene un procesador de 32 bits, los valores y los rangos cambian un poco, ya que es 65536 / N:

N = 3, multiply by 21,846, right shift 16 bits, max value roughly 196,600.
N = 5, multiply by 13,108.
N = 6, multiply by 10,923.
N = 7, multiply by  9,363.
N = 9, multiply by  7,282.

Nuevamente, elijamos 20,000 / 7 al azar: 20,000 multiplicado por 9,363 es 187,260,000 y, cuando desplazas a la derecha esos 16 bits, obtienes 2,857 - el resultado real es 2,857.

El siguiente programa de prueba en C muestra las cifras de precisión para los valores dados. Utiliza valores con signo, por lo que solo es bueno hasta aproximadamente 98,000, pero puede ver que el error más grande es 1 y que ocurre en el punto más bajo de 13,110 (solo el 0,008% de error).

#include <stdio.h>
int res[5] = {0};
int low[5] = {-1,-1,-1,-1,-1};
int da[] = {3,5,6,7,9};
int ma[] = {21846,13108,10923,9363,7282};
int main (void) {
    int n, i;
    for (n = 0; n < 98000; n++) {
        for (i = 0; i < sizeof(da)/sizeof(da[0]); i++) {
            int r1 = n / da[i];
            int r2 = (n * ma[i])>>16;
            int dif = abs (r1-r2);
            if (dif >= 5) {
                printf ("%d / %d gives %d and %d\n", n, da[i], r1, r2);
                return 1;
            }
            res[dif]++;
            if (low[dif] == -1) {
                low[dif] = n;
            }
        }
    }
    for (i = 0; i < sizeof(res)/sizeof(res[0]); i++) {
        printf ("Difference of %d: %6d, lowest value was %6d\n", i, res[i], low[i]);
    }
    return 0;
}

Esto genera:

Difference of 0: 335874, lowest value was      0
Difference of 1: 154126, lowest value was  13110
Difference of 2:      0, lowest value was     -1
Difference of 3:      0, lowest value was     -1
Difference of 4:      0, lowest value was     -1