Cómo ejecutar [(A * B) mod C] sin desbordamiento, si A y B son menores que C

Puede usar Divide & Conquer para encontrar (A * B)% C. A continuación se muestra el código en C ++.

#include
using namespace std;
long long mulmod(long long a,long long b,long long c) {
if (a == 0 || b == 0)
return 0;
if (a == 1)
return b;
if (b == 1)
return a;
long long a2 = mulmod(a, b / 2, c);
if ((b & 1) == 0)
{
return (a2 + a2) % c;
}
else
{
return ((a % c) + (a2 + a2)) % c;
}
}
int main() {
long long a,b,c;
cin>>a>>b>>c;
cout << mulmod(a,b,c) < return 0;
}


Si [math] (C-1) ^ 2 [/ math] no desborda el límite de entero largo largo sin signo, simplemente puede calcular la solución en tiempo constante.

De lo contrario, tendrá que usar la multiplicación campesina rusa ( http://en.wikipedia.org/wiki/Anc …) para encontrar la solución.

Aquí está mi implementación:

unsigned long long russianPeasant(unsigned long long a, unsigned long long b, unsigned long long c) {
unsigned long long ret=0;

mientras que (b) {
si (b & 1) {
ret + = a;
ret% = c;
}
a * = 2;
a% = c;
b / = 2;
}

volver ret;
}

La respuesta de Dana Jacobsen es realmente buena.

Sin embargo, no evita completamente el desbordamiento. Aquí hay una versión similar, que evita el desbordamiento:

static uint64_t slowModulo (uint64_t A, uint64_t B, uint64_t C)
{
uint64_t r = 0;
uint64_t C_down = C >> 1;
uint64_t C_up = C – C_down;
mientras que (B> 0)
{
si (B & 1)
r = ((r> = C- A)
? (A> = C_up? A – C_up + r: r – C_up + A) – C_down
: r + A);
si (A> = C_up)
A = (A-C_down) + (A-C_up);
más
A = A + A;

B >> = 1;
}
volver r;
}

Tenga en cuenta que evitar el desbordamiento aquí no es útil, porque en C ++ el desbordamiento en tipos sin signo simplemente se envuelve, y el código de Dana produce el mismo resultado. Con suerte, gcc produce el mismo código para ambos. Todavía es un buen ejercicio mental para deshacerse de todos los desbordamientos.

También probé una optimización, que elimina tantos bits de B como sea posible en cada iteración del bucle. Sin embargo, resulta que no es notablemente más rápido, incluso cuando se utiliza la función incorporada gcc “contar los ceros iniciales” (clz). Sin embargo, el código está abajo:

static long fastModulo (uint64_t A, uint64_t B, uint64_t C, uint64_t stepSize)
{
uint64_t mask = (1 << stepSize) - 1;
uint64_t r = 0;

mientras que (B> 0)
{
r + = A * (B y máscara);
r% = C;

A << = stepSize;
B >> = tamaño de paso;
A% = C;
}
volver r;
}

estático uint64_t bigModulo (uint64_t A, uint64_t B, uint64_t C)
{
afirmar (C> A);
afirmar (C> B);
if ((A | B) <(1ULL << 32))
retorno (A * B)% C;
if (A

int stepSize = __builtin_clz ((uint32_t) (C >> 32));
if (stepSize == 0)
return slowModulo (A, B, C);
return fastModulo (A, B, C, stepSize);
}

Me parece que puedes calcular la cantidad de bits que cada número tomaría para almacenar. Súmelos y reste uno. Esa es la cantidad de bits que se necesitarían para almacenar el resultado. Verifique ese valor en comparación con su tamaño de almacenamiento más grande y antes de realizar la operación, sabrá si la multiplicación se desbordará. Si desea que A & B sea absolutamente arbitrariamente grande, deberá cambiar a una versión BCD con memoria asignada para almacenar los números BCD pero, en primer lugar, A & B no son un tipo de datos interno.

Si estás atrapado en un mundo entero (como sospecho que es este problema de tarea), necesitarás un poco de contador. Aquí hay uno simple:

int
num_of_bits_unsigned(long long int i) {
int bits=1;
if(!i)
return(0);
while((i = i >> 1) > 0)
bits++;
return(bits);
}


Dejaré descubrir cómo manejar enteros firmados y el resto del problema.

Es posible calcular la multiplicación sin división utilizando operaciones de bit o búsqueda de tabla. En general, solo he visto operaciones de bits utilizadas para campos finitos muy pequeños (GF (2) o GF (3)), y las tablas explotan rápidamente y nunca las he visto utilizadas en código de alto rendimiento.

Usar plus en lugar de multi, pero solo usar plus puede ser demasiado lento, así que pruebe binary plus como el algoritmo de potencia binaria.
ej .: 3 * 5 escribe 5 como código binario 101, entonces 3 * 5 = 3 * 2 ^ 0 + 3 * 2 ^ 2.