Двуцифровое значение (А, В) делится на d:

uint large::DDquotient(uint A, uint B, uint d)const

{ uint left, middle, right, qHi, qLo, x, dLol,

dHi = d >> hLen, dLo = d & rMask;

qHi = А/(dHi + 1);

Это начальное приближение к qHi может оказаться

слишком малым.

middle = qHi * dLo;

left = qHi * dHi;

X = В - (middle hLen);

A -= (middle >> hLen) + left + (x > B); В = x;

dLol = dLo hLen;

Увеличить qHi при необходимости:

while (A > dHi (A == dHi && В >= dLol))

{ X = В - dLol;

A -= dHi + (x > B) ;

В = x;

qHi++;

qLo = ((A hLen) I (B hLen))/(dHi + 1);

Это начальное приближение к qLo может оказаться

слишком малым.

right = qLo * dLo; middle = qLo * dHi; x = В - right; A -= (x > B); В = x;

X = В - (middle hLen);

A -= (middle >> hLen) + (x > B);

В = x;

Увеличить qLo при необходимости: while (A II В >= d) { X = В - d;

A -= (x > B);

В = x;

qLo++;

uint result = (qHi hLen) + qLo;

return result == 0 && qHi > 0 ? uintmax : result;

Вычесть произведение q * b из a, где a и b -

значения длиной n цифр. Остаток a - q * b

будет меньше, чем b, и должен быть неотрицательным.

Последнее условие может потребовать

уменьшения q на 1:

void large::subtractmul(uint *a, uint *b, int n, uint &q)const

{ uint Hi, Lo, d, carry = 0; int i;

for (i=0; i<n; i++)

{ DDproduct(b[i], q. Hi, Lo);

d = a[i];

a[i] -= Lo;

if (a[i] > d) carry++; d = a[i + 1]; a[i + 1] -= Hi + carry; carry = a[i + 1] > d;

if (carry) q was too large { q-; carry = 0;

for (i=0; i<n; i++) { d = a[i] + carry; carry = d < carry; a[i] = d + b[i]; if (a[i] < d) carry = 1;

a[n] = 0;

Нормализация путем сдвига denom и num влево, так что самая левая позиция denom станет 1; оба операнда выражения num/denom сдвигаются на X битовых позиций:

bool large::normalize(large &denom, large &num,

int &x)const { int r = denom.P.sizeO - 1;

uint у = denom.P[r]; x = 0;

while ( (y & IBit) == 0) {y = 1; x++;}

denom = x; num = x;

Возможно второе действие согласно К. Дж. Мифсуду (см. библиографию):

if (г > О && denom.Р[г] < denom.Р[г-1]) { denom *= uintmax; num *= uintmax; return 1;

return 0;

Откатить нормализацию (включая поправку Мифсуда, если SecondDone == 1), чтобы получить правильный остаток:

void large::unnormalize(large &rem, int x, bool SecondDone)const

{ if (SecondDone) rem /= uintmax;

if (x > 0) rem = x; else rem. reduce () ;

Разделить *this на denom, получив quot = num / denom, И, если RemDesired == 1, rem = num % denom: void large::divide(large denom,

large &quot, large &rem, bool RemDesired)const { int L = P.sizeO, Ld = denom. P. size () ;

if (Ld == 0) {cout Zero divide.\n ; return;}

bool QuotNeg = neg denom.neg;

int i, r, X = 0, n;

bool RemNeg = neg, SecondDone = false;

uint q, d;

large num = *this;

num.neg = denom.neg = 0;

if (num < denom)

{ quot = 0; rem = num; rem.neg = RemNeg; return; }

if (Ld == 1 && L == 1)

{ quot = uint(num.P[0]/denom.P[0]);

rem = uint(num.P[0]%denom.P[0]);

quot.neg = QuotNeg; rem.neg = RemNeg;

return; } else

if (Ld == 1 && (denom.P[0] & IMask) == 0) { Делитель умещается в половину слова

uint divisor = denom.Р[0], dHi = О, ql, г, q2, dividend;

quot.SetLen(L);

for (int i=L-l; i>=0; i--)

{ dividend = (dHi hLen) I (P[i] hLen); ql = dividend/divisor; r = dividend % divisor; dividend = (r hLen) I (P[i] & rMask); q2 = dividend/divisor; dHi = dividend % divisor; quot.P[i] = (ql hLen) I q2;

quot.reduce 0; rem = dHi;

quot.neg = QuotNeg; rem.neg = RemNeg;

return;

large numO = num, denomO = denom;

SecondDone = normalize(denom, num, x);

r = denom.P.sizeO - 1; n = num.P.sizeO - 1;

quot.SetLen(n - r);

int Lq = quot.P.size 0;