Мак-Сорлі

Операція ділення цілих чисел, коли у внутрішніх регістрах арифметич-ного пристрою ділене і дільник подаються відповідно в подвоєному і одинар-ному форматах виконується за найпростішими алгоритмами, оскільки в операціях ділення чисел за вказаних форматів практично вилучаються витрати часу на здійснення різного роду попередніх перетворень операндів. У зв’язку з цим саме ця операція ділення цілих чисел застосовується в багатьох сучасних комп’ютерах.

Машинна операція ділення цілих чисел у прямих кодах за зазначених форматів полягає в тому, що за модулем діленого подвійної довжини і модулем дільника одинарного формату визначаються ціла частина модуля частки і модуль лишку та формується знак прямого коду результату:

;

ND = NAÅNB; NC = NA, ( 3.1 )

де NA, NB, ND, NC – відповідно знак прямого коду діленого А_ПК, дільника В_ПК, частки D_ПК і остачі С_ПК (МСⁿ < МВⁿ).

Згідно з правилами арифметики операція ділення модулів чисел і виконується за наступною програмою.

На першому рівні в операції ділення перевіряються логічні умови (повідомні сигнали операційного пристрою) на переривання (блокування) основної частини програми ділення модулів чисел. Для цього, перш за все, проводиться аналіз модуля дільника на рівність нулю. У випадку, коли =0, програма ділення аварійно переривається і установлюється ознака переповнення частки . Тракт блокування операції ділення на передбачає також аналіз нульового значення чисельника . За умови, коли чисельник = 0, модулю частки присвоюється нульове значення і операція ділення модулів вважається виконаною. Окрім цих двох випадків блокування операції ділення на програма ділення пере-ривається з фіксацією переповнення частки у тому випадку, коли за аргументів ≠ 0 і ≠ 0 ціла частина модуля частки MD перевищує гранично-допустимий діапазон представлення результату операції, тобто перевищує n-розрядний (одинарний) формат модуля частки . Розгляне-мо докладно умови, за яких виникає переповнення одинарного формату частки на прикладі виконання операції ділення за наступних форматів:

MA⁶ / MB³ ≥ MD³, ( 3.2 )

де МА⁶ = а₆ а₅ а₄ а₃ а₂ а₁, МВ³= b₃b₂b₁, MD³ = d₃d₂d₁ – відповідно скорочений запис шестирозрядного подвійного діленого і трирозряд-них поліномів дільника і цілої частини частки;

Очевидно, що у загальному випадку кількість значущих цифр цілочислового результату операції ділення (3.2) може змінюватися в межах від одного до шести розрядів, тобто повна частка операції (3.2) визначається шестирозрядним цілочисловим кодом D⁶, елементами якого є коефіцієнти двійкового полінома d₆÷ d₁ :

D⁶ = d₆ d₅ d₄ d₃ d₂ d₁ ( 3.3 )

Отже, результат операції (3.2) у загальному випадку визначається нерівністю:

МА⁶ / МВ³ ≥ d₆×2⁵ + d₅×2⁴ + d₄×2³ + d₃×2² + d₂×2¹ + d₁×2⁰ , ( 3.4 )

де 2⁵, 2⁴, …, 2¹, 2⁰ – вага відповідних позицій послідовності цифр повної цілочислової частини частки D⁶.

Зазначимо, що згідно з (3.1) знаки « = » і « > » у (3.4) визначають операцію ділення відповідно без залишку (МС = 0) і при залишку МС ≠ 0.

Згідно з визначеним машинним алгоритмом (3.2) гранично-допустимий формат цілочислової частини частки операції (3.2) складає три біта. Отже, операція ділення (3.2) можлива без аварійного переповнення модуля частки МD³ у тому випадку, коли старша тріада d₆d₅d₄ повного шестирозрядного полінома частки D⁶ має нульове значення.

