Деление длинных чисел. Умножение длинного на короткое. Необходимые аппаратные средства для работы с длинной арифметикой

А что делать, если надо представить число, такое как, например, 29! = 8841761993739701954543616000000? Такое число не поместится ни в 64-х разрядный, ни тем более 32-х разрядный тип данных. Именно для работы с такими большими числами существует длинная арифметика.

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

Длинную арифметику также можно считать одним из разделов олимпиадного программирования, поскольку очень часто при решении задач, разрядности стандартных типов не хватает для представления конечного результата. При выборе языка программирования для олимпиадных нужд не маловажным является встроенный в него набор средств (готовых библиотек, реализованных классов). Многие языки (Java, Ruby, Python) имеют встроенную поддержку длинной арифметики, что в разы может сократить время написания программы.

Платформа.NET вплоть до 4.0 версии не имела встроенной поддержки работы с длинными числами. В 4-той же версии.NET обзавелась не только длинными, но и комплексными числами. Этот функционал доступен через сборку System.Numerics и типы BigInteger и Complex определенные в одноимённом с названием сборки пространстве имён.

Следует сказать, что структура BigInteger должна была , однако на тот момент она не была полностью готова, её реализация не отвечала всем потребностям (сюда можно отнести и проблемы производительности), поэтому было принято решение отложить её выход до.NET 4.0.

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

Общие понятия

123456789 10 = 1*10 8 + 2*10 7 + 3*10 6 + 4*10 5 + 5*10 4 + 6*10 3 + 7*10 2 + 8*10 1 + 9*10 0

В общем случае, любое число можно представить в виде:

A = a n-1 β n-1 + a n-2 β n-2 +…+a 1 β + a 0
где β – основание системы счисления, в которой мы представляем число, а коэффициенты a i удовлетворяют двойному неравенству 0 ≤ a i < β.

Представление числа напоминает представление многочлена, только вместо x в соответствующей степени имеем основание β в нужной степени. Как известно, многочлен a 0 + a 1 x + a 2 x 2 + … + a n x n удобно представлять в виде массива, элементы которого представляют коэффициенты a i , а индекс i - определяет соответствующую степень x. Длинное число хранится аналогично, осталось определиться с выбором основания β.

Например, то же самое число 123456789 можно представить в десятитысячной (β = 10 4) системе счисления следующим образом:

123456789 10 = 1*(10 4) 2 + 2345*(10 4) 1 + 6789*(10 4) 0

Представляя число 123456789 в десятитысячной системе счисления, мы получаем сразу два преимущества: во-первых, сокращаем количество потребляемой памяти, так как вместо массива из 9 чисел нам достаточно хранить массив из 3 чисел (1, 2345 и 6789), во-вторых, значительно уменьшаем время выполнения стандартных операций над длинными числами, поскольку за раз обрабатываем 4 разряда числа. В общем, компьютер одинаково быстро складывает одноразрядные и 32-разрядные числа, поэтому этим следует воспользоваться.

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

1. основание должно подходить под один из базовых типов данных;
2. основание должно быть как можно больше, чтобы уменьшить размер представления длинного числа и увеличить скорость операций с ними, но достаточно малого размера, чтобы все операции с коэффициентами использовали базовый тип данных;
3. для удобства вывода и отладки можно выбрать β как степень 10, β - степень двойки позволяет проводить быстрые операции на низком уровне.

BigInteger от Microsoft

Private static readonly BigInteger s_bnMinInt = new BigInteger(-1, new uint{ (uint) int.MinValue }); private static readonly BigInteger s_bnOneInt = new BigInteger(1); private static readonly BigInteger s_bnZeroInt = new BigInteger(0); private static readonly BigInteger s_bnMinusOneInt = new BigInteger(-1); internal int _sign; internal uint _bits; private const int knMaskHighBit = -2147483648; private const uint kuMaskHighBit = 2147483648U; private const int kcbitUint = 32; private const int kcbitUlong = 64; private const int DecimalScaleFactorMask = 16711680; private const int DecimalSignMask = -2147483648;
Структура содержит всего два экземплярных поля (_sign и _bits), остальные поля представляют собой константы и статические поля для чтения представляющие значения структуры для чисел -1, 0 и 1.

