Dividere la moltiplicazione di numeri interi

Ho bisogno di un algoritmo che utilizza due interi a 32 bit come parametri e restituisce la moltiplicazione di questi parametri divisi in altri due numeri interi a 32 bit: parte 32-bit più alta e parte 32-bit più basso.

Proverei:

uint32_t p1, p2; // globals to hold the result void mult(uint32_t x, uint32_t y){ uint64_t r = (x * y); p1 = r >> 32; p2 = r & 0xFFFFFFFF; } 

Sebbene funzioni 1 , non è garantita l’esistenza di numeri interi a 64 bit nella macchina, né l’utilizzo da parte loro del compilatore.

Quindi, qual è il modo migliore per risolverlo?


Nota 1 : In realtà, non ha funzionato perché il mio compilatore non supporta gli interi a 64 bit.

Obs : per favore, evita di usare boost .

Basta usare cifre a 16 bit.

 void multiply(uint32_t a, uint32_t b, uint32_t* h, uint32_t* l) { uint32_t const base = 0x10000; uint32_t al = a%base, ah = a/base, bl = b%base, bh = b/base; *l = al*bl; *h = ah*bh; uint32_t rlh = *l/base + al*bh; *h += rlh/base; rlh = rlh%base + ah*bl; *h += rlh/base; *l = (rlh%base)*base + *l%base; } 

Come ho commentato, puoi trattare ogni numero come una stringa binaria di lunghezza 32.

Basta moltiplicare questi numeri usando l’aritmetica scolastica. Otterrai una stringa lunga 64 caratteri.

Quindi basta dividerlo.

Se si desidera una moltiplicazione rapida, è ansible esaminare l’algoritmo di moltiplicazione di Karatsuba .

Questa è la spiegazione e l’implementazione dell’algoritmo di Karatsubas . Ho scaricato il codice e l’ho eseguito più volte. Sembra che stia andando bene. È ansible modificare il codice in base alle proprie esigenze.

Se il tipo unsigned long è supportato, questo dovrebbe funzionare:

 void umult32(uint32 a, uint32 b, uint32* c, uint32* d) { unsigned long long x = ((unsigned long long)a)* ((unsigned long long)b); //Thanks to @Толя *c = x&0xffffffff; *d = (x >> 32) & 0xffffffff; } 

Logica presa in prestito da qui .