В операції ділення (3.4) старший розряд повної частки d₆ = 0у тому випадку, якщо згідно з (3.4) виконується нерівність виду:

МА⁶ / МВ³ < 1×2⁵,

Таким чином, d₆ = 0 за умови:

А6 = МА⁶ – МВ6 < 0, ( 3.5 )

де А6 – частковий залишок шестирозрядного діленого МА⁶, який визначає стан старшого коефіцієнта d₆ повного полінома частки D⁶;

МВ6 =МB³ * 2⁵ = b₃b₂b₁ 00 000, - формат розширеного модуля дільника МВ³ для визначення стану старшого коефіцієнта d₆ повного полінома частки, вага позиції якого дорівнює 2⁵.

За відсутністю значущого розряду у шостому розряді повної частки D⁶ аналогічним чином можна визначити умову нульового стану коефіцієнта d₅ повної частки:

МА⁶ / МВ³ < 1×2⁴.

Звідси дістанемо:

d₅ = 0, якщо А5 = МА⁶ – МВ5 < 0, ( 3.6 )

де А5 – частковий залишок шестирозрядного діленого МА⁶ для визначення стану п’ятого розряду d₅ у повному поліномі частки D⁶ за умови, що d₆=0;

В5 = МB³ * 2⁴ = b₃b₂b₁ 0 000, - стан розширеного модуля дільника для визначення значення коефіцієнта d₅ повного полінома частки D⁶.

2⁴ - ваговий коефіцієнт п’ятої позиції повної частки.

За умови, коли значущі розряди у шостому і п’ятому розрядах повної частки відсутні (d₆=0 і d₅=0), наступний коефіцієнт повної частки d₄ = 0, очевидно, за умови:

МА⁶ / МВ³ < 1×2³,

тобто при виконанні нерівності виду :

А4 = МА⁶ – МВ4 < 0, ( 3.7 )

де А4 – частковий залишок шестирозрядного діленого МА⁶, що несе інформацію щодо відсутності значущого розряду у четвертому розряді повної частки D⁶;

МВ4 = МB³ * 2³ = b₃b₂b₁ 000, - стан дільника для визначення значення четвертого розряду d₄ повної частки D⁶;

2³ – вага четвертої позиції повної частки D⁶.

У залежностях (3.5) ÷ (3.7), очевидно, справедливі нерівності виду: МВ6 > МВ5 > МВ4, через те, що МВ6 = b₃b₂b₁ 00 000, МВ5 = b₃b₂b₁ 0 000, МВ4=b₃b₂b₁ 000. У зв’язку з цим, якщо частковий залишок А4=МА⁶– -(b₃b₂b₁ 000), утворює від’ємне значення, то часткові залишки А6=МА⁶– -(b₃b₂b₁ 00 000) і А5=МА⁶–(b₃b₂b₁0000) безумовно набувають від’ємні значен-ня. Таким чином, від’ємне значення залишку А4 = МА⁶ – (b₃b₂b₁)* 2³ являє собою необхідну і достатню умову від’ємних значень залишків А6 і А5, тобто визначає умову відсутності значущих цифр в усіх трьох старших розрядах d₆ d₅ d₄ повної частки (3.3) і гарантує відсутність аварійного переповнення гранично-допустимого трирозрядного формату частки. Звідси випливає, що ознака переповнення частки за згаданих форматів результату і аргументів повинна визначатися за співвідношенням:

1, якщо ;

0, якщо < 0, ( 3.8 )

де ПП – ознака переповнення трирозрядної частки МD³ (d₃d₂d₁);

МВ4 =МB³ * 2³ = b₃b₂b₁ 000 – формат розширеного модуля дільника для визначення умови переповнення гранично-допустимого формату цілої частини модуля частки;

А4 - частковий залишок у так званому пробному кроці ділення, який несе інформацію щодо переповнення розрядної сітки цілої частини частки MD³.

