В целочисленной арифметике C# всегда ли A/b/C равен a / (b*c)?

мне так понравился этот вопрос, что я сделал его предметом мой блог от 4 июня 2013 года. Спасибо за отличный вопрос!

---

большие случаи легко найти. Например:

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

, потому что b * c перетекает в отрицательное число.

я бы добавил к этому тот факт, что в проверил арифметические, разница между a / (b * c) и (a / b) / c может быть разница между программой, которая работает и программа, которая выходит из строя. Если произведение b и c переполняет границы целого числа, то первый будет сбой в проверенном контексте.

для малых положительных целых чисел, скажем, достаточно малых, чтобы вписаться в короткий, идентичность должна быть сохранена.

---

Тимоти Шилдс только что опубликовал доказательство; я представляю здесь альтернативное доказательство. Предположим, что все числа здесь являются неотрицательными целыми числами и ни одна из операций переполнения.

целое число деление x / y находит значение q такое, что q * y + r == x, где 0 <= r < y.

отдел a / (b * c) находит значение q1 такое, что

q1 * b * c + r1 == a

здесь 0 <= r1 < b * c

отдела ( a / b ) / c сначала находит значение qt такое, что

qt * b + r3 == a

и затем находит значение q2 такое, что

q2 * c + r2 == qt

так замените это на qt и мы получаем:

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

здесь 0 <= r2 < c и 0 <= r3 < b.

две вещи, равные одному и тому же, равны друг другу, поэтому мы имеем

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

предположим q1 == q2 + x для некоторого целого числа x. Замените это и решите для 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

можете x быть больше нуля? Нет. У нас есть неравенства:

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

значит числитель этой дроби всегда меньше b * c, так что x не может быть больше, чем нуль.

можете x быть меньше нуля? Нет, по аналогичной аргументации, оставленной читателю.

поэтому целое число x равно нулю, а значит q1 == q2.

если абсолютные значения b и c ниже о sqrt(2^31) (прим. 46 300), так что b * c никогда не будет переполнения, значения всегда будут совпадать. Если b * c переполнения, то ошибка может быть брошена в checked контекст, или вы можете получить неверные значения в unchecked контексте.

избегая ошибок переполнения, замеченных другими, они всегда совпадают.

предположим, что a/b=q1, Что означает a=b*q1+r1, где 0<=r1<b.
Теперь предположим, что a/b/c=q2, что означает q1=c*q2+r2, где 0<=r2<c.
Это значит, что a=b(c*q2+r2)+r1=b*c*q2+br2+r1.
Для того, чтобы a/(b*c)=a/b/c=q2, мы должны иметь 0<=b*r2+r1<b*c.
Но b*r2+r1<b*r2+b=b*(r2+1)<=b*c, как требовалось, и две операции совпадают.

это не работает, если b или c отрицательные, но я не знайте, как целочисленное деление работает и в этом случае.

я предложу свое собственное доказательство для удовольствия. Это также игнорирует переполнение и, к сожалению, обрабатывает только положительные стороны, но я думаю, что доказательство чисто и ясно.

цель состоит в том, чтобы показать, что

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

здесь / является нормальным делением (во всем этом доказательстве).

мы представляем частное и остаток a/bоднозначно как a = kb + r (под этим мы подразумеваем, что k,r уникальны, а также Примечание |r| < |b|). Тогда мы есть:

(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

так что наша цель-просто показать, что k1 == k2. Ну у нас есть:

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

и так:

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

теперь заметьте из (2), что r1 - целое число (для k1*z является целым числом по определению) и r1 < z (также по определению). Кроме того, из (1) мы знаем, что r < y => r/y < 1. Теперь рассмотрим сумму r1 + r/y из (4). Претензия заключается в том, что r1 + r/y < z и это ясно из предыдущих утверждений (потому что 0 <= r1 < z и r1 является целым числом так у нас есть 0 <= r1 <= z-1. Поэтому 0 <= r1 + r/y < z). Таким образом r1 + r/y = r2 по определению r2 (иначе было бы два остатки от x/y что противоречит определению остатка). Следовательно, мы имеем:

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

и у нас есть наш желаемый вывод, что k1 = k2.

приведенное выше доказательство должно работать с негативами, за исключением нескольких шагов, которые вам нужно будет проверить в дополнительном случае(ах)... но я не стал проверять.

счетчик пример: INT_MIN / -1 / 2