Целочисленное деление без восстановления остатка

Алгоритм без восстановления остатка разработаем, опираясь на рассмотренный алгоритм с восстановлением остатка.

Пусть после шага 4.1 алгоритма 6.5 имеем текущее значения остатка A_i, делитель B_i и очередная цифра частного равна 0, что означает необходимость выполнения шага восстановления остатка. При этих условиях заметим особенности последующих шагов выполнения алгоритма.

1. Восстановление остатка связано с выполнением операции

A_i+1:= A_i + B_i. (6.15)

 

2. Операции B:=R1(0· B) и D:= R1(1· D) шага 4.5 алгоритма приводят к уменьшению значения делителя в 2 раза. То есть, на этом шаге

B_i+1:= B_i / 2 (6.16)

 

3. На следующем цикле вычисления очередной цифры частного новое значение остатка на шаге 4.1 алгоритма будет вычисляться следующим образом:

A_i+2:= A_i+1 - B_i+1. (6.17)

 

Подставим в (1.50) выражения из (1.48) и (1.49):

A_i+2:= A_i + B_i - B_i / 2. (6.18)

 

Получим:

A_i+2 = A_i + B_i / 2= A_i + B_i+1. (6.19)

 

Таким образом, выражение (6.19) показывает, что очередное значение остатка A_i+2 может быть вычислено на основе остатка A_i без использования промежуточного значения A_i+1, то есть без выполнения шага восстановления остатка. С учетом этих наблюдений, модифицируем алгоритм 6.5.

Алгоритм 6.6. Целочисленноеделение без восстановления остатка со сдвигом делителя вправо.

Постановку задачи и обозначения примем как в алгоритме 6.5.

1. Подготовка переменных:

1.1. C:= 0 (- задание начального значения кода частного)

1.2. i:= 0 (- задание начального значения величины сдвига делителя)

1.3. p:= 1 (- подготовка условий для первого уменьшения делимого)

2. Начальный сдвиг кода делителя

2.1. Если b_n-1 =0, топерейти к 2.2, иначеперейти к 3

2.2. Сдвиг кода делителя влево на 1 разряд с целью удаления из РС делителя незначащего нуля:

B:= L1(B· 0); (- сдвиг кода делителя влево на 1 разряд)

i:= i+1; (- код делителя сдвинут влево еще на один разряд)

2.3. Перейти к 2.1

3. D:= nota(B)+1; (- формирование цифровой части от (-B)^ДК)

4. Цикл формирования кода частного:

4.1. Если p = 0, то A:= A+B (- это увеличение остатка);

иначе A:= A+D (- это уменьшение остатка);

(При суммировании кодов в обоих случаях фиксируем значение переноса p из старшего разряда разрядной сетки)

4.2. C:= L1(C· p)

4.3. Сдвиг кодов B и D делителя вправо на 1 разряд:

B:= R1(0· B); D:= R1(1· D)

4.4. Если i = 0, топерейти к 5

4.5. i:= i -1

4.6. Перейти к 4.1

5. Конец алгоритма (Код C задает искомый результат: A div B)

---

Дата добавления: 2016-01-04; просмотров: 11; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!