Можно предположить, что в переменной _sign хранится знак числа, а массив _bits содержит коэффициенты a i . Учитывая, что массив _bits имеет тип uint, можно так же предположить, что в качестве основания β взята степень двойки 2 32 (поскольку uint - 32 разрядное беззнаковое число).

Итак, попробуем подтвердить или опровергнуть наши предположения.

Конструктор, принимающий int, в качестве аргумента выглядит так:

Конструктор принимающий int

public BigInteger(int value) { if (value == int.MinValue) { this = BigInteger.s_bnMinInt; } else { this._sign = value; this._bits = (uint) null; } }

Конструктор, принимающий uint в качестве аргумента, выглядит следующим образом:

Конструктор принимающий uint

public BigInteger(uint value) { if (value <= (uint) int.MaxValue) { this._sign = (int) value; this._bits = (uint) null; } else { this._sign = 1; this._bits = new uint; this._bits = value; } }

Следующий конструктор, принимающий 64-х разрядное число со знаком (long) поможет ответить на вопрос о выборе основания системы счисления:

Конструктор принимающий long

public BigInteger(long value) { if ((long) int.MinValue <= value && value <= (long) int.MaxValue) { if (value == (long) int.MinValue) { this = BigInteger.s_bnMinInt; } else { this._sign = (int) value; this._bits = (uint) null; } } else { ulong num; if (value < 0L) { num = (ulong) -value; this._sign = -1; } else { num = (ulong) value; this._sign = 1; } this._bits = new uint; this._bits = (uint) num; this._bits = (uint) (num >> 32); } }

This._bits = new uint; this._bits = (uint) num; this._bits = (uint) (num >> 32);
В данном случае 64-х разрядное число num разбивается на два 32-х разрядных: (uint)num и (uint)(num >> 32). Первое число представляет собой последние 32 бита числа num, в то время как второе первые 32 бита (смещение вправо на n бит равносильно целочисленному делению на 2 n).

Давайте определим, как будет храниться число long.MaxValue = 2 63 -1 = 9223372036854775807 в структуре BigInteger . Для этого поделим его на 2 32:

Фактически (uint)long.MaxValue = 4294967295, (uint)(long.MaxValue >> 32) = 2147483647.

Значит, 9223372036854775807 = 2147483647*(2 32) 1 + 4294967295*(2 32) 0 , и BigInteger
будет представлен парой:

_sign = 1
_bits = {4294967295, 2147483647} // вспоминаем, что число храниться задом наперёд

Для длинного числа -1234567891011121314151617181920 имеем:

То есть число раскладывается по степеням 2 32 следующим образом:
1234567891011121314151617181920 = 15*(2 32) 3 + 2501550035*(2 32) 2 + 3243814879*(2 32) 1 + 4035623136*(2 32) 0

Значит, BigInteger будет представлен парой:

_sign = -1 // знак числа
_bits = {4035623136, 3243814879, 2501550035, 15}

Число, помещающееся в int диапазон, скажем, 17 будет храниться следующим образом:

_sign = 17
_bits = null

Исследовав конструкторы структуры BigInteger можно заключить:

1. если число помещается в int диапазон, то оно хранится в переменной _sign;
2. если число не помещается в int диапазон, то его знак хранится в переменной _sign (-1 – для отрицательного и 1 – для положительного), а массив _bits содержит коэффициенты a i разложения длинного числа с основанием 2 32 .

В общем, структура BigInteger является полноценной реализацией длинной арифметики на платформе.NET. При этом Microsoft постаралась максимально близко приблизить её к примитивным числовым типам: экземпляр BigInteger можно использовать точно так же, как и любой другой целочисленный тип. BigInteger перегружает стандартные числовые операторы для выполнения основных математических операций, таких как сложение, вычитание, деление, умножение, вычитания, отрицание и унарное отрицание. Можно также использовать стандартные числовые операторы для сравнения двух значений BigInteger друг с другом. Как и другие типы целого числа, BigInteger поддерживает битовые операторы And, Or, XOR, сдвиг влево и сдвиг вправо.

