Реферат: "Длинная" арифметика
«Длинная» арифметика
Известно,что арифметические действия, выполняемые компьютером в ограниченном числеразрядов, не всегда позволяют получить точный результат. Более того, мыограничены размером (величиной) чисел, с которыми можем работать. А если намнеобходимо выполнить арифметические действия над очень большими числами,например,
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
Номер элемента в массиве А 1 2 3 4 5 6 7 8 9 Значение 9 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 - Конечное состояние 2 Начальное состояние 1 2 3 1-й шаг 1 23 8 2-й шаг 1 238 5 3-й шаг 2 385 2 1 4-й шаг: старшая цифра элемента А [1] перешла в пока «пустой» элемент А[2] 2 851 23 6 5-й шаг 2 516 238 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 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 ThenInc(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) < Length(Is) Do s :='0' + 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 2 1302 51 6912 1354 3 8706 9121 6912 1354 7827 1 4 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] := kElse 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] < B[0] Then More := False
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);
Ifi = 0 Then More := False
ElseIf A[i] > B[i] Then More := True
ElseMore:=False
End
End;
Остальныефункции реализуются через функции Eq и More.
Function Less(A, B: Tlong):Boolean; {A < B}
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] <B[0] + sdvig Then More := l
Else Begin
i:= A[0];
While(i > sdvig) And
(A[i]= B[i-sdvig]) Do Dec(i);
Ifi = sdvig Then Begin
More:=0;
{совпадениечисел с учетом сдвига}
For i := 1 To sdvig Do
IfA[i] > 0 Then Exit;
More := 2;
{числаравны, «хвост» числа А равен нулю}
End
ElseMore := Byte(A[i] < B[i-sdvig])
End
End;
Пятаязадача. Умножение длинного числа на короткое. Под коротким понимается целоечисло типа LongInt.
Процедураочень походит на процедуру сложения двух длинных чисел.
Procedure Mul(Const A: TLong;Const К: Longlnt; Var С: TLong);
Var i: Integer;
{результат — значение переменной С}
Begin
FillChar (С,SizeOf(С), 0);
IfK = 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 BeginInc(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 10 315 = 63 * ( (0 + 10) Div 2) C < Ost 5 10 441 = 63 * ( (5 + 10) Div 2) C < Ost 7 10 504 = 63 * ( (7 + 10) Div 2) C < Ost 8 10 567 = 63 * ( (8 + 10) Div 2) C > Ost 8 9 504 = 63 * ( (8 + 9) Div 2) C < OstИтак,результат — целая часть частного — равен (Up + Down) Div 2, остаток от деления— разность между значениями Ost и С. Нижнюю границу (Down) изменяем, если результат(С) меньше остатка, верхнюю (Up), — если больше.
Усложнимпример. Пусть А равно 27856, а В — 354. Основанием системы счисления являетсяне 10, а 10000.
Down Up С Ost = 27856 10000 1770000 C > Ost 5000 885000 C > Ost 2500 442500 C > Ost 1250 221250 C > Ost 625 110448 C > Ost 312 55224 C > Ost 156 27612 C < Ost 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 < OstЦелаячасть частного равна 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.Для хранения «длинных» чисел используется не массив, а стек,реализованный с помощью списка. Модифицировать модуль работы с «длинными»числами.
Список литературы
С.М.Окулов/ «Длинная» арифметика/
Дляподготовки данной работы были использованы материалы с сайта www.comp-science.narod.ru/