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

Ответ 1

Пусть \ обозначает целочисленное деление (оператор С# / между двумя int s), а / обозначает обычное математическое деление. Тогда, если x,y,z положительные целые числа, и мы игнорируем переполнение,

(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)

Переход от строки [1] к строке [2] выше объясняется следующим образом. Предположим, что у вас есть два целых числа a и b и дробное число f в диапазоне [0, 1). Нетрудно видеть, что

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

Если в строке [1] вы идентифицируете a = floor(x / y), f = (x / y) - floor(x / y) и b = z, то [3] означает, что [1] и [2] равны.

Вы можете обобщить это доказательство на отрицательные целые числа (все еще игнорирование переполнения), но я оставлю это для чтения, чтобы точка была простой.

В вопросе переполнения - см. ответ Эрика Липперта за хорошее объяснение! Он также берет гораздо более строгий подход в своем сообщении в блоге и отвечает, что-то, на что вы должны обратить внимание, если чувствуете, что я слишком волнительный.

Ответ 2

Мне так понравился этот вопрос, я сделал его предметом моего блога 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.

Ответ 3

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

Ответ 4

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

Предположим, что 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 являются отрицательными, но я не знаю, как работает целочисленное деление в этом случае.

Ответ 5

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

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

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.

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

Ответ 6

встречный пример: INT_MIN/-1/2