Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. Более того, мы ограничены размером (величиной) чисел, с которыми можем работать. А если нам необходимо выполнить арифметические действия над очень большими числами, например,
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.
Мы можем считать, что наше "длинное" число представлено в 10000—10 системе счисления (десятитысячно-десятичная система счисления, приведите аналогию с восьмерично-десятичной системой счисления), а "цифрами" числа являются четырехзначные числа.
Возникают вопросы. Что за 9 в А [ 0 ] , почему число хранится "задом наперед" ? Ответы очевидны, но подождем с преждевременными объяснениями. Ответы на вопросы будут ясны из текста.
Примечание. Мы работаем с положительными числами!
Первая задача. Ввести "длинное" число из файла. Решение задачи начнем с описания данных.
Const MaxDig=1000;{Максимальное количество цифр — четырехзначных!}
 Osn=10000; {Основание нашей системы счисления, в элементах массива храним четырехзначные числа} Type Tlong=Array[0..MaxDig] Of Integer;
{Максимальное количество десятичных цифр в нашем числе?}
Алгоритм ввода "длинного" числа из файла рассмотрим на конкретном примере.
Пусть в файле записано число 23851674 и основанием (Osn) является 1000 (храним по три цифры в элементе массива А). Изменение значений элементов массива А в процессе ввода (посимвольного в переменную ch) отражено в табл. 2
Проанализируем таблицу  (и получим ответы на поставленные выше вопросы). 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 ] . Выписанный фрагмент программы "освобождает" место для этой цифры. В таблице отражены результаты работы этого фрагмента.
После этого остается только добавить текущую (считанную в 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 будет в массиве А представлено следующим образом:
 
При выводе "длинного" числа из массива нам необходимо вывести 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.
 Алгоритм имитирует привычное сложение столбиком, начиная с младших разрядов. И именно для простоты реализации арифметических операций над "длинными числами используется машинное представление "задом наперед".
Результат: С = 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 равен делимому. 
 
Итак, результат — целая часть частного — равен (Up + Down) Div 2, остаток от деления—разность
между значениями Ost и С. Нижнюю границу (Down) изменяем, если результат (С) меньше остатка, верхнюю (Up), если больше.
Усложним пример. Пусть А равно 27856, а -В — 354. Основанием системы счисления является не 10, а 10000.
 
Целая часть частного равна 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;

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 50
#define OSN 10000
void InputNum(const char *str, long a[MAX_LEN])
{
int j,i=strlen(str); long ln;
char *tmp=(char*)malloc(i>>3<<2+8);
strcpy(tmp, str); j=0;
do
{
tmp[i]=0; i-=4; if(i<0) i=0;
sscanf(&tmp[i], "%d", &ln), a[MAX_LEN - ++j]=ln;
} while (i);
while (j<MAX_LEN) a[MAX_LEN - ++j]=-1;
free(tmp);
}
void OutputNum(long a[MAX_LEN])
{
int i,fn=0;
while (fn<MAX_LEN && a[fn]==-1) fn++;
if(fn==MAX_LEN) return;
for (i=fn;i<MAX_LEN; i++)
printf((i==fn) ? "%d" : "%04d", a[i]);
}
int Less(long a[MAX_LEN], long b[MAX_LEN])
{
int i=-1;
while (++i<MAX_LEN)
if (a[i]==b[i]) continue;
else return a[i]<b[i] ? 1 : -1;
return 0;
}
int SubNum(long ta[MAX_LEN], long tb[MAX_LEN], long c[MAX_LEN])
{
long *a, *b, tmp; int j,i,to=MAX_LEN-1,minus=0;
if (Less(ta,tb)==1) a=tb, b=ta, minus=1; else a=ta, b=tb;
for (i=0;i<MAX_LEN;i++) c[i]=a[i];
for (i=MAX_LEN-1; ; i--)
{
if (b[i]==-1) break;
tmp=c[i]-b[i];
if(tmp<0)
{
tmp+=OSN, j=i;
while (c[j-1]-1<0 && j>0) c[j-1]+=-1+OSN, j--;
c[j-1]--;
}
c[i]=tmp;
}
i=0; while (c[i]<=0 && i<MAX_LEN-1) c[i++]=-1;
return minus;
}
int main()
{
char *szA=(char*)malloc(500);
char *szB=(char*)malloc(500);
int g;
long a[MAX_LEN], b[MAX_LEN], c[MAX_LEN];
printf("a = "), scanf("%s", szA), printf("b = "), scanf("%s", szB);
InputNum(szA,a), InputNum(szB,b);
g=SubNum(a,b,c);
printf("a - b = "); if(g) printf("-"); OutputNum(c);
printf("\n"); free(szA), free(szB);
return 0;
}
Результат виконання.
a=66555221236121
b=12312464143123
a-b=54242757092998
Блок-схеми підпрограм та функцій.
А) Блок-схема алгоритму введення довгого числа.





