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

81

Пусть a, b и c не большие положительные целые числа. Всегда ли a / b / c равно a / (b * c) с целочисленной арифметикой C #? Для меня в C # это выглядит так:

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

Итак, мой вопрос: подходит ли x1 == x2для всех a, b и c?

Джейсон Криз
источник
3
Это вопрос математики, а не программирования. Можете ли вы объяснить, какова конкретная часть этого вопроса, связанная с программированием?
Одед
38
@Oded в рамках любого рационального числа, конечно, но это конкретно относится к целочисленной арифметике (в C #). ИМО, что делает его связанным с программированием. Может быть, правило a / b / c == a / (b * c) выполняется в целочисленной арифметике, возможно, оно выполняется только в арифметике рациональных чисел.
Тим С.
43
Это вполне разумный вопрос о C #, на который легко ответить.
Эрик Липперт
12
@Oded Это вопрос о компьютерной арифметике и о том, ведет ли она себя так же, как чистая математика. Его не следует закрывать.
Джеффри Сакс
4
Мне было бы очень интересно математическое доказательство того, почему (или действительно ли), игнорируя переполнения, эти два фактически эквивалентны, но мне еще не удалось собрать одно вместе.
Rawling

Ответы:

71

Позвольте \обозначить целочисленное деление ( /оператор C # между двумя ints) и позвольте /обозначить обычное математическое деление. Тогда, если 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]равны.

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


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

Тимоти Шилдс
источник
1
Ха, вот что я
искал
Мне нравится, что вы для этого используете \ и /. Делает вещи намного более ясными.
Джастин Морган
@JustinMorgan Обозначения фактически используются в некоторых других языках программирования (хотя я не помню, какие из них на данный момент).
Тимоти Шилдс
1
@TimothyShields VB.net делает.
Ари Сяо
Я думаю, что утверждение верно, но в вашем доказательстве, похоже, отсутствует ключевой шаг. Возможно, я неправильно понял ваше обоснование для строки 2 => строка 3. То, как я истолковал это, было floor(x / y) - (x / y)маленьким, z >= 1поэтому, принимая значение floor0, мы можем проигнорировать это. На самом деле этого не происходит, поскольку на самом деле это добавление в floor()(т.е. рассмотрим floor(1/2)vs floor(1/2 + 1/2)).
rliu
77

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

Эрик Липперт
источник
7
@JoseRuiSantos да, но как x1 иx2 операция будет врезаться тождественно в этом случае
Marc Gravell
@JoseRuiSantos, разве это не так в обоих случаях?
Джодрелл
Ответ vc 74 был удален, поэтому большинство людей больше не могут видеть пример, на который вы ссылаетесь.
Гейб
Это правильно, оба x1и x2будут вылетать, если bили cравны нулю. Для других значений, то x1выражение лучше, так как будет избежать возможного целочисленного переполнения , ( b * c)что x2есть.
Хосе Руи Сантос
Интересный момент о переполнениях и проверенной арифметике, спасибо!
Джейсон Криз
4

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

Тим С.
источник
2

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

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

Teepeemm
источник
0

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

Цель - показать, что

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.

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

Rliu
источник
0

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

Hustwcw
источник
«Пусть a, b и c - не большие положительные целые числа».
Pang
Это интересный случай (т.е. -INT_MIN - переполнение). Благодаря!
Джейсон Криз