Стр. 11 - Скоростные свойства алгоритмов умножения и деления целых чисел произвольного размера
Упрощенная HTML-версия
ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
11
max
1max
2
3 max
4
5
ByteBitDiv
W W W W W W
= + + + + =
2
82 337 84 243
243 2 4 7 1
nb na na nb nb
= − +
− +
⋅
−
+ + + + =
(
)
110 367 106 251
.
nb na na na nb
= +
−
+
−
Таким образом, проведенный анализ подтвердил фактически
квадратичную зависимость операций умножения и деления целых
чисел от размерности обрабатываемых чисел. В то же время, макси-
мальный коэффициент при произведении размерностей
(
)
na nb
⋅
об-
рабатываемых чисел равен 24, а при делении — 251, что говорит о
десятикратной длительности операции деления по сравнению с опе-
рацией умножения целых чисел произвольной размерности. При этом
для деления чисел использована функция дихотомического поиска
множителя, что позволило сократить число итераций поиска с 10 до
четырех (log29 = 4)
]
[
2
log 9 4
=
и, в свою очередь, ускорить операцию
деления.
СПИСОК ЛИТЕРАТУРЫ
1.
О к у л о в С . М . Основы программирования. М.: Лаборатория базо-
вых знаний, 2002. 424 с.
2.
Д е о н А . Ф . Дихотомический поиск множителя целых чисел произ-
вольного размера // Вестник МГТУ им. Н.Э. Баумана: электронное
научно-техническое издание. 2013.
3.
С е д ж в и к Р . Функциональные алгоритмы на С++: Ана-
лиз/Структуры данных/Сортировка/Поиск/: пер. с англ. СПб.: ООО
«ДианаСофЮП», 2002. 688 с.
Статья поступила в редакцию 25.10.2012