У сучасних пристроях для ділення модулів чисел при визначенні часткових залишків операцію віднімання звичайно замінюють додаванням від’ємного дільника в доповняльному коді. У разі застосування допов-няльного коду для визначення пробного залишку діленого А4 залежності (3.8) набувають вигляду:

1, якщо NA4 = 0;

0, якщо NA4 = 1, ( 3.9 )

де = [ 128 + (МА⁶ –MB4)] =

= [(128 +(+МА⁶))_m128 + (128 + (-MB4)) _m128]_m128 =

= [(+МА⁶) + (- МB4) )] _m128;

(+МА⁶) = 0 МА⁶; (- МB) = (128 – MB4) _m128 =

= ((127 – MB4) + 0 000 001) _m128 = 1 + 0 000 001;

NA4 – знак доповняльного коду залишку А4.

Типові фрагменти операції ділення для визначення ознаки перепов-нення частки, які реалізують залежності (3.1) і (3.9), подано на рис.3.1 ÷ 3.2.

( ± МD3)ПК	( ± МА6)ПК	( ± МВ4)ПК
± 3 2 1	± 6 5 4 3 2 1	± 6 5 4 3 2 1
Х ХХХ   D Х ХХ ±   NA4 = 1 (A4 < 0), тому ПП = 0	± 0 1 1 0 0 1 NA NB     ND 0 0 1 1 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 1 NA4=1	± 1 0 1 0 0 0     = (+ 011 001) = (+МА6) = (- 101 000) = (-МВ4) = А4

Рисунок 3.1 - Фрагмент операції ділення чисел А на В для

визначення ознаки переповнення трирозрядної сітки цілої частини

модуля частки МD³ (при ПП = 0)

При відсутності блокування операції ділення чисел за будь-якої із трьох вищеназваних причин в програмі ділення чисел виконується виклик процедури послідовного визначення цифр цілої частини трирозрядної частки МD³, починаючи із старшого розряду d₃.

Очевидно, що за згаданих форматів і за умови, коли ціла частина частки МD³ ≤ 111 (за умови, коли ПП = 0), найстарший розряд частки МD³ визначається за співвідношенням:

1, якщо МА⁶ / МB³ ≥ 2²,

0, якщо МА⁶ / МB³ < 2².

Із цього випливає, що найстарший розряд частки d₃ потрібно обчислювати за нерівностями виду:

1, якщо А3 = МА⁶ - МB3 ≥ 0,

0, якщо А3 = МА⁶ - МB3 < 0, ( 3.10)

де МВ3 = (МB³*2²) = (МB³00) = (b₃b₂b₁ 00) – розширений код модуля дільника для визначення позиції d₃ частки із ваговим коефіцієнтом 2²;

А3 – частковий залишок діленого МА⁶ для визначення стану найстаршого коефіцієнта d₃ полінома частки МD³ = d₃d₂d₁.

( ± МD3)ПК	( ± МА6)ПК	( ± МВ4)ПК
± 3 2 1	± 6 5 4 3 2 1	± 6 5 4 3 2 1
Х ХХХ   Х ХХ ±   NA4 = 0 (A4 > 0), тому ПП = 1	± 1 1 0 0 0 1 NA NB     ND 0 1 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 1 NA4=0	± 1 0 1 0 0 0     = (+ 011 001) = (+МА6) = ( - 101 000) = (-МВ4) = А4

Рисунок 3.2 - Фрагмент операції ділення чисел А на В для

визначення ознаки переповнення трирозрядної сітки цілої частини

частки МD³ ( при ПП = 1)

У зв’язку з тим, що МВ4 = МB³ 000, очевидно, розширений формат модуля дільника МВ3 взаємопов’язаний із кодом МВ4 співвідношенням: МВ3 = МВ4 / 2, ( 3.11 )

де МВ4 – розширений формат модуля дільника в пробному кроці операції ділення.

