Стр. 12 - Дихотомический поиск множителя целых чисел произвольного размера
Упрощенная HTML-версия
ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
12
Итак, минимальная оценка второго этапа с циклом
while
(
n1 <= n2
)
получается тогда, когда выполняется одна итерация, т. е. результатом
дихотомического поиска является число 4:
2 min
2,0
2,1min
2
2,3 min
2,4 max
2,5 min
2,6 min
false
W W W W W W W W
= +
+
+
+
+
+
=
1 10 12 1 7 12 5 7 12 3
nv
nv
nv
= + + + + + + + + + =
34 36 .
nv
= +
Максимальная оценка второго этапа получается тогда, когда вы-
полняется
]
[
2
log 9 4
=
итераций, т. е. результатом дихотомического
поиска является число 0 или число 9:
(
)
2 max
2,0
2,1max
2,2
2,3 max
2,4 min
2,5 max
2,6 max
4
true
W W W W W W W W
=
+
+
+
+
+
+
=
(
)
4 1 11 21 3 4 20 3 4 20 5
nv
nv
nv
= + + + + + + + + + =
(
)
4 31 61 124 244 .
nv
nv
= + = +
Функция
DichMult
( ) завершена, можно записать минимальную и
максимальную оценки ее выполнения:
min
1
2 min
2 34 36 36 36 ;
DichMult
W W W
nv
nv
= + = + + = +
max
1
2 max
2 124 244 126 244 .
DichMult
W W W
nv
nv
= + = + +
= +
Дихотомический поиск множителя для произвольных целых
чисел.
В некоторых случаях одноразрядный дихотомический поиск
приходится выполнять, когда исходное число
a
содержит на одну
цифру больше, чем число
b
, например
12,
3,
4
a b z
= = =
, поскольку
12
b z
∗ =
. Из арифметики следует, что число
a
может быть длиннее
числа
b
не более, чем на одну цифру для одноразрядного множителя
z
. Если числа
a
и
b
произвольной длины при условии, что
b a
≤
, то,
выполняя одноразрядный дихотомический поиск и последовательно
перебирая все цифры числа
a
, можно получить все цифры дихотоми-
ческого множителя.
Дихотомический поиск множителя для произвольных чисел
a
и
b
выполняется в представленной далее функции
DMultiplier
( ). Алго-
ритм функции устроен таким образом, что сначала проверяется
старшая цифра числа
a
. Если результат нулевой, то поиск осуществ-
ляется с двумя старшими цифрами числа
a
. Например, если
12,
3
a b
= =
, то поиск с одной старшей цифрой 1 дает множитель
0
z
=
. Следующий поиск с числом из двух цифр
12
a
=
дает пра-
вильный результат
4
z
=
. В общем случае, продолжая перебирать все
цифры числа
a
, получаем требуемый множитель
z
.
В функции
DMultiplier
( ) параметр
unsigned char* c
указывает на
байтовый массив результата
b z
∗
, параметр
unsigned char* a
содер-
