При каких условиях для целых чисел a и b выражение (a/b) в целочисленном делении можно заменить на округление к ближайшему целому без изменения результата в дальнейших алгебраических преобразованиях, и приведи примеры, где это приводит к ошибке
Коротко: всё зависит от остатка при делении. Принятие эквивалентно тогда и только тогда, когда дробная часть ab\frac{a}{b}ba меньше 12\tfrac1221 по модулю (и в случае ровной половины — когда правило округления совпадает с выбранным целочисленным делением). Более формально (предположим сначала b>0b>0b>0 и целочисленное деление — это округление вниз, a÷b=⌊a/b⌋a\div b=\lfloor a/b\rfloora÷b=⌊a/b⌋). Пусть q=⌊a/b⌋,r=a−bq,0≤r<b.
q=\lfloor a/b\rfloor,\qquad r=a-bq,\qquad 0\le r<b. q=⌊a/b⌋,r=a−bq,0≤r<b.
Тогда округление до ближайшего (правило «round half-up»: round(x)=⌊x+1/2⌋\mathrm{round}(x)=\lfloor x+1/2\rfloorround(x)=⌊x+1/2⌋) даёт то же значение, что и ⌊a/b⌋\lfloor a/b\rfloor⌊a/b⌋ тогда и только тогда, когда r<b2.
r<\tfrac{b}{2}. r<2b.
Если r>b2r>\tfrac{b}{2}r>2b, то round(a/b)=q+1\mathrm{round}(a/b)=q+1round(a/b)=q+1. При r=b2r=\tfrac{b}{2}r=2b зависит от правила обработки полуцелых (tie): при «half-up» округление даст q+1q+1q+1, при «round-to-even» — возможно qqq. Если целочисленное деление в вашей системе делает усечение к нулю (как в C/C++ для отрицательных чисел), то условие записывают через модуль остатка: для записи a=bq+ra=bq+ra=bq+r с ∣r∣<∣b∣|r|<|b|∣r∣<∣b∣ замена на округление безопасна, когда ∣r∣<∣b∣/2|r|<|b|/2∣r∣<∣b∣/2; при ∣r∣=∣b∣/2|r|=|b|/2∣r∣=∣b∣/2 — снова зависит от правила округления и от того, как устроено целочисленное деление. Примеры, где замена приводит к ошибке: - a=3, b=2a=3,\; b=2a=3,b=2: ⌊3/2⌋=1\lfloor 3/2\rfloor=1⌊3/2⌋=1, а round(3/2)=2\mathrm{round}(3/2)=2round(3/2)=2 (поскольку остаток r=1≥b/2=1r=1\ge b/2=1r=1≥b/2=1). - a=5, b=2a=5,\; b=2a=5,b=2: ⌊5/2⌋=2\lfloor 5/2\rfloor=2⌊5/2⌋=2, round(5/2)=3\mathrm{round}(5/2)=3round(5/2)=3. - При отрицательных: в языках с усечением к нулю a=−3, b=2a=-3,\; b=2a=−3,b=2: целочисленное деление даёт −1-1−1, а округление round(−1.5)=−2\mathrm{round}(-1.5)=-2round(−1.5)=−2 — различие. - Точная полуцелая ситуация: a=3, b=2a=3,\; b=2a=3,b=2 (см. первый пример) или a=6, b=4a=6,\; b=4a=6,b=4 — здесь r=b/2r=b/2r=b/2, и итог зависит от правила «половинок». Вывод: можно безопасно заменить только если известно, что остаток удовлетворяет r<∣b∣/2r<|b|/2r<∣b∣/2 (и при равенстве — что правило округления совпадает с поведением используемого целочисленного деления).
Более формально (предположим сначала b>0b>0b>0 и целочисленное деление — это округление вниз, a÷b=⌊a/b⌋a\div b=\lfloor a/b\rfloora÷b=⌊a/b⌋). Пусть
q=⌊a/b⌋,r=a−bq,0≤r<b. q=\lfloor a/b\rfloor,\qquad r=a-bq,\qquad 0\le r<b.
q=⌊a/b⌋,r=a−bq,0≤r<b. Тогда округление до ближайшего (правило «round half-up»: round(x)=⌊x+1/2⌋\mathrm{round}(x)=\lfloor x+1/2\rfloorround(x)=⌊x+1/2⌋) даёт то же значение, что и ⌊a/b⌋\lfloor a/b\rfloor⌊a/b⌋ тогда и только тогда, когда
r<b2. r<\tfrac{b}{2}.
r<2b . Если r>b2r>\tfrac{b}{2}r>2b , то round(a/b)=q+1\mathrm{round}(a/b)=q+1round(a/b)=q+1. При r=b2r=\tfrac{b}{2}r=2b зависит от правила обработки полуцелых (tie): при «half-up» округление даст q+1q+1q+1, при «round-to-even» — возможно qqq.
Если целочисленное деление в вашей системе делает усечение к нулю (как в C/C++ для отрицательных чисел), то условие записывают через модуль остатка: для записи a=bq+ra=bq+ra=bq+r с ∣r∣<∣b∣|r|<|b|∣r∣<∣b∣ замена на округление безопасна, когда ∣r∣<∣b∣/2|r|<|b|/2∣r∣<∣b∣/2; при ∣r∣=∣b∣/2|r|=|b|/2∣r∣=∣b∣/2 — снова зависит от правила округления и от того, как устроено целочисленное деление.
Примеры, где замена приводит к ошибке:
- a=3, b=2a=3,\; b=2a=3,b=2: ⌊3/2⌋=1\lfloor 3/2\rfloor=1⌊3/2⌋=1, а round(3/2)=2\mathrm{round}(3/2)=2round(3/2)=2 (поскольку остаток r=1≥b/2=1r=1\ge b/2=1r=1≥b/2=1).
- a=5, b=2a=5,\; b=2a=5,b=2: ⌊5/2⌋=2\lfloor 5/2\rfloor=2⌊5/2⌋=2, round(5/2)=3\mathrm{round}(5/2)=3round(5/2)=3.
- При отрицательных: в языках с усечением к нулю a=−3, b=2a=-3,\; b=2a=−3,b=2: целочисленное деление даёт −1-1−1, а округление round(−1.5)=−2\mathrm{round}(-1.5)=-2round(−1.5)=−2 — различие.
- Точная полуцелая ситуация: a=3, b=2a=3,\; b=2a=3,b=2 (см. первый пример) или a=6, b=4a=6,\; b=4a=6,b=4 — здесь r=b/2r=b/2r=b/2, и итог зависит от правила «половинок».
Вывод: можно безопасно заменить только если известно, что остаток удовлетворяет r<∣b∣/2r<|b|/2r<∣b∣/2 (и при равенстве — что правило округления совпадает с поведением используемого целочисленного деления).