redondear - math.round c#

En la aritmética de enteros de C#, ¿a/b/c siempre es igual a/(b*c)?

Question

Deje a, byc ser enteros positivos no grandes. ¿A / b / c siempre es igual a / (b * c) con la aritmética de enteros de C #? Para mí, en C # parece:

int a = 5126, b = 76, c = 14;
int x1 = a / b / c;
int x2 = a / (b * c);

Entonces mi pregunta es: ¿ x1 == x2 para todo a, byc?

Answer 1

Deje / denote la división entera (el operador C # / entre dos int s) y deje / denote la división matemática habitual. Entonces, si x,y,z son enteros positivos y estamos ignorando el desbordamiento ,

(x / y) / z
= floor(floor(x / y) / z) [1]
= floor((x / y) / z) [2]
= floor(x / (y * z))
= x / (y * z)

dónde

a / b = floor(a / b)

El salto de la línea [1] a la línea [2] anterior se explica de la siguiente manera. Supongamos que tiene dos enteros b y un número fraccionario f en el rango [0, 1) . Es sencillo ver eso

floor(a / b) = floor((a + f) / b) [3]

Si en la línea [1] identifica a = floor(x / y) , f = (x / y) - floor(x / y) , y b = z , entonces [3] implica que [1] y [2] son iguales.

Puede generalizar esta prueba en enteros negativos (aún ignorando el desbordamiento ), pero le dejaré eso al lector para mantener el punto simple.

Sobre el problema del desbordamiento : ¡vea la respuesta de Eric Lippert para una buena explicación! También adopta un enfoque mucho más riguroso en su publicación de blog y responde, algo que debería considerar si siente que estoy demasiado ondulado.

Answer 2

Evitando los errores de desbordamiento notados por otros, siempre coinciden.

Supongamos que a/b=q1 , lo que significa que a=b*q1+r1 , donde 0<=r1<b .
Ahora supongamos que a/b/c=q2 , lo que significa que q1=c*q2+r2 , donde 0<=r2<c .
Esto significa que a=b(c*q2+r2)+r1=b*c*q2+br2+r1 .
Para que a/(b*c)=a/b/c=q2 , necesitamos tener 0<=b*r2+r1<b*c .
Pero b*r2+r1<b*r2+b=b*(r2+1)<=b*c , según sea necesario, y las dos operaciones coinciden.

Esto no funciona si b c son negativos, pero tampoco sé cómo funciona la división de enteros en ese caso.

Answer 3

Me gustó tanto esta pregunta que la convertí en tema de mi blog el 4 de junio de 2013 . Gracias por la gran pregunta!

Los casos grandes son fáciles de conseguir. Por ejemplo:

a = 1073741823;
b = 134217727;
c = 134217727;

porque b * c desborda a un número negativo.

Agregaría a eso el hecho de que en la aritmética controlada , la diferencia entre a / (b * c) y (a / b) / c puede ser la diferencia entre un programa que funciona y un programa que falla. Si el producto de c rebasa los límites de un entero, el primero se bloqueará en un contexto verificado.

Para pequeños enteros positivos, digamos, lo suficientemente pequeños como para caber en un corto, la identidad debe mantenerse.

Timothy Shields acaba de publicar una prueba; Presento aquí una prueba alternativa. Suponga que todos los números aquí son enteros no negativos y ninguna de las operaciones se desborda.

La división entera de x / y encuentra el valor q tal que q * y + r == x , donde 0 <= r < y .

Entonces la división a / (b * c) encuentra el valor q1 tal que

q1 * b * c + r1 == a

donde 0 <= r1 < b * c

la división ( a / b ) / c primero encuentra el valor qt tal que

qt * b + r3 == a

y luego encuentra el valor q2 tal que

q2 * c + r2 == qt

Entonces sustitúyalo por qt y obtenemos:

q2 * b * c + b * r2 + r3 == a

donde 0 <= r2 < c y 0 <= r3 < b .

Dos cosas iguales son iguales, por lo que tenemos

q1 * b * c + r1 == q2 * b * c + b * r2 + r3

Supongamos q1 == q2 + x para un entero x . Sustituye eso en y resuelve para x :

q2 * b * c + x * b * c + r1 = q2 * b * c + b * r2 + r3
x = (b * r2 + r3 - r1) / (b * c)

dónde

 0 <= r1 < b * c
0 <= r2 < c
0 <= r3 < b

¿Puede x ser mayor que cero? No. Tenemos las desigualdades:

 b * r2 + r3 - r1 <= b * r2 + r3 <= b * (c - 1) + r3 < b * (c - 1) + b == b * c

Entonces, el numerador de esa fracción siempre es más pequeño que b * c , por lo que x no puede ser mayor que cero.

¿Puede x ser menor que cero? No, por un argumento similar, dejado al lector.

Por lo tanto, el entero x es cero, y por lo tanto q1 == q2 .

Answer 4

Ofreceré mi propia prueba por diversión. Esto también ignora el desbordamiento y solo maneja aspectos positivos desafortunadamente, pero creo que la prueba es clara y clara.

El objetivo es mostrar que

floor(floor(x/y)/z) = floor(x/y/z)

donde / es división normal (a lo largo de esta prueba).

Representamos el cociente y el resto de a/b únicamente como a = kb + r (con esto queremos decir que k,r es único y también nota |r| < |b| ). Entonces nosotros tenemos:

(1) floor(x/y) = k => x = ky + r
(2) floor(floor(x/y)/r) = k1 => floor(x/y) = k1*z + r1
(3) floor(x/y/z) = k2 => x/y = k2*z + r2

Entonces, nuestro objetivo es solo mostrar que k1 == k2 . Bueno, tenemos:

k1*z + r1 = floor(x/y) = k = (x-r)/y (from lines 1 and 2)
=> x/y - r/y = k1*z + r1 => x/y = k1*z + r1 + r/y

y por lo tanto:

(4) x/y = k1*z + r1 + r/y (from above)
x/y = k2*z + r2 (from line 3)

Ahora observe desde (2) que r1 es un número entero (para k1*z es un número entero por definición) y r1 < z (también por definición). Además de (1) sabemos que r < y => r/y < 1 . Ahora considere la suma r1 + r/y de (4). La afirmación es que r1 + r/y < z y esto está claro en las reivindicaciones anteriores (porque 0 <= r1 < z y r1 es un número entero, por lo que tenemos 0 <= r1 <= z-1 . Por lo tanto, 0 <= r1 + r/y < z ). Por lo tanto r1 + r/y = r2 por definición de r2 (de lo contrario habría dos residuos de x/y que contradice la definición de residuo). Por lo tanto, tenemos:

x/y = k1*z + r2
x/y = k2*z + r2

y tenemos nuestra conclusión deseada de que k1 = k2 .

La prueba anterior debería funcionar con negativos, excepto por un par de pasos que necesitaría para verificar un caso (s) adicional ... pero no lo revisé.

Answer 5

Si los valores absolutos de c están por debajo de sqrt(2^31) (aproximadamente 46 300), de modo que b * c nunca se desbordará, los valores siempre coincidirán. Si b * c desborda, se puede lanzar un error en un contexto checked , o puede obtener un valor incorrecto en un contexto unchecked .

Answer 6

contador de ejemplo: INT_MIN / -1 / 2