Пусть a, b и c - не большие положительные целые числа. Всегда ли a/b/c равен a/(b * c) с С# целочисленной арифметикой? Для меня в С# это выглядит так:
int a = 5126, b = 76, c = 14;
int x1 = a / b / c;
int x2 = a / (b * c);
Итак, мой вопрос: делает x1 == x2 для всех a, b и c?
Пусть \ обозначает целочисленное деление (оператор С# / между двумя 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] равны.
Вы можете обобщить это доказательство на отрицательные целые числа (все еще игнорирование переполнения), но я оставлю это для чтения, чтобы точка была простой.
В вопросе переполнения - см. ответ Эрика Липперта за хорошее объяснение! Он также берет гораздо более строгий подход в своем сообщении в блоге и отвечает, что-то, на что вы должны обратить внимание, если чувствуете, что я слишком волнительный.
Мне так понравился этот вопрос, я сделал его предметом моего блога 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