ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
3
интервала
[0;9]
. Старшая цифра прибавляется к цифре следующего
старшего разряда.
Перенос цифр выполняется в функции
MultCarry
( ). В интерфейсе
функции параметр
unsigned char* c
является указателем байтового
массива с числом, полученным после поразрядного умножения. Пара-
метр
int nc
содержит длину числа без знака. Параметр
int k
задает ин-
декс байта, с которого следует оценивать перенос. Функция возвраща-
ет новую длину числа после реализации поразрядных переносов:
// Файл MultCarry.h (Win32)
// Перенос в цифрах байтового числа
int inline MultCarry( unsigned char* c, int nc, int k )
{ c[nc] = 0;
for( int j = k; j < nc; j++ )
{ if( c[j] > 9 ) // двухзначное число после умножения
{ c[j+1]+=c[j]/10;//перенос старшей цифры умножения
c[j] = c[j] % 10; // младшая цифра умножения
}
}
if( c[nc] == 0 ) return nc; // длина результата без переноса
return nc+1; // длина результата с переносом
}
В теле функции
MultCarry
( ) анализ скоростных свойств [3]
начинается на первом этапе с инструкции
c
[
nc
]
= 0
, в которой пред-
полагается, что пока в старшем разряде числа отсутствует какая-либо
цифра переноса. В этой инструкции выполняются две операции:
1
2.
W
=
На втором этапе выполняется цикл под управлением заголовка
for
(
int j = k; j < nc; j++
). Инициализация
int j = k
занимает одну
операцию:
2,0
1.
W
=
На каждой итерации происходит проверка условия
j < nc
и вы-
полнение приращения
j++
, затрачивая в общей сложности три опе-
рации:
(
)
1
2,1
3 3
.
nc
j k
W
nc k
−
=
= = −
∑
В теле цикла заголовок инструкции условия
if
(
c
[
j
]
> 9
) осу-
ществляет контроль каждого разряда числа, при этом затрачиваются
две операции. Если условие
c
[
j
]
>
9 истинно, то производится пере-
нос с помощью инструкций
c
[
j+1
]
+=c
[
j
]
/10; c
[
j
]
= c
[
j
]
% 10
с общим
числом операций
6 4 10 :
+ =
(
)
1
2,2 min
2 2
;
nc
j k
W
nc k
−
=
= = −
∑
1,2 4,5,6,7,8,9,10,11