ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
10
то на мониторе появится результат, позволяющий проследить после-
довательность дихотомического поиска множителя
dm
:
sa = +41
a = 00000001 00000100 00101011
sb = +12
b = 00000010 00000001 00101011
Begin DichMult
n1 = 0 n2 = 9
z = 4
c = v * z = 00001000 00000100
n1 = 0 n2 = 3
z = 1
c = v * z = 00000010 00000001
n2 = 2 n2 = 3
z = 2
c = v * z = 00000100 00000010
n1 = 3 n2 = 3
z = 3
c = v * z = 00000110 00000011
End DichMult
dm = 3
s = a – b * dm = 00000101 00000000
Оценка скоростных свойств функции
DichMult
( ) начинается на
первом этапе с выполнения инструкции
int n1 = 0, n2 = 9
, содержа-
щей две операции:
1
2.
W
=
На втором этапе находится инструкция цикла поиска множителя
с заголовком
while
(
n1 <= n2
). На каждой итерации затрачивается
одна операция для проверки условия
n1 <= n2
:
2, 0
1.
W
=
В теле цикла вычисляется дихотомический множитель
z =
(
n1 +
+ n2
)
>> 1
, на что приходятся три операции. Затем проводится
умножение
v z
∗
с помощью инструкции
int nc = SingleMultiply
(
c, v,
nv, z
). Оценка выполнения функции
SingleMultiply
( ) была приведена
ранее. Учитывая одну операцию на запоминание в
nc
, всего будет за-
трачено следующее количество операций:
2,1min
min
3
1 3 6 12 1 10 12 ;
SingleMultiply
W W
nv
nv
= +
+ = + + + = +
2,1max
max
3
1 3 7 21 1 11 21 .
SingleMultiply
W
W
nv
nv
= +
+ = + + + = +
Следует проанализировать длину результата после умножения.
Если получаемое число длиннее множителя
v
, то значение
z
не может
быть результатом дихотомического поиска. Проверка выполняется с
помощью инструкции условия с заголовком
if
(
nc > nv
). На выясне-
ние условия затрачивается одна операция в выражении
nc > nv
. Если
условие истинно, то для следующей итерации дихотомического по-
1,2,3,4,5,6,7,8,9 11,12,13,14,15,16,17,18