Приведем алгоритм деления длинного числа на цифру. За эту операцию отвечает процедура ShortDiv.  Деление С = А/х и вычисление остатка r = A mod x (х-цифра)

void ShortDiv(

DIGIT *C,    /* результат */

const DIGIT A[ ],   /* делимое */

DIGIT x,       /* делитель (1 цифра) */

DIGIT *pr,   /* остаток */

int n)      /* длина делимого */

{

TWODIGIT Т = 0;

int i;

if (x=0) return ;             /* если х = 0, то конец */

for (i=n-l; i>=0; i—)

{              T = MAKELONG (A[i], T);

if(C != NULL)C[i] = LODIGIT (T/x);

T %= x;

}

if (pr != NULL) *pr = LODIGIT (T);/* остаток */

}

Сложность этого алгоритма O(n).

Теперь программа «длинного» деления. Деление длинных чисел с получением частного и остатка.

void Div(

const DIGIT A[ ],   /* делимое */

const DIGIT B[ ],    /* делитель */

DIGIT *Q,    /* частное */

DIGIT *R,   /* остаток */

int     t,   /* размер чисел А и Q в словах */

int     n)   /* размер чисел В и R в словах */

{

DIGIT q;   /* промежуточные результаты */

DIGIT U[MAX_SIZE*2+2];   /* нормализованной делимое */

DIGIT V[MAX_SIZE+1];   /* нормализованный делитель */

DIGIT W[MAX_SIZE+1];   /* промежуточные результаты */

TWODIGIT T;   /* промежуточные результаты */

int i, j, k;   /* индексные переменные */

DIGIT d;               /* нормализующий множитель */

if (R!=NULL) Zero (R,n);         /* R := 0 */

if (Q!=NULL) Zero (Q,t);         /* Q := 0 */

for (i=n-1; (i>=0)&&(B[i]==0); i—);   /* анализ делителя */

n = i+1;                  /* новый размер делителя */

if (n=0) return;             /* «Деление на ноль» */

for (k=t-l; (к>=0)&&(А[к]==0); к—);         /* анализ делимого */

t = к+1;                 /* новый размер делимого */

if(n>t)

{                   /* В > А */

if (R!=NULL) Assign (R,A,t); /* R := A */

return;

}

else if (n==1)         /* размер делителя 1 */

{              ShortDiv (Q, A, B[0], R, t); /* упрощенный алгоритм */

return;

}

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

d = (DIGIT)(((TWODIGIT)MAXDIGIT+1)/((TWODIGIT)B[n-1]+1));

ShortMul (V, B, d, n);      /* V = B*d */

ShortMul (U, A, d, t);     /* U = A*d */

U[t+1] = 0;

/* Основной цикл */

for (j=t; j>=n; j~)

{              T = MAKELONG (U[j-1], U[j]);

if(U[j]=V[n-1])q=MAXDIGIT;

else q=(DIGIT)(T/V[n-1]);

T%=V[n-l];

if ((TWODIGIT)V[n-2]*q>MAKELONG ((DIGIT)T, U|j-2]))

while ((TWODIGIT)V[n-2]*q >

MAKELONG(U[j-2],(DIGIT)(T-(TWODIGIT)q*V[n-l])))

q—;

ShortMul (W, V, q, n); /* W = V*q */

Sub (U+j-n, U+j-n, W, n+1);

if(U[j+1])           /* U < 0 */

{              U[j] += Add (U+j-n, U+j-n, V, n);

q—;

}

if (Q!=NULL) Q[j-n] = q;   /* цифра частного */

}

if(R!=NULL)

ShortDiv (R, U, d, NULL, n);   /* денормализация остатка */

Пример реализации алгоритма на Паскале.

Procedure MakeDel(Const А, В : TLong; Var Res, Ost : TLong);

Var sp : Integer;

Begin

Ost := A; {первоначальное значение остатка}

sp := А[0] — В[0];

If More(А, В, sp) = l Then Dec(sp);

{B * Osn > A, в результате одна цифра}

Res[0] := sp + l;

While sp >= 0 Do

Begin

{находим очередную цифру результата}

Res[sp + 1] := FindBin(Ost, B, sp);

Dec(sp)

End

End;

Function FindBin(Var Ost : Tlong; Const В : TLong; Const sp : Integer) : Longint;

Var Down, Up : Word; C : TLong;

Begin

Down := 0;Up := 0sn;

{основание системы счисления}

While Up — l > Down Do

Begin

{Есть возможность преподавателю сделать сознательную ошибку. Изменить условие цикла на Up>Down. Результат — зацикливание программы.}

Mul(В, (Up + Down) Div 2, С);

Case More(Ost, C, sp) Of

0: Down := (Down + Up) Div 2;

1: Up := (Up + Down) Div 2;

2: Begin Up := (Up + Down) Div 2; Down := Up End;

End;

End;

Mul(B, (Up + Down) Div 2, C);

If More (Ost, C, 0) = 0 Then Sub(Ost, C, sp)

{находим остаток от деления}

Else begin Sub (C, Ost, sp); Ost := C end;

FindBin := (Up + Down) Div 2;

{целая часть частного}

End;

Function More(A, B : Tlong) : Boolean;

Var i : Integer;

Begin If A[0] < B[0] Then More := False

Else   If A[0] > B[0] Then More := True

Else Begin

i := A[0];

While (i > 0) And (A[i] = B[i]) Do Dec(i);

If i = 0     Then More := False

Else If A[i] > B[i] Then More := True

Else More:=False

End

End;