Деление с остатком. Метод итераций.

Рассмотрим задачу деления числа на число с остатком. Представим b в виде ( выбирается так, чтобы минимизировать отношение ). В качестве приближенного частного можно взять . Остаток от деления удовлетворяет соотношениям . Если отношение , то получаем следующий итеративный процесс деления.

1. Положим r=a, v=0

2. Вычислим , v=v+u, r=r-bu. Перейдем на шаг 3.

3. Если , то перейдем на шаг 4, иначе вернемся на шаг 2.

4. Если r<0, то положим v=v–sign(b), и r=r+|b|. Алгоритм работу закончил, частное равно v, а остаток r.

Число итераций алгоритма равно , где .

Выбор осуществляется так, чтобы можно легко проводить деление на шаге 2. Например, можно положить . В этом случае (если используем «обычную» позиционную систему счисления, в сокращенной системе счисления ) Операция деления на шаге 2 может выполняться процедурой DivCnst с последующим отбрасыванием n-1 разряда. Для величины справедливы неравенства (или в «сокращенной» системе счисления ). Число итераций алгоритма определяется величиной старшего разряда делителя. Чем она больше, тем меньше количество итераций. Для увеличения используют ускоряющий множитель. Перед делением делимое и делитель умножают на число (в сокращенной системе на число ). В результате, гарантировано, что старший разряд, нового делимого не меньше p/2. А число итераций алгоритма пропорционально m-n+1. Таким образом, общая трудоемкость алгоритма деления методом «итераций» пропорциональна .

В случае малого p, можно положить . При таком выборе гарантируется неравенство (для сокращенной системы ). Единственное ограничение, величина должна убираться в ячейку памяти.

Приведем программу деления Div числа A на B с остатком (длина числа B больше 1) без уточнения остатка (шаг 4).

procedure Div(A,B,Part,Rest);

Begin

Rest.last:=A.last;SetEmpty(Part);

t:=B.last;n:=0;

while t^.next B.last do {t:=t^.next;n:=n+1}

beta:=t^.info+p*t^.next^.info;

Repeat

DivCnst(U,Rest,beta);i:=1;

while (i<n)and(u.last<>nil) do {i:=i+1;Del(U,U.last)}

Add(S,Part,U);{список Part можно удалить}

Part.last:=S.last;

Mult(S,B,U);Sub(S1,Rest,S);{списки S,Rest можно удалить}

Rest.last:=S1.last;

until U.last=nil; );{список U можно удалить}

end;