Напоминание: в случае технических проблем любого характера, вы можете использовать m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

Блог пользователя simp1eton

Does order of division matter in computer arithmetic?
Автор simp1eton, 13 лет назад, По-английски
Hi all, I would like to ask the following qn:

In a computer, will

x / (a * b * c * d * e)

give a different solution from

x / a / b / c / d / e

where x,a,b,c,d,e are all integer data types? Since values are rounded down, I was wondering if that would cost the 2nd method of division to reach a smaller value than the 1st method if too much rounding is done.

Intuitively, it seems that it should not matter, but I cannot really prove it. Can someone help me out? Thanks!
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Yes, it can give different results. There're several problems here:
  1. Overflow. If a = b = c = d = e = 109, a· b· c· d· e is really larger than maximal value of int. So, result is undefined
  2. Rounding together with negative numbers. For example, 3/2/-1=1/-1=-1, but 3/(2·(-1))=3/(-2)=-2
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    3/(-2) даёт -1, а не -2.
    Там идёт не округление вниз, а отброс дробной части.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Извиняюсь, проверял в питоне.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Хм, это интересный нюанс. Я сам в питоне не проверял, только С++.
        Интересно, зачем было в питоне делать иначе.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Очевидно, чтобы питон вёл себя по-математически предсказуемо.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Зато в C++ (-a)/b == -(a/b).
            → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Не совсем правда. В Java это действительно так. А вот в C++ — implementation defined, если только спецификация языка не изменилась, пока я спал.
              → Ответить
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                <irony/>
                Я все-таки не выдержу и спрошу. Вы действительно читаете спецификацию C++ перед сном?
                → Ответить
                • 13 лет назад, # ^ |
                    Проголосовать: нравится +6 Проголосовать: не нравится
                  В некотором смысле, все, что обычно делается не во время сна, делается перед сном)
                  → Ответить
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится +4 Проголосовать: не нравится
                    Во время сна тоже перед сном. Кроме самого последнего мгновения самого последнего сна :)
                    → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Это было чудно, когда в одном контесте на opencup я писал прогу на питоне и предусмотрел, что во всех известных мне компиляторах целочисленное деление сделано через криво. И я написал несколько строк для этого случая. Но нет, питон оказался умнее меня :).
            → Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Let x be (a*b*c*d*e)*q + r where r is remainder of the division x / (a*b*c*d*e).
Then x/a is (b*c*d*e)*q + [r/a], where [x] is rounding down of float value.
        x/a/b is (c*d*e)*q + [[r/a]/b]
        ...
        x/a/b/c/d/e is q+[[[[[r/a]/b]/c]/d]/e].
As r is strictly less than a*b*c*d*e, [[[[[r/a]/b]/c]/d]/e]=0.
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Yes, it can give different results. There're several problems here:
  1. Overflow. If a = b = c = d = e = 109, a· b· c· d· e is really larger than maximal value of int. So, result is undefined
  2. Rounding together with negative numbers. For example, 3/2/-1=1/-1=-1, but 3/(2·(-1))=3/(-2)=-2. UPD: it isn't correct in C/C++ (maybe Java), but correct in Python, because in C/C++ 3/(-2)=-1. Thanks to VladBelous
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Hi all,

Thanks for your comments. Actually, what I was asking is whether

floor(x / (a * b * c * d * e))

in normal arithmetic is the same as

x / a / b / c / d / e

in computer arithmetic.

But you have still managed to answer my question. Thanks everyone! So unless I am dealing with negative numbers in Python, this should work fine.
→ Ответить