161 votos

Cómo evitar desbordamiento en expr. A * B - C * D

Necesito calcular una expresión que se parece a: A*B - C*D, donde sus tipos son: signed long long int A, B, C, D; Cada número puede ser muy grande (no se desborde de su tipo). Mientras A*B podría provocar un desbordamiento, al mismo tiempo que la expresión A*B - C*D puede ser muy pequeña. ¿Cómo puedo calcular correctamente?

Por ejemplo: MAX * MAX - (MAX - 1) * (MAX + 1) == 1donde MAX = LLONG_MAX - n y n - algún número natural.

120voto

Anirudh Ramanathan Puntos 25113

Esto parece demasiado trivial, supongo. Pero A*B es la que podría desbordarse.

Se podría hacer lo siguiente, sin perder la precisión

A*B - C*D = A(D+E) - (A+F)D
          = AD + AE - AD - DF
          = AE - DF
             ^smaller quantities E & F

E = B - D (hence, far smaller than B)
F = C - A (hence, far smaller than C)

Esta descomposición se puede hacer más.
@Gian señalado, la atención podría ser necesario tomar durante la operación de resta si el tipo unsigned long long.


Por ejemplo, con el caso que tiene en la pregunta, se necesita sólo una iteración,

 MAX * MAX - (MAX - 1) * (MAX + 1)
  A     B       C           D

E = B - D = -1
F = C - A = -1

AE - DF = {MAX * -1} - {(MAX + 1) * -1} = -MAX + MAX + 1 = 1

68voto

Ofir Puntos 5760

La forma más simple y más general de la solución es el uso de una representación que no se desborde, ya sea mediante el uso de un entero largo biblioteca (por ejemplo, http://gmplib.org/) o la que representa el uso de una estructura o matriz y la implementación de un tipo de multiplicación larga (es decir, la separación de cada número en dos mitades de 32 bits y la realización de la multiplicación de la siguiente manera:

(R1 + R2 * 2^32 + R3 * 2^64 + R4 * 2^96) = R = A*B = (A1 + A2 * 2^32) * (B1 + B2 * 2^32) 
R1 = (A1*B1) % 2^32
R2 = ((A1*B1) / 2^32 + (A1*B2) % 2^32 + (A2*B1) % 2^32) % 2^32
R3 = (((A1*B1) / 2^32 + (A1*B2) % 2^32 + (A2*B1) % 2^32) / 2^32 + (A1*B2) / 2^32 + (A2*B1) / 2^32 + (A2*B2) % 2^32) %2^32
R4 = ((((A1*B1) / 2^32 + (A1*B2) % 2^32 + (A2*B1) % 2^32) / 2^32 + (A1*B2) / 2^32 + (A2*B1) / 2^32 + (A2*B2) % 2^32) / 2^32) + (A2*B2) / 2^32

Suponiendo que el resultado final se ajusta en 64 bits que en realidad no necesitamos realmente la mayoría de los bits de R3 y ninguno de R4

46voto

RiaD Puntos 15744

Tenga en cuenta que esto no es estándar, ya que se basa en wrap-around firmado por desbordamiento. (CCG ha compilador de indicadores que permiten esto).

Pero si usted acaba de hacer todos los cálculos en long long, el resultado de aplicar directamente la fórmula:
(A * B - C * D) serán exactos mientras el resultado correcto encaja en long long.


He aquí una solución que sólo se basa en la aplicación definida por el comportamiento de fundición de entero a entero con signo. Pero esto se puede esperar que el trabajo en casi todos los sistemas de hoy en día.

(long long)((unsigned long long)A * B - (unsigned long long)C * D)

Esto arroja que las entradas unsigned long long donde el desbordamiento de comportamiento está garantizado de ser wrap-around por la norma. Casting de nuevo a un entero con signo, al final, es la aplicación definidos parte, pero funciona en casi todos los ambientes de hoy en día.


Si necesita más pedante solución, creo que tienes que usar "largo de la aritmética"

18voto

paquetp Puntos 1286

Esto debería funcionar ( creo ):

signed long long int a = 0x7ffffffffffffffd;
signed long long int b = 0x7ffffffffffffffd;
signed long long int c = 0x7ffffffffffffffc;
signed long long int d = 0x7ffffffffffffffe;
signed long long int bd = b / d;
signed long long int bdmod = b % d;
signed long long int ca = c / a;
signed long long int camod = c % a;
signed long long int x = (bd - ca) * a * d - (camod * d - bdmod * a);

Aquí está mi derivación:

x = a * b - c * d
x / (a * d) = (a * b - c * d) / (a * d)
x / (a * d) = b / d - c / a

now, the integer/mod stuff:
x / (a * d) = (b / d + ( b % d ) / d) - (c / a + ( c % a ) / a )
x / (a * d) = (b / d - c / a) - ( ( c % a ) / a - ( b % d ) / d)
x = (b / d - c / a) * a * d - ( ( c % a ) * d - ( b % d ) * a)

9voto

Gian Puntos 9459

Usted podría considerar la posibilidad de calcular un factor común más grande de todos sus valores, y luego dividiendo por el que el factor antes de hacer sus operaciones aritméticas, luego multiplicando de nuevo. Esto supone que ese factor existe, sin embargo (por ejemplo, si A, B, C y D de pasar a ser relativamente primos, ellos no tienen un factor común).

Del mismo modo, usted podría considerar la posibilidad de trabajar en escalas de registro, pero esto va a ser un poco de miedo, sujeto a la precisión numérica.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X