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

ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013

1

УДК 681.142.2

Дихотомический поиск множителя

целых чисел произвольного размера

А.Ф. Деон

1

МГТУ им. Н.Э. Баумана, Москва, 105005, Россия

Рассмотрены вопросы формирования множителя целых чисел произ-

вольного размера по алгоритму дихотомического поиска и анализа

количества выполняемых компьютерных операций при определении

скоростных свойств алгоритма.

E-mail:

deonalex@mail.ru

Ключевые слова:

быстродействие, алгоритм, числа, размерность.

В операции деления десятичных чисел произвольного размера

необходимо последовательно находить очередную цифру в числе ре-

зультата. Эту цифру можно получать перебором цифр 0, 1, … , 9 в

десятичной системе счисления (десятичной арифметике). Заранее эта

цифра неизвестна, поэтому для самого длительного последовательно-

го перебора цифр потребуются 10 итераций. Поскольку при анализе

быстродействия выполняемых программ часто приходится ориенти-

роваться на самый длительный случай, то следует учитывать именно

эти 10 итераций.

Число итераций можно сократить, если учесть свойство возраста-

ющей упорядоченности десятичных цифр. Тогда поиск необходимой

цифры можно выполнить дихотомическим способом. Число итераций

в самом длительном случае оценивается с округлением в бóльшую

сторону как

]

[

2

log 9 4

=

. Целью исследования является построение и

оценка быстродействия алгоритма дихотомического поиска множите-

ля для целых десятичных чисел произвольного размера в байтовом

представлении. В качестве языка программирования используется ис-

торический процедурный диалект языка С. Такие диалекты языка С,

как CLR (common language runtime) или С#, позволяют получить ана-

логичные реализации по технологии объектно-ориентированного про-

граммирования.

Для представления целых чисел произвольного размера можно ис-

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

ном байте, представляя все число как массив цифр-байтов [1]. Посколь-

ку далее потребуется выполнить операцию вычитания, то применяется

обратный порядок расположения десятичных цифр в массиве [2]. В

процессе вычитания положительных чисел возможно появление отри-

цательного результата, например (+5) – (+9) = –4, поэтому старший байт

массива числа должен содержать код знака «+» или «–».

Исходные данные.

Ниже представлены функции:

ByteBits

( )

—

для двоичного представления цифр числа,

ByteBitPrint

( ) — для печа-