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

Информация - Компьютеры, программирование

Другие материалы по предмету Компьютеры, программирование

Для того чтобы скачать эту работу.
1. Подтвердите что Вы не робот:
2. И нажмите на эту кнопку.
закрыть



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

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

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

Номер элемента в массиве А0123456789Значение9080003084863691058121285965252Мы можем считать, что наше "длинное" число представлено в 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Примечание367485123-Конечное состояние00002Начальное состояние120031-й шаг1230082-й шаг12380053-й шаг23852014-й шаг: старшая цифра элемента А [1] перешла в пока "пустой" элемент А[2]285123065-й шаг2516238076-й шаг3167385247-й шаг367485123Проанализируем таблицу (и получим ответы на поставленные выше вопросы).

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]ch2516238072516380211603852После этого остается только добавить текущую (считанную в 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]33274581284При выводе "длинного" числа из массива нам необходимо вывести 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.

iA[i]B[i]C[1]C[2]C[3]C[4]19451746169121002130251691213540038706912169121354782714034756912135478273476Алгоритм имитирует привычное сложение столбиком, начиная с младших разрядов. И именно для простоты реализации арифметических операций над "длинными" числами используется машинное представление "задом наперед".

Результат: С = 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 <= 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);

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 :