Стр. 7 - Дихотомический поиск множителя целых чисел произвольного размера
Упрощенная HTML-версия
ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
7
цию. На каждой итерации выполняются одна операция проверки
условия
i < nv
и две операции приращения
i++
. В теле цикла опреде-
лены три инструкции. В первой инструкции
signed char d = u
[
i
]
–
– tranzit – v
[
i
] проводится вычитание соответствующих разрядов чи-
сел с учетом занимаемой единицы на предыдущей итерации, для чего
будет затрачено пять операций. Во второй инструкции заголовок
условия
if
(
d < 0
) проверяет, надо ли занимать единицу из следую-
щего старшего разряда, на что уходит одна операция. Если условие
истинно, выполняются инструкции
d = 10 + d; tranzit = 1
, затрачивая
в общем три операции. В противном случае на выполнение инструк-
ции
else tranzit = 0
затрачивается одна операция. В третьей инструк-
ции
s
[
i
]
= d
выполняются две операции. Таким образом, оценка числа
операций на втором этапе может быть минимальной и максимальной:
(
)
1
2 min
0
1 1 2 5 1 1 2 1 12 ;
nv
i
W
nv
−
=
= + + + + + + = +
∑
(
)
1
2 max
0
1 1 2 5 1 3 2 1 14 .
nv
i
W
nv
−
=
= + + + + + + = +
∑
На третьем этапе проводится проверка, является ли результат вы-
читания положительным или отрицательным. Если результат
if
(
tranzit == 0
) положительный, то будут выполнены три операции в
инструкциях
s
[
nv
]
= 43;
return nv+1
:
3 min
1;
W
=
3 max
1 3 4.
W
= + =
Если результат вычитания отрицательный, то выполняется чет-
вертый этап: необходимо преобразовать полученный байтовый код в
цифры, соответствующие отрицательному числу в евклидовой ариф-
метике. Для этого сначала модифицируется младшая цифра результа-
та в инструкции
s
[
0
]
= 10 – s
[
0
], затрачивая две операции. Затем пре-
образуются остальные цифры в цикле
for
(
int i = 1; i < nv; i ++
)
s
[
i
]
= 9 – s
[
i
]; на этот этап будет затрачено следующее число операций:
(
)
(
)
1
4
1
2 1 1 2 3 3 6 1 3 6 .
nv
i
W
nv
nv
−
=
= + + + + = + − = − +
∑
На последнем, пятом этапе выполняются инструкции
s
[
nv
]
= 45;
return nv+1
, для чего потребуются три операции:
5
3
W
=
.
Оценка общего количества операций в функции
SingleSubtract
( )
может быть минимальной или максимальной в зависимости от коли-
чества занимаемых единиц при вычитании и от знака результата:
