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

ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013 14
unsigned char a[256];
char sb[256]; // символьный буфер целого числа b
unsigned char b[256];
InputAB( sa, a, sb, b ); // ввод чисел a и b
int na = strlen( sa ); // байтовая длина числа a
int nb = strlen( sb ); // байтовая длина числа b
// Дихотомический поиск целого множителя
unsigned char c[256]; // для результата умножения
unsigned char s[256]; // для промежуточного вычитания
int nc = DMultiplier( c, a, na, b, nb, s );//поиск множителя
cout << "c = "; ByteBitPrint( c, nc ); // результат
cout << "s = "; ByteBitPrint( s, nb-1 ); // листинг остатка
_getch(); // просмотр результата
}
Если при выполнении программы HI05 ввести числа 96918
a = и
999 b = , то на мониторе получается множитель 97 с = и остаток
2 s = . Для просмотра поиска в функции DMultiplier( ) снят коммен-
тарий с инструкции cout << "dm = " << dm << endl:
sa = +96918
a = 00001000 00000001 00001001 00000110 00001001 00101011
sb = +999
b = 00001001 00001001 00001001 00101011
dm = 0
dm = 9
dm = 7
c = 00000111 00001001 00000000
s = 00000101 00000001 00000000
В теле функции DMultiplier( ) первые три инструкции позволяют
выделить динамическую память для промежуточных вычислений. Не
будем учитывать время их выполнения, поскольку в реальных усло-
виях эта память может быть предоставлена заранее исходя из кон-
кретных условий решаемых задач.
Оценка скоростных свойств функции DMultiplier ( ) начинается на
первом этапе с выполнения инструкций int na1 = na – nb; int na2 =
= na – 2; int nv = nb – 1, в которых в общей сложности шесть опера-
ций:
1
6. W =
На втором этапе находится инструкция цикла для исходного ко-
пирования с заголовком for( int i = 0; i < nv; i++ ), на выполнение ко-
торой затрачивается одна операция инициализации int i = 0:
2, 0
1. W =
В теле цикла на каждой итерации выполняется проверка условия
i < nv и приращение i++, это занимает три операции:
1
2,1
0
3 3 .
nv
i
W nv
−
=
= =∑