"Длинная" арифметика С.М. Окулов ""Длинная" арифметика" ("Информатика", № 4, 2000, с. 19-23) Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. Более того, мы ограничены размером (величиной) чисел, с которыми можем работать. А если нам необходимо выполнить арифметические действия над очень большими числами, например, 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+1] := A[i+1] + (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+1]} A[i+1] := A[i+1] + (LongInt(A[i]) * 10) Div Osn; A[i] := (LongInt(A[i]) * 10) Mod Osn End; A[1] := A[1] + 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 Is, s : String; i : Integer; Begin Str(Osn Div 10, Is); Write(A[A[0]]; {выводим старшие цифры числа} For i := A[0] - 1 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 | 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 := 1 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+1] = 0 Then C[0] := k Else C[0] := k + 1 End; Четвертая задача. Реализация операций сравнения для "длинных" чисел (А = В, А < В, А > В, А <= В, А >= В). Function Eq(A, B : TLong) : Boolean; Var i : Integer; Begin Eq := False; If A[0] <> B[0] Then Exit Else Begin i := 1; While (i <= A[0]) And (A[i] = B[i]) Do Inc(i); Eq := i = A[0] + 1 End End;
|