Dans l'arithmétique des nombres entiers C #, a / b / c est-il toujours égal à a / (b * c)?

Question

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

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

Ma question est donc la suivante: est-ce que x1 == x2 pour tous a, b et c?

Answer 1

J'ai aimé cette question tellement j'en ai fait le sujet de mon blog sur 4 juin 2013. Merci pour la grande question!

---

Grand cas sont faciles à trouver. Par exemple:

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

parce qu' b * c déborde à un nombre négatif.

Je voudrais ajouter à cela le fait que, dans coché l'arithmétique, 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 se bloque. Si le produit de l' b et c déborde les limites d'un entier puis l'ancien va se planter dans un activée contexte.

Pour les petits nombres entiers positifs, disons, assez petit pour tenir dans une bref, l'identité doit être maintenue.

---

Timothy Boucliers vient de poster une preuve; je vous présente ici une autre preuve. Supposons que tous les chiffres ici sont des entiers non négatifs et aucun des opérations dépassement de capacité.

Division entière de x / y trouve la valeur q tels que q * y + r == xoù 0 <= r < y.

De sorte que la division a / (b * c) trouve la valeur q1 tels que

q1 * b * c + r1 == a

où 0 <= r1 < b * c

la division de l' ( a / b ) / c trouve d'abord la valeur qt tels que

qt * b + r3 == a

et puis trouve la valeur q2 tels que

q2 * c + r2 == qt

Donc un substitut pour qt et nous obtenons:

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

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

De deux choses égales à la même chose sont égales les unes aux autres, de sorte que nous avons

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

Supposons q1 == q2 + x pour certains entiers x. Substitut et résoudre x:

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

où

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

Peut - x être supérieure à zéro? Pas de. Nous avons les inégalités:

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

Si le numérateur de cette fraction est toujours plus petit que b * c, alors x ne peut pas être supérieure à zéro.

Peut - x inférieur à zéro? Non, par le même raisonnement, à gauche pour le lecteur.

Donc entier x est égal à zéro, et par conséquent q1 == q2.

Answer 2

Laissez - \ désigner la division entière (le C# / opérateur entre deux ints) et laissez - / désigner l'habitude de mathématiques de la division. Alors, si x,y,z sont des entiers positifs et nous sommes ignorant de débordement,

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

où

a \ b = floor(a / b)

Le saut de ligne, [1] ligne [2] ci-dessus s'explique comme suit. Supposons que vous avez deux entiers a et b et un nombre fractionnaire f dans la gamme [0, 1). Il est facile de voir que

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

Si en ligne, [1] vous identifier a = floor(x / y), f = (x / y) - floor(x / y), et b = z, alors [3] implique qu' [1] et [2] sont égaux.

Vous pouvez généraliser cette preuve, de nombres entiers négatifs (encore ignorant de débordement), mais je vais laisser ça pour le lecteur à garder le point simple.

---

Sur la question du dépassement de - voir Eric Lippert réponse à une bonne explication! Il prend aussi beaucoup plus de rigueur dans son billet de blog et de répondre, quelque chose que vous devriez regarder dans si vous pensez que je suis trop attrayante.

Answer 3

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

Answer 4

En évitant les erreurs de dépassement remarqué par d'autres, ils correspondent toujours.

Supposons qu' a/b=q1, ce qui signifie qu' a=b*q1+r1où 0<=r1<b.
Supposons maintenant que a/b/c=q2, ce qui signifie qu' q1=c*q2+r2où 0<=r2<c.
Cela signifie qu' a=b(c*q2+r2)+r1=b*c*q2+br2+r1.
Pour a/(b*c)=a/b/c=q2, nous avons besoin d' 0<=b*r2+r1<b*c.
Mais b*r2+r1<b*r2+b=b*(r2+1)<=b*c, tel que requis, et les deux opérations match.

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

Answer 5

Je vais offrir à mes propres éléments de preuve pour le plaisir. Cela ne tient pas compte de débordement et ne s'occupe que des points positifs malheureusement, mais je pense que la preuve est claire et propre.

L'objectif est de montrer que

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

où / est normal de division tout au long de cette preuve).

Nous représentons le quotient et le reste de l' a/b unique en tant que a = kb + r (c'est-à-dire qu' k,r sont uniques et également note |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

Donc notre but est simplement de montrer qu' k1 == k2. Eh bien, nous avons:

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

et donc:

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

Maintenant observer à partir de (2) r1 est un entier ( k1*z est un nombre entier par définition) et r1 < z (par définition). En outre, à partir de (1) nous savons que l' r < y => r/y < 1. Considérons maintenant la somme r1 + r/y de (4). La demande est que l' r1 + r/y < z et cela est évident à partir de la précédente revendications (parce qu' 0 <= r1 < z et r1 est un entier nous avons donc 0 <= r1 <= z-1. Par conséquent, 0 <= r1 + r/y < z). Ainsi, r1 + r/y = r2 , par définition, r2 (sinon il y aurait deux des restes de x/y ce qui contredit la définition de reste). Nous avons donc:

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

et nous avons notre conclusion désirée qu' k1 = k2.

Le dessus de la preuve devrait travailler avec les négatifs à l'exception de quelques étapes que vous auriez besoin de vérifier un cas additionnel(s)... mais je n'ai pas vérifier.