"Длинная" арифметика

Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. Более того, мы ограничены размером (величиной) чисел, с которыми можем работать. А если нам необходимо выполнить арифметические действия над очень большими числами, например,

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) < 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 := 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] < 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);

                                                               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 < 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[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);

                                                               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] < B[i-sdvig])

                                                   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 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
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: