MODULE Factor;
 IMPORT In, StdLog, Math,Services;
 TYPE
   Numbers=RECORD
     digit:ARRAY 1000 OF BYTE;
     len:INTEGER;
   END;

(*=================Блок процедур длинной арифметики================*)
PROCEDURE CopyNumber(OUT res:Numbers;IN arg:Numbers); (*Присвоение. Операция позволяет экономить время для коротких чисел записанных в динном массиве*)
VAR
 k:INTEGER;
BEGIN
 k:=0;
WHILE k<=arg.len DO
  res.digit[k]:=arg.digit[k];
  k:=k+1;
END;
res.len:=arg.len;
END CopyNumber;

PROCEDURE Sr(IN a,b:Numbers):BOOLEAN; (*Сравнение a<=b*)
VAR
  i:INTEGER;
BEGIN 
 (*Проверка неравенства a<=b*)
 IF b.len>a.len THEN  RETURN TRUE; END;
 IF b.len<a.len THEN  RETURN FALSE; END;
 i:=a.len;
WHILE ( i>=0 ) & (a.digit[i]=b.digit[i])  DO
      DEC(i);
END;
IF i=-1 THEN RETURN TRUE; END;
IF a.digit[i]<=b.digit[i] THEN RETURN TRUE; 
ELSE RETURN FALSE;
END;
END Sr;


PROCEDURE Summ(OUT res:Numbers;IN a,b:Numbers); (*Сложение*)
 VAR
   i,sum:BYTE;
   max:INTEGER;
BEGIN
  IF a.len>b.len THEN (*Наибольшее a*)
  i:=0;
  sum:=0;
  max:=a.len;
  WHILE i<=max DO
     INC(sum,a.digit[i]);
   IF i<=b.len THEN
     INC(sum,b.digit[i]);
   END;
   IF sum<10 THEN
     res.digit[i]:=sum;
     sum:=0;
   ELSE
      DEC(sum,10);
      res.digit[i]:=sum;
      sum:=1;
    END;
   INC(i);
  END;
  IF sum>0 THEN
    INC(max);
    res.len:=max;
    res.digit[max]:=sum;
  ELSE
    res.len:=max;
  END;
  ELSE (*Наибольшее b*)
  i:=0;
  sum:=0;
  max:=b.len;
  WHILE i<=max DO
     INC(sum,b.digit[i]);
   IF i<=a.len THEN
     INC(sum,a.digit[i]);
   END;
   IF sum<10 THEN
     res.digit[i]:=sum;
     sum:=0;
   ELSE
      DEC(sum,10);
      res.digit[i]:=sum;
      sum:=1;
    END;
   INC(i);
  END;
  IF sum>0 THEN
    INC(max);
    res.len:=max;
    res.digit[max]:=sum;
  ELSE
    res.len:=max;
  END;
  END;
END Summ;


PROCEDURE Substruction(OUT res:Numbers;IN a,b:Numbers); (*Вычитание из большего меньшего*)
VAR
  k,j,i:INTEGER;
BEGIN
  (*Вычитание разрядов b из разрядов а*)
  CopyNumber(res,a);
  i:=0;
  WHILE i<=b.len DO
    IF b.digit[i]<=res.digit[i] THEN
      DEC(res.digit[i],b.digit[i]);
    ELSE
      (*Поиск ненулевого разряда*)
      k:=i+1;
      WHILE res.digit[k]=0 DO
        INC(k);
      END;
      DEC(res.digit[k]);
      j:=i+1;
      WHILE j<k DO
        res.digit[j]:=9;
        INC(j);
      END;
      INC(res.digit[i],10-b.digit[i]);
    END;
    INC(i);
  END;
  WHILE res.digit[res.len]=0 DO
    DEC(res.len);
  END;
END Substruction;


PROCEDURE Multiply(OUT res:Numbers;IN a,b:Numbers); (*Умножение*)
VAR
  k,i,c:BYTE;
BEGIN
  (*Инициализация числа - результата*)
  k:=0;
  WHILE k<=a.len+1 DO
    res.digit[k]:=0;
    INC(k);
  END;
  (*Расчет произведения*)
  k:=0;
  WHILE k<=b.len DO
    i:=0;
    WHILE i<=a.len DO
      INC(res.digit[i+k],a.digit[i]*b.digit[k]);
      INC(res.digit[i+k+1],(res.digit[i+k] DIV 10));
      res.digit[i+k]:=SHORT(SHORT(res.digit[i+k] MOD 10)); 
      INC(i);
    END;
    INC(k);
    res.digit[a.len+k+1]:=0;
  END;
  (*Определение длины произведения*)

  IF res.digit[a.len+b.len+1]#0 THEN
   res.len:=SHORT(SHORT(a.len+b.len+1));
  ELSE
   res.len:=SHORT(SHORT(a.len+b.len));
  END;
