Стр. 17 - Дихотомический поиск множителя целых чисел произвольного размера
Упрощенная HTML-версия
ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
17
(
) (
)
53 43 1
;
nv na nb
= +
+ −
3 max
3,1
3,2 max
3,3
3,4
3,5
3,6
3,7 max
W W W W W W W W
= +
+ + + + +
=
(
)
(
)
(
)
(
)
1 126 244 6 1 1 7 5 5 1
nv
nv
na nb
= + +
+ + + + + + + − =
(
) (
)
145 251 1
.
nv na nb
= +
+ −
В конце тела функции
DMultiplier
( ) присутствуют инструкции
освобождения динамической памяти
delete
[ ]
u;
delete
[ ]
v; delete
[ ]
w
. При оценке скоростных свойств их можно не учитывать, посколь-
ку эту память всегда можно зарезервировать заранее, исходя из кон-
кретных условий решаемых задач.
Таким образом, оценка скоростных свойств дихотомического по-
иска множителя определяется скоростью выполнения функции
DMul-
tiplier
( ). Минимальная оценка
min
DMultiplier
W
получается, если однораз-
рядный множитель равен четырем:
min
1
2
3 min
DMultiplier
W W W W
= + + =
(
) (
) (
)
6 1 10
53 43 1
nv
nv na nb
= + + + +
+ − =
(
) (
)
7 10 53 43 1
.
nv
nv na nb
= + + +
+ −
Максимальная оценка
max
DMultiplier
W
дихотомического поиска множи-
теля получается, если одноразрядный поиск все время находит цифру
0 или цифру 9:
max
1
2
3 max
DMultiplier
W W W W
= + + =
(
) (
) (
)
6 1 10 145 251 1
nv
nv na nb
= + + + +
+ − =
(
) (
)
7 10 145 251 1
.
nv
nv na nb
= + + +
+ −
Рассматривая определение функции
DichMult
( ) и параметры об-
ращения к ней в программе
HI04
, имеем
1
nv nb
= −
. Подставляя это
выражение в предыдущие формулы, получаем окончательные оценки
скоростных свойств функции
DMultiplier
( ):
(
)
(
)
(
)
(
)
min
7 10 1 53 43 1 1
DMultiplier
W
nb
nb
na nb
= + − + +
− + − =
(
)
7 43 10 43
;
nb na nb na nb
= + + +
−
(
)
(
)
(
)
(
)
max
7 10 1 145 251 1 1
DMultiplier
W
nb
nb
na nb
= + − + +
− + − =
(
)
109 367 106 251
.
nb na nb na nb
= +
−
+
−
