Длинная арифметика
автор: Качанова Елена Ивановна Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. Более того, мы ограничены размером (величиной) чисел, с которыми можем работать. Диапазон представления целых чисел (Integer, Word, LongInt) ограничен. Поэтому при решении задач всегда приходится действовать с оглядкой, — как бы не допустить возникновения ошибки выхода за диапазон или переполнения. Например, вычисляя факториал (n! = 1 * 2 * 3 * … * n), в диапазоне представления величин типа Integer удастся правильно получить только 7! = 5040, а в диапазоне представления типа LongInt — 12! = 479001600. Для больших значений, конечно, можно использовать действительные типы данных, но это уже не гарантирует точного результата. А если нам необходимо выполнить арифметические действия над очень большими числами, например, 30! = 265252859812191058636308480000000? Поэтому полезно для получения точных значений при действиях с многозначными числами разработать другие способы представления таких чисел, алгоритмы выполнения арифметических и других операций, процедуры ввода и вывода результатов и т.д. В таких случаях мы сами должны позаботиться о представлении чисел в машине и о точном выполнении арифметических операций над ними. Числа, для представления которых в стандартных компьютерных типах данных не хватает количества двоичных разрядов, называются "длинными". Реализация арифметических операций над такими "длинными" числами получила название "длинной арифметики". Организация работы с "длинными" числами во многом зависит от того, как мы представим в компьютере эти числа. "Длинное" число можно записать, например, с помощью массива десятичных цифр, количество элементов в таком массиве равно количеству значащих цифр в "длинном" числе. Но если мы будем реализовывать арифметические операции над этим числом, то размер массива должен быть достаточным, чтобы разместить в нем и результат, например, умножения. Покажем реализацию решения такого рода задач на примере умножения одного многозначного числа на другое. Именно эта арифметическая операция наиболее часто используется при решении других задач. Наиболее естественным способом представления многозначного числа является запись каждого его разряда в виде отдельного элемента линейного массива. Пусть (для удобства дальнейших действий) разряды "длинного" числа при записи в массив нумеруются с единицы, начиная с разряда единиц, т.е. цифра из разряда единиц — элемент массива с номером один, цифра из разряда десятков — элемент массива с номером два и т.д. Определим для работы с "длинными" неотрицательными числами тип данных: Const MNax = 2000; Type Digit = 0..9; Dl_Ch = Array[1..Nmax] Of Digit; Для решения поставленной задачи необходимо уметь выполнять следующие действия: 1) ввод "длинного" числа; 2) собственно умножение двух "длинных" чисел; 3) вывод "длинного" числа; 4) определение количества цифр в записи числа. Каждую из подзадач реализуем в виде отдельной подпрограммы. Начнем с ввода. Ввести большое число целесообразно в виде строки, а в дальнейшем преобразовать в массив цифр (можно читать число из файла). В процедуре учтен указанный выше способ размещения "длинного" числа в массиве, т.е. с точки зрения пользователя число записывается как бы в обратном порядке. {Процедура преобразования длинного числа, записанного в виде строки, в массив цифр; переменная F принимает значение True, если в записи числа нет посторонних символов, отличных от десятичных цифр, иначе — false} Procedure Translate(S : String; Var A : Dl_Ch; Var F : Boolean); Var I : Word; Begin Zero(A); I := Length(S); F := True; While (I >= 1) And F Do Begin If S[I] In ['0'..'9'] Then A[Length(S)- I + 1]:= Ord(S[I]) - 48 Else F := False; I := I - 1 End End; Прокомментируем эту процедуру на примере: S:='5678'
После выполнения процедуры Translate цифры в массиве А расположатся следующим образом: | 8 | 7 | 6 | 5 | | | 1 | 2 | 3 | 4 | -номер элемента массива |
В процедуре вызывается подпрограмма Zero(A), назначение которой — запись нуля в каждый разряд длинного числа. Вот текст этой процедуры: {Процедура обнуления длинного числа} Procedure Zero(Var A : Dl_Ch); Var I : Integer; Begin For I := 1 To NMax Do A[I] := 0; End; Таким образом, длинное число записано в массив, где впереди (в качестве элементов с большими номерами) стоят незначащие нули. При выполнении действий и выводе ответа они не учитываются. Сейчас разработаем функцию определения количества значащих цифр в записи числа, поскольку она потребуется при реализации подпрограммы умножения. {Функция определения количества цифр в записи длинного числа} Function Dlina(C : Dl_Ch) : Integer; Var I : Integer; Begin I := NMax; While (I > 1) And (C[I] = 0) Do I := I - 1; Dlina := I End; При ее разработке было использовано следующее соображение: если число не равно нулю, то количество цифр в его записи равно номеру первой цифры, отличной от нуля, если просмотр числа осуществляется от старшего разряда к младшему. Если же длинное число равно нулю, то получается, что количество цифр в его записи равно одной, что и требовалось. Ну и, наконец, главная процедура. При составлении алгоритма используется идея умножения "столбиком", хотя в нашем варианте сложение выполняется не по окончанию умножения, а по ходу его, т.е. перемножив очередные цифры, сразу же добавляем результирующую цифру в нужный разряд и формируем перенос в следующий разряд. {Процедура умножения длинных чисел. A, B — множители, C — произведение} Procedure umn(A, B : Dl_Ch; Var C : Dl_Ch); Var I, J : Integer; P : Digit; Rez : 0..99; Begin Zero(C); For I := 1 To Dlina(A) Do {Цикл по количеству цифр в первом числе} Begin P := 0; {Первоначально перенос равен нулю} For J := 1 To Dlina(B) Do {Цикл по количеству цифр во втором числе} Begin Rez := A[I] * B[J] + P + C[I + J - 1]; C[I + J - 1] := Rez Mod 10; {Очередное значение цифры в разряде I + J - 1} P := Rez Div 10 {Перенос в следующий разряд} End; C[I + J] := P {последний перенос может быть отличен от нуля, запишем его в пока ещё свободный разряд} End End; Сейчас приведем листинг программы целиком. Program DlUmn; Const NMax = 2000; Type Digit = 0..9; Dl_Ch = Array[1..Nmax] Of Digit; Var S : String; M, N, R, F : Dl_Ch; I, MaxF : Word; Logic : Boolean; {Процедура обнуления длинного числа} Procedure Zero(Var A : Dl_Ch); Var I : Integer; Begin For I := 1 To NMax Do A[I] := 0; End; {Функция определения количества цифр в записи длинного числа} Function Dlina(C : Dl_Ch) : Integer; Var I : Integer; Begin I := NMax; While (I > 1) And (C[I] = 0) Do I := I - 1; Dlina := I End; {Процедура печати длинного числа} Procedure Print(A : Dl_Ch); Var I : Integer; Begin For I := Dlina(A) DownTo 1 Do Write(A[I] : 1); WriteLn End; {Процедура преобразования длинного числа в массив цифр} Procedure Translate(S : String; Var A : Dl_Ch; Var F : Boolean); Var I : Word; Begin Zero(A); I := Length(S); F := True; While (I >= 1) And F Do Begin If S[I] In ['0'..'9'] Then A[Length(S) - I+ 1] := Ord(S[I]) - 48 Else F := False; I := I - 1 End End; Procedure Umn(A, B : Dl_Ch; Var C : Dl_Ch); Var I, J : Integer; P : Digit; Rez : 0..99; Begin Zero(C); For I := 1 To Dlina(A) Do Begin P := 0; For J := 1 To Dlina(B) Do Begin Rez := A[I] * B[J] + P + C[I + J - 1]; C[I + J - 1] := Rez Mod 10; P := Rez Div 10 End; C[I + J] := P End End; {Основная программа} Begin Repeat {повторяем ввод, пока число не будет введено правильно} Write('Введите первый множитель: '); ReadLn(S); Translate(S, M, Logic) Until Logic; Repeat Write('Введите второй множитель: '); ReadLn(S); Translate(S, N, Logic) Until Logic; Umn(M, N, R); Print(R) End. В приведенном листинге Print — процедура вывода длинного числа.
Для того чтобы прочитать исходное число из файла и результат писать в файл, достаточно изменить следующие процедуры и аккуратно прочитать числа:
Procedure Print(A : Dl_Ch); Var I : Integer; Begin For I := Dlina(A) DownTo 1 Do Write(f2,A[I] : 1); WriteLn End;
Procedure Translate(Var A : Dl_Ch; Var F : Boolean); Var I,j,z : Word;s:char; Begin F := True; i:=1; While not eoln(f1) And F Do Begin read(f1,s); If S In ['0'..'9'] Then A[I] := Ord(S) - 48 Else F := False; I := I + 1; End ; for j:=1 to (i-1) div 2 do begin z:=a[j];a[j]:=a[i-j];a[i-j]:=z; end; End;
Процедура сложения двух "длинных» чисел может выглядить следующим образом: Procedure Summa(A, B : Dl_Ch; Var C : Dl_Ch); Var I, J,m : Integer; P : Digit; Rez : 0..99; Begin Zero(C); P:=0; if Dlina (A)>Dlina(B) Then m:=Dlina(A) Else m:=Dlina(B); For I := 1 To m Do Begin Rez := A[I] + B[I] + C[I]; C[I] := Rez Mod 10; P := Rez Div 10 ; C[I+1] := P End End;
В рассмотренных примерах для каждой цифры числа выделялось определенное место в таблице. Можно в каждой ячейке таблицы хранить по несколько цифр, например, по 3. Тогда основные процедуры обработки можно посмотреть в статье Окулова.
| 