END Multiply;

PROCEDURE Division(OUT rem,ost:Numbers; IN a,b:Numbers); (*Деление большего на меньшее нацело, с остатком*)
VAR
 L,R,k,c,t,Nz:INTEGER;
 sum:BYTE;
 flag:BOOLEAN;
PROCEDURE proverka():BOOLEAN;
VAR
 k:INTEGER;
BEGIN
  IF ost.digit[R+1]>0 THEN
    RETURN TRUE
  ELSE
  IF L<0 THEN 
    RETURN FALSE
  ELSE
   k:=R;
   WHILE k>=L DO
     IF ost.digit[k]>b.digit[b.len+k-R] THEN
        RETURN TRUE;
     END;
     IF ost.digit[k]<b.digit[b.len+k-R] THEN
        RETURN FALSE;
     END;
     DEC(k);
   END;
   RETURN TRUE;
  END;
 END;
END proverka;
BEGIN
ost:=a;
 IF a.len>=b.len THEN
 ost.digit[ost.len+1]:=0;
 R:=ost.len;
 L:=ost.len-b.len;
 IF ost.digit[R]<b.digit[b.len] THEN (*Сдвиг еще на один разряд*)
   DEC(R);DEC(L);
 rem.len:=a.len-b.len-1;
 ELSE
 rem.len:=a.len-b.len;
 END;
 Nz:=rem.len+1;

IF L>=0 THEN
 WHILE (R>=b.len) DO
   (*Вычисление очередной цифры*)
   sum:=0;
   WHILE proverka() DO
     (*Очередное вычитание*)
     k:=L;
     WHILE k<=R DO

      IF ost.digit[k]>=b.digit[k-L] THEN
        DEC(ost.digit[k],b.digit[k-L]);
      ELSE
       INC(ost.digit[k],10-b.digit[k-L]);
       DEC(ost.digit[k+1]);
      END;
      INC(k);
     END;
     INC(sum);
   END;
   (*Смещение отрезка*)
    DEC(R);
    DEC(L);
    DEC(Nz);
   rem.digit[Nz]:=sum;
END; (*Главный цикл*)
 WHILE (ost.len>0) & (ost.digit[ost.len]=0) DO
  DEC(ost.len);
 WHILE (rem.len>0) & (rem.digit[rem.len]=0) DO
  DEC(rem.len);
 END;
 END;
ELSE
 rem.len:=0;
 rem.digit[0]:=0;
END;
ELSE
 rem.len:=0;
 rem.digit[0]:=0;

END;


END Division;


PROCEDURE Division2(OUT res:Numbers;IN a:Numbers); (*Деление на 2*)
 VAR
   i,d:INTEGER;
BEGIN
  d:=0;
  i:=a.len;
  WHILE i>=0 DO
    d:=10*d+a.digit[i];
    res.digit[i]:=SHORT(SHORT(d DIV 2));
    d:=d MOD 2;
    DEC(i);
  END;
  IF res.digit[a.len]=0 THEN
   res.len:=a.len-1;
  ELSE
   res.len:=a.len;
  END;
END Division2;

PROCEDURE Minus_1(VAR a:Numbers); (*Вычитание единицы*)
VAR
  i:BYTE;
BEGIN
 i:=0;
 WHILE a.digit[i]=0 DO
   a.digit[i]:=9;
   INC(i);
 END;
 DEC(a.digit[i]);
 IF (a.digit[a.len]=0) THEN
  DEC(a.len);
 END;
END Minus_1;

PROCEDURE Plus_1(VAR a:Numbers); (*Прибавление единицы*)
VAR
   k:INTEGER;
BEGIN
  k:=0;
  a.digit[k]:=SHORT(SHORT(a.digit[k]+1));
  WHILE (k<a.len) & (a.digit[k]>9) DO
    a.digit[k]:=SHORT(SHORT(a.digit[k]-10));
    a.digit[k+1]:=SHORT(SHORT(a.digit[k+1]+1));
    k:=k+1;
  END;
  IF (k=a.len) & (a.digit[k]>9) THEN
     a.digit[k]:=SHORT(SHORT(a.digit[k]-10));
     a.len:=k+1;
     a.digit[a.len]:=1; 
  END;
END Plus_1;

PROCEDURE Equal(IN a,b:Numbers):BOOLEAN; (*Проверка равенства*)
VAR
  k:BYTE;
BEGIN
  IF a.len#b.len THEN
   RETURN FALSE;
  ELSE
   k:=0;
   WHILE k<=a.len DO
     IF a.digit[k]#b.digit[k] THEN
       RETURN FALSE;
     END;
     INC(k);
   END; 
   RETURN TRUE;
  END;
END Equal;

END Factor.