Для языков, не поддерживающих пользовательские операторы, структура BigInteger также предоставляет эквивалентные методы для выполнения математических операций. Это относится к методам Add, Divide, Multiply, Negate, Subtract и некоторым другим. Точно так же Microsoft поступило в реализации структуры Decimal .

Многие члены структуры BigInteger напрямую соответствуют членам других целых типов. Кроме того, BigInteger добавляет такие элементы как:

• IsEven – определяет является ли число чётным;
• IsPowerOfTwo - определяет является ли число степенью двойки;
• Sign - возвращает значение, указывающее знак числа BigInteger;
• Abs - возвращает абсолютное значение числа BigInteger;
• DivRem - возвращает частное и остаток от операции деления;
• GreatestCommonDivisor - возвращает наибольший общий делитель для двух чисел;
• Log - возвращает логарифм указанного числа в системе счисления с указанным основанием;
• Max / Min - возвращает наибольшее / наименьшее из двух чисел;
• ModPow - выполняет модульное деление числа, возведенного в степень другого числа;
• Pow - возводит значение BigInteger в заданную степень.

Пару слов о BigInteger в Mono и Java

То есть число 17 в Mono будет представлено парой:

_sign = 1 // знак числа
_bits = {17}

Аналогичная реализация BigInteger представлена в Java:

Public class BigInteger extends Number implements Comparable { int signum; int mag; private int bitCount = -1; private int bitLength = -1; private int lowestSetBit = -2; private int firstNonzeroByteNum = -2; private int firstNonzeroIntNum = -2; private final static long LONG_MASK = 0xffffffffL; }
Поскольку в Java отсутствуют беззнаковые типы, то массив mag имеет тип int. Соответственно представления длинного числа в Java и.NET будут отличаться. В.NET представление будет немного эффективнее, поскольку тип uint охватывает больший диапазон:

Конструктор принимающий long

private BigInteger(long val) { if (val < 0) { signum = -1; val = -val; } else { signum = 1; } int highWord = (int)(val >>> 32); if (highWord == 0) { mag = new int; mag = (int)val; } else { mag = new int; mag = highWord; mag = (int)val; } }

Производительность BigInteger

Int length = 1000000; BigInteger num = BigInteger.Parse("12345678910111213141516171819"); for (int i = 2; i < length; i++) { if (IsPrime(i)) num++; } Console.WriteLine(num);
Хотя, кажется, что в этом примере происходит изменение значения существующего объекта, это не так. Объекты BigInteger неизменяемы, то есть внутренне, общеязыковая среда выполнения фактически создает новый объект BigInteger и присваивает ему значение на единицу больше предыдущего.

В данном примере, можно поступить следующим образом: выполнить промежуточные операции, используя обычные числовые типы, а затем использовать BigInteger :

Int length = 1000000; BigInteger num = BigInteger.Parse("12345678910111213141516171819"); int temp = 0; for (int i = 2; i < length; i++) { if (IsPrime(i)) temp++; } num += temp; Console.WriteLine(num);
Другие числовые типы.NET Framework также являются неизменяемыми. Однако поскольку тип BigInteger не имеет верхней или нижней границы, его значения могут расти до очень больших значений и иметь измеримое влияние на производительность.

Вместо заключения

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

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

Основные потребители

