"Длинная"
арифметика
Известно, что
арифметические действия, выполняемые компьютером в ограниченном числе разрядов,
не всегда позволяют получить точный результат. Более того, мы ограничены
размером (величиной) чисел, с которыми можем работать. А если нам необходимо
выполнить арифметические действия над очень большими числами, например,
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 В также прозрачна.
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[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]
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.narod.ru/