У разі застосування доповняльного коду для визначення залишку А3 залежності (3.10) набувають вигляду:

1, якщо NA3 = 0; 0, якщо NA3 = 1, ( 3.12 )

де ( 3.13 )

МА⁶ – первинне значення модуля діленого;

Оскільки згідно з (3.9) при відсутності переповнення частки (за ПП=0) у пробному циклі формується від’ємна остача A4, для обчислення залишку за формулою (3.13) в пристрої ділення спочатку необхідно відновити первинний стан модуля діленого МА⁶, тобто згідно з (3.9) виконати операцію:

МА⁶ = [(А4) + (+МВ4) ]_m128 ( 3.14 )

Таким чином, згідно з (3.13) і (3.14) для визначення найстаршої позиції d₃ модуля частки потрібно виконати таку послідовность операцій:

1. МА⁶ = [(А4) + (+МВ4) ]_m128; ( 3.15 )

2. (А3) = [(МА⁶) + ((-МВ4)/2) ]_m128; ( 3.16 )

3. 1, якщо NA3 = 0;

0, якщо NA3 = 1. ( 3.17 )

Аналогічним чином можна визначити залежності для обчислення наступних позицій d₂ і d₁ частки.

Спочатку розглянемо алгоритм визначення цифри d₂ частки за умови, коли попередня цифра частки d₃ = 1, тобто за А3 ≥ 0.

Якщо d₃ = 1, то згідно з (3.4) маємо:

1, якщо МА⁶ / МB³ ≥ (2² + 2¹);

0, якщо МА⁶ / МB³ < (2² + 2¹),

де 2², 2¹ – вага коефіцієнтів d₃ і d₂ полінома частки МD³ = d₃d₂d₁.

Із цього виразу випливають нерівності виду:

1, якщо МА⁶ - МB3 – МB2 ≥ 0;

0, якщо МА⁶ - МB3 – МB2 < 0,

де МB3 = МB³·(2²) = МB³ 00; МB2 = МB³·(2¹) = МB³ 0.

Звідси дістанемо:

1, якщо A2 ≥ 0;

0, якщо A2 < 1,

де А2 = (А3 – MВ2); В2 = (MВ3) /2;

MВ2, MВ3 – стан первинного дільника MВ³ = b₃b₂b₁ відповідно у поточному і попередньому циклах ділення;

;

А3 – залишок діленого у попередньому циклі ділення (за умови, коли d₃= 1 і А3 ≥ 0 ).

Таким чином, за умови, коли d₃ = 1 (за А3 ≥ 0), наступну цифру d₂ частки потрібно обчислювати за співвідношеннями:

1, якщо NA2 = 0;

0, якщо NA2 = 1, ( 3.18 )

де ;

MВ2 = (MВ3)/2 - стан дільника для визначення позиції d₂ частки.

Якщо коефіцієнт d₃ розшукованого полінома частки (d₃ d₂ d₁) дорівнює нулю (d₃ = 0), то позицію d₂ частки згідно з (3.4) потрібно обчислювати за нерівностями виду:

1, якщо МА⁶ / МB³ ≥ 2¹;

0, якщо МА⁶ / МB³ < 2¹,

де ( 2¹) – вага позиції d₂ частки.

Звідси дістанемо:

1, якщо А2 = МА⁶ – МB2 ≥ 0;

0, якщо А2 = МА⁶ – МB2 < 0. ( 3.19 )

За умови, коли d₃ = 0, попередній залишок діленого А3 < 0, тому для обчислення поточної цифри частки d₂ за нерівностями (3.19) спочатку необхідно відновити модуль діленого МА⁶. Згідно з (3.10) для цього потрібно виконати операцію:

МА⁶ = [A3+ (+МВ3 )] ( 3.20 )

Якщо від’ємний залишок А3 визначений у доповняльному коді, то відновлення залишку, очевидно, потрібно здійснювати за правилами підсумовування доповняльних кодів:

