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

ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013 13
жит адрес байтового массива числа a, параметр int na содержит дли-
ну числа a с учетом знака. Аналогично параметры unsigned char* b,
int nb содержат информацию числа b, параметр unsigned char* s
предназначен для байтового массива остатка a b z− ∗ . Функция
DMultiplier ( ) возвращает длину найденного дихотомического мно-
жителя:
// Файл DMultiplier.h (Win32)
// Дихотомический поиск множителя для произвольных целых чисел
int DMultiplier( unsigned char* c, unsigned char* a, int na,
unsigned char* b, int nb,
unsigned char* s )
{ unsigned char* u = new unsigned char[na]; // для цифр из a
unsigned char* v = new unsigned char[na]; // для цифр из b
unsigned char* w = new unsigned char[na]; // для дихотомии
int na1 = na - nb; // начало поиска со старших цифр а
int na2 = na - 2;
int nv = nb - 1; // длина b без знака
for( int i = 0; i < nv; i++ ) // для начала поиска
{ u[i] = a[na1+i]; // начальная порция из a
v[i] = b[i]; // исходный делитель
}
while( na1 >= 0 ) // деление в столбик
{ int dm = DichMult( u, v, nv, w, s );// дихотомия поиска
// cout << "dm = " << dm << endl;
c[na1] = dm; // очередная цифра результата
na1--; // индекс следующей цифры делимого a
if( na1 < 0 ) break; // в делимом больше цифр нет
for( int j = nv; j > 0; j-- ) u[j] = s[j-1];
u[0] = a[na1];//следующая младшая цифра порции делимого
v[nv++] = 0; // выравнивание делителя v
if( s[nv-2] == 0 ) nv = nv - 1;// длина порции делителя
}
delete [] u; // освободить динамическую память
delete [] v;
delete [] w;
return na – nb + 1; // длина c = b * dm
}
В программе HI05, приведенной ниже, выполняется дихотомиче-
ский поиск множителя c для введенных чисел a и b произвольной
длины. В подключаемом файле #include "DMultiplier.h" находится
функция DMultiplier( ):
// Program HI05 (Win32)
// Дихотомический поиск целого множителя для произвольных чисел
#include <conio.h> // _getch
#include <iostream>
using namespace std;
#include <string.h> // strlen
#include "InputAB.h"
#include "SingleMultiply.h"
#include "SingleSubtract.h"
#include "DichMult.h"
#include "DMultiplier.h"
void main(void)
{ char sa[256]; // символьный буфер целого числа a