Б) Алгоритм виведення довгого числа.

Г) Блок-схема алгоритму віднімання довгих чисел.


Г) алгоритм додавання довгих чисел


В) Блок-схеми алгоритмів порівняння довгих чисел.

Текст програми
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <ctype.h>
#define max 50
#define osn 1000
long int *vvid( char mas[ ])
{
long int *a, res, a22;
char ch;
a = (long int*)malloc(max*sizeof(int));
int i = 0;
int j = 0;
for(i = 0; i < max; i++)
a[i] = 0;
for(j = 0; mas[j] != 0; j++)
{
if ( isdigit(mas[j]) )
{
for (i = a[0]; i >= 1; i--)
{
a[i + 1] = a[i + 1] + (a[i] * 10) / osn;
a[i] = a[i] * 10 % osn;
}
ch = mas[j];
a22 = atoi(&ch);
a[1] = a[i+1] + a22;
if (a[a[0] + 1] > 0)
a[0]++;
}
}
return a;
}
void vyvid(long int *b)
{
long int res;
int N = 0;
int NN = 1;
int p;
int b_osn = b[0];
int i = 0;
for(i = b[0]; i>=1 ; i--)
{
N = b[i];
if (N == 0)
NN = 0;
for (p = 1; N > 0; p = p*10)
N = N / 10;
while (osn - p != 0)
{
if (b[0] == i)
break;
printf("%c",'0');
p = p*10;
}
if (NN == 1)
{
res = b[i];
printf("%d",res);
}
NN = 1;
N = 0;
}
}
long int *sum(long int a[], long int b[])
{
int k;
long int *c;
c = (long int*)malloc(max*sizeof(int));
int i;
for( i = 0; i < max; i++)
c[i] = 0;
if(a[0] > b[0])
k = a[0];
else
k = b[0];
for(i = 1; i <= k; i++)
{
c[i + 1] = (c[i] + a[i] + b[i]) / osn;
c[i] = (c[i] + a[i] + b[i]) % osn;
}
if (c[k + 1] == 1)
c[0] = k + 1;
else
c[0] = k;
return c;
}
int nerivne(long int a[], long int b[])
{
int e,i=0;
while (i++<max)
if (a[i]==b[i]) {e=0; continue;}
else {break; e=1;}
return e;
}
int main()
{
long int *a = 0, *b = 0, *c = 0, g;
char mas1[100], mas2[100];
puts("vvedit 1 chyslo:");
gets(mas1);
a = vvid(mas1);
puts("vvedit 2 chyslo:");
gets(mas2);
b = vvid(mas2);
vyvid(a);
printf("\n");
vyvid(b);
c = sum(a,b);
printf("\na + b =");
vyvid(c);
printf("\na nerivne b:");
g=nerivne(a,b);
if(g)
puts("true");
else
puts("false");
system("PAUSE");
getch();
return 0;
}
int More(long int a[], long int b[])
{
int e;
if (a[0] < b[0])
e = 0;
else
e = 1;
for (long i = a[0]; i >= 1; i--)
{
if (a[i] == b[i])
continue;
else
if (a[i] < b[i])
e = 0;
else
e = 1;
}
return e;
}