// Q = A/B, R=A%B

void Div(const BigInt &A, BigInt &B, BigInt &Q, BigInt &R) {

// Вырожденный случай 1. Делитель больше делимого.

if ( A.Size < B.Size ) {

Q.zero();

R=A;

return;

}

// Вырожденный случай 2. Делитель – число базового типа.

if ( B.Size == 1) {

SDiv ( A, B.Coef[0], Q, R.Coef[0]);

R.Size = 1;

return;

}

1 Доказательства не очень сложны, и если они интересны – они присутствуют в книге Д. Кнута [3].

// Создать временный массив U, равный A

// Максимальный размер U на цифру больше A, с учетом

// возможного удлинения A при нормализации

BigInt U(A.Size+1); U = A; U.Coef[A.Size]=0;

// Указатели для быстрого доступа

short *b=B.Coef, *u=U.Coef, *q=Q.Coef;

long n=B.Size, m=U.Size-B.Size;

long uJ, vJ, i;

long temp1, temp2, temp;

short scale; // коэффициент нормализации

short qGuess, r; // догадка для частного и соответствующий остаток

short borrow, carry; // переносы

// Нормализация

scale = BASE / ( b[n-1] + 1 );

if (scale > 1) {

SMul (U, scale, U);

SMul (B, scale, B);

}

// Главный цикл шагов деления. Каждая итерация дает очередную цифру частного.

// vJ - текущий сдвиг B относительно U, используемый при вычитании,

// по совместительству - индекс очередной цифры частного.

// uJ – индекс текущей цифры U

for (vJ = m, uJ=n+vJ; vJ>=0; --vJ, --uJ) {

qGuess = (u[uJ]*BASE + u[uJ-1]) / b[n-1];

r = (u[uJ]*BASE + u[uJ-1]) % b[n-1];

// Пока не будут выполнены условия (2) уменьшать частное.

while ( r < BASE) {

temp2 = b[n-2]*qGuess;

temp1 = r*BASE + u[uJ-2];

if ( (temp2 > temp1) || (qGuess==BASE) ) {

// условия не выполнены, уменьшить qGuess

// и досчитать новый остаток

--qGuess;

r += b[n-1];

} else break;

}

// Теперь qGuess - правильное частное или на единицу больше q

// Вычесть делитель B, умноженный на qGuess из делимого U,

// начиная с позиции vJ+i

carry = 0; borrow = 0;

short *uShift = u + vJ;

// цикл по цифрам B

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

// получить в temp цифру произведения B*qGuess

temp1 = b[i]*qGuess + carry;

carry = temp1 / BASE;

temp1 -= carry*BASE;

// Сразу же вычесть из U

temp2 = uShift[i] - temp1 + borrow;

if (temp2 < 0) {

uShift[i] = temp2 + BASE;

borrow = -1;

} else {

uShift[i] = temp2;

borrow = 0;

}

}

// возможно, умноженое на qGuess число B удлинилось.

// Если это так, то после умножения остался

// неиспользованный перенос carry. Вычесть и его тоже.

temp2 = uShift[i] - carry + borrow;

if (temp2 < 0) {

uShift[i] = temp2 + BASE;

borrow = -1;

} else {

uShift[i] = temp2;

borrow = 0;

}

// Прошло ли вычитание нормально ?

if (borrow == 0) { // Да, частное угадано правильно

q[vJ] = qGuess;

} else { // Нет, последний перенос при вычитании borrow = -1,

// значит, qGuess на единицу больше истинного частного

q[vJ] = qGuess-1;

// добавить одно, вычтенное сверх необходимого B к U

carry = 0;

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

temp = uShift[i] + b[i] + carry;

if (temp >= BASE) {

uShift[i] = temp - BASE;

carry = 1;

} else {

uShift[i] = temp;

carry = 0;

}

}

uShift[i] = uShift[i] + carry - BASE;

}

// Обновим размер U, который после вычитания мог уменьшиться

i = U.Size-1;

while ( (i>0) && (u[i]==0) ) i--;

U.Size = i+1;

}

// Деление завершено !

// Размер частного равен m+1, но, возможно, первая цифра - ноль.

while ( (m>0) && (q[m]==0) ) m--;

Q.Size = m+1;

// Если происходило домножение на нормализующий множитель –

// разделить на него. То, что осталось от U – остаток.

if (scale > 1) {

short junk; // почему-то остаток junk всегда будет равен нулю…

SDiv ( B, scale, B, junk);

SDiv ( U, scale, R, junk);

} else R=U;

}