Способы представления «длинных» чисел

Организация работы с “длинными” числами во многом зависит от того, как мы представим в компьютере эти числа. Рассмотрим, как можно организовать работу с «длинными» числами, определив способы представления ДЧ.

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

На рисунке показано размещение числа 50236 в массиве цифр
(в первом элементе массива записан старший разряд числа)

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

Пример 1. Туре abyte=array [l..1000] of byte;

При этом в первом элементе массива может располагаться как старшая (самая левая), так и младшая (правая) значащая цифра. Зависит это от конкретной задачи и вкуса программиста.

При считывании «длинного» числа из файла или с клавиатуры проще разместить старшую значащую цифру в первом элементе массива, так как она будет считана первой.

Если же число мы генерируем программным образом или его длина известна до считывания, то в первый элемент можно помещать младшую цифру.

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

Но в любом случае для описания конкретного «длинного» числа требуется еще один параметр — длина текущего числа, расположенного в подобном массиве. Этот параметр можно хранить как в отдельной целочисленной переменной, так и в нулевом элементе массива, или в элементе, следующем за последним использованным, ставить управляющий код.

Однако для массива, описанного в примере 1, добавление нулевого элемента для хранения длины невозможно, так значение любого, в том числе и нулевого, элемента такого массива не может превосходить 255, а текущая длина массива может достигать 1000.

Показанный в примере 1 способ записи «длинных» чисел наиболее очевиден, так как число оказывается представленным в привычной для нас десятичной системе счисления, однако не очень эффективен. При организации арифметических операций над подобными массивами процессор будет непосредственно складывать, вычитать, умножать или делить лишь однозначные числа, а количество самих действий при этом будет достаточно большим.

Поэтому один из способов повышения эффективности «длинной» арифметики — это хранение в каждом элементе массива не одной, а двух или более цифр.

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

Попробуем это сделать для построения "длинных" чисел.

Если элементы массива, как и в примере 1, состоят из одного байта, то есть не должны превосходить 255, то в каждом элементе мы можем разместить двузначное число. Это соответствует записи чисел в 100-ичной системе счисления.

Размещение числа 50236 в массиве типа abyte.

Текущая длина массива, в данном примере — 3,

хранится отдельно

Пример 2. Покажем, как можно разместить число 10234560078. Для этого представим его в виде:

10234560078 = 1×(10²)⁵+02×(10²)⁴+34×(10²)³+56×(10²)²+00×(10²)¹+78×(10²)⁰

Это представление наталкивает на мысль о массиве типа abyte, представленном в табл.1:

Таблица 1

Как мы это получили? Мы взяли массив обычных целых чисел и считаем его позиционной записью "длинного" числа в системе счисления с некоторым основанием В. Тогда каждый элемент этого массива может принимать значение от 0 до В -1, а N таких элементов позволяет представить числа от 0 до В -1.

Мы можем считать, что наше “длинное” число представлено в 100-10-ичной системе счисления (стоично-десятичной системе счисления), “цифрами” числа являются двузначные числа.

Таблица 1 представляет собой наш массив, в который записано "длинное" число в обратном порядке.

Значения элементов массива a[2] и a[5] оказались однозначными числами, так как они содержат еще и значащий ноль в качестве второй цифры. У последнего же элемента массива ведущий ноль значимым не является. Текущая длина массива равна 6.

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

Так как 100-ичная система счисления является смешанной с десятичной, то, как это будет показано ниже, сами арифметические действия сложнее от такого представления не станут.

Аккуратно при этом следует производить лишь действия умножения, так как промежуточный результат умножения двух двузначных чисел может быть четырехзначным и не может быть записан в однобайтном типе.

Представление "длинных" чисел можно сделать еще более эффективным с точки зрения повышения быстродействия программы, если элементами («цифрами») в таком представлении будут служить числа, состоящие из четырех цифр. Именно такая величина элементов массива позволяет, в том числе и при выполнении операции умножения, всегда оставаться в рамках целочисленной арифметики.

Представим наше число 30! = 265252859812191058636308480000000 в виде:

30! =2×(10⁴)⁸+6525×(10⁴)⁷+2859×(10⁴)⁶+8121×(10⁴)⁵+9105×(10⁴)⁴+8636×(10⁴)³+

+3084×(10⁴)²+8000×(10⁴)¹+0000×(10⁴)⁰

Получаем таблицу:

Пример 3. Покажем, как можно описать массив для записи 1000-значных «длинных» чисел:

Туре along=array [0..250] of longint;

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

Размещение числа 10234560078 в массиве типа along
с хранением текущей длины массива в нулевом элементе

Во всех приведенных выше способах представления «длинных» чисел мы заранее фиксируем максимально допустимую длину числа, а реальную его длину, которая не может превышать размерности массива, мы вынуждены либо хранить отдельно, либо в нулевом элементе массива.

Длина числа будет подсчитываться автоматически, если для его представления использовать строковый тип данных ( string в Turbo-Pascal). Несмотря на то, что элементами этого типа служат символы, код каждого из символов является обычным десятичным числом.

Размещение числа 50236 в типе string

Поэтому, например, при записи числа из примера 2 в строковый тип, мы получим строку, состоящую из 6 символов с кодами 78, 0, 56, 34, 2 и 1 соответственно. А все операции, включая печать результата, будем проводить над кодами символов, из которых такая строка будет состоять.

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

А запись «длинного» числа в список, организованный по правилам работы со стеком, при считывании данных позволяет разместить младшую цифру в первом элементе списка.

Размещение числа 50236 в динамической структуре данных типа стек

Однако подобный способ представления «длинных» чисел может сделать программу, оперирующую такими числами, менее прозрачной и усложняет ее отладку. Поэтому более подробно данный способ мы рассматривать не будем.

Сказанное выше относится лишь к способам представления «длинных» целых чисел. Если же требуется получить точный результат при операциях с конечными дробными числами, то все их значащие цифры должны быть записаны в подобные описанным выше структуры данных, а место для запятой можно запомнить в отдельной переменной и учесть при печати результата. Такой способ соответствует операциям над вещественными числами, записанными в формате с фиксированной запятой.

Размещение числа 50236 в массиве типа abyte;
место для запятой должно быть запомнено отдельно

Все описанные ниже операции проводятся над «длинными» целыми числами. После минимальной модификации этот способ можно использовать и для операций над вещественными числами с фиксированной запятой.