Арифметичні дії з великими числами

У мікроконтролерах сімейства і8051 відсутній набір команд для здійснення арифметичних дій у тих випадках, коли для представлення чисел потрібно використовувати більш одного байта. Тому розглянемо, яким чином можна здійснювати 4 дії арифметики для позитивних чисел, що представляються двома байтами. Для програмування арифметичних дій з такими числами варто мати на увазі, що вага старшого байта в 256 разів більше, ніж у його сусіда праворуч. Позначаючи молодший байт індексом 0, а старший — індексом 1, представимо операнди виразами

256*Х(1) + Х(0) і 256*Y(1) + Y(0).

Тут Х(0) і Y(0) — числові значення молодших байтів операндів, а Х(1) і Y( 1) — числові значення старших байтів операндів. Представлені вирази можна складати, віднімати і множити, але не ділити.

У результаті додавання одержимо наступний вираз для суми:

 

256*(Х(1) + Y(l)) + (Х(0) + Y(0))

з якого видно, що для обчислення молодшого байта суми потрібно скласти молодші байти операндів, а для обчислення старшого байта суми — старші байти операндів. Але незалежного додавання старших і молодших байтів недостатньо, тому що у випадку переповнення суми молодших байтів потрібно додати до суми старших байтів 1. Тому потрібно спочатку обчислити суму молодших байтів командою ADD, а потім — суму старших байтів з урахуванням переносу, тобто командою ADDC. Нехай перший операнд записаний у регістрах RO і R1, а другий — у регістрах R2 і R3, причому в регістрах з парними номерами зберігаються молодші байти. Складемо програму підсумовування із записом суми за адресою першого операнда:

MOV A, R0 ; мол. байт першого числа в нагромаджувачі

ADD A, R2 ; доданий мол. байт другого числа

MOV R0, A ; запам'ятовування мол. байта суми

MOV A, R1 ; ст. байт першого числа в нагромаджувачі

ADDC A, R3 ; доданий ст. байт другого числа і перенос

MOV R1, А ; запам'ятовування ст. байта суми

Варто помітити, що при виконанні команд пересилання кодів стан біта переносу не змінюється. Для віднімання потрібно проробити аналогічні дії, але потрібно врахувати одну тонкість. Справа в тім, що в системі команд і8051 відсутне звичайне віднімання, тому програма віднімання повинна починатися з очищення біта переносу:

CLR С; ; очищення біта переносу

MOV A, R0 ; мол. байт першого числа в нагромаджувачі

SUBB A, R2 ; віднімання мол. байта другого числа

MOV R0, А ; запам'ятовування мол. байта різниці

MOV A, R1 ; ст. байт першого числа в нагромаджувачі

SUBB A, R3 ; віднімання ст. байта другого числа і позики

MOV R1, А ; запам'ятовування ст. байта різниці

Різниця між діями додавання і віднімання складається ще в тім, що при додаванні потрібно враховувати перенос, а при відніманні – позику. Але для збереження позики при відніманні використовується той же самий біт переносу. В обох прикладах використані реєстрова адресації операндів і результату.

