Стр. 4 - Скоростные свойства алгоритмов умножения и деления целых чисел произвольного размера
Упрощенная HTML-версия
ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
4
(
)
(
)
1
2,2 max
2 10 12
.
nc
j k
W
nc k
−
=
= + = −
∑
Таким образом, на втором этапе выполняется следующее количе-
ство операций:
2 min
2,0
2,1
2,2 min
W W W W
= + +
=
(
)
(
)
1 3
2
nc k
nc k
= + − + − =
(
)
1 5
;
nc k
= + −
2 max
2,0
2,1
2,2 max
W W W W
= + +
=
(
)
(
)
1 3
12
nc k
nc k
= + − + − =
(
)
1 15
.
nc k
= + −
Третий этап включает выполнение одной инструкции
if
(
c
[
nc
]
== 0
)
return nc
:
3
2.
W
=
Если условие
c
[
nc
]
== 0
ложно, то была цифра переноса в стар-
ший разряд результата, а само число стало на один разряд длиннее.
Следовательно, на четвертом этапе будет выполнена инструкция
return nc+1
:
4
1.
W
=
Функция
MultCarry
( ) завершена. Ее быстродействие можно оце-
нивать по количеству операций на каждом этапе:
min
1
2 min
3
MultCarry
W W W W
= + + =
(
)
2 1 5
2
nc k
= + + − + =
(
)
5 5
;
nc k
= + −
max
1
2 max
3
4
MultCarry
W W W W W
= + + + =
(
)
2 1 15
2 1
nc k
= + + − + + =
(
)
6 15
.
nc k
= + −
Функция умножения.
Умножение целых чисел произвольного
размера в байтовом представлении проводится в приведенной ниже
функции
ByteBitMult
( ). Параметр
unsigned char* c
является указате-
