rápida multiplicação

Question

Eu estou escrevendo código para um microprocessador com aritmética inteira rápido e não tão rápido flutuador aritmética. Eu preciso dividir um inteiro por um número de 1 a 9 e convertido resultado de volta para inteiro.

I feita uma matriz flutuador com membros como 0, 1, 0,5, 0,3333 etc. Mas eu acho que há constantes mágicas (como 0x55555556) para um número, exceto (1/3).

O que são estes números?

Answer 1

Se a instrução divisão em seu microcontrolador é rápido o suficiente, use isso. Se você precisar a parte fracionária do resultado, você pode ser capaz de usar o restante; na maioria das arquiteturas, as puts instrução divisão do quociente de um registo eo restante em outro.

Se a sua instrução de divisão não é rápido o suficiente, mas a instrução de multiplicação é, você pode usar a seguinte técnica (e soa como se esta é a técnica que você está depois). Na maioria das arquitecturas, multiplicando-se um número de 32 bits por outro número de 32 bits resulta em um resultado de 64 bits; a metade mais significativo é armazenado em um registo ea metade menos significativa é armazenado na outra. É possível explorar esta por perceber que a divisão por um número n é o mesmo que multiplicar por (2 ^ 32) / N, em seguida, tomando os mais significativos bits de 32 o resultado. Em outras palavras, se você quiser dividir por 3, você pode em vez multiplicar por 0x100000000 / 3 = 0x55555555, em seguida, tomar as mais significativas 32 bits do resultado.

O que você está fazendo aqui é realmente uma forma de aritmética de ponto fixo. Dê uma olhada na Wikipedia artigo para obter mais informações.

Answer 2

A divisão de um número inteiro por um número inteiro constante pode ser substituído com uma combinação de um deslocamento e uma multiplicação. Consulte essa otimização guia para mais detalhes. De cource isto é útil se for actully mais rápido no chip de interesse.

Answer 3

Estou assumindo, com base na tag micro-controlador, você não tem uma divisão inteira rápido. Minha resposta é também para valores não assinados -. Ele vai trabalhar para valores assinados, você só tem que limitar os números utilizados no pouco complicado abaixo

Um bom começo é dividir por 2, 4 e 8. Estes podem ser feitos com as mudanças certas de 1, 2 e 3 bits, respectivamente, assumindo que o seu CPU tem uma instrução de deslocamento para a direita lógico.

Em segundo lugar, dividindo por 1 é apenas manter o número como está. Isso só folhas, 3, 5, 6, 7 e 9.

pouco complicado começa aqui:

Para os outros números, você pode usar o fato de que uma divisão pode ser substituído por um-e-shift multiplicar.

Vamos dizer que você tem um processador de 16-bit. Para dividir por N, você multiplicar por 256 / N e deslocamento para a direita 8 bits:

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

Tomemos o exemplo aleatório de 72 / 5. Multiplicar 72 por 51 para obter 3672, em seguida, deslocamento para a direita 8 bits para obter 14.

Para que isso funcione, os números que você está usando não devem transbordar os 16 bits. Desde o seu pior caso é multiplicar-by-85, você pode lidar com números até 771.

A razão isto funciona é porque um shift-direito de 8 bits é o mesmo que dividir por 256, e:

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

Se você tem um processador de 32 bits, os valores e os intervalos mudar um pouco, já que é 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.

Mais uma vez, vamos escolher o aleatório 20.000 / 7:. 20.000 multiplicado por 9363 é 187.260.000 e, quando deslocamento para a direita que 16 bits, você começa 2857 - o resultado real é 2.857

O seguinte programa de teste em C mostra os números de precisão para os valores indicados. Ele usa valores assinados por isso só é bom até cerca de 98.000, mas você pode ver que o maior erro é de 1 e que ocorre no ponto baixo de 13.110 (erro somente 0,008%).

#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;
}

Esta saídas:

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