• Компьютеры низкой разрядности, микроконтроллеры . Например, микроконтроллеры серии AVR имеют 8-битный регистр и 10-битный АЦП - так что при обработке информации с АЦП без длинной арифметики не обойтись.
• Криптография . Большинство систем шифрования данных, а также систем цифрофой подписи данных используют целочисленную арифметику по модулю m, где m - очень большое положительное натуральное чисто, не обязательно простое. Для примера RSA , Rabin или Эль Гамаль требуют наличие эффективных методов для операций перемножения и возведения в степень для чисел, имеющих порядки 10 309 . Впрочем довольно распространенные языки программирования, такие как ISO C и JAVA, умеют работать только с числами, заданной десятичной точности. В частности для C99 максимальная длина встроенного типа данных long long не превышает число 10 19 . Впрочем в некоторых других языках программирования, таких как Python, имеются встроенные библиотеки работы с большими числами.
• Математическое и финансовое ПО, требующее, чтобы результат вычисления на компьютере совпал до последнего разряда с результатом вычисления на бумаге. В частности, калькулятор Windows (начиная с Windows 95).
• Числа с плавающей запятой . В компьютерах числа с плавающей запятой представлены в виде n = *m*b x , где n - само число, - знак числа , m - мантисса , b - основание показательной функции , x - показатель степени . При обработке чисел повышенной точности, размеры мантиссы могут превысить аппаратно допустимые нормы. В этих случаях для работы с мантиссой можно использовать алгоритмы работы с большими числами.
• Одна из излюбленных тем спортивного программирования. С распространением стандартных библиотек для работы с длинными числами постепенно сходит на нет.

Необходимые аппаратные средства для работы с длинной арифметикой

Строго говоря, для реализации арифметики произвольной точности от процессора требуется лишь косвенная адресация; в арифметике фиксированной точности можно обойтись даже без неё. Тем не менее, определённые функции процессора ускоряют длинную арифметику, одновременно упрощая её программирование.

• Флаг переноса . Операции «сложить/вычесть с переносом», «циклический сдвиг через бит переноса ».
• Автоинкрементные и автодекрементные операции доступа к памяти.

Реализация в языках программирования

Как говорилось выше, языки программирования имеют встроенные типы данных, размер которых, в основном, не превышает 64 бита.
Десятичная длинная арифметика была реализована в языке программирования АЛМИР-65 на ЭВМ МИР-1 и в языке программирования АНАЛИТИК на ЭВМ МИР-2 .
Для работы с большими числами, однако, существует довольно много готовых оптимизированных библиотек для длинной арифметики.

• LibTomMath

Алгоритмы

Алгоритмы умножения

Базовый

Представляет собой алгоритм по школьному методу «в столбик». Занимает время O(N*M), где N, M - размеры перемножаемых чисел. Его алгоритм подробно описан в книге . Секция 4.3.1.

Умножение Карацубы

Этот алгоритм также описан в . Секция 4.3.3, часть А . Данный алгоритм представляет собой наиболее простую реализацию идеи разделения входных данных, которая стала базисной для нижеперечисленных алгоритмов.

Toom 3-Way

