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

81

Sean a, byc números enteros positivos no grandes. ¿A / b / c siempre es igual a a / (b * c) con aritmética de números enteros de C #? Para mí, en C # se ve así:

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

Entonces mi pregunta es: ¿ x1 == x2para todo a, by c?

Jason Crease
fuente
3
Esta es una pregunta de matemáticas, no de programación. ¿Puede explicar cuál es la parte específica de programación de esta pregunta?
Oded
38
@Oded en el alcance de cualquier número racional, claro, pero esto se refiere específicamente a la aritmética de enteros (en C #). En mi opinión, eso lo hace relacionado con la programación. Quizás la regla que a / b / c == a / (b * c) se cumple en aritmética de números enteros, quizás solo se cumple en aritmética de números racionales.
Tim S.
43
Esta es una pregunta perfectamente razonable sobre C # y fácil de responder.
Eric Lippert
12
@Oded Esta es una pregunta sobre la aritmética informática y si se comporta igual que la matemática pura. No debe estar cerrado.
Jeffrey Sax
4
Me interesaría bastante una prueba matemática de por qué (o de hecho si), ignorando los desbordamientos, los dos son de hecho equivalentes, pero todavía no he logrado armar uno.
Rawling

Respuestas:

71

Dejar que \denotan división entera (C # /operador entre dos ints) y dejar que /denotan división matemática habitual. Entonces, si x,y,zson 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 una línea [1]a otra [2]se explica a continuación. Suponga que tiene dos números enteros ay by un número fraccionario fen el rango [0, 1). Es sencillo ver que

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

Si de acuerdo [1]a identificar a = floor(x / y), f = (x / y) - floor(x / y)y b = z, a continuación, [3]implica que [1]y [2]son iguales.

Puede generalizar esta prueba a enteros negativos (aún ignorando el desbordamiento ), pero se lo dejo al lector para que sea sencillo.


Sobre el tema del desbordamiento , consulte la respuesta de Eric Lippert para obtener una buena explicación. También adopta un enfoque mucho más riguroso en la publicación y la respuesta de su blog , algo que deberías considerar si sientes que estoy siendo demasiado ondulante.

Timothy Shields
fuente
1
Ja, eso es lo que
buscaba
Me gusta su uso de \ y / para esto. Deja las cosas mucho más claras.
Justin Morgan
@JustinMorgan La notación se usa en algunos otros lenguajes de programación (aunque no recuerdo cuáles en este momento).
Timothy Shields
1
@TimothyShields VB.net lo hace.
Arie Xiao
Creo que la afirmación es cierta, pero parece que a tu prueba le falta un paso clave. Es posible que no haya entendido bien su justificación para la línea 2 => línea 3. La forma en que lo interpreté floor(x / y) - (x / y)es pequeña, z >= 1por lo que tomando el valor floorde eso es 0 y podemos ignorarlo. Eso en realidad no sigue, ya que en realidad es un sumando dentro de un floor()(es decir, considerar floor(1/2)vs floor(1/2 + 1/2)).
rliu
77

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


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

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

porque se b * cdesborda a un número negativo.

Yo agregaría a eso el hecho de que en aritmética comprobada , la diferencia entre a / (b * c)y (a / b) / cpuede ser la diferencia entre un programa que funciona y un programa que falla. Si el producto de by cdesborda 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, se debe mantener la identidad.


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

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

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

q1 * b * c + r1 == a

dónde 0 <= r1 < b * c

la división ( a / b ) / cprimero encuentra el valor qttal que

qt * b + r3 == a

y luego encuentra el valor q2tal que

q2 * c + r2 == qt

Así que sustituye eso por qty obtenemos:

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

donde 0 <= r2 < cy 0 <= r3 < b.

Dos cosas iguales son iguales entre sí, así que tenemos

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

Supongamos q1 == q2 + xpor algún número entero x. Sustituye eso 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 xser 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 es siempre menor que b * c, por xlo que no puede ser mayor que cero.

¿Puede xser menor que cero? No, por argumento similar, se deja al lector.

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

Eric Lippert
fuente
7
@JoseRuiSantos sí, pero tanto la operación x1 como la x2operación fallarán de manera idéntica en ese caso
Marc Gravell
@JoseRuiSantos, ¿eso no es cierto en ambos casos?
Jodrell
La respuesta de vc 74 se ha eliminado, por lo que la mayoría de las personas ya no pueden ver el ejemplo al que hace referencia.
Gabe
Eso es correcto, ambos x1y x2fallarán si bo cson cero. Para otros valores, la x1expresión es mejor, ya que evitará el posible desbordamiento de enteros ( b * c)que x2tiene.
Jose Rui Santos
Un punto interesante sobre los desbordamientos y la aritmética comprobada, ¡gracias!
Jason Crease
4

Si los valores absolutos de by cestán por debajo de aproximadamente sqrt(2^31)(aprox. 46 300), por lo que b * cnunca se desbordará, los valores siempre coincidirán. Si se b * cdesborda, se puede arrojar un error en un checkedcontexto o se puede obtener un valor incorrecto en un uncheckedcontexto.

Tim S.
fuente
2

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

Supongamos eso a/b=q1, lo que significa eso a=b*q1+r1, dónde 0<=r1<b.
Ahora suponga eso a/b/c=q2, lo que significa eso q1=c*q2+r2, dónde 0<=r2<c.
Esto significa eso a=b(c*q2+r2)+r1=b*c*q2+br2+r1.
Para 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 bo cson negativos, pero tampoco sé cómo funciona la división de enteros en ese caso.

Teepeemm
fuente
0

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

El objetivo es demostrar que

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

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

Representamos el cociente y el resto de a/b únicamente como a = kb + r(con eso queremos decir que k,rson únicos y también nota |r| < |b|). Entonces 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 simplemente mostrar eso 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 de (2) que r1es un número entero (porque k1*zes un número entero por definición) y r1 < z(también por definición). Además de (1) sabemos eso r < y => r/y < 1. Ahora considere la suma r1 + r/yde (4). La afirmación es que r1 + r/y < zy esto se desprende de las afirmaciones anteriores (porque 0 <= r1 < zy r1es un número entero, por lo que tenemos 0 <= r1 <= z-1. Por lo tanto 0 <= r1 + r/y < z). Así, r1 + r/y = r2por definición de r2(de lo contrario, habría dos residuos de los x/yque contradice la definición de residuo). Por tanto tenemos:

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

y tenemos la conclusión deseada de eso 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 (s) ... pero no lo verifiqué.

rliu
fuente
0

ejemplo de contador: INT_MIN / -1 / 2

hustwcw
fuente
"Sean a, byc no grandes números enteros positivos ".
Pang
Ese es un caso interesante (es decir, -INT_MIN es un desbordamiento). ¡Gracias!
Jason Crease