УДК 681.142.2
Дихотомический поиск множителя
целых чисел произвольного размера <...> Н.Э. Баумана, Москва, 105005, Россия
Рассмотрены вопросы формирования множителя целых чисел произвольного размера по алгоритму дихотомического поиска и анализа
количества выполняемых компьютерных операций при определении
скоростных свойств алгоритма. <...> В операции деления десятичных чисел произвольного размера
необходимо последовательно находить очередную цифру в числе результата. <...> Заранее эта
цифра неизвестна, поэтому для самого длительного последовательного перебора цифр потребуются 10 итераций. <...> Поскольку при анализе
быстродействия выполняемых программ часто приходится ориентироваться на самый длительный случай, то следует учитывать именно
эти 10 итераций. <...> Число итераций
в самом длительном случае оценивается с округлением в бóльшую
сторону как ]log 2 9[ = 4 . <...> Ниже представлены функции: ByteBits( ) —
для двоичного представления цифр числа, ByteBitPrint( ) — для печаISSN 2305-5626. <...> В дальнейшем для реализации поиска дихотомического множителя потребуется функция SingleMultiply( ), выполняющая умножение целого числа b произвольного размера на одноразрядное целое число e. <...> В функции SingleMultiply( ) параметр
int nb1 содержит количество байтов в числе b без учета знака числа. <...> Функция возвращает число байтов в массиве c без учета знака результата.
int inline SingleMultiply( unsigned char* c, unsigned char* b,
int nb1, int e )
{
c[nb1] = 0;
// позиция для старшей цифры переноса
for( int i = 0; i < nb1; i++ )
c[i] = b[i] * e;
// поразрядное умножение
for( int j = 0; j < nb1; j++ )
// поразрядный перенос
{
if( c[j] > 9 )
// двухзначное число после умножения
{
c[j+1] += c[j] / 10; // перенос старшей цифры
c[j] = c[j] % 10;
// младшая цифра умножения
}
}
if( c[nb1] == 0 ) return nb1;//длина результата без переноса
return nb1 + 1;
// длина результата с переносом
}
В
представленной
ниже
программе
SingleMultiply( ) выполняет умножение c = a ∗ b :
HI02
функция
// Program HI02 (Win32)
// Умножение одноразрядного целого числа на байтовое число <...>