Идея впервые была предложена А. Л. Тоомом в , и заключается в разделении входных данных (множителей) на 3 равные части(для простоты все части считаем равными).
Рассмотрим данный алгоритм на следующем примере. Пусть дано два числа Y и X. Пусть определены операции над числами, размер которых равен 1/3 от размеров исходных чисел (см. рисунок). (предположим также, что числа занимают равную память и делятся ровно на 3 части, в противном случае дополним оба числа нулями до необходимых размеров.

Решая задачи, многим из нас приходилось сталкиваться с тем, что нам просто не хватало размерностей типов для, казалось, простейших операций: сложение, вычитание и умножение. Все эти операции знакомы Вам с ранних классов. Но что делать, если одну из этих операций необходимо применить для огромных чисел, скажем так 1000 знаков или более…(насколько хватит фантазии!). Данная статья поможет решить эту проблему.

Каждую арифметическую операцию рассмотри отдельно, предварительно написав на языке С++ код реализации. Прежде всего необходимо понимать, что бесконечно длинное число можно представить только в виде динамического массива, что нам и предстоит сделать. Но даже, если числа представлять в виде динамических массивов, некоторые ограничения будут накладываться все равно. Например, длинна такого числа будет ограничена объемом памяти компьютера. Также следует понимать, что при использовании операций сложения и умножения, результат будет занимать больше места в памяти компьютера, нежели операнды.

Сложение длинных чисел

Рассмотрим арифметическую операцию сложения, применяемую в длинной арифметике. Алгоритм этого нехитрого арифметического действия, на удивление, простой. Он выглядит так:

// определяем длину массива суммы if (size_a > size_b) length = size_a + 1; else length = size_b + 1; for (int ix = 0; ix < length; ix++) { b += a; // суммируем последние разряды чисел b += (b / 10); // если есть разряд для переноса, переносим его в следующий разряд b %= 10; // если есть разряд для переноса он отсекается } if (b == 0) length--;

“ Виновники торжества” – то есть числа, которые мы будем складывать, предположительно записаны в массивы a и b . Необходимо учесть, что они записаны “зеркально”, то есть первый элемент массива соответствует последней цифре соответствующего числа, второй элемент – предпоследней, и т.д. Размеры длин чисел хранятся в переменных size_a и size_b , но Вы можете использовать любые другие. Вы конечно же задумались: “Зачем здесь оператор выбора if, строки 2 — 5?” или “Для чего он здесь?”. В этом блоке кода мы определяем максимальную длину числа, полученного в результате суммирования. Ведь, чаще всего суммируемые числа, разной длинны, одно больше, другое меньше, а нам нужно выделить память так, чтобы каждое число вместилось.

Далее, в алгоритме, делаем так, как нас учили на уроках математики: сначала складываем отдельные разряды, начиная с конца, строка 9; делим получившуюся сумму на 10 и получаем целую часть от деления на десять, которую мы сразу прибавляем к следующему разряду, строка 10. В строке 11, мы отсекаем первый разряд полученного числа, если конечно он есть.
Вот и все. Главное не забыть, что число будет храниться в массиве b и выводить его следует с конца.

Вычитание длинных чисел

Вторая, наиболее используемая арифметическая операция – это вычитание. И эта часть статьи поможет Вам научиться писать алгоритмы вычитания больших и огромных чисел. Будем считать, что наши числа хранятся в массивах a и b , m и n – длинны этих чисел соответственно. Следует учесть, что числа записаны “зеркально”(см. выше). Конечно, если мы знаем какое число больше, то задача упрощается. Но мы можем и не знать этого. Тогда нам следует сперва найти, какое из чисел больше. Это нам понадобится для определения знака получившегося числа, то есть, если первое число меньше второго, то в ответе появится минус. И так, приступим к написанию первой части алгоритма, то есть определению большего числа. Алгоритм выглядит так:

Int k = 3; // если к == 3, значит числа одинаковой длинны length = size_a; if (size_a > size_b) { length = size_a; k = 1; // если к == 1, значит первое число длиннее второго } else if (size_b > size_a) { length = size_b; k = 2; // если к == 2, значит второе число длиннее первого } else // если числа одинаковой длинны, то необходимо сравнить их веса for (int ix = 0; ix < length;) // поразрядное сравнение весов чисел { if (a > b) // если разряд первого числа больше { k = 1; // значит первое число длиннее второго break; // выход из цикла for } if(b > a) // если разряд второго числа больше { k = 2; // значит второе число длиннее первого break; // выход из цикла for } } // конец for

Теперь поясню написанное. Сначала Вы можете увидеть, что переменной k придается значение 3. В данной части алгоритма переменная k является флагом результата проверки. Если числа равны, то k останется равно 3, если первое больше второго, то k примет значение 1, если второе больше первого, то k примет значение 2. Переменная length примет значение длинны большего числа. Теперь перейдем к обоснованию работоспособности этого алгоритма. Сравнение чисел происходит в два этапа. Сначала мы сравниваем длинны чисел: какое число длиннее, то и больше, строки 1 — 11. Если числа одинаковой длинны, то переходим к по разрядовому сравнению, строки 13 — 26. Начинаем по порядку сравнивать разряды начиная с самого старшего, так мы определим, больший вес числа. В этом и заключается суть и сложность первой части. Теперь перейдем ко второй части алгоритма — вычитание. Она выглядит так:

Int difference (int *x, int *y, int *z, int length) { for (int ix = 0; ix < (length - 1); ix++) // проход по всем разрядам числа, начиная с последнего, не доходя до первого { if (ix < (length - 1)) // если текущий разряд чисел не первый { x--; // в следующуем разряде большего числа занимаем 1. z += 10 + x; // в ответ записываем сумму значения текущего разряда большего числа и 10-ти } else // если текущий разряд чисел - первый z += x; // в ответ суммируем значение текущего разряда большего числа z -= y; // вычитаем значение текущего разряда меньшего числа if (z / 10 > 0) // если значение в текущем разряде двухразрядное { z++; // переносим единицу в старший разряд z %= 10; // в текущем разряде отсекаем ее } } return 0; }

Для самого вычитания удобно написать функцию, ведь нам тогда не придется писать два алгоритма для двух случаев: когда первое число больше второго, и наоборот. В массиве x мы содержим большее число, в массиве y – меньшее, в массиве z – результат. Алгоритм довольно простой: для каждого разряда мы добавляем 10, с учетом вычитания из старшего разряда — 1. Это делается для упрощения вычитания разрядов. Эта операция делается лишь в том случае, когда рассматриваемый разряд не является последним в массиве (первым в числе). После вычитания разрядов мы проверяем получившееся число в данном разряде в массиве z . Ответ запишется в массив z , причем “зеркальным” (см. выше) способом. Процедуру следует вызывать следующим образом:

If (k == 1) difference(a,b,c, length); - если первое число больше второго, if (k == 2) difference(b,a,c, length); - если второе число больше первого.

Теперь ответ будет храниться в массиве c все в том же “зеркальном” порядке. Вот мы и научились вычитать большие и огромные числа.

Умножение длинных чисел

Теперь перейдем к последней, но не менее важной теме нашей статьи – к произведению. Этот алгоритм чаще двух предыдущих можно встретить при решении задач. Собственно меньше демогогики. Перейдем непосредственно к самому алгоритму. Представляю Вашему вниманию алгоритм:

Length = size_a + size_b + 1; for (int ix = 0; ix < size_a; ix++) for (int jx = 0; jx < size_b; jx++) c += a * b; for (int ix = 0; ix < length; ix++) { c += c / 10; c %= 10; } while (c == 0) length-- ;

Вот так выглядит алгоритм задачи. Теперь попробуем “это” разобрать, точнее разобраться, как это работает. Сначала у нас имелось два числа в массивах a и b все в том же “зеркальном” (см. выше) виде. Длинны чисел хранятся в переменных size_a и size_b . В переменной length хранится длинна результирующего числа. Она будет равна либо сумме длин первоначальных чисел, либо этой сумме увеличенной на единицу. Но так, как мы не знаем точной длинны полученного числа, то возьмем длину побольше, то есть второй вариант. Теперь после этих не хитрых подсчетов, приступим к перемножению чисел. Будем их перемножать так, как нас учили в школе. Для этого запускаем два цикла: один до size_a , другой до size_b . После этих циклов вы можете увидеть еще один до length . благодаря ему в записи числа в массиве, в каждой ячейке массива мы получаем по одной цифре полученного числа. Последний цикл нужен, что бы узнать точную длину полученного числа, ведь предположенная нами длина числа может быть больше действительной. Ответ будет храниться в массиве c , все в том же “зеркальном” виде.
Вот и весь алгоритм. Проще его понять, когда он реализован на языке программирования, в нашем случае — это С++.

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

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

Задача сложения

Алгоритм решения

Задача решается таким же образом, как и при сложении в столбик. Производим сложение по каждому разряду отдельно. Если сумма больше 9, берем остаток от деления числа на 10 и не забываем прибавить количество десятков к следующему по старшинству разряду

Программный код

Задача вычитания

Данная программа осуществляет нахождения разности двух целых чисел не позволяющих хранить их в переменных допустимых типов какого-либо языка программирования.

Алгоритм решения

В отличии от задачи сложения, мы не можем выбирать по длине какого числа будем двигаться, поэтому прежде требует проверить конечный результат на его знак. Это освобождает от дальнейших трудностей. Непосредственно нахождения разности ничем не отличается от нахождения разности путем "вычитания в столбик".

Программный код