if( a[na-1] == ’+’ && b[nb-1] == ’-’ ) //a >= 0, b < 0
return nc = BinaryAdd( c, a, pna, b, pnb ); //c = a + b
Анализ этого этапа совпадает с анализом предыдущих этапов.
В итоге получаем:
W
−
4
min
= 9;
W
−
4
max
= 9 +
BA
4
.
Если на четвертом этапе не выполняется сложение, то следует
последний, пятый, этап по инструкции выбора:
if( a[na-1] == ’-’ && b[nb-1] == ’+’ ) //a <0 0, b >= 0
return nc = BinarySubtract( c, b, pnb, a, pna ); //c = b - a
Анализ пятого этапа совпадает с анализом предыдущих этапов.
В итоге получаем:
W
−
5
min
= 9;
W
−
5
max
= 9 +
BS
5
.
В целом минимальное количество операций на выполнение функ-
ции вычитания целых чисел произвольного размера определяется на
втором этапе:
W
−
min
=
W
−
1
+
W
−
2
min
= 3 + 9 +
BS
2
= 12 +
BS
min
=
= 3 + 9 + 4 + 18
n
= 16 + 18
n.
При вычитании целых чисел произвольного размера количество
операций будет максимальным в случае, если проверки условий при-
ведут к последнему, пятому, этапу:
W
−
max
=
W
−
1
+
W
−
2
.
условие
+
W
−
3
.
условие
+
W
−
4
.
условие
+
W
−
5
max
=
= 3 + 9 + 9 + 9 + 9 +
BS
5
= 39 +
BS
max
= 39 + 25
n
−
1
= 38 + 25
n.
Проведенный анализ показал, что при сложении и вычитании це-
лых чисел произвольной размерности несмотря на очевидный ли-
нейный характер зависимости количества элементарных операций от
разрядности числа
n
коэффициенты при
n
оказывают существенное
влияние на быстродействие алгоритмов реализации данных операций.
Таким образом, преимущества удобства и простоты реализации адди-
тивных операций над “длинными” числами, представленными в виде
одномерных массивов, в которых каждая цифра числа занимает один
байт, могут нивелироваться дополнительными временными затратами
на выполнение указанных действий.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
55