За допомогою непрямої адресації можна написати більш компактну програму додавання чи віднімання чисел, що складаються з будь-якої кількості байтів (аби вистачило пам'яті). Нехай молодший байт першого операнда записаний в осередку з ім'ям first, а всі наступні — у наступних осередках. Аналогічним чином байти другого операнда повинні бути записані в масив, перший осередок якого має ім'я scnd. Припустимо, що ці два числа складаються з 5 байтів. Для резервування пам'яті запишемо

.RSECT

frst: .DS 5/5 байт ОЗП для першого операнда

send: .DS 5/5 байт ОЗП для другого операнда

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

.CODE

MOV RO, #frst ; запис адреси 1-го операнда в регістр

MOV Rl, #scnd ; запис адреси 2-го операнда в регістр

MOV R3, #5 ; запис кількості байтів у регістр

CLR С ; очищення біта переносу

addm: MOV A, @R0 ; байт першого числа в нагромаджувачі

ADDC A, @R1 ; додавання байта 2-го операнда

MOV @R0, А ; запам'ятовування байта суми

INC R0 ; обчислення адреси байта 1-го числа

INC R1 ; обчислення адреси байта 2-го числа

DJNZ R3, addm ; рахунок кількості неопрацьованих байтів

Три команди на самому початку програми використовують безпосередню адресацію джерела. Притім для двох з них транслятор здійснює підстановку фактичних значень адрес молодших байтів операндів. Команда очищення біта переносу потрібна тому, що в циклічній частині програми використовується команда додавання з урахуванням переносу. За рахунок використання непрямої адресації вдається обробити всі байти першого і другого операндів тими самими командами. А для того, щоб у наступному циклі звернутися до наступного осередка ОЗП, уміст регістрів R0 і R1 треба збільшувати на 1. Рахунок кількості неопрацьованих байтів виробляється останньою командою. При її виконанні число в регістрі R3 зменшується на 1, і якщо результат не дорівнює 0, то керування передається на початок циклу. При показаному раніше способі для додавання 5 пар байтів довелося б використовувати 15 команд, у наведеному прикладі їх тільки 10. Крім економії пам'яті програм, цей фрагмент більш універсальний. З іншого боку тривалість роботи цієї програми більше, тому що для її завершення потрібно виконати 34 команди замість 15. Таким чином, економія одного ресурсу, як правило, здійснюється за рахунок витрати інших.

Переходячи до двох інших арифметичних дій, слід зазначити, що множення чи ділення двійкового числа, що складається з декількох байтів, на цілу ступінь двійки здійснюється за допомогою зсуву всіх байтів цього числа вліво чи вправо. Оскільки вага двійкової цифри 1 зростає вдвічі при переході в сусідній лівий розряд, то для множення на 2 потрібен зсув вліво на 1 розряд, для множення на 4 — на 2 розряди і так далі. Для передачі бітів коду числа з одного байта в інший потрібно використовувати операцію циклічного зсуву вліво за участю біта переносу. Оскільки перед черговим зсувом крайнього байта значення біта переносу може бути довільним, треба встановлювати потрібне значення або після завершення зсувів коректувати уміст відповідної кількості розрядів молодшого або старшого байта. Множення на заздалегідь задану константу, у коді якої міститься невелика кількість одиниць, також може вироблятися послідовністю операцій зсувів і підсумовування. Однак у тому випадку, коли значення множника заздалегідь невідомо, потрібно використовувати операції множення.

При перемножуванні чисел, кожне з який представлене двома байтами, добуток може зайняти 4 байти. Перенумеруємо їх від молодших до старших байтів 0, 1, 2 і 3. Для обчислення добутку можна скористатися формулою

 

65536*(X(1)*Y(1)) + 256*(X(1)*Y(0) + X(0)*Y(1)) +X(0)*Y(0).

 

З формули випливає, що результат повинен виходити нагромадженням, причому молодший байт добутку молодших байтів повинен бути записаний у 0 байт, а старший — у 1. Добутки молодшого байта на старший і старшого байта на молодший додаються відповідно до першого і другого байтів. Добуток старших байтів додається до другого і третього байтів. Загальне правило таке: зсув добутку байтів щодо молодшого байта результату дорівнює сумі зсувів щодо молодших байтів множеного і множника. Для зменшення кількості операцій додавання часткових добутків доцільно починати з обчислення добутків молодших байтів (множення "стовпчиком"). Нехай співмножники знаходяться в регістрах R1, R0 і R3, R2. Наступна програма розміщує добуток у регістри R7, R6, R5 і R4 (старші байти знаходяться в регістрах з великими номерами):

MOV A, R0

MOV B, R2

MUL АВ ; добуток мол. байтів

MOV R4, А ; у 0-й байт добутку

MOV R5, B ; у 1-й байт добутку

MOV A, R1

MOV B, R3

MUL АВ ; добуток від. байтів

MOV R6, А ; у 2-й байт добутку

MOV R7, B ; у 3-й байт добутку

MOV A, R1

MOV B, R2

MUL АВ ; добуток від. байта на мол. байт

ADD A, R5

MOV R5, А ; у 1-й байт добутку

MOV A, R6

ADDC А, B

JNC ncy1 ; перехід, якщо немає переносу в 3-й байт

INC R7 ; корекція 3-го байта добутку

ncyl: MOV R6, А ; у 2-й байт добутку

MOV A, R0

MOV B, R3

MUL АВ ; добуток мол. байта на ст. байт

ADD A, R5

MOV R5, А ; у 1-й байт добутку

MOV A, R6

ADDC А, B

JNC nсy2 ; перехід, якщо немає переносу в 3-й байт

INC R7 ; корекція 3-го байта добутку

ncy2: MOV R6, А ; у 2-й байт добутку

 

У наведеному прикладі після запису добутку молодших байтів виробляється обчислення добутку старших, оскільки їхні результати записуються в ті байти результату, що не перекриваються. Потім до них додаються добутки старшого на молодший і молодшого на старший. Для обчислення добутку довелося використовувати 4 команди множення, 4 команди додавання і багато операцій пересилання.

Як видно з наведених прикладів, програми для додавання, віднімання і множення великих чисел не представляють особливих труднощів. Потрібно тільки написати розрахункові формули, відповідно до яких повинен бути складений вихідний текст програми.

Програмування ділення великих чисел утрудняється через відсутність кінцевих формул для обчислення частки і залишку. Розглянемо докладно як приклад задачу обчислення частки від поділу двобайтового числа на однобайтове. З використанням колишніх позначень запишемо вираз для розподілу першого числа на друге у вигляді дробу

 

(256*Х(1) + Х(0)) / Y(0).

 

Операція цілочислового поділу полягає в переведенні неправильного дробу в правильний, при цьому ціла частина числа є часткою, а чисельник дробової частини — залишком. Позначимо частку і залишок літерами Q і R відповідно. Тоді задача цілочислового поділу зводиться до знаходження двох ненегативних цілих чисел, що задовольняють рівнянню і нерівності

X = Q * у + R;

R < у.

 

Це рівняння зважується підбором частки, тобто методом проб і помилок. Наприклад, це можна робити багаторазовим діленням дільника з діленим доти, поки залишок не буде менше ділення. Тоді частка дорівнює кількості операцій вирахування. Більш ощадливим є метод спробних обчислень різниці між діленим і добутком дільника на наближене значення частки. При цьому спочатку підбирається старша цифра частки як найбільше зі значень, при якому залишок ще позитивний, потім наступні цифри. Це відомий усім школярам (принаймні, до впровадження кишенькових калькуляторів) метод ділення "стовпчиком". Для двійкового кодування чисел цей метод найбільш ефективний, тому що дозволяє при кожній пробі обчислювати чергову цифру частки. Нехай ділене знаходиться в регістрах R3, R2, а дільник — у регістрі R0. Відведемо для запам'ятовування поточного залишку регістр R4, а для рахунка кількості цифр частки — регістр R1. При діленні "стовпчиком" добуток дільника на чергову цифру частки зсувається вправо на 1 розряд відносно діленого. При програмуванні доцільніше зсувати залишок уліво. Тоді у вивільнювані біти регістрів, використовуваних для збереження діленого, можна записувати значення чергових бітів частки. Після завершення програми частку буде записано на місці діленого.

MOV B, R0 ; запис дільника в регістр B

MOV R1, #16 , кількість розрядів діленого

MOV R4, #0 ; заготівля для залишку

dwb3: CLR C ; очищення чергового біта для частки

MOV A, R2

RLC А ; зсув мол. розрядів частки

MOV R2, А

MOV A, R3

RLC A ; зсув ст. розрядів частки

MOV R3, А

MOV A, R4

RLC A ; зсув поточного залишку

CJNE А, B, dwbl ; порівняння поточного залишку з дільником

dwbl: JC dwb2 ; перехід, якщо залишок менше дільника

SUBB А, B ; обчислення дільника з поточного залишку

INC R2 ; запис 1 у черговий розряд частки

dwb2: MOV R4, А

DJNZ Rl, dwb3 ; 16-кратне повторення циклу

Використання операції порівняння чисел дозволяє обійтися без спробного обчислення дільника з поточного залишку. Якщо обчислення можливо, то в чергову цифру частки заноситься 1. Хоча ця програма займає небагато місця в пам'яті, вона виконується набагато довше попередніх прикладів, тому що вхідні в цикл команди будуть виконані 16 разів.

Програма для ділення двобайтового числа на однобайтове може бути удосконалена за рахунок одержання старшого байта приватною командою ділення:

MOV A, R3 ; ст. байт діленого

MOV B, R0 ; запис дільника в регістр B

DIV АВ

MOV R3, А ; ст. байт частки

MOV А, B ; поточний залишок

MOV B, R0 ; запис дільника в регістр B

MOV R1, #8 ; кількість розрядів залишку

dwb3: CLR C ; очищення чергового біта для частого

XCH A, R2 ;

RLC А ; зсув мол. розрядів частки

XCH A, R2

RLC A ; зсув поточного залишку

CJNE А, B, dwbl ; порівняння поточного залишку з дільником

dwbl: JC dwb2 ; перехід, якщо залишок менше дільника

SUBB А, B ; обчислення дільника з поточного залишку

INC R2 ; запис 1 у черговий розряд частки

dwb2: DJNZ R1, dwb3 ; 8-кратне повторення циклу

На відміну від попереднього варіанта регістр R4 тут не використовується, і залишок записується в нагромаджувач. За обсягом ці програми практично однакові. Але друга програма працює набагато швидше першої, оскільки удалося зменшити як кількість циклів, так і кількість команд у циклі. У випадку дільника, що представлений декількома байтами, потрібно використовувати алгоритм першого варіанта.

Якщо обійтися без великих чисел неможливо, то при програмуванні потрібно брати до уваги не тільки формули й алгоритми обчислень, але й обмеження по ресурсах. У залежності від поставленої задачі може знадобитися оптимізація програми за обсягом ОЗП, за обсягом ПЗП чи за швидкодією. Написати програму, яка одночасно і мінімізувала б споживання всіх цих ресурсів, неможливо.