УДК 681.142.2(075.8)
М. Ю. Б а р ы ш н и к о в а, А. Ф. Д е о н,
А. В. С и л а н т ь е в а
СКОРОСТНЫЕ СВОЙСТВА АЛГОРИТМОВ
СЛОЖЕНИЯ И ВЫЧИТАНИЯ ЦЕЛЫХ ЧИСЕЛ
ПРОИЗВОЛЬНОГО РАЗМЕРА
Приведено описание подходов к оценке быстродействия алгорит-
мов, реализующих операции сложения и вычитания целых чисел
произвольной размерности, на основе подсчета числа операций,
выполняемых в ходе их обработки. Это позволяет определить гра-
ницы применимости формы представления “длинных” чисел в виде
одномерных массивов, в которых каждая цифра занимает один
байт.
E-mail:
Ключевые слова
:
быстродействие, алгоритм, числа, размерность.
Операции компьютерного процессора стандартизованы выполне-
нием действий с двоичными целыми числами размером
n
байт, где
n
—
разрядность процессора. Количество различимых чисел находит-
ся в диапазоне [
0
,
2
n
−
1
],
т.е. от 0 до 4294967296 при 32-разрядном
процессоре или от 0 до 18446744073709551616 — при 64-разрядном.
Этого достаточно для выполнения почти всех прикладных задач.
В исключительных ситуациях, когда требуется оперировать числами
большего размера, необходима реализация алгоритмических опера-
ций, которые выполняются процессором компьютера по специальным
программам. К числу таких операций относятся операции сложения
и вычитания целых чисел произвольного размера. Оценка быстродей-
ствия алгоритмов реализации этих операций и составляет суть дан-
ного исследования. В качестве языка программирования используется
исторический С. Такой выбор был сделан исходя из понимания того,
что такие диалекты этого языка, как CLR (common language runtime)
или С#, предоставляют аналогичные реализации, но с возможностями
объектно-ориентированного программирования.
Для представления целых чисел произвольного размера можно ис-
пользовать битовую модель из нескольких байт, учитывая при сложе-
нии или вычитании возникающий особый характер переноса бит как
внутри байт, так и между байтами. В другой модели предусматрива-
ется расположение каждой цифры целого числа в отдельном байте,
представляя все число как массив цифр-байтов [1, 2]. В данной рабо-
те принят подход с представлением каждой десятичной цифры числа
в отдельном байте. Поскольку при реализации операции сложения
возможно появление дополнительной единицы переноса (например,
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
39
