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

Виды целочисленной длинной арифметики

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

Классическая длинная арифметика

Основная идея заключается в том, что число хранится в виде массива его цифр.

Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), либо двоичная система счисления.

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

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

Структура данных

Хранить длинные числа будем в виде вектора чисел , где каждый элемент — это одна цифра числа.

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

Цифры будут храниться в векторе в таком порядке, что сначала идут наименее значимые цифры (т.е. единицы, десятки, сотни, и т.д.).

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

Вывод

Самое простое — это вывод длинного числа.

Сначала мы просто выводим самый последний элемент вектора (или , если вектор пустой), а затем выводим все оставшиеся элементы вектора, дополняя их нулями до символов:

(здесь небольшой тонкий момент: нужно не забыть записать приведение типа , поскольку в противном случае число будут беззнаковым, и если , то при вычитании произойдёт переполнение)

Чтение

Считываем строку в , и затем преобразовываем её в вектор:

Если использовать вместо массив ‘ов, то код получится ещё компактнее:

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

Сложение

Прибавляет к числу число и сохраняет результат в :

Вычитание

Отнимает от числа число () и сохраняет результат в :

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

Умножение длинного на короткое

Умножает длинное на короткое () и сохраняет результат в :

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

(Примечание: способ дополнительной оптимизации. Если скорость работы чрезвычайно важна, то можно попробовать заменить два деления одним: посчитать только целую часть от деления (в коде это переменная ), а затем уже посчитать по ней остаток от деления (с помощью одной операции умножения). Как правило, этот приём позволяет ускорить код, хотя и не очень значительно.)

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

Умножает на и результат сохраняет в :

Деление длинного на короткое

Делит длинное на короткое (), частное сохраняет в , остаток в :

Длинная арифметика в факторизованном виде

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

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

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

Длинная арифметика по системе простых модулей (Китайская теорема или схема Гарнера)

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

Как утверждает Китайская теорема об остатках, этого достаточно, чтобы однозначно хранить любое число в диапазоне от 0 до произведения этих модулей минус один. При этом имеется Алгоритм Гарнера, который позволяет произвести это восстановление из модульного вида в обычную, "классическую", форму числа.

Таким образом, этот метод позволяет экономить память по сравнению с "классической" длинной арифметикой (хотя в некоторых случаях не столь радикально, как метод факторизации). Крому того, в модульном виде можно очень быстро производить сложения, вычитания и умножения, — все за асимптотически однаковое время, пропорциональное количеству модулей системы.

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

Помимо этого, производить деление чисел в таком представлении по системе простых модулей не представляется возможным.

Виды дробной длинной арифметики

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

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

Число представляется в виде несократимой дроби , где и — целые числа. Тогда все операции над дробными числами нетрудно свести к операциям над числителями и знаменателями этих дробей.

Обычно при этом для хранения числителя и знаменателя приходится также использовать длинную арифметику, но, впрочем, самый простой её вид — "классическая" длинная арифметика, хотя иногда оказывается достаточно встроенного 64-битного числового типа.

Выделение позиции плавающей точки в отдельный тип

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

Приём, собственно, очень простой — вводится ещё одна целочисленная переменная, отвечающая за экспоненту, а после выполнения каждой операции дробное число "нормализуется", т.е. возвращается в отрезок , путём увеличения или уменьшения экспоненты.

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

Наконец, понятно, что не обязательно выбирать в качестве основания экспоненты. Исходя из устройства встроенных типов с плавающей точкой, самым выгодным представляется класть основание равным .

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

В основном мы будем рассматривать работу с целыми числами. Для хранения длинного числа можно использовать целочисленный массив, где в качестве элемента массива будет одна цифра числа. В 1м элементе массива будем хранить последнюю цифру числа, во 2м — предпоследнюю и т.д. до последней цифры. В 0м элементе можно хранить общее количество цифр в числе. В простейшем случае, для хранения числа 154 достаточно будет использовать следующую запись:

Элементом массива может быть не одна цифра, возможно использовать один элемент для хранения 4х цифр, т.к. мы понимаем, что на современных ЭВМ все операции как минимум 32-разрядные, поэтому время на сложение двух цифр такое же как и на сложение чисел, состоящих из 4х цифр. Поэтому часто используют порядок системы счисления base=10000 и фактически длинные числа хранятся как бы в 10000-й системе счисления, это позволяет увеличить скорость выполнения операций над ними в 3-4 раза.

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

Задачи, которые рассматриваются в данном разделе представляют собой базовый набор, достаточный для формирования первоначальных навыков овладения принципами длинной арифметики. Практически все задачи на длинную арифметику требуют чтения из файла и запись в файл длинных чисел, поэтому приведем реализацию этих функций в данном разделе, а в разборе задач будем их использовать:

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

Структура класса

Первое, что нужно решить — это то, как хранить наше число. Я храню его в виде массива цифр, в обратном порядке (это позволяет проще реализовывать все операции), сразу по 9 цифр в одном элементе массива (что позволяет сэкономить память):

В моей реализации будет сразу два представления нуля — в виде пустого вектора и в виде вектора с одним-единственным нулём.

Создание числа

Первое, что нужно научиться делать — это создавать число. Вот так оно преобразуется из строки, содержащей цифры:

Код процедуры удаления ведущих нулей прост до безобразия:

Также нам нужно уметь преобразовывать обычные числа в длинные:

Код преобразования из остальных типов еще проще, я не стал приводить его здесь.

Вывод числа

Теперь нам нужно научиться печатать наше число в поток и преобразовывать его в строку:

Сравнение чисел

Теперь нам нужно научиться сравнивать два числа друг с другом. Теория говорит, что для этого достаточно всего двух операций, остальные могут быть выведены на их основе. Итак, сначала научимся сравнивать два числа на равенство:

Теперь проверим, меньше ли одно число другого:

Здесь мы используем унарное отрицание, чтобы сменить знак числа. Также я для симметрии ввел унарный плюс:

Знания о том, почему нужно возвращать const big_integer, а не просто big_integer, а также о правилах выбора между дружественной функцией-оператором и оператором-членом класса, я подчерпнул из этой статьи.

Дальше все совсем просто:

Арифметические операции
Сложение

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

Здесь я избежал «дорогой» операции деления в случае, когда получившаяся «цифра» больше основания, по которому я работаю, путем простого сравнения.

Вычитание

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

Инкремент и декремент

Перед реализацией этих двух операций нам нужно реализовать сложение и вычитание с присвоением:

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

Умножение

Я не стал писать быстрое умножение Карацубы, а снова использовал «школьную» арифметику:

Деление

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

Теперь опишем само деление:

Здесь big_integer::divide_by_zero это пустой класс, унаследованный от std::exception .

Взятие остатка

Вообще-то в предыдущей операции остаток фактически хранится в переменной current . Но я задался вопросом определения знака остатка. Википедия говорит, что остаток от деления всегда положителен. Поэтому я написал такую версию этой операции:

Возведение в степень

Я использовал алгоритм быстрого возведения в степень. Он требует проверки числа на нечетность. Поскольку вычислять остаток от деления на 2, мягко говоря, было бы затратно, введем такие операции:

Теперь напишем само возведение:

Всё! Теперь можно вычислить, к примеру, 2 1000 , либо факториал 100: