6.4.5. Ділення двійкових чисел

Ділення X:Yпередбачає визначення частки Qі залишку Rвідповідно до рівності

X= Q*Y+R,

де X- ділене, Y- дільник.

Алгоритм ділення в комп'ютерах виконується як послідовність операцій віднімання дільника Yвід часткового залишку Ri,початкове значення якого рівне значенню ділено­го X.Знаковий розряд частки визначається за знаками діленого і дільника аналогічно операції множення (табл. 6.7). Приймемо, що значення X і Y завжди відповідають вимозі X<Y.

Існує два варіанти виконання операції ділення двійкових чисел:

■ зі зсувом залишків ліворуч відповідно до рекурентної формули

При цьому і-й розряд частки визначається з ви-

разу q=NOT(p.);

■ зі зсувом дільника праворуч відповідно до рекурентної формули

і-й розряд частки, причому q. =SignR.

На n-му кроці ділення в обох випадках визначається значення n-го розряду частки і залишок.

223

Блок-схема алгоритму ділення за першим варіантом, який має ширше використанш наведена на рис. 6.22.

Ділення може бути виконано двома способами: з відновленням і без відновлення за­лишку.

При діленні з відновленням залишку послідовно віднімається дільник від діленого і проводиться аналіз значення поточного залишку. Якщо після чергового віднімання за­лишок позитивний, то відповідний розряд частки рівний одиниці. При від'ємному за­лишку розряд частки рівний нулю. В цьому випадку виконується коригуюче збільшення дільника до поточного залишку (відновлення залишку), він зсувається на один розряд ліворуч і процес повторюється. Обчислення проводяться за формулою першого варіан­ту, де q. = 1, якщо R. -Y>= 0 і q. = 0, якщо R. -Y<0. На рис. 6.23 наведено два перші яруси графа, описаного алгоритму ділення.

224

У методі ділення без відновлення залишку віднімання, що викликало появу від'єм­ного залишку при визначенні значення розряду частки, еквівалентне двом відніманням при визначенні сусіднього молодшого розряду частки. Ділення виконується за тим же співвідношенням зі зсувом залишків ліворуч відповідно до рекурентної формули

R1= 2(R_i-1 - p_iY),

де р_i = 1, якщо (R_i-1 - Y)> = 0, та р_i = -1, якщо (R_i-1- Y)< 0, R₀= X,і=1,2,...n. При цьому і-й розряд частки визначається з виразу q_i=SignR_i.

Ділення чисел, які представлені в оберненому та доповняльному кодах, можна ви­конувати за правилами ділення в прямих кодах при відповідному перетворенні операн-дів в цей код. Розглянемо виконання операції ділення без відновлення залишків чисел, представлених доповняльними кодами. У цьому випадку ділення зводиться до послідов­ності додавань і віднімань дільника від діленого, а потім часток і часткових залишків і їх зсуву на розряд ліворуч за наступними виразами:

R_i = 2R_i-1 - Y, при Sign R_i = Sign Y;

R_i = 2R_i-1 + Y, при Sign R_i =/ Sign Y,

для i=l,2,...,n+l при 2R₀ = X та Sign R₀ = Sign X. Тут Sign R_i - знак і-го часткового за­лишку, Sign Y, Sign X - відповідно знаки Y та Х.

При цьому розряди частки визначаються наступним чином:

q_i = 1, якщо Sign R_i = Sign Y,

q_i = 0, якщо Sign R_i =/ Sign Y.

Операція виконується за n+1кроків і дає значення частки в доповняльному коді.