Стр. 15 - Дихотомический поиск множителя целых чисел произвольного размера
Упрощенная HTML-версия
ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
15
Затем в теле цикла выполняются две инструкции
u
[
i
]
= a
[
na1+i
]
;
v
[
i
]
= b
[
i
], затрачивая семь операций:
1
2,2
0
7 7 .
nv
i
W
nv
−
=
= =
∑
В итоге на втором этапе затрачивается следующее количество
операций:
2
2,0
2,1
2,2
1 3 7 1 10 .
W W W W nv nv
nv
= + + = + + = +
Третий этап занимает главный цикл поиска с заголовком
while
(
na1 >= 0
). В теле цикла на каждой итерации проверяется условие
na1 >= 0
. Число итераций определяется количеством цифр в числе
a
и в числе
b
, по которым осуществляется поиск дихотомического
множителя:
3,1
1 0
1 1
.
na nb
na
W
na nb
−
=
= = + −
∑
Далее в цикле поиска выполняется инструкция одноразрядного
дихотомического поиска очередной цифры множителя
int dm =
= DichMult
(
u, v, nv, w, s
). Оценка функции
DichMult
( ) была получе-
на ранее. Учитывая операцию запоминания в
dm
, имеем следующий
результат:
(
) (
)
3,2 min
min
1 0
1
1 1
36 36 ;
na nb
DichMult
na
W
W
na nb
nv
−
=
= +
= + + −
+
∑
(
) (
)
3,2 max
max
1 0
1
1 1
126 244 .
na nb
DichMult
na
W
W
na nb
nv
−
=
= +
= + + −
+
∑
Полученная очередная цифра множителя запоминается в масси-
ве
c
[
k++
]
= dm
, а индекс старшей цифры сдвигается на одну пози-
цию к младшим цифрам
na1--
. Всего потребуется выполнить шесть
операций:
(
)
3,3
1 0
6 6 1
.
na nb
na
W
na nb
−
=
= = + −
∑
Следует проверить, что все цифры числа
a
уже рассмотрены
if
(
na1 < 0
)
break
и множитель найден, тогда условие
na1 < 0
истинно:
3,4
1 0
1 1
.
na nb
na
W
na nb
−
=
= = + −
∑
Если условие
na1 < 0
ложно, то необходимо увеличить порцию
делимого на одну цифру. Для этого остаток порции делимого смеща-
