Стр. 1 - Скоростные свойства алгоритмов умножения и деления целых чисел произвольного размера

ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013 1
УДК 681.142.2
Скоростные свойства алгоритмов умножения и деления
целых чисел произвольного размера
М.Ю. Барышникова 1, А.Ф. Деон 1, А.В. Силантьева 1
1 МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
Приведено описание подходов к оценке быстродействия алгоритмов
реализации операций умножения и деления целых чисел произвольной
размерности на основе подсчета количества операций, выполняемых
в ходе их обработки. Это позволяет определить границы применимо-
сти формы представления «длинных» чисел в виде одномерных мас-
сивов, в которых каждая цифра занимает один байт.
E-mail: baryshnikovam@mail.ru,deonalex@mail.ru, av_sil@mail.ru
Ключевые слова: быстродействие, алгоритм, числа, размерность.
Компьютерные операции процессора ориентированы на выполне-
ние действий с двоичными целыми числами размером n байтов, где
n — разрядность процессора. Количество различимых чисел находится
в диапазоне [0, 2n – 1], т. е. от 0 до 4 294 967 296 при 32-разрядном про-
цессоре или от 0 до 18 446 744 073 709 551 616 — при 64-разрядном.
В исключительных ситуациях, когда требуется оперировать чис-
лами большего размера, необходима реализация алгоритмических
операций, выполняемых по специальным программам. К таким опера-
циям относятся умножение и деление целых чисел произвольного раз-
мера. Оценка быстродействия этих алгоритмов составляет суть данно-
го исследования. В качестве единицы измерения быстродействия в
рамках этой работы используются операции — элементарные команды
из перечня машинных команд сложения, вычитания, сохранения,
сравнения и пересылки данных. При этом предполагается, что эти ко-
манды выполняются за одну операцию. В качестве языка программи-
рования используется исторический язык С, хотя такие его диалекты,
как CLR (common language runtime) или С#, предоставляют аналогич-
ные реализации, но с возможностями объектно-ориентированного
программирования.
Для представления целых чисел произвольного размера исполь-
зуется модель, согласно которой каждая цифра целого числа распола-
гается в отдельном байте, представляя все число как массив цифр-
байтов [1]. Поскольку возможно появление дополнительных старших
цифр при выполнении операции умножения, то десятичные цифры в
массиве располагаются в обратном порядке, что упрощает реализа-
цию умножения простым заполнением цифр в следующих старших
байтах результата. Старший байт массива числа должен содержать
код знака «+» или «–». В представленных далее программах исполь-