Маніпулювання з цілими числами довільної довжини

Маніпулювання з цілими числами довільної довжини Постановка задачі:

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

Модуль, що реалізує цілі числа довільної довжини, і тестова програма написані на мові С + +.

Для представлення цілих чисел довільної довжини визначено клас UNLIM. Операції над цими числами реалізовані шляхом перевизначення для класу UNLIM наступних операцій:

+ (унарний і бінарний)

- (унарний і бінарний)

! =

> =

<<(операція виведення класу OSTREAM). Структура даних:

Абсолютна величина числа довільної довжини зберігається в пам'яті у вигляді масиву типу CHAR. В кожному елементі масиву може знаходиться число від 0 до 99, то є два розряди усього числа. У нульовому елементі зберігаються молодші два розряди, в останньому елементі - старші два розряди. Якщо число має непарну кількість розрядів, то в останньому елементі масиву зберігається один останній розряд, тобто число від 0 до 9. Лідируючі нулі в масиві не зберігаються. Число 0 представлено масивом з одного елемента, в якому зберігається 0.

З метою мінімізувати копіювання і витрата пам'яті клас UNLIM реалізований так, що на одне подання абсолютної величини можуть посилатися кілька чисел, при цьому ведеться облік посилань.

Об'єкт класу UNLIM складається з поля SIGN - знаку числа і поля PV - покажчика на дескриптор подання абсолютної величини. Число 0 завжди має знак PLUS.

Дескриптор подання абсолютної величини числа являє собою об'єкт структури DESCRIPTOR і має наступні поля:

body - вказівник на масив, в якому зберігається уявлення абсолютної величини числа;

len - довжина масиву body [] в байтах;

HowMany - кількість посилань на дане подання; Реалізація операцій порівняння:

З операцій порівняння тільки <и! = прямо порівнюють числа, інші операції виражені через ці дві. При роботі операцій <и! = Спочатку перевіряються знаки і довжини чисел, і лише у разі їх збігу проводиться порозрядне порівняння чисел (як розрядів тут беруться цілі байти - тобто розряди в системі числення з основою 100). Реалізація операцій арифметики:

Операція унарний + просто повертає саме число.

Операція унарний - повертає новий об'єкт класу UNLIM, який посилається на те саме подання модуля числа, що й аргумент, і має знак, протилежний знаку аргументу.

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

У першому випадку знак результату відповідає знаку одного (кожного) з операндів, а модуль результату є результатом складання модулів операндів. При цьому якщо кількість розрядів першого операнда одно A, а другий - B, то кількість розрядів операнда може бути або max (A, B), або max (A, B) +1, тому при виділенні пам'яті під масив для модуля результату береться другий значення. Ніякої оптимізації цього масиву після складання модулів операндів не робиться, тому що в даному випадку втрата пам'яті на лідируючі нулі може бути максимум 1 байт, і вигідніше заощадити на швидкості, ніж на пам'яті.

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

Додавання і віднімання модулів аргументів проводиться в системі числення з основою 100.

Операція бінарний - визначена через унарний мінус і бінарний плюс.

Операція * проводиться за технологією, аналогічної множення у стовпчик. При цьому всі дії ведуться в системі числення з основою 100. Довжина масиву результату може бути або дорівнює сумі довжин операндів, або цій сумі мінус 1. Ця ситуація аналогічна тій, яка була при складання чисел з однаковим знаком, і тут теж не робиться оптимізації.

Операція <<- просто операція виведення класу OSTREAM, визначена для класу UNLIM. Спочатку вона виводить '-' якщо знак числа негативний, а потім саме число порозрядної (за десятковим розрядів), починаючи зі старшого. При цьому використовується функція digit (number), яка повертає значення десяткового розряду з номером number.

Функція-конструктор unlim (char *) обробляє ініціалізацію символьної рядком. При цьому розпізнаються такі помилкові ситуації: ініціалізація нового рядка; неприпустимий символ в рядку; рядок містить знак, але не містить значення. У всіх цих випадках число ініціалізується нулем.

Функція-конструктор unlim (unlim &) обробляє ініціалізацію іншим об'єктом класу UNLIM. Звіт тестової програми

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

Без ініціалізації:

unlim a;

a = 0

Ініціалізація рядком:

unlim b = "123"

b = 123

unlim c = "-123"

c =- 123

unlim d = "123"

d = 123

unlim e = "+" Unlim class error: Sign without value. Value = 0

e = 0

unlim f = "-" Unlim class error: Sign without value. Value = 0

f = 0

unlim g = "aaa" Unlim class error: Not digit symbol in string. String ignored. Value = 0

g = 0

unlim h = "4a123" Unlim class error: Not digit symbol in string. String ignored. Value = 0

h = 0

Перевірка виводу, арифметики і порівняння:

Введено:

a = 123

b = 45

Результат:

a = 123

b = 45

a =- 123 + a = 123

a> b a> = b a! = b

a + b = 168 a-b = 78 a * b = 5535

Введено:

a = 0000000000000000123

b = 0000000000000000000000000000000045

Результат:

a = 123

b = 45

a =- 123 + a = 123

a> b a> = b a! = b

a + b = 168 a-b = 78 a * b = 5535

Введено:

a =- 123

b =- 45

Результат:

a =- 123

b =- 45

a = 123 + a =- 123

a + b =- 168 a-b =- 78 a * b = 5535

Введено:

a = 123

b =- 45

Результат:

a = 123

b =- 45

a =- 123 + a = 123

a> b a> = b a! = b

a + b = 78 a-b = 168 a * b =- 5535

Введено:

a =- 123

b = 45

Результат:

a =- 123

b = 45

a = 123 + a =- 123

a + b =- 78 a-b =- 168 a * b =- 5535

Введено:

a = 1000000000000000000000000000000000000000000000

b = 999999999999999999999999999999999999999999999

Результат:

a = 1000000000000000000000000000000000000000000000

b = 999999999999999999999999999999999999999999999

a =- 1000000000000000000000000000000000000000000000 + a = 1000000000000000000000000000000000000000000000

a> b a> = b a! = b

a + b = 1999999999999999999999999999999999999999999999 ab = 1 a * b = 999999999999999999999999999999999999999999999000000000000000000000000000000000000000000000

Введено:

a =- 100000000000000000000000000000000000000000000

b = 999999999999999999999999999999999999999999999

Результат:

a =- 100000000000000000000000000000000000000000000

b = 999999999999999999999999999999999999999999999

a = 100000000000000000000000000000000000000000000 + a =- 100000000000000000000000000000000000000000000

a + b = 899999999999999999999999999999999999999999999 ab =- 1099999999999999999999999999999999999999999999 a * b =- 99999999999999999999999999999999999999999999900000000000000000000000000000000000000000000