Длинная арифметика: сложение

Итак, сегодня мы напишем длинное сложение. Так что же это такое и для чего это нужно?

Довольно часто нужно работать с очень большими числами (до 10000 знаков). Ни один стандртный тип Delphi не может “вместить” в себя такое огромное число, что уж говорить про Turbo Pascal. В таких случаях на помощь приходит длинная арифметика.

Если Delphi не может сложить два больших числа, то это ещё не значит, что это не может сделать человек. Например, нужно посчитать сумму: 9223372036854775817 + 14685537510068352681. Эти числа не помещаются ни в int64, ни в extended. Точнее, extended может хранить только 19-20 значащих знаков, всё остальное округляется - потеря точности. Тем не менее, мы можем взять бумажку и сложить эти два числа в столбик:

Ничего сложного! А почему бы не научить компьютер делать то же самое? Научим!

Первый вопрос, который приходит в голову: “А где же хранить такие огромные числа?” А хранить их можно либо в массиве, либо в строке. И там и там есть свои плюсы и минусы: строки удобно использовать, т.к. все элементы ввода возвращают строки (Edit1.Text, Memo1.Lines[0] и т.д.), но скорость работы со строками очень мала и длина типа string ограничена - 255 символов; в массивах не очень удобно учитывать длину числа, нужно постоянно при получении строки конвертировать в массив, но с массивом можно работать намного быстрее и длина массива может быть больше. Вариант с массивом всё-таки предпочтительнее: длинная арифметика нужна там, где числа действительно большие, чем больше числа, тем дольше считать результат. Да и писать код работы с массивом намного проще.

Теперь перейдём непосредственно к алгоритму. Как мы считаем столбик: начинаем с конца и складываем по одному знаку. Если получившаяся сумма меньше 10 - то записываем её в соответствующую клетку ответа. Если же сумма больше либо равна 10, то разряд единиц пишем в соответствующую клетку ответа, а разряд десятков (заметьте, он может быть равен только 1) прибавляем к следующему ответу (т.е. переносим эту единицу левее). Также может получиться такая ситуация, когда при сложении двух чисел длиной n мы получаем число длиной n+1 (например 80+41=121). При сложении на бумажке мы этого не замечаем, однако этот аспект есть.

Ну вот мы и рассмотрели всем с детства знакомый алгоритм :) . Хранить числа в массивах прям так, как мы их видим на бумажке не очень удобно - длина чисел может быть разной, проще всего просто напросто развернуть наши числа и делать всё наоборот: начинать с первого символа и при получении результата больше 10 переносить 1 вправо :

Заметьте, если перевернуть наш ответ, то он будет равен ответу из 1 примера. Хоть и этот метод и кажется немного сложнее, но запрограммировать его намного проще…

Теперь обратимся непосредственно к реализации:

type
  digit = array [0..7899] of shortint ; 
  { Размер массива в Delphi можно сделать и больше }
  int = longint ;
var
  a, b, c : digit;
  na, nb, nc : int;

a и b - массивы, которые мы будем складывать, а na и nb - их длины. с - результирующий массив, nc - его длина. Нулевой элемент в массивах предназначен для хранения знака числа. Пускай там стоит 0, если число положительное, и 1 - если число отрицательное. Теперь нам нужно научить нашу программу считывать такие массивы с экрана и разворачивать их:

  { Процедура чтения длинного числа с экрана }
  procedure LongRead(var a: digit; var n: int);
  var
    c: char;
    code: integer;
    x: byte;
  begin
    { Заполняем массив нулями }
    fillchar(a,SizeOf(a),0);
    { Длина пока равна 0 }
    n:=0;
    { Пока не конец строки }
    while not eoln do
    begin
      { читаем по одному символу }
      Read(c);
      { Если символ первый и он равен quot;-quot; }
      if (n=0) and (c='-') then
      a[0]:=1 else { тогда число отрицательно }
      begin
        inc(n); { иначе увеличиваем длину }
        val(c,x,code); { и добавляем символ, ... }
        { ... если он корректный }
	if code=0 then a[n]:=x;
      end;
    end;
  end;

  { Процедура разворота длинного числа }
  procedure Invert(var a: digit; n: int);
  var
    i: integer;
    x: shortint;
  begin
    { Идём до середины }
    for i:=1 to n div 2 do
    begin
      { и попарно меняем символы местами }
      x:=a[i];
      a[i]:=a[n-i+1];
      a[n-i+1]:=x;
    end;
  end; 

Ну вот и всё. Теперь можно приступать к написанию самой процедуры сложения.

Правильнее всего для хранения единички, переходящей в следующий разряд, завести отдельную переменную - смещение. Так мы и сделаем:

  { Процедура сложения }
  procedure Add(a,b: digit; var c: digit;
                 na,nb: int; var nc: int);
  var
    i: integer;
    x,sm: byte;
    h: int;
  begin
    { Длина ответа не может быть меньше макс. из длин }
    if na>nb then nc:=na
             else nc:=nb;
    { Изначально смещение равно 0 }
    sm:=0;
    { Разворачиваем массивы а и b }
    Invert(a,na);
    Invert(b,nb);
    { Основной цикл }
    for i:=1 to nc do
    begin
      { Складываем цифры на текущих позициях + смещение }
      x:=a[i]+b[i]+sm;
      { Смещение учтено - обнуляем }
      sm:=0;
      { Если х - двузначное число }
      if x>=10 then
      begin
      { Делаем смещение }
        sm:=1; { Равносильно sm:=x div 10; }
        { Делаем число однозначным }
        x:=x-10; { Равносильно x:= x mod 10; }
      end;
      { Записываем на текущую позицию ответ }
      c[i]:=x;
    end;
    { Случай, когда  na=nb и nc=na+1 }
    if sm<>0 then
    begin
      inc(nc);
      c[nc]:=1;
    end;
    { Разворачиваем ответ обратно }
    Invert(c,nc);
  end;

Ну вот мы и рассмотрели целочисленное длинное сложение. Пока наше сложение умеет работать только с положительными числами, однако позже (после изучения длинного вычитания) мы модифицируем его. Процедуру чтения мы сразу сделали полнофункциональной - для целочисленной арифметики большего не нужно и изменять мы её не будем.

Надеюсь, эта статья хоть каплю помогла Вам разобраться в огромном океане алгоритмов…

Скачать юнит длинной арифметики ›

Другие Алгоритмы

• Алгоритмы · Структура данных бинарная куча
• Алгоритмы · Способы хранения графов в памяти компьютера
• Алгоритмы · Поиск в глубину
• Алгоритмы · Длинная арифметика: сложение
• Алгоритмы · Введение в рекурсию