Dans l’arithmétique entière en C #, est-ce que a / b / c est toujours égal à / (b * c)?

Soit a, b et c des entiers positifs non grands. Est-ce que / b / c est toujours égal à / (b * c) avec l’arithmétique entière C #? Pour moi, en C #, ça ressemble à:

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

Donc ma question est: est-ce que x1 == x2 pour tous les a, b et c?

Soit \ indique la division entière (l’opérateur C # / entre deux int s) et laisse / dénote la division mathématique habituelle. Alors, si x,y,z sont des entiers positifs et que nous ignorons le débordement ,

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

 a \ b = floor(a / b) 

Le saut de la ligne [1] à la ligne [2] ci-dessus est expliqué comme suit. Supposons que vous ayez deux entiers a et b et un nombre fractionnaire f dans l’intervalle [0, 1) . Il est simple de voir que

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

Si dans la ligne [1] vous identifiez a = floor(x / y) , f = (x / y) - floor(x / y) , et b = z , alors [3] implique que [1] et [2] sont égaux.

Vous pouvez généraliser cette preuve à des entiers négatifs ( ignorant toujours le dépassement de capacité ), mais je vais laisser cela au lecteur pour garder le point simple.


Sur la question du débordement – voir la réponse d’Eric Lippert pour une bonne explication! Il prend également une approche beaucoup plus rigoureuse dans son article et répond, ce que vous devriez examiner si vous pensez que je suis trop agité.

J’ai tellement aimé cette question que j’en ai fait le sujet de mon blog le 4 juin 2013 . Merci pour la bonne question!


Les grosses caisses sont faciles à trouver. Par exemple:

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

car b * c déborde vers un nombre négatif.

J’appendais à cela que dans l’ arithmétique cochée , la différence entre a / (b * c) et (a / b) / c peut être la différence entre un programme qui fonctionne et un programme qui plante. Si le produit de b et de c dépasse les limites d’un entier, le premier se bloquera dans un contexte vérifié.

Pour les petits nombres entiers positifs, disons suffisamment petits pour tenir dans un court, l’identité doit être maintenue.


Timothy Shields vient de poster une preuve; Je présente ici une preuve alternative. Supposez que tous les nombres ici sont des entiers non négatifs et qu’aucune des opérations ne déborde.

La division entière de x / y trouve la valeur q telle que q * y + r == x , où 0 <= r < y .

Donc la division a / (b * c) trouve la valeur q1 telle que

 q1 * b * c + r1 == a 

0 <= r1 < b * c

la division ( a / b ) / c trouve d'abord la valeur qt telle que

 qt * b + r3 == a 

puis trouve la valeur q2 telle que

 q2 * c + r2 == qt 

Alors remplacez cela par qt et nous obtenons:

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

0 <= r2 < c et 0 <= r3 < b .

Deux choses égales sont les mêmes, nous avons donc

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

Supposons que q1 == q2 + x pour un entier x . Remplacez cela par et résolvez pour x :

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

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

Est-ce que x peut être supérieur à zéro? Non, nous avons les inégalités:

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

Donc, le numérateur de cette fraction est toujours inférieur à b * c , donc x ne peut pas être supérieur à zéro.

Est-ce que x peut être inférieur à zéro? Non, par un argument similaire, laissé au lecteur.

Par conséquent, l'entier x est zéro, et donc q1 == q2 .

Si les valeurs absolues de b et de c sont inférieures à environ sqrt(2^31) (environ 46 300), de sorte que b * c ne débordera jamais, les valeurs correspondent toujours. Si b * c déborde, une erreur peut être générée dans un contexte checked ou vous pouvez obtenir une valeur incorrecte dans un contexte unchecked .

En évitant les erreurs de débordement constatées par les autres, elles correspondent toujours.

Supposons que a/b=q1 , ce qui signifie que a=b*q1+r1 , où 0<=r1 .
Supposons maintenant que a/b/c=q2 , ce qui signifie que q1=c*q2+r2 , où 0<=r2 .
Cela signifie que a=b(c*q2+r2)+r1=b*c*q2+br2+r1 .
Pour a/(b*c)=a/b/c=q2 , il faut avoir 0<=b*r2+r1 .
Mais b*r2+r1 , comme requirejs, et les deux opérations correspondent.

Cela ne fonctionne pas si b ou c sont négatifs, mais je ne sais pas non plus comment fonctionne la division entière.

Je vais offrir ma propre preuve pour le plaisir. Cela ignore également le débordement et ne gère malheureusement que les positifs, mais je pense que la preuve est claire et nette.

Le but est de montrer que

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

/ est la division normale (tout au long de cette preuve).

Nous représentons le quotient et le rest de a/b uniquement comme a = kb + r (par ce que nous voulons dire que k,r sont uniques et notons aussi |r| < |b| ). Ensuite nous avons:

 (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 

Notre objective est donc simplement de montrer que k1 == k2 . Eh bien, nous avons:

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

Et ainsi:

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

Observez maintenant de (2) que r1 est un entier (pour k1*z est un entier par définition) et r1 < z (aussi par définition). De plus, de (1) nous soaps que r < y => r/y < 1 . Considérons maintenant la sum r1 + r/y de (4). L’allégation est que r1 + r/y < z et cela ressort clairement des revendications précédentes (parce que 0 <= r1 < z et r1 est un entier, donc nous avons 0 <= r1 <= z-1 . Donc 0 <= r1 + r/y < z ). Donc r1 + r/y = r2 par définition de r2 (sinon il y aurait deux rests de x/y qui contredisent la définition du rest). Nous avons donc:

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

et nous avons la conclusion que k1 = k2 .

La preuve ci-dessus devrait fonctionner avec des négatifs, à l'exception de quelques étapes dont vous aurez besoin pour vérifier un cas supplémentaire ... mais je n'ai pas vérifié.

contre-exemple: INT_MIN / -1 / 2