ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
4
int na = strlen( sa ); // байтовая длина числа a
// Одноразрядное умножение c = a * b
unsigned char c[256]; // для результата умножения
int e = b[0]; // одноразрядный множитель
int nc = SingleMultiply( c, a, na-1, e ); // c = a * e
cout << "c = a * b = "; ByteBitPrint( c, nc ); // результат
_getch(); // просмотр результата
}
Если ввести числа
58
a
=
и
3
b
=
, то получаем следующий ре-
зультат:
sa = +58
a = 00001000 00000101 00101011
sb = +3
b = 00000011 00101011
c = a * b = 00000100 00000111 00000001
Скоростные свойства функции
SingleMultiply
( ) определяются ко-
личеством операций над целыми числами внутри тела функции. По-
скольку в результате умножения количество цифр в итоге может
быть на единицу больше, то в начале функции предполагается, что
c
[
nb1
]
= 0
, пока нет переноса старшей цифры.
В теле функции
SingleMultiply
( )
на первом этапе выполняется
инструкция
c
[
nb1
]
= 0
с одной операцией индексирования и с одной
операцией сохранения числа 0:
1
1 1 2.
W
= + =
На втором этапе выполняется цикл одноразрядного умножения
for
(
int i = 0; i < nb1; i++
)
c
[
i
]
= b
[
i
]
* e
. Сначала производится одна
операция в выражении
int i = 0
. Затем на каждой итерации выполня-
ются одна операция проверки условия
i < nb1
, две операции для при-
ращения
i++
и четыре операции в выражении
c
[
i
]
= b
[
i
]
* e
. В общей
сложности на втором этапе будет выполнено следующее количество
операций:
(
)
1 1
2
0
1
1 2 4 1 7 1
nb
i
W
nb
−
=
= + + + = +
∑
.
На третьем этапе возможен перенос цифр в старшие разряды ре-
зультата под управлением заголовка цикла
for
(
int j = 0
;
j < nb1
;
j++
).
Сначала выполняется одна операция в выражении
int j = 0
. На каждой
итерации выполняются по три операции на условие
j < nb1
и прира-
щение
j++
. В теле цикла заголовок условия
if
(
c
[
j
]
> 9
) контролирует
появление цифры переноса, если цифра результата представлена дву-
значным числом. При этом выполняется одна операция индексирова-
ния и одна операция проверки условия
>9
. Если переносы отсутству-
ют, то на этом этапе будет выполнено минимальное количество
операций:
(
)
1 1
3 min
0
1
3 2 1 5 1.
nb
j
W
nb
−
=
= + + = +
∑
1,2,3 5,6,7,8,9,10,11,12,13,14,...18