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

ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013 8
min 1 2 min 3 max 1 1 12 4 6 12 ; SingleSubtract
W W W W nv nv
= + + = + + + = +
max 1 2 max 3 min 4 5
SingleSubtract
W W W W W W
= + + + + =
1 1 14 1 3 6 3 3 20 .nv nv nv = + + + − + + = +
Дихотомический поиск одноразрядного множителя для чисел
одной длины. Пусть заданы два числа a и b одной длины. Необхо-
димо найти такое одноразрядное число 0, 9 z ⎡ ⎤ ∈ ⎣ ⎦ , чтобы выполнялось
условие a b z b− ∗ < . Это накладывает дополнительное ограничение
на число 9 a b≤ ∗ . Такая задача возникает при делении в столбик из
начального курса арифметики.
Поиск числа z можно выполнить, последовательно перебирая
цифры 0, 1, 2, …, 9. Если в каком-либо случае окажется, что 9
z = , то
выполняется 10 итераций поиска числа 9: в произвольном случае это
соответствует максимальному числу итераций поиска.
При дихотомическом поиске числа z учитывается арифметиче-
ская упорядоченность цифр 0, 1, 2, …, 9. Дихотомия заключается в
том, что сначала проверяют число из середины интервала: полагают
( )
0 9 / 2 4
z ⎡ ⎤ = + =
⎣ ⎦ , отбрасывая дробную часть. Если для такого z
условие a b z b− ∗ < не соблюдается, то ищут следующее число в ин-
тервале [ ]
0,1,2,3 или [ ]
5,6,7,8,9 . Всего таких итераций будет
] [
2 log 9 4= . В общем случае максимальное число итераций при дихо-
томическом поиске почти в два раза меньше, чем при последователь-
ном поиске.
Одноразрядный дихотомический поиск выполняется в функции
DichMult( ) при условии, что длина числа a равна длине числа b. В
этой функции параметр unsigned char* u является указателем на бай-
товый массив числа a, параметр unsigned char* v задает байтовый
массив числа b. Параметр int nv содержит байтовую длину массива v
без учета знака числа, параметр unsigned char* c предназначен для
байтового массива, в который помещается произведение v z∗ , пара-
метр unsigned char* s обозначает байтовый массив, в котором нахо-
дится остаток s a s z= − ∗ . Функция DichMult( ) возвращает найден-
ный дихотомический множитель z:
int inline DichMult( unsigned char* u, unsigned char* v,
int nv,
unsigned char* c, unsigned char* s )
{
// cout << "Begin DichMult" << endl;
int n1 = 0, n2 = 9; // начало и конец поиска
int z; // середина интервала
while( n1 <= n2 ) // цикл поиска
{