Примеры подпрограмм, реализующих некоторые операции над целыми длинными числами

Длинные целые числа

Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. Более того, мы ограничены диапазоном встроенных типов данных системы, с которой работам. Например, необходимо выполнить арифметические действия над очень большим числом – 30! = 265252859812191058636308480000000?В таких случаях необходимо позаботится о точном представлении этих чисел в памяти компьютера и о точном выполнении арифметических операций над ними.. Числа, для представления которых в стандартных компьютерных типах данных не хватает количества двоичных разрядов, называются «длинными».. Реализация арифметических операций над такими «длинными» числами получила название «длинной арифметики». Организация работы с «длинными» числами во многом зависит от того, как мы представим в компьютере эти числа. Существует несколько способов представления длинных чисел в памяти компьютера. Первый способ представления «длинных» чисел – «длинное» число можно записать, например, с помощью массива десятичных цифр, количество элементов в таком массиве равно количеству значащих цифр в «длинном» числе. Если же, впоследствии, мы будем реализовывать над таким числом арифметические операции, то размер массива должен быть достаточным, чтобы разместить в нём результат. Так, при выполнении умножения длина результирующего массива может быть в два раза больше, чем длина массивов для множителей. При этом в первом элементе массива может распола­гаться как старшая (самая левая), так и младшая (правая) значащая цифра. Способ записи «длинных» чисел, когда младшая цифра располагается в первом элементе массива, предпочтительнее для организации тех арифметических действий, в которых обрабатываются цифры от младшей к старшей, например, при сложении и вычитании столбиком, а сами числа имеют различную длину. Для описания конкретного «длинного» числа требуется еще один параметр — длина текущего числа, расположенного в массиве. Этот параметр можно хранить как в отдельной целочисленной переменной, так и в нулевом элементе массива.

Примерописания массива для записи «длинных» чисел в языке программирования ТигЬо-Разса1:

Пример

Type

Аtype =array[l..1000] of byte;

. При организации ариф­метических операций над длинными числами, с использованием первого способа представления, процессор будет непосредственно складывать, вычитать, умножать или делить лишь однозначные числа, следовательно, количество самих дей­ствий при этом будет достаточно большим. Второй способ представления « длинных» чисел и повышения эффективности «длинной» арифметики — это хранение в каждом элементе массива двух цифр (размещение в каждом элементе массива двузначного числа). Это соответствует записи чисел в 100-ичной системе счисления. При этом следует следить за тем, чтобы промежуточный резуль­тат умножения двух двузначных чисел не был четы­рехзначным, так как он не может быть записан в однобайтном типе. Третий способ представления « длинных» чисел и повышения эффективности «длинной» арифметики — это хранение в каждом элементе массива четырёх цифр. Рассмотрим третий способ представления. Представим число30! = 265252859812191058636308480000000в виде:30! = 2 • (10⁴)⁸ + 6525 • (10⁴)⁷ + 2859 • (10⁴) ⁶ + 8121 • (10⁴)⁵ + 9105 • (10⁴)⁴ + 8636 • (10⁴)³ + 3084 • (10⁴)² + 8000 • (10⁴)¹ + 0000 • (10⁴)⁰.Это представление наталкивает на мысль о массиве, представленном в таблице 1:

Номер элемента в массиве А
Значение

Мы можем считать, что наше "длинное" число представлено в системе счисления с основанием 10000, смешанной с десятичной, а «цифрами» числа являются четырёхзначные числа. Описание такого массива на Turbo-Pascal дополнено нулевым элементом, в котором будет храниться текущая длина числа (количество 10000-ичных цифр)

Пример. О писание массива для записи «длинных» чисел третьим способом:

Туре

Btype = array [0..250] of longint;

Четвёртый способ представления «длинных» чисел – представление их с использованием строковых типов данных (string в Turbo-Pascal).

Пятый способ представления «длинных» чисел – представление их с использованием динамических структур данных, таких как списки из чисел, являющихся цифрами в записи «длинных» чисел (,например, 10000-ичных).

При операциях с конечными дробными числами, все значащие цифры записываются выбранным способом представления, место для запятой запоминается, например, в отдельной переменной и учитывается при печати результата. Такой способ соответствует операциям над вещественными числами, записанными в формате с фиксированной запятой.

В программах, оперирующих с очень большими числами, удобно иметь набор подпрограмм, выполняющих арифметические операции (+, -, *,div, mod) и операции сравнения (<, <=, >, >=, =, <>), то есть иметь модуль, в котором эти операции реализованы. Реализацию подпрограмм, выполняющих действия над целыми длинными числами см. [12],стр.223 – 239

Примеры подпрограмм, реализующих некоторые операции над целыми длинными числами.