Можно доказать, что верно следующее:
c = floor((a+b/2)/b)
a = a - c*b
Обратите внимание, что floor означает округление вниз, к отрицательной бесконечности: не к 0. (Например, floor (-3.1) = - 4. Это будут делать библиотечные функции floor(); просто убедитесь, что не просто приведен к int, что вместо этого обычно округляется к 0.)
Предположительно b является строго положительным, потому что в противном случае ни один цикл никогда не прекратится: добавление b не увеличит a, а вычитание b не сделает a меньшим. С этим предположением мы можем доказать, что приведенный выше код работает. (И код paranoidgeek также почти правильный, за исключением того, что он использует приведение к int вместо floor.)
Умный способ доказать это :
Код добавляет или вычитает кратные b от a до a в [-b/2,b/2), которые можно просмотреть как сложение или вычитание целых чисел из a/b до a/b в [-1/2,1/2), то есть до (a/b+1/2) (назовите его x) в [0,1). Поскольку вы меняете его только целыми числами, значение x не меняется mod 1, то есть оно переходит к его модулю остатка 1 , который равен x-floor(x). Таким образом, эффективное количество вычитаний, которое вы делаете (c), составляет floor(x).
Утомительный способ доказать это :
В конце первого цикла значение c является отрицательным числом выполненных циклов, т. Е .:
- 0, если: a> -b / 2 <=> a + b / 2> 0
- -1, если: -b / 2 ≥ a> -3b / 2 <=> 0 ≥ a + b / 2> -b <=> 0 ≥ x> -1
- -2, если: -3b / 2 ≥ a> -5b / 2 <=> -b ≥ a + b / 2> -2b <=> -1 ≥ x> -2 и т. Д.,
где x = (a+b/2)/b, поэтому c равно: 0, если x> 0, и «потолок (x) -1» в противном случае. Если первый цикл вообще выполнялся, то это было ≤ -b / 2 как раз перед тем, как последний раз цикл был выполнен, так что теперь это ≤ -b / 2 + b, то есть ≤ b / 2. В зависимости от того, является ли оно точно b / 2 или нет (т. Е. Было ли x, когда вы начинали, было точно неположительным целым числом или нет), второй цикл выполняется ровно 1 раз или 0, и c является либо потолком (x) или потолок (х) -1. Так что это решает проблему для случая, когда первый цикл действительно работал.
Если первый цикл не выполнялся, то значение c в конце второго цикла:
- 0, если: a a-b / 2 <0 </li>
1, если: b / 2 ≤ a <3b / 2 <=> 0 ≤ a-b / 2 0 ≤ y <1 </li>
2, если: 3b / 2 ≤ a <5b / 2 <=> b ≤ a-b / 2 <2b <=> 1 ≤ y <2 и т. Д., </li>
, где y = (a-b/2)/b, поэтому c равно 0, если y <0, и 1 + floor (y) в противном случае. [И <code>a сейчас, безусловно,
Таким образом, вы можете написать выражение для c как:
x = (a+b/2)/b
y = (a-b/2)/b
c = (x≤0)*(ceiling(x) - 1 + (x is integer))
+(y≥0)*(1 + floor(y))
Конечно, затем вы заметите, что (ceiling(x)-1+(x is integer)) совпадает с floor(x+1)-1, что составляет floor(x), и что y на самом деле x-1, то есть (1+floor(y))=floor(x), и что касается условных выражений:
когда x≤0, это не может быть (y≥0), поэтому c - это только первый член, который равен floor(x),
когда 0 c равно 0,
когда 1 ≤ x, то только 0≤y, так что c - это просто второй член, который снова равен floor(x).
Так что с = floor(x) во всех случаях.