МА⁶ = [ + (+МВ3 ) ]_m128. ( 3.21 )

Узагальнюючи (3.18) ÷(3.20), для визначення коефіцієнтів полінома частки МD³ = d₃d₂d₁ маємо наступну послідовність операцій:

MB3 = (MB4)/2;

; ( 3.22 )

1, якщо NA3 = 0;

0, якщо NA3 = 1; ( 3.23 )

MB2 = (MB3)/2;

,

якщо NА3 = 1;

, якщо NА3 = 0; ( 3.24 )

1, якщо NA2 = 0;

0, якщо NA2 = 1; ( 3.25 )

MB1 = (MB2)/2;

,

якщо NА2 = 1;

, якщо NА2 = 0; ( 3.26 )

1, якщо NA1 = 0;

0, якщо NA1 = 1; ( 3.27 )

де А4 - частковий залишок подвійного формату діленого у пробному кроці операції ділення, який несе інформацію щодо переповнення розрядної сітки цілої частини частки;

і = 3,2,1 – номери позицій цілої частини частки;

МВ4 = b₃b₂b₁ 000 – стан розширеного подвійного формату модуля дільника у пробному циклі операції ділення.

Модуль остачі МС⁶ згідно з (3.1) пов'язаний з аргументами операції ділення співвідношенням:

МА⁶ = (МВ³)*(МD³) +MC⁶.

У розгорнутій формі маємо:

MC⁶ = МА⁶ - МВ³(d₃·2² + d₂·2¹ + d₁·2⁰).

Звідси дістанемо:

МА⁶ - МВ³(d₃·2² + d₂·2¹ +2⁰), якщо d₁ = 1,

МА⁶ - МВ³(d₃·2² + d₂·2¹), якщо d₁ = 0.

Згідно з (3.24) в останньому циклі ділення частковий залишок А1 обчислюється за формулою:

А1 = МА⁶ - (МВ³·2²)d₃ – (МВ³·2¹)d₂ + 1 =

= МА⁶ - (МВ³·2²)d₃ – (МВ³·2¹)d₂ – МВ³.

Звідси випливає, що останній залишок діленого А1 взаємопов’язаний з остачею МС⁶ співвідношенням:

МС⁶, якщо d₁ = 1, тобто А1 ≥ 0;

МС⁶ - МВ³, якщо d₁ = 0, тобто А1< 0.

Таким чином, маємо:

А1, якщо NA1 = 0;

А1 + (+МВ³), якщо NA1 = 1.

Звідси дістанемо:

(А1 )⁶, якщо NA1 ≥ 0;

[(А1 + (+МВ³) )_m128]⁶, якщо NA1 < 0.

Схема блока ділення чисел, представлених у прямому коді, за розгляну-тим алгоритмом зі зсувом вправо модуля дільника МВ (за алгоритмом «б») і відновленням залишку (ЗВЗ) подана на рис.3.3.

Рисунок 3.3,а – Cхема регістра діленого (РА) і суматора ( SM)

блока ділення за алгоритмом «б» з відновленням залишку (ЗВЗ)

Схема блока ділення містить:

- регістр А для приймання прямого коду діленого (А ) або рядку цифр на виході суматора SM;

- регістр В для приймання прямого коду дільника (В ) та формування його подвійного формату на відповідних входах суматора SM;

- лічильник циклів СТ;

- комутатор КА для формування змінних на інформаційних входах регістра А;

- комутатор ВК для подання прямого або оберненого коду дільника на входи суматора SM;

- тригер ознаки переповнення (ТПП) цілої частини частки;

- схему аналізу нульового стану модулів регістра А (САНА) і регістра В (CAHB).

Рисунок 3.3,б – Схема регістра дільника (РВ), частки (PD),

лічильника циклів (СТ) та тригера переповнення (ТПП) блока

ділення за алгоритмом «б» з відновленням залишку (ЗВЗ)