В поисках теории на следующий трюк уклонения от переполнения - PullRequest
Новая
       46

В поисках теории на следующий трюк уклонения от переполнения

0 голосов
/ 07 мая 2019

В следующем коде используется некий целочисленный метод предотвращения переполнения, который я пытаюсь понять: 

// x,y,z are positive numbers
boolean check(long x, long y, long z) {
  return x >= (z+y-1)/y;
}

Исходя из определения проблемы, я предполагаю, что фактическое намерение для кода: 

return x*y >= z;

Похоже, что автор избегает целочисленного переполнения следующим образом: 

1. x*y >= z
2. x >= z / y //Divide both sides by y
3. x - 1 >= (z - 1) / y //Subtract 1 from left side and dividend
4. x >= (z - 1) / y + 1 //Move 1 to the right side
5. x >= (z + y - 1) / y //Place 1 inside the brackets

Точка 3 - это то, что я пытаюсь понять.

Второе неравенство не совпадает с исходным намерением (например, x = 10, y = 10, z = 101), но третья точка служит обходным путем (основываясь на моих тестах).

Можете ли выпожалуйста, объясните теорию, стоящую за этим?

1 Ответ

0 голосов
/ 07 мая 2019

Проблема в том, что используется целочисленное деление.

  • x * y> = z
  • x> = z / ((double) y)

Или целое переполнение было бы для

  • x> = ceil (z / ((double) y))

, что с целочисленным делением (усечениеостаток)

  • x> = (z + y - 1) / y

Или сформулировать иначе: given z = m*y + n, where 0 <= n < y, тогда для n == 0 деление выше будетукажите m, в противном случае m+1, предельное значение.Ниже невозможно переполнение для x.

...