Multiplicación de módulo (en C)

Question

Específicamente: Tengo dos enteros sin signo (a, b) y deseo calcular (a * b)% UINT_MAX (UINT_MAX se define como el int sin signo máximo). ¿Cual es la mejor manera de hacerlo?

Antecedentes: necesito escribir un módulo para Linux que emule una secuencia geométrica, leer de él me dará el siguiente elemento (módulo UINT_MAX), la única solución que encontré es agregar el elemento actual a los tiempos, mientras que la adición se realiza utilizando la siguiente lógica:. (que utilizo para la secuencia aritmética)

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

cuando Current_Value = a en la primera iteración (y se actualiza en cada iteración, y la diferencia = a (siempre) Obviamente, esta no es una solución inteligente. ¿Cómo lo lograría una persona inteligente?

¡Gracias!

Answer 1

Como se ha mencionado, si usted tiene un tipo de dos veces la anchura disponible, sólo tiene que utilizar que, aquí

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

si int es de 32 bits y long long 64 (o más). Si no tiene un tipo más grande, puede dividir los factores a la mitad del ancho del bit, multiplicar y reducir las partes, finalmente ensamblarlo. Ilustrado para 32 bits sin signo aquí:

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. 

Por supuesto, si lo que necesita es en realidad la reducción de módulo UINT_MAX + 1, como supone @Toad, entonces eso es justamente lo que hace la multiplicación de unsigned int.

Answer 2

EDITAR: Como se señala en los comentarios ... esta respuesta se aplica al Módulo MAX_INT + 1 Lo dejo aquí, para referencia futura.

Es mucho más que eso simpeler:

sólo multiplica los dos enteros sin signo, el resultado será también un entero sin signo. Todo lo que no encajaba en la int sin firmar básicamente no está allí. Así que no hay necesidad de hacer una operación de módulo:

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

respuesta es: 0x20000000 (por lo que debería haber sido 0x120000000, pero la respuesta ha sido truncado, justo lo que queríamos con la operación de módulo)