"Длинная" арифметика

 С.М.Окулов

Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. Более того, мы ограничены размером (величиной) чисел, с которыми можем работать. А если нам необходимо выполнить арифметические действия над очень большими числами, например,

30! == 265252859812191058636308480000000?

В таких случаях мы сами должны позаботиться о представлении чисел в машине и о точном выполнении арифметических операций над ними.

Числа, для представления которых в стандартных компьютерных типах данных не хватает количества двоичных разрядов, называются "длинными". Реализация арифметических операций над такими "длинными" числами получила название "длинной" арифметики.

Организация работы с "длинными" числами во мно­гом зависит от того, как мы представим в компьютере эти числа. "Длинное" число можно запи­сать, например, с помощью массива десятичных цифр, количество элементов в таком массиве равно количеству значащих цифр в "длинном" числе. Но если мы будем реализовывать арифметические операции над этим числом, то размер массива должен быть достаточным, чтобы разместить в нем и результат, например, умножения.

Существуют и другие представления "длинных" чисел. Рассмотрим одно из них.

Представим наше число

30! = 265252859812191058636308480000000

в виде:

30! =2- (104)8+6525• (104)7+2859• (104) +
+
  8121- (104)5  + 9105(104)4+
+  8636- (104)3 + 3084 • (104)2 +
+  8000- (104)1 + 0000- (104)0.
 Это представление наталкивает на мысль о массиве, представленном в табл. 1.

Номер элемента в массиве А 0 1 2 3 4 5 6 7 8 9
Значение 9 0 8000 3084 8636 9105 8121 2859 6525 2

Мы можем считать, что наше "длинное" число представлено в 10000—10 системе счисления (десятитысячно-десятичная система счисления, приведите аналогию с восьмерично-десятичной системой счисления), а "цифрами" числа являются четырехзначные числа.

Возникают вопросы. Что за 9 в А [ 0 ] , почему число хранится "задом наперед" ? Ответы очевидны, но подождем с преждевременными объяснениями. Ответы на вопросы будут ясны из текста.

Примечание. Мы работаем с положительными числами!

Первая задача. Ввести "длинное" число из файла. Решение задачи начнем с описания данных.

Const MaxDig=1000;
{Максимальное количество цифр — четырехзначных!}

 Osn=10000; {Основание нашей системы счисления, в элементах массива храним четырехзначные числа} 
Type Tlong=Array
[0..MaxDig] Of Integer;

{Максимальное количество десятичных цифр в нашем числе?}

Алгоритм ввода "длинного" числа из файла рассмотрим на конкретном примере.

Пусть в файле записано число 23851674 и основанием (Osn) является 1000 (храним по три цифры в элементе массива А). Изменение значений элементов массива А в процессе ввода (посимвольного в переменную ch) отражено в табл. 2

А[0]

А[1]

А[2]

А[3]

ch

Примечание

3

674

851

23

-

Конечное состояние

0

0

0

0

2

Начальное состояние

1

2

0

0

3

1-й шаг

1

23

0

0

8

2-й шаг

1

238

0

о

5

3-й шаг

2

385

2

0

1

4-й шаг: старшая цифра элемента А [1] перешла в пока "пустой" элемент А[2]

2

851

23

0

6

5-й шаг

2

516

238

0

7

6-й шаг

3

167

385

2

4

7-й шаг

3

574

851

23

 

 

Проанализируем таблицу  (и получим ответы на поставленные выше вопросы).
1. В А [ 0 ] храним количество задействованных (ненулевых) элементов массива А — это уже очевидно. 2. При обработке каждой очередной цифры входного числа старшая цифра элемента массива с номером
i становится младшей цифрой числа в элементе i + 1, а вводимая цифра будет младшей цифрой числа из А [ 1 ] . В результате работы нашего алгоритма мы получили число, записанное "задом наперед".

Примечание (методическое): Можно ограничиться этим объяснением и разработку процедуры вынести на самостоятельное задание. Можно продолжить объяснение. Например, выписать фрагмент текста процедуры перенос старшей цифры из A[i]B младшую цифру А [ i +1 ], т.е. сдвиг уже введенной части числа на одну позицию вправо:

For i:=A[0] DownTo 1 Do Begin
      A[i+l]:=A[i+l]+(Longint(A[i])*10) Div Osn;
      A[i]:=(LongInt(A[i])*10) Mod Osn;
End;

Пусть мы вводим число 238516 74 и первые 6 цифр уже разместили "задом наперед" в массиве А. В символьную переменную ch считали очередную цифру "длинного" числа — это "7". По нашему алгоритму эта цифра "7" должна быть размещена младшей цифрой в А [ 1 ] . Выписанный фрагмент программы "освобождает" место для этой цифры. В таблице отражены результаты работы этого фрагмента.

i

А[1]

А[2]

А[3]

ch

2

516

238

0

7

2

516

380

2

  

1

160

385

2

 


После этого остается только добавить текущую (считанную в ch ) цифру "длинного" числа к А [ 1 ] и изменить значение А [ 0 ].

В конечном итоге процедура должна иметь следующий вид:

Procedure ReadLong(Var A:Tlong);
  Var ch:char;i:Integer;
   Begin
      FillChar(A,SizeOf(A)
, 0) ;
     
Read(ch);
      While Not(ch In ['0'..'9']) Do Read(ch);
          
{пропуск не цифр во входном файле}
     
While ch In ['0'..'9'] Do Begin
          For i:=A[0] DownTo
1 Do Begin
          
{"протаскивание" старшей цифры в числе из A[i]
              в младшую цифру числа из
A[i+l]}
             A[i+l]:=A[i+l]+(LongInt(A[i]
)*10) Div Osn;
             A[i]:=(LongInt(A[i]
)*10) Mod Osn;
          End;
         A[1]:=A[l]+Ord(ch)-Ord(
'0' ) ;
           {добавляем младшую цифру к числу из А[1]}
        
If A[A[0]+1]>0 Then Inc(A[0]);
        
{изменяем длину, число задействованных
           элементов массива А}
        
Read(ch) ;
        End;
End;

Вторая задача. Вывод "длинного" числа в файл или на экран.

Казалось бы, нет проблем — выводи число за числом. Однако в силу выбранного нами представления "длинного" числа мы должны всегда помнить, что в каждом элементе массива хранится не последовательность цифр "длинного" числа, а значение числа, записанного этими цифрами. Пусть в элементах массива хранятся четырехзначные числа. Тогда "длинное" число 128400583274 будет в массиве А представлено следующим образом:

А[0]

А[1]

А[2]

А[3]

3

3274

58

1284

 

При выводе "длинного" числа из массива нам необходимо вывести 0058, иначе будет потеря цифр. Итак, незначащие нули также необходимо выводить. Процедура вывода имеет вид:

Procedure WriteLong(Const A:Tlong);
 
Var ls,s:String;
     
  i:Integer;
 Begin
     Str (Osn Div
10,Is) ;
     Write(A[A[0]];{выводим старшие цифры числа}
     
For i:=A[0]-l DownTo 1 Do Begin
           Str(A[i],s)
;
          
While Length(s)<Length(Is) Do s:='0'+s;
           
{дополняем незначащими нулями}
          
Write (s) ;
      End;
      Writein;
End;

Третья задача. Предварительная работа по описанию способа хранения, вводу и выводу "длинных" чисел выполнена.

У нас есть все необходимые "кирпичики", например, для написания программы сложения двух "длинных" положительных чисел. Исходные числа и результат храним в файлах. Назовем процедуру сложения SumLongTwo.

Тогда программа ввода двух "длинных" чисел и вывода результата их сложения будет иметь следующий вид:

Var A,B,C:Tlong;
Begin
  Assign(Input,'Input.txt'); Reset(Input) ;
 
ReadLong(A);ReadLong(B) ;
  Close (Input) ;
 
SumLongTwo(A,B,C);]
  Assign(Output,'Output.txt') ;
 
Rewrite(Output);
 
WriteLong(C) ;
  Close(Output) ;
End.

Алгоритм процедуры сложения можно объяснить на простом примере. Пусть А = 870613029451, В = 3475912100517461.

i

A[i]

B[i]

С[1]

С[2]

С[3]

С[4]

1

9451

7461

6912

1

0

0

2

1302

51

6912

1354

0

  

3

8706

9121

6912

1354

7827

1

4

0

3475

6912

1354

7827

3476

 
Алгоритм имитирует привычное сложение столбиком, начиная с младших разрядов. И именно для простоты реализации арифметических операций над "длин
ными числами используется машинное представление "задом наперед".

Результат: С = 3476782713546912.

Ниже приведен текст процедуры сложения двух "длинных" чисел.

Procedure SumLongTwo(A,B:Nlong; Var C:Tlong);
  Var i,k:Integer;
    Begin
       FillChar(C,SizeOf (C)
,0) ;
      
If A[0]>B[0] Then k:=A[0] Else k:=B[0];
     
  For i:=l To k Do
            Begin
С [i+1]:=(C[i]+A[i]+B[i]) Div Osn;
                      C[i]:=(C[i]+A[i]+B[i]) Mod Osn;
                     {Есть ли в этих операторах ошибка?}
            
End;
             If C[k+l]=0 Then C[0]:=k Else C[0]:=k+l;
End;

Четвертая задача. Реализация операций сравнения для "длинных" чисел (А=В, А<В, А>В, А<В, А>В).

Function Eq(A,B:TLong):Boolean;
Var i:Integer;
  Begin
    Eq:=False;
    If A[0]OB[0] Then Exit
       Else Begin
                i:=l;
               While (i<=A[0]) And (A[i]=B[i]-) Do Inc(i);
               Eq:==(i=A[0]+l)
;
           End;
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;

Остальные функции реализуются через функции Eq и More.

Function Less(A,B:Tlong):Boolean;{A<B}
 Begin
    Less:=Not(More(A,B) Or Eq(A,B));
 
End;

Function More_Eq(A,B:Tlong):Boolean;
   Begin
       More_Eq:=More(A,B) Or Eq(A,B);
    End;

И, наконец, последняя функция А<В.

Function Less_Eq (A, B:Tlong) : Boolean;
    Begin
         Less_Eq:-Not(More(A,B)
) ;
    End;

Для самостоятельного решения может быть предложена следующая, более сложная, задача. Требуется разработать функцию, которая выдает 0, если А больше В, 1, если А меньше В, и 2 при равенстве чисел. Но сравнение должно быть выполнено с учетом сдвига. О чем идет речь? Поясним на примере. Пусть А равно 56784, а В — 634. При сдвиге числа В на 2 позиции влево функция должна сказать, что В больше А, без сдвига, что А больше В. Другой пример. При А равном 56700, а В — 567 и сдвиге 2 функция должна "сказать" , что числа равны. Решение может иметь следующий вид:

Function More(Const А, В: Tlong;
                     
Const sdvig: Integer): Byte;
      Var i: Integer;
         Begin
            If A[0]>(B[0]+sdvig) Then More:=0
                Else If A[0]<(B[0]+sdvig) Then More:=l
                       Else Begin
                            i:=A[0];
                            While (i>sdvig) And
                                      (A[i]=B[i-sdvig]
) Do Dec(i);
                          
  If i=sdvig Then Begin
                             More:=0;
                             {совпадение чисел с учетом сдвига}
            
For i:=l To sdvig Do If A[i]>0 Then Exit;
             More
:=2;
             {числа равны, "хвост" числа А равен нулю}
  
End
       Else More:=Byte(A[i]<B[i-sdvig]
) ;
End;
  End;

Пятая задача. Умножение длинного числа на короткое. Под коротким понимается целое число типа Longlnt.

Процедура очень походит на процедуру сложения двух длинных чисел.

Procedure Mul(Const A: TLong;Const К:
   
Longlnt;Var С: TLong) ;
      Var i: Integer;
       
{результат - значение переменной С}
         
Begin
             FillChar
(С, SizeOf (С), 0) ;
              
If K=0 Then Inc(С[0]){умножение на ноль}
                 
Else Begin
                      For i:==l To A[0] Do Begin
                       C[i+l]:=(LongInt(A[i]
)*K+C[i]) Div Osn;
                       C[i]:=(LongInt(A[i]
)*K +C[i]) Mod Osn;
                      End;
               If C[A[0]+1]>0 Then C[0]:=A[0]+1
                   Else C[0]:=A[0]
;
                  {определяем длину результата}
     
End;
End;

Шестая задача. Вычитание двух длинных чисел с учетом сдвига.

Если понятие сдвига пока не понятно, то оставьте его в покое, на самом деле вычитание с учетом сдвига потребуется при реализации операции деления. В начале выясните логику работы процедуры при нулевом сдвиге.

Введем ограничение: число, из которого вычитают, больше числа, которое вычитается. Работать с "длинными" отрицательными числами мы не умеем.

Процедура была бы похожа на процедуры сложения и умножения, если бы не одно "но" — заимствование единицы из старшего разряда вместо переноса единицы в старший разряд. Например, в обычной системе счисления мы вычитаем 9 из 11 — идет заимствование 1 из разряда десятков, а если из 10000 вычитаем 9 — процесс заимствования несколько сложнее.

Procedure Sub (Var A: TLong;
                        Const B: TLong;
                        Const sp: Integer);
 
   Var i,j: Integer;

    {из А вычитаем В с учетом сдвига sp, результат вычитания в А}
   
Begin
         For i:=l To B[0] Do Begin Dec(A[i+sp], B[i]);
         
j:=i;{*}

     {реализация сложного заимствования}
     
while (A[j+sp]<0) and (j<=A[0}) Do
            Begin
{*}
               
Inc(A[j+sp], Osn) ;
                Dec(A[j+sp+l]);Inc(j) ; {*}
           
end; {*}
             {Реализация простого заимствования.
               Если операторы, отмеченные *, заменить
               на нижеприведенные операторы в фигурных скобках, то,
               по понятным причинам, логика не будет работать
               при всех исходных данных. Можно сознательно сделать
               ошибку и предложить найти ее — принцип "обучение через ошибку"}
    
{If A[i+sp]<0 Then Begin Inc(A[i+sp], Osn);
           
Dec (A[i+sp+l]);End;}
    
End;
 
  i : =A [ 0 ] ;
       While (i>l) And (A[i]=0) Do Dec(i);
   A[0]:=i;
 
{корректировка длины результата операции}
End;

Рекомендуется выполнить трассировку работы данной процедуры, например, для следующих исходных данных. Число А равно 100000001000000000000, число В - 2000073859998.

Седьмая задача. Деление двух длинных чисел, т.е. нахождение целой части частного и остатка.

Написать исходную (без уточнений) часть логики не составляет труда. Это:

Procedure Long_Div_Long(Const А, В: TLong;
                                         
Var Res, Ost: TLong);
    Begin
        FillChar(Res, SizeOf(Res),
0);Res[0]:=1;
        FillChar(Ost, SizeOf(Ost),
0);0st[0]:=1;
       
Case More(A, B, 0) Of
           0:
Begin MakeDel(A, B, Res, Ost);
       
End;

{А больше В, пока не знаем, как выполнять операцию - "выносим" в процедуру}
         1:
Begin Ost:=A; End;{А меньше В}
         2:
Begin Res[l]:=l; End;{А равно В}
    
End;

End;

А дальше? Дальше начинаются проблемы. Делить столбиком нас научили в школе. Например:

    1000143123567   |   73859998
 -    73859998         
|   13541 (Целая часть частного)
      261543143
 -   221579994
        399631495
     - 369299990
          303315056
      -   295439992
               78750647
           -  73859998
                 4890649 (Остаток)

Что мы делали? На каждом этапе в уме подбирали цифру (1, 3, 5 и т.д.), такую, что произведение этой цифры на делитель дает число меньшее, но наиболее близкое к числу... Какому? Это трудно сказать словами, но из примера ясно. Зачем нам это делать в уме, пусть делает компьютер. Однако упростим пример, оставим его для тестирования окончательной логики процедуры, тем более что и числа "длинные". Пусть число А будет меньше В • 10, тогда в результате (целой части деления) будет одна цифра. Например, А равно 564, а В — 63 и простая десятичная система счисления. Попробуем подобрать цифру результата, но не методом прямого перебора, а методом деления отрезка пополам. Пусть Down — верхняя граница интервала изменения подбираемой цифры, Up — нижняя граница интервала, Ost равен делимому. 

