Пусть 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?
c#
math
integer
integer-arithmetic
Джейсон Криз
источник
источник
Ответы:
Позвольте
\
обозначить целочисленное деление (/
оператор 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)
где
Переход от строки
[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]
равны.Вы можете обобщить это доказательство на отрицательные целые числа (все еще игнорируя переполнение ), но я оставлю это читателю для простоты.
По вопросу о переполнении - см. Ответ Эрика Липперта для хорошего объяснения! Он также использует гораздо более строгий подход в своем сообщении в блоге и ответах, на что вам следует обратить внимание, если вы чувствуете, что я слишком волнист.
источник
floor(x / y) - (x / y)
маленьким,z >= 1
поэтому, принимая значениеfloor
0, мы можем проигнорировать это. На самом деле этого не происходит, поскольку на самом деле это добавление вfloor()
(т.е. рассмотримfloor(1/2)
vsfloor(1/2 + 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
, чтогде
0 <= r1 < b * c
деление
( a / b ) / c
сначала находит такое значениеqt
, чтоа затем находит такое значение
q2
, чтоЗамените это на,
qt
и мы получим:где
0 <= r2 < c
и0 <= r3 < b
.Две одинаковые вещи равны друг другу, поэтому имеем
Предположим
q1 == q2 + x
для некоторого целого числаx
. Подставьте это и решите дляx
:где
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
.источник
x1
иx2
операция будет врезаться тождественно в этом случаеx1
иx2
будут вылетать, еслиb
илиc
равны нулю. Для других значений, тоx1
выражение лучше, так как будет избежать возможного целочисленного переполнения ,( b * c)
чтоx2
есть.Если абсолютные значения
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
которых противоречит определение остатка). Следовательно, мы имеем:и у нас есть желаемый вывод
k1 = k2
.Приведенное выше доказательство должно работать с негативами, за исключением пары шагов, которые вам понадобятся для проверки дополнительных случаев ... но я не проверял.
источник
пример счетчика: INT_MIN / -1 / 2
источник