"Довга"
арифметика
Відомо, що
арифметичні дії, що виконуються комп'ютером в обмеженій кількості розрядів,
не завжди дозволяють отримати точний результат. Більше того, ми обмежені
розміром (величиною) чисел, з якими можемо працювати. А якщо нам необхідно
виконати арифметичні дії над дуже великими числами, наприклад,
30! =
265252859812191058636308480000000?
У таких випадках
ми самі повинні подбати про представлення чисел в машині і про точний
виконання арифметичних операцій над ними.
Числа, для
представлення яких в стандартних комп'ютерних типах даних не вистачає
кількості двійкових розрядів, називаються "довгими". Реалізація
арифметичних операцій над такими "довгими" числами отримала
назва "довгої арифметики".
Організація
роботи з "довгими" числами багато в чому залежить від того, як ми
наведемо у комп'ютері ці числа. "Довгий" число можна записати,
наприклад, за допомогою масиву десяткових цифр, кількість елементів у такому
масиві дорівнює кількості значущих цифр у "довгому" числі. Але якщо ми
будемо реалізовувати арифметичні операції над цим числом, то розмір масиву
повинен бути достатнім, щоб розмістити в ньому і результат, наприклад,
множення.
Існують і
інші вистави "довгих" чисел. Розглянемо одне з них.
Уявімо наше число
30! =
265252859812191058636308480000000
у вигляді:
30! = 2 *
(104) 8 + 6525 * (104) 7 + 2859 * (104) + 8121 * (104) 5 + 9105 * (104) 4 + 8636 *
(104) 3 + 3084 * (104) 2 + 8000 * (104) 1 + 0000 * (104) 0.
Це
подання наштовхує на думку про масиві, представленому в табл. 1.
Таблиця 1
Номер елемента в масиві А
0
1
2
3
4
5
6
7
8
9
Значення
9
0
8000
3084
8636
9105
8121
2859
6525
2
Ми можемо
вважати, що наше "довге" число представлено в 10000-10 системі
числення (десятитисячне-десяткова система числення, приведіть аналогію з
вісімкове-десяткового системою числення), а "цифрами" числа
є чотиризначні числа.
Виникають
питання. Що за 9 в А [0], чому число зберігається "задом наперед"?
Відповіді очевидні, але почекаємо з передчасними поясненнями. Відповіді на питання
будуть ясні з тексту.
Примітка. Ми
працюємо з позитивними числами!
Перше завдання.
Ввести "довге" число з файлу. Рішення задачі почнемо з опису
даних.
Const MaxDig = 1000; (Максимальне
кількість цифр - чотиризначних!)
Osn = 10000; (Основа нашої системи
числення,
в
елементах масиву зберігаємо чотиризначні числа)
Type Tlong
= Array [0 .. MaxDig] Of Integer;
(Максимальна кількість десяткових цифр у
нашому числі)
Алгоритм введення
"довгого" числа з файлу розглянемо на конкретному прикладі.
Нехай у файлі
записано число 23851674 і підставою (Osn) є 1000 (зберігаємо по три цифри в
елементі масиву А). Зміна значень елементів масиву А в процесі введення
(посимвольний в змінну Ch) показано в табл. 2.
Таблиця 2
А [0]
А [1]
А [2]
А [3]
Ch
Примітка
3
674
851
23
-
Кінцеве стан
0
0
0
0
2
Початкове стан
1
2
0
0
3
1-й крок
1
23
0
0
8
2-й крок
1
238
0
0
5
3-й крок
2
385
2
0
1
4-й крок: старша цифра елемента А [1]
перейшла в поки "порожній" елемент А [2]
2
851
23
0
6
5-й крок
2
516
238
0
7
6-й крок
3
167
385
2
4
7-й крок
3
674
851
23
Проаналізуємо
таблицю (і отримаємо відповіді на поставлені вище питання).
1. В А [0]
зберігаємо кількість задіяних (ненульових) елементів масиву А - це вже
очевидно.
2. При
обробці кожної чергової цифри вхідного числа старша цифра елемента масиву
з номером i стає молодшою цифрою числа в елементі i +1, а сума, що вводиться цифра
буде молодшою цифрою числа з А [1]. У результаті роботи нашого алгоритму ми
отримали число, записане "задом наперед".
Примітка
(методичне): Можна обмежитися цим поясненням і розробку процедури
винести на самостійне завдання. Можна продовжити пояснення. Наприклад,
виписати фрагмент тексту процедури перенесення старшої цифри з A [i] в молодшу
цифру А [i +1], тобто зрушення вже введеної частини числа на одну позицію вправо:
For i: = A [0] DownTo 1 Do
Begin
A [i + l]: = A [i + l] + (Longint (A [i]) *
10) Div Osn;
A [i]: = (LongInt (A [i]) * 10) Mod
Osn;
End;
Нехай ми вводимо
число 23851674 і перші 6 цифр вже розмістили "задом наперед" в
масиві А. У символьну змінну вважали чергову цифру "довгого"
числа - це "7". На нашу алгоритму ця цифра "7" повинна
бути розміщена молодшою цифрою в А [1]. Виписаний фрагмент програми
"звільняє" місце для цієї цифри. У таблиці показані результати
роботи цього фрагмента.
i
А [1]
А [2]
А [3]
ch
2
516
238
0
7
2
516
380
2
1
160
385
2
Після цього
залишається тільки додати поточну (зчитану в ch) цифру "довгого"
числа до А [1] і змінити значення А [0].
У кінцевому
підсумку процедура повинна мати такий вигляд:
Procedure ReadLong (Var A: Tlong);
Var ch: char;
i: Integer;
Begin
FillChar (A, SizeOf (A), 0);
Read (ch);
While Not (ch In ['0 '.. '9']) Do
Read (ch);
(пропуск не цифр у вхідному файлі)
While
ch In ['0 '.. '9'] Do
Begin
For i: = A [0] DownTo 1 Do
Begin
( "протягування" старшої
цифри в числі з A [i]
в молодшу цифру числа з A [i + l])
A [i + l]: = A [i + l] +
(LongInt (A [i]) * 10) Div Osn;
A [i]
: = (LongInt (A [i]) * 10) Mod Osn
End;
A [1]: = A [l] + Ord (ch) - Ord ('0');
(додаємо молодшу цифру до числа з А [1])
If A [A [0] 1]
> 0 Then Inc (A [0 ]);
(змінюємо довжину, кількість задіяних елементів масиву А)
Read (ch)
End
End;
Друге завдання.
Висновок "довгого" числа у файл чи на екран.
Здавалося б,
немає проблем - виводь число за числом. Однак у силу обраного нами представлення
"довгого" числа ми повинні завжди пам'ятати, що в кожному елементі
масиву зберігається не послідовність цифр "довгого" числа, а
значення числа, записаного цими цифрами. Нехай в елементах масиву зберігаються
чотиризначні числа. Тоді "довге" число 128400583274 буде в
масиві А представлено наступним чином:
A [0]
A [1]
A [2]
A [3]
3
3274
58
1284
При виведенні
"довгого" числа з масиву нам необхідно вивести 0058, інакше буде
втрата цифр. Отже, незначущий нулі також необхідно виводити. Процедура виводу
має вигляд:
Procedure WriteLong (Const A:
Tlong);
Var ls, s: String; i: Integer;
Begin
Str (Osn Div 10, Is);
Write (A [A [0]]; (виводимо старші цифри числа)
For i
: = A [0] - l DownTo 1 Do
Begin
Str (A [i], s);
While Length (s)
(доповнюємо незначущий нулями)
Write (s)
End;
WriteLn
End;
Третє завдання.
Попередня робота по опису способу зберігання, вводу та виводу
"довгих" чисел виконана.
У нас є все
необхідні "цеглинки", наприклад, для написання програми складання
двох "довгих" позитивних чисел. Вихідні числа і результат зберігаємо
у файлах. Назвемо процедуру складання SumLongTwo.
Тоді програма
введення двох "довгих" чисел та виведення результату їх складання буде мати
наступний вигляд:
Var A, B, C: Tlong;
Begin
Assign (Input, 'Input.txt');
Reset (Input);
ReadLong (A); ReadLong (B);
Close (Input);
SumLongTwo (A, B, C);
Assign (Output, 'Output.txt');
Rewrite (Output);
WriteLong (C);
Close (Output)
End.
Алгоритм процедури
складання можна пояснити на простому прикладі. Нехай А = 870613029451,
В = 3475912100517461.
i
A [i]
B [i]
C [1]
C [2]
C [3]
C [4]
1
9451
7461
6912
1
0
0
2
1302
51
6912
1354
0
0
3
8706
9121
6912
1354
7827
1
4
0
3475
6912
1354
7827
3476
Алгоритм
імітує звичне додавання стовпчиком, починаючи з молодших розрядів. І саме
для простоти реалізації арифметичних операцій над "довгими"
числами використовується машинне подання "задом наперед".
Результат: С =
3476782713546912.
Нижче наведено
текст процедури складання двох "довгих" чисел.
Procedure SumLongTwo (A, B: Nlong;
Var C: Tlong);
Var i, k:
Integer;
Begin
FillChar (C, SizeOf (C), 0);
If A [0]> B [0] Then k: = A [0]
Else k: = B [0];
For i: = l To k Do
Begin З [i +1]
: = (C [i] + A [i] + B [i]) Div Osn;
C [i]: = (C [i] + A [i] + B [i]) Mod Osn
(Чи є в цих операторах помилка?)
End;
If C [k + l] = 0 Then C [0]: = k Else
C [0]: = k + l
End;
Четверта
завдання. Реалізація операцій порівняння для "довгих" чисел (А = В,
А <В, А> В, А <= В, А> = В).
Function Eq (A, B: TLong):
Boolean;
Var i:
Integer;
Begin
Eq: = False;
If A [0] <> B [0] Then Exit
Else Begin
i: = l;
While (i <= A [0]) And (A [i] =
B [i]) Do Inc (i);
Eq: = i = A [0] + l
End
End;
Реалізація
функції А> В також прозора.
Function More (A, B: Tlong):
Boolean;
Var i:
Integer;
Begin If A [0]
Else
If A [0]> B [0] Then More: =
True
Else Begin
i: =
A [0];
While (i
> 0) And (A [i] = B [i]) Do Dec (i);
If i = 0
Then More: = False
Else
If A [i]> B [i] Then More: = True
Else
More: = False
End
End;
Решта
функції реалізуються через функції Eq і More.
Function Less (A, B: Tlong):
Boolean; (A
Begin
Less: = Not (More (A, B) Or Eq (A, B))
End;
Function
More_Eq (A, B: Tlong): Boolean; (A> = B)
Begin
More_Eq: = More (A, B) Or Eq (A, B)
End;
Function
Less_Eq (A, B: Tlong): Boolean; (A <= B)
Begin
Less_Eq: = Not More (A, B)
End;
Для
самостійного рішення може бути запропонована наступна, більш складна, завдання.
Потрібно розробити функцію, яка видає 0, якщо А більше В, 1, якщо А
менше В, і 2 при рівності чисел. Але порівняння повинно бути виконано з урахуванням
зсуву. Про що йде мова? Пояснимо на прикладі. Нехай А одно 56784, а В - 634.
При зсуві числа В на 2 позиції вліво функція повинна сказати, що більше В А,
без зсуву, що А більше В. Інший приклад. При А рівному 56700, а В - 567 і
зрушенні 2 функція має "сказати", що числа рівні. Рішення може
мати такий вигляд:
Function More (Const А, В: Tlong; Const sdvig: Integer): Byte;
Var i: Integer;
Begin
If A [0]>
B [0] + sdvig Then More: = 0
Else
If A [0]
Else Begin
i: =
A [0];
While (i
> Sdvig) And
(A [i]
= B [i-sdvig]) Do Dec (i);
If i =
sdvig Then Begin
More: = 0;
(збіг
чисел з урахуванням зсуву)
For i
: = 1 To sdvig Do
If A [i]> 0 Then Exit;
More: = 2;
(числа
рівні, "хвіст" числа А дорівнює нулю)
End
Else
More: = Byte (A [i]
End
End;
П'ята задача.
Множення довгого числа на коротке. Під коротким розуміється ціле число типу
LongInt.
Процедура дуже
походить на процедуру складення двох довгих чисел.
Procedure Mul (Const A: TLong;
Const До:
Longlnt; Var З: TLong);
Var i:
Integer;
(результат - значення змінної С)
Begin
FillChar (С, SizeOf (С), 0);
If K = 0 Then Inc (С [0]) (множення на нуль)
Else
Begin
For i: = l To A [0] Do
Begin
C [i + l]
: = (LongInt (A [i]) * K + C [i]) Div Osn;
C [i]
: = (LongInt (A [i]) * K + C [i]) Mod Osn
End;
If C [A [0] +1]> 0 Then C [0]: = A [0]
+ 1
Else C [0]: = A [0]
(визначаємо довжину результату)
End
End;
Шоста задача.
Віднімання двох довгих чисел з урахуванням зсуву
Якщо поняття
зсуву поки не зрозуміло, то залиште його в спокої, насправді віднімання з
урахуванням зсуву буде потрібно при реалізації операції ділення. На початку з'ясуйте
логіку роботи процедури при нульовому зсуві.
Введемо
обмеження: число, з якого віднімають, більше числа, яке віднімається. Працювати
з "довгими" негативними числами ми не вміємо.
Процедура була
б схожа на процедури додавання та множення, якби не одне "але" --
запозичення одиниці зі старшого розряду замість перенесення одиниці в старший
розряд. Наприклад, у звичайній системі числення ми віднімаємо 9 з 11 - йде
запозичення 1 з розряду десятків, а якщо з 10000 віднімаємо 9 - процес
запозичення трохи складніше.
Procedure Sub (Var A: TLong; Const
B: TLong; Const sp: Integer);
Var i, j:
Integer;
(з А віднімаємо В з урахуванням зсуву sp, результат віднімання в А)
Begin
For i: = l To B [0] Do
Begin Dec (A [i + sp], B [i ]);
j: = i ;{*}
(реалізація
складного запозичення)
while
(A [j + sp] <0) and (j <= A [0]) Do
Begin {*}
Inc (A [j + sp],
Osn);
Dec (A [j + sp + l]);
Inc (j); {*}
end; {*}
(Реалізація
простого запозичення.
Якщо
оператори, позначені *, замінити
на
наведені нижче оператори в фігурних дужках, то,
по
зрозумілих причин, логіка не будепрацювати
при
усіх вихідних даних. Можна свідомо зробити
помилку
і запропонувати знайти її - принцип "навчання через помилку")
(If
A [i + sp] <0 Then Begin Inc (A [i + sp], Osn);
Dec (A [i + sp + l]); End;)
End;
i: = A [0];
While (i> l) And (A [i] = 0) Do
Dec (i);
A [0]: = i
(коректування
довжини результату операції)
End;
Рекомендується
виконати трасування роботи даної процедури, наприклад, для наступних вихідних
даних. Число А одно 100000001000000000000, число В - 2000073859998.
Сьома завдання.
Ділення двох довгих чисел, тобто знаходження цілої частини приватного та залишку.
Написати
вихідну (без уточнень) частина логіки не складає труднощів. Це:
Procedure
Long_Div_Long (Const А, В: TLong; Var Res, Ost: TLong);
Begin
FillChar (Res, SizeOf (Res), 0);
Res [0]: = 1;
FillChar (Ost, SizeOf (Ost), 0);
0st [0]: = 1;
Case More (A, B, 0) Of
0: MakeDel (A, B, Res, Ost);
(А більше В, поки не знаємо, як виконувати операцію --
"виносимо" в процедуру)
1:
Ost: = A; (А менше В)
2:
Res [l]: = l; (А одно У)
End;
End;
А далі?
Далі починаються проблеми. Ділити стовпчиком нас навчили у школі. Наприклад,
1000143123567 | 73859998
- 73859998 |----------
--------- | 13541 (Ціла частина приватного)
261543143
- 221579994
----------
399631495
- 369299990
---------
303315056
- 295439992
----------
78750647
- 73859998
--------
4890649 (Залишок)
Що ми робили?
На кожному етапі в розумі підбирали цифру (1, 3, 5 і т.д.), таку, що твір
цієї цифри на дільник дає число менше, але найбільш близьке до числа ...
Якому? Це важко сказати словами, але з прикладу ясно. Навіщо нам це робити в
розумі, нехай робить комп'ютер. Однак спростимо приклад, залишимо його для
тестування остаточної логіки процедури, тим більше що і числа
"довгі". Нехай число А буде менше В * 10, тоді в результаті (цілої
частини поділу) буде одна цифра. Наприклад, А дорівнює 564, а В - 63 і проста
десяткова система числення. Спробуємо підібрати цифру результату, але не методом
прямого перебору, а методом поділу відрізка навпіл. Нехай Down - верхня
межа інтервалу зміни підбираємо цифри, Up - нижня межа інтервалу,
Ost дорівнює діленим.
Down
Up
С = В * ((Down + Up)
Div 2)
Ost =
564
0
10
315 =
63 * ((0 + 10) Div 2)
C
5
10
441 =
63 * ((5 + 10) Div 2)
C
7
10
504 =
63 * ((7 + 10) Div 2)
C
8
10
567 =
63 * ((8 + 10) Div 2)
C
> Ost
8
9
504 =
63 * ((8 + 9) Div 2)
C
Отже, результат
- Ціла частина приватного - рівний (Up + Down) Div 2, залишок від ділення - різниця
між значеннями Ost і С. Нижню кордон (Down) змінюємо, якщо результат (С)
менше залишку, верхню (Up), - якщо більше.
Ускладнимо
приклад. Нехай А одно 27856, а В - 354. Підставою системи числення є
не 10, а 10000.
Down
Up
С
Ost =
27856
0
10000
1770000
C
> Ost
0
5000
885000
C
> Ost
0
2500
442500
C
> Ost
0
1250
221250
C> Ost
0
625
110448
C
> Ost
0
312
55224
C
> Ost
0
156
27612
C
78
156
41418
C
> Ost
78
117
34338
C
> Ost
78
97
30798
C
> Ost
78
87
29028
C
> Ost
78
82
28320
C
> Ost
78
80
27966
C> Ost
78
79
27612
C
Ціла частина
приватного дорівнює 78, залишок від ділення - 27856 мінус 27612, тобто 244.
Пора приводити
процедуру. Використовувані "цеглинки": функція порівняння чисел (More) з
урахуванням зсуву і функція множення довгого числа на короткий (Mul) описані
вище.
Function FindBin (Var Ost: Tlong; Const В: TLong; Const sp: Integer):
Longint;
Var Down, Up: Word; C: TLong;
Begin
Down: = 0; Up
: = 0sn;
(основа системи числення)
While Up - l> Down Do
Begin
(Є
можливість викладачу зробити
свідому
помилку. Змінити умова
циклу
на Up> Down. Результат - зациклення програми.)
Mul (В, (Up + Down) Div 2, С);
Case More (Ost, C, sp) Of
0: Down: = (Down + Up) Div 2;
1: Up: = (Up + Down) Div 2;
2: Begin Up: = (Up + Down) Div 2;
Down: = Up End;
End;
End;
Mul (B, (Up +
Down) Div 2, C);
If More (Ost,
C, 0) = 0 Then Sub (Ost, C, sp)
(знаходимо залишок від ділення)
Else begin Sub (C, Ost, sp); Ost: =
C end;
FindBin: = (Up
+ Down) Div 2;
(ціла частина приватного)
End;
Залишилось
розібратися зі зрушенням, значенням змінної sp в нашому викладі. Знову
повернемося до звичайної системі числення і спробуємо розділити, наприклад, 635 на
15. Що ми робимо? Спочатку ділимо 63 на 15 і формуємо, підбираємо в розумі першим
цифру результату. Підбирати за допомогою комп'ютера ми навчилися. Підібрали - це
цифра 4, і це старша цифра результату. Змінимо залишок. Якщо спочатку він був
635, то зараз став 35. Віднімати з урахуванням зсуву ми вміємо. Знову підбираємо
цифру. Другу цифру результату. Це цифра 2 і залишок 5. Отже, результат (ціла
частина) 42, залишок від ділення 5. А що зміниться, якщо підставою буде не 10,
а 10000? Логіка співпадає, тільки в розумі вважати дещо важче, але ж у
нас же є молоток під назвою комп'ютер - нехай він забиває цвяхи.
Procedure MakeDel (Const А, В: TLong; Var Res, Ost: TLong);
Var sp: Integer;
Begin
Ost: = A; (первинне значення залишку)
sp: = А [0] - В [0];
If More (А, В, sp) = l Then Dec (sp);
(B * Osn> A, в результаті одна цифра)
Res [0]: = sp + l;
While sp> =
0 Do
Begin
(знаходимо чергову цифру результату)
Res [sp
+ 1]: = FindBin (Ost, B, sp);
Dec (sp)
End
End;
Методичні
рекомендації. Представлений матеріал викладається на чотирьох заняттях з
відомою схемою: 10-15-хвилинне виклад ідей, а потім робота учнів під
керівництвом викладача.
1-е заняття.
Введення, висновок і складання довгих чисел (завдання 1, 2, 3).
2-е заняття.
Функції порівняння (задача 4).
3-е заняття.
Множення і віднімання довгих чисел (завдання 5, 6).
4-е заняття.
Розподіл довгих чисел (завдання 7). Безумовно, ця схема не догма. Залежно
від рівня підготовки учнів на самостійне виконання може бути винесена
значна частина матеріалу. Зазначу тільки, що в силу традицією, що склалася в
ряді випадків допускаються при викладі свідомі помилки. У результаті роботи
кожен учень повинен мати власний модуль для роботи з
"довгими" числами.
Теми для
досліджень
1. Рішення
задач: пошук найбільшого загального дільника двох "довгих" чисел; пошук
найменшого спільного кратного двох "довгих" чисел; витяг
квадратного кореня з "довгого" числа і т.д.
2.
"Довгі" числа можуть бути негативними. Як зміняться описані
вище операції для цього випадку?
3. Для зберігання
"довгих" чисел використовується не масив, а стек, реалізований з
допомогою списку. Змінити модуль роботи з "довгими" числами.
Список
літератури
С.М. Окулов.
"Довга" арифметика.
Для підготовки
даної роботи були використані матеріали з сайту http://www.comp-science.ru/
