С и л а н т ь е в а
СКОРОСТНЫЕ СВОЙСТВА АЛГОРИТМОВ
СЛОЖЕНИЯ И ВЫЧИТАНИЯ ЦЕЛЫХ ЧИСЕЛ
ПРОИЗВОЛЬНОГО РАЗМЕРА
Приведено описание подходов к оценке быстродействия алгоритмов, реализующих операции сложения и вычитания целых чисел
произвольной размерности, на основе подсчета числа операций,
выполняемых в ходе их обработки. <...> Это позволяет определить границы применимости формы представления “длинных” чисел в виде
одномерных массивов, в которых каждая цифра занимает один
байт. <...> Операции компьютерного процессора стандартизованы выполнением действий с двоичными целыми числами размером n байт, где
n — разрядность процессора. <...> К числу таких операций относятся операции сложения
и вычитания целых чисел произвольного размера. <...> Оценка быстродействия алгоритмов реализации этих операций и составляет суть данного исследования. <...> Для представления целых чисел произвольного размера можно использовать битовую модель из нескольких байт, учитывая при сложении или вычитании возникающий особый характер переноса бит как
внутри байт, так и между байтами. <...> В другой модели предусматривается расположение каждой цифры целого числа в отдельном байте,
представляя все число как массив цифр-байтов [1, 2]. <...> Поскольку при реализации операции сложения
возможно появление дополнительной единицы переноса (например,
ISSN 0236-3933. <...> 2012
39
5 + 9 = 14), то используется обратный порядок расположения десятичных цифр в массиве, что упрощает реализацию сложения простым заполнением единицы в следующем старшем байте результата. <...> Аналогично, поскольку в процессе вычитания положительных чисел
возможно появление отрицательного результата (например, (+5) −
−(+9) = −4), старший байт массива числа должен содержать код
знака ‘+’ или ‘–‘. <...> Ниже приведена программа AI03, в которой
функции Align( ) и Align2( ) выполняют выравнивание количества
цифр в двух числовых массивах, дополняя нули в старших разрядах
числа с меньшим количеством цифр:
// Program AI03 (Win32)
// Выравнивание <...>