Стр. 7 - Скоростные свойства алгоритмов умножения и деления целых чисел произвольного размера
Упрощенная HTML-версия
ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
7
(
)
(
)
(
)
2
2
4,3 max
max
0
0
1
1 6 13
nb
nb
MultCarry
j
j
W
W
na j j
−
−
=
=
= +
= + + + − =
∑
∑
(
) (
)
1 7 13 .
nb
na
= − +
Цикл четвертого этапа завершен. Можно оценить его минималь-
ные и максимальные скоростные свойства:
4 min
4,1
4,2
4,3 min
W W W W
= + +
=
(
) (
) (
) (
) (
)
3 1
1 11 10
1 6 5
nb
nb
na
nb
na
= − + −
− + − + =
(
) (
)
1 3 11 10 6 5
nb
na
na
= − + − + + =
(
)(
)
1 16
1 ;
na nb
= − +
−
4 max
4,1
4,2
4,3 max
W W W W
= + +
=
(
) (
) (
) (
) (
)
3 1
1 11 10
1 7 13
nb
nb
na
nb
na
= − + −
− + − + =
(
) (
)
1 3 11 10 7 13
nb
na
na
= − + − + + =
(
)
24
1 .
na nb
=
−
Пятый этап характеризуется циклом под управлением заголовка
for
(
; m > 0; m--
). На каждой итерации проходит проверка условия
m > 0
(одна операция) и обеспечение декремента
m--
(две операции).
Поскольку числа
a
и
b
минимально содержат по одной цифре и знак,
то хотя бы одна итерация будет выполнена:
5,1min
1 2 3
W
= + =
;
(
)
(
)
2
5,1max
1
1 2 3
2 .
na nb
m
W
na nb
+ −
=
=
+ = + −
∑
В теле цикла выполняется инструкция условия
if
(
c
[
m
]
! = 0
)
break
. На проверку условия
c
[
m
]
! = 0
затрачиваются две операции:
5,2 min
1 2 2;
W
= ⋅ =
(
)
2
5,2 max
1
2 2
2 .
na nb
m
W
na nb
+ −
=
=
= + −
∑
Таким образом, на пятом этапе затрачивается следующее количе-
ство операций:
5 min
5,1min
5,2 max
3 2 5;
W W W
=
+
= + =