Down

Up

С=В • ( (Down+Up) Div 2)

Ost=564

0

10

315 = 63 • ( (0 + 10) Div 2)

C<Ost

5

10

441 = 63 • ( (5 + 10) Div 2)

C<Ost

7

10

504 = 63 • ( (7 + 10) Div 2)

C<Ost

8

10

567 = 63 • ( (8 + 10) Div 2)

C<Ost

8

9

504 = 63 • ( (8 + 9) Div 2)

C<Ost

 

Итак, результат — целая часть частного — равен (Up + Down) Div 2, остаток от деления—разность

между значениями Ost и С. Нижнюю границу (Down) изменяем, если результат (С) меньше остатка, верхнюю (Up), если больше.

Усложним пример. Пусть А равно 27856, а -В — 354. Основанием системы счисления является не 10, а 10000.

Down

Up

С

Ost=27856

0

10000

1770000

С>Ost

0

5000

885000

C>OOst

о

2500,

442500

C>Ost

0

1250

221250

C>Ost

0

625

110448

C>Ost

0

312

55224

C>Ost

о

156

27612

C<Ost

78

156

41418

C>Ost

78

117

34338

C>Ost

78

97

30798

C>Ost

78

87

29028

C>Ost

78

82

28320

C>Ost

78

80

27966

C>Ost

78

79

27612

C<Ost

 

Целая часть частного равна 78, остаток от деления — 27856 минус 27612, т.е. 244.

Пора приводить процедуру. Используемые "кирпичики": функция сравнения чисел (More) с учетом сдвига и функция умножения длинного числа на короткое (Mul) описаны выше.

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;

Осталось разобраться со сдвигом, значением переменной sp в нашем изложении. Опять вернемся к обычной системе счисления и попытаемся разделить, например, 635 на 15. Что мы делаем? Вначале делим 63 на 15 и формируем, подбираем в уме первую цифру результата. Подбирать с помощью компьютера мы научились. Подобрали — это цифра 4, и это старшая цифра результата. Изменим остаток. Если вначале он был 635, то сейчас стал 35. Вычитать с учетом сдвига мы умеем. Опять подбираем цифру. Вторую цифру результата. Это цифра 2 и остаток 5. Итак, результат (целая часть) 42, остаток от деления 5. А что изменится, если основанием будет не 10, а 10000 ? Логика совпадает, только в уме считать несколько труднее, но ведь у нас же есть молоток под названием компьютер — пусть он вбивает гвозди.

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;

Методические рекомендации. Представленный материал излагается на четырех занятиях по известной схеме:

10—15-минутное изложение идей, а затем работа учащихся под руководством преподавателя.

1-е занятие. Ввод, вывод и сложение длинных чисел (задачи 1, 2, 3).

2-е занятие. Функции сравнения (задача 4).

3-е занятие. Умножение и вычитание длинных чисел (задачи 5, 6).

4-е занятие. Деление длинных чисел (задача 7). Безусловно, эта схема не догма. В зависимости от уровня подготовки учащихся на самостоятельное выполнение может быть вынесена значительная часть материала. Замечу только, что в силу сложившейся традиции в ряде случаев допускаются при изложении сознательные ошибки. В результате работы каждый учащийся должен иметь собственный модуль для работы с "длинными" числами.

Темы для исследований:

  1. Решение задач: поиск наибольшего общего делителя двух "длинных" чисел; поиск наименьшего общего кратного двух "длинных" чисел; извлечение квадрат­ного корня из "длинного" числа и т.д.

  2. "Длинные" числа могут быть отрицательными. Как из­менятся описанные выше операции для этого случая?

  3. Для хранения "длинных" чисел используется не массив, а стек, реализованный с помощью списка. Модифицировать модуль работы с "длинными" числами.

TopList