Стр. 5 - Скоростные свойства алгоритмов умножения и деления целых чисел произвольного размера

ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013 5
лем на массив результата , c a b= ∗ параметр unsigned char* a — на
байтовый массив сомножителя a со знаком. Длина массива находится
в параметре int na. Параметры unsigned char* b, int nb содержат ана-
логичную информацию для сомножителя b.
// Файл ByteBitMult.h (Win32)
// Умножение целых десятичных чисел произвольного размера
int ByteBitMult( unsigned char* c, unsigned char* a, int na,
unsigned char* b, int nb )
{ int m = na + nb - 2; // длина результата c=a*b
for( int i = 0; i < m; i++ ) c[i] = 0; // чистка c
int na1 = na - 1; // длина a без знака
int nb1 = nb - 1; // длина b без знака
for( int j = 0; j < nb1; j++ ) // сомножитель позиций b
{ for( int i = 0; i < na1; i++)//сомножитель повторения a
{ int k = i + j; // позиция в результате
c[k] += a[i] * b[j];
}
m = MultCarry( c, na+j, j ); // перенос в умножении
}
for( ; m > 0; m-- )
if( c[m] != 0 ) break; // старшая цифра
m = m + 1; // позиция знака
if( a[na-1] == b[nb-1] ) c[m] = 43; // знак '+'
else c[m] = 45; // знак '-'
return m+1; // длина со знаком
}
В теле функции ByteBitMult( ) на первом этапе выполняется ин-
струкция int m = na + nb – 2 , затрачивая при этом три операции:
1
3. W =
Второй этап содержит цикл чистки массива for( int i = 0; i < m;
i++ ) c[i] = 0. Одна операция затрачивается на инициализацию int i =
= 0 . На каждой итерации проверяется условие i < m за одну опера-
цию, создается приращение i++ (две операции), выполняется ин-
струкция c [i] = 0 (две операции):
( ) ( )
1 2 1
2
0 0
1 1 2 2 5 5 2
m na nb
i i
W na nb
− + − −
= =
= + + + = = + − ∑ ∑ .
На третьем этапе выполняются две инструкции — int na1 = na – 1;
int nb1 = nb – 1, затрачивая четыре операции:
3
4. W =
Четвертый этап содержит главный цикл умножения под управле-
нием заголовка for( int j = 0; j < nb1; j++ ). Одна операция затрачива-
ется на инициализацию int j = 0:
4,0
1. W =
На каждой итерации выполняется проверка условия j < nb1 (одна
операция), и две операции затрачиваются на приращение j++: