Стр. 16 - Дихотомический поиск множителя целых чисел произвольного размера
Упрощенная HTML-версия
ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
16
ется на одну позицию с помощью цикла с заголовком
for
(
int j = nv;
j > 0; j--
), затрачивается одна операция инициализации
int j = nv
:
3,5,0
1 0
1 1
.
na nb
na
W
na nb
−
=
= = + −
∑
В теле этого цикла на каждой итерации выполняется одна опера-
ция проверки условия
j > 0
и две операции для декремента
j--
:
(
)
(
)
3,5,1
1 0 1
1 2 3 1
.
na nb nv
na j
W
nv na nb
−
= =
=
+ = + −
∑ ∑
Также на каждой итерации выполняется смещение элементов
массива
u
[
j
]
= s
[
j–1
]:
(
)
3,5,2
1 0 1
4 4 1
.
na nb nv
na j
W
nv na nb
−
= =
=
= + −
∑ ∑
Всего на этот внутренний цикл уходит следующее количество
операций:
(
)(
)
(
)(
)
3,5
3,5,0
3,5,1
3,5,2
1 3 4 1
1 7 1
.
W W W W
nv nv na nb
nv na nb
= + + = + +
+ − =
= +
+ −
Остается добавить очередную младшую цифру в новую порцию
делимого
u
[
0
]
= a
[
na1
] и выровнять делимое и делитель по количе-
ству цифр
v
[
nv++
]
= 0
. Последнее будет необходимо для функции
вычитания байтовых чисел:
(
)
(
)
3,6
1 0
2 3 5 1
.
na nb
na
W
na nb
−
=
=
+ = + −
∑
Если в массиве
v
присутствует старший 0, то его следует убрать,
используя
if
(
s[nv–2] == 0
)
nv = nv – 1
:
(
)
3,7
1 0
3 3 1
;
na nb
min
na
W
na nb
−
=
= = + −
∑
(
)
(
)
3,7
1 0
3 2 5 1
.
na nb
max
na
W
na nb
−
=
=
+ = + −
∑
Итак, рассмотрены все инструкции третьего этапа в функции
DMultiplier
( ). Их общее количество определяется суммированием:
3 min
3,1
3,2 min
3,3
3,4
3,5
3,6
3,7 min
W W W W W W W W
= +
+ + + + +
=
(
)
(
)
(
)
(
)
1 36 36 6 1 1 7 5 3 1
nv
nv
na nb
= + + + + + + + + + − =
