3.5. Алгоритми прискореного ділення (111)

Алгоритми прискореного ділення, як і алгоритми прискореного множення, розділяють на логічні, апаратні й комбіновані.

Один з простих логічних алгоритмів прискореного ділення для двійкової системи числення, нормалізованого дільника й використання прямих кодів для подання операндів складається з аналізу знакових і старшого числового розряду остачі. Ідея прискорення ґрунтується на наступних міркуваннях.

Припустимо, що чергова остача Ri=0.00. У цьому випадку чергове число частки zi =1, тоді треба виконувати зрушення вмісту РХ та PZ. Якщо після зсуву виявиться, що 2Ri=00,0..., то це значить, що далі треба виконувати віднімання дільника, причому остача R_i+1 буде свідомо від’ємною, тому що дільник нормалізований (Y=00,1...), а z_i+1=0. Однак, якщо свідомо відомий знак R_i+1 і число частки z_i+1, то в такій ситуації віднімання можна не виконувати, а після формування числа z_i+1 переходити до зсувів. Якщо після зсуву виявиться, що 2R_i+1,=4R_i =00,0..., то можна стверджувати, що R_i+2<0 і z_i+2=0 і т.д. Аналогічно міркуючи відносно остачі R_i =11,1...при z_i =0 можна показати, що при всіх наступних подвоєних залишках виду 11,1... (тобто, коли, 2R_i = 11,1…, 2R_i+1,=4R_i =11,1...) додавання можно не виконувати, числа частки z_i+1, z_i+2 і т.д. при цьому рівні 1. ГСА такого прискореного ділення наведена на рис.11.

Складемо числову діаграму ділення X=208/256 на Y=221/256 за алгоритмом на рис.11. (табл.5, де Х=0,11010000, Y=0,11011101, (-Y)ДК =1,00100011).

Таблиця 11

РХ	PY	PZ	СТШ	Пояснення
00,11010000	00,11011101	000000000	0000	Початковий стан
11.00100011				-Y
11,11110011		z0		R0
11,11100110		0	0001	Зсув
11,11001100		01	0010	Зсув
11,10011000		011	0011	Зсув
11,00110000		0111	0100	Зсув
00,11011101				+Y
00,00001101				r4
00,00011010		01111	0101	Зсув
00,00110100		011110	0110	Зсув
00,01101000		0111100	0111	Зсув
00,11010000		01111000	1000	Зсув
11.00100011				-Y
11,11110011				Rs
11,11100110		011110000	1001	Зсув
11,11001100		111100001	1010	Зсув

Продовження додатку

Рис.11.

41