Moltiplicazione modulo (in C)

Question

In particolare: ho due interi senza segno (a, b) e voglio calcolare (a * b)% UINT_MAX (UINT_MAX è definito come int max senza segno). Qual è il modo migliore per farlo?

Sfondo: Ho bisogno di scrivere un modulo per linux che emuli una sequenza geometrica, leggendo da esso mi darà l'elemento successivo (modulo UINT_MAX), l'unica soluzione che ho trovato è quella di aggiungere l'elemento corrente a se stesso volte, mentre l'aggiunta avviene utilizzando la seguente logica:. (che uso per la sequenza aritmetica)

for(int i=0; i<b; ++i){ 
    if(UINT_MAX - current_value > difference) { 
    current_value += difference; 
    } else { 
    current_value = difference - (UINT_MAX - current_value); 
    } 

quando Current_Value = a nella prima iterazione (e viene aggiornato ad ogni iterazione, e la differenza = a (sempre) Ovviamente questa non è una soluzione intelligente Come potrebbe raggiungere una persona intelligente?

Grazie!

Answer 1

Come è stato detto, se si dispone di un tipo di due volte la larghezza disponibile, basta usare quello, qui

(unsigned int)(((unsigned long long)a * b) % UINT_MAX) 

se int è 32 bit e long long 64 (o più). Se non si dispone di un tipo più grande, è possibile suddividere i fattori a metà larghezza del bit, moltiplicare e ridurre le parti, infine assemblarlo. Illustrato a 32 bit senza segno qui:

a_low = a & 0xFFFF; // low 16 bits of a 
a_high = a >> 16; // high 16 bits of a, shifted in low half 
b_low = b & 0xFFFF; 
b_high = b >> 16; 
/* 
* Now a = (a_high * 65536 + a_low), b = (b_high * 65536 + b_low) 
* Thus a*b = (a_high * b_high) * 65536 * 65536 
*   + (a_high * b_low + a_low * b_high) * 65536 
*   + a_low * b_low 
* 
* All products a_i * b_j are at most (65536 - 1) * (65536 - 1) = UINT_MAX - 2 * 65536 + 2 
* The high product reduces to 
* (a_high * b_high) * (UINT_MAX + 1) = (a_high * b_high) 
* The middle products are a bit trickier, but splitting again solves: 
* m1 = a_high * b_low; 
* m1_low = m1 & 0xFFFF; 
* m1_high = m1 >> 16; 
* Then m1 * 65536 = m1_high * (UINT_MAX + 1) + m1_low * 65536 = m1_high + m1_low * 65536 
* Similar for a_low * b_high 
* Finally, add the parts and take care of overflow 
*/ 
m1 = a_high * b_low; 
m2 = a_low * b_high; 
m1_low = m1 & 0xFFFF; 
m1_high = m1 >> 16; 
m2_low = m2 & 0xFFFF; 
m2_high = m2 >> 16; 
result = a_high * b_high; 
temp = result + ((m1_low << 16) | m1_high); 
if (temp < result) // overflow 
{ 
    result = temp+1; 
} 
else 
{ 
    result = temp; 
} 
if (result == UINT_MAX) 
{ 
    result = 0; 
} 
// I'm too lazy to type out the rest, you get the gist, I suppose. 

Naturalmente, se quello che vi serve è in realtà modulo riduzione UINT_MAX + 1, come assume @Toad, allora questo è proprio quello che la moltiplicazione di unsigned int fa.

Answer 2

MODIFICA: Come indicato nei commenti ... questa risposta vale per Modulo MAX_INT + 1 Lascerò qui in piedi, per riferimento futuro.

E 'molto più di quello simpeler:

Basta moltiplicare i due unsigned int, il risultato sarà anche un unsigned int. Fondamentalmente, tutto ciò che non rientrava nell'int unsigned non esiste. Quindi nessun bisogno di fare un'operazione di modulo:

See example here

#include <stdio.h> 

void main() 
{ 
    unsigned int a,b; 
    a = 0x90000000; 
    b = 2; 

    unsigned int c = a*b; 

    printf("Answer is %X\r\n", c); 
} 

risposta è: 0x20000000 (così avrebbe dovuto essere 0x120000000, ma la risposta è stata troncata, proprio quello che si voleva, con l'operazione di modulo)