Moltiplicazione rapida

Question

Sto scrivendo il codice per un microprocessore con aritmetica a numero intero veloce e non così veloce aritmetica float. Devo dividere un numero intero per un numero compreso tra 1 e 9 e riconvertire il risultato in numero intero.

Ho creato un array float con membri come 0, 1, 0,5, 0,3333 ecc. Ma penso che ci siano costanti MAGIC (come 0x55555556) per un numero tranne (1/3).

Che cosa sono questi numeri?

Answer 1

Se l'istruzione di divisione sul microcontrollore è abbastanza veloce, usala. Se hai bisogno della parte frazionaria del risultato, potresti essere in grado di usare il resto; sulla maggior parte delle architetture, l'istruzione di divisione inserisce il quoziente in un registro e il resto in un altro.

Se l'istruzione di divisione non è abbastanza veloce ma l'istruzione di moltiplicazione è, è possibile utilizzare la seguente tecnica (e sembra che questa sia la tecnica che stai cercando). Sulla maggior parte delle architetture, la moltiplicazione di un numero a 32 bit per un altro numero a 32 bit produce un risultato a 64 bit; la metà più significativa viene archiviata in un registro e la metà meno significativa viene archiviata nell'altro. Puoi sfruttarlo realizzando che la divisione per un numero n equivale a moltiplicare per (2 ^ 32) / n, quindi prendere i 32 bit più significativi del risultato. In altre parole, se vuoi dividere per 3, puoi invece moltiplicare per 0x100000000 / 3 = 0x55555555, quindi prendere i 32 bit più significativi del risultato.

Quello che stai facendo qui è davvero una forma di aritmetica a virgola fissa. Dai un'occhiata all ' articolo di Wikipedia per maggiori informazioni.

Answer 2

Una divisione di un numero intero per una costante intera può essere sostituita con una combinazione di uno spostamento e una moltiplicazione. Vedi questa guida di ottimizzazione per i dettagli. Di certo questo è utile se è effettivamente più veloce sul chip di interesse.

Answer 3

Suppongo che, in base al tag del microcontrollore, non si abbia una divisione intera veloce. La mia risposta è anche per i valori senza segno: funzionerà per i valori con segno, devi solo limitare i numeri usati nel bit complicato di seguito.

Un buon inizio è dividere per 2, 4 e 8. Questi possono essere fatti con spostamenti a destra di 1, 2 e 3 bit rispettivamente, supponendo che la CPU abbia un'istruzione logica di spostamento a destra.

In secondo luogo, la divisione per 1 sta semplicemente mantenendo il numero così com'è. Rimangono solo 3, 5, 6, 7 e 9.

Il bit complicato inizia qui:

Per gli altri numeri, puoi usare il fatto che una divisione può essere sostituita da un moltiplicare e spostare.

Supponiamo che tu abbia un processore a 16 bit. Per dividere per N, si moltiplica per 256 / N e si sposta a destra di 8 bit:

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

Prendi l'esempio casuale di 72 / 5. Moltiplica 72 per 51 per ottenere 3672, quindi sposta a destra di 8 bit per ottenere 14.

Affinché ciò funzioni, i tuoi numeri che stai utilizzando non devono superare i 16 bit. Poiché il tuo caso peggiore è moltiplicare per 85, puoi gestire numeri fino a 771.

Il motivo per cui funziona è perché un turno-destra di 8 bit è uguale alla divisione per 256 e:

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

Se si dispone di un processore a 32 bit, i valori e gli intervalli cambiano leggermente, poiché è 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.

Ancora una volta, scegliamo il 20.000 / 7: 20.000 casuale moltiplicato per 9.363 è 187.260.000 e, quando si sposta correttamente quei 16 bit, si ottengono 2.857 - il risultato reale è 2.857.

Il seguente programma di test in C mostra le cifre di accuratezza per i valori indicati. Utilizza valori con segno, quindi va bene solo fino a circa 98.000, ma puoi vedere che l'errore più grande è 1 e che si verifica nel punto più basso di 13.110 (solo errore 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;
}

Questo output:

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