Стр. 11 - Дихотомический поиск множителя целых чисел произвольного размера
Упрощенная HTML-версия
ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
11
иска необходимо выбрать левый интервал
1, 1
n z
⎡
⎤− ⎣
⎦
. Параметры но-
вого интервала вычисляются в теле инструкции условия с помощью
инструкции
n2 = z – 1
, на что затрачиваются две операции:
2,2
1;
false
W
=
2,2
1 2 3.
true
W
= + =
Далее с помощью вычитания
int ns1 = SingleSubtract
(
s, u, c, nc
)
выполняется анализ, является ли полученный множитель
z
искомым
дихотомическим множителем. Количество операций для функции
SingleSubtract
( ) было вычислено ранее. Учитывая запоминание в
ns1
,
получаем следующее количество операций:
2,3 min
min
1 6 12 1 7 12 ;
SingleSubtract
W W
nv
nv
=
+ = + + = +
2,3 max
max
1 3 20 1 4 20 .
SingleSubtract
W W
nv
nv
=
+ = + + = +
После вычитания необходимо проанализировать знак результата
с помощью заголовка инструкции условия
if
(
s
[
ns1–1
]
== 45
). На это
затрачиваются три операции. Если знак отрицательный, то предлага-
ется продолжить поиск в левом интервале
n2 = z – 1
:
2,4 min
3;
W
=
2,4 max
3 2 5.
W
= + =
При положительном знаке после вычитания необходимо выпол-
нить еще одно вычитание
int ns2 = SingleSubtract
(
c, s, v, nc
), чтобы
убедиться в том, что либо дихотомический множитель найден, либо
его следует искать в правом интервале. Учитывая запоминание в
ns2
,
получаем следующее количество операций:
2,5 min
min
1 6 12 1 7 12 ;
SingleSubtract
W W
nv
nv
=
+ = + + = +
2,5 max
max
1 3 20 1 4 20 .
SingleSubtract
W W
nv
nv
=
+ = + + = +
Оценка знака результата второго вычитания проводится в заго-
ловке инструкции условия
if
(
c
[
ns2–1
]
== 45
). На это затрачивают-
ся три операции. Истинность условия
c
[
ns2–1
]
== 45
завершает ди-
хотомический поиск
break
. Ложное условие показывает, что
необходимо продолжить поиск в правом интервале с помощью ин-
струкции
n1 = z + 1
, на которую приходятся две операции:
2,6 min
3;
W
=
2,6 max
3 2 5.
W
= + =
