Введение
Длинная арифметика — это набор структур данных и алгоритмов, который позволяет нам работать с числами, значительно большими, чем могут хранить стандартные целочисленные типы.
В этой заметке мы используем простое представление на основе десятичных цифр.
Структура данных
Мы будем хранить число как vector<int>, где каждый элемент содержит одну десятичную цифру, а цифры хранятся в обратном порядке.
Например, если
то мы храним его как
То есть сначала идёт младшая значащая цифра.
Вывод
Чтобы вывести число, мы проходим по вектору от последней цифры к первой.
Ввод
Чтобы преобразовать обычное целое число в наш формат, мы многократно извлекаем его последнюю цифру.
Нормализация
После арифметических операций результат может содержать лишние ведущие нули в обратном представлении. Мы удаляем их с помощью вспомогательной функции.
Сложение
Чтобы сложить два длинных числа, мы складываем их цифры позиция за позицией, а затем распространяем переносы.
Вычитание
Чтобы вычесть два длинных числа, мы предполагаем, что
Затем мы вычитаем цифра за цифрой и обрабатываем заёмы.
Умножение
Чтобы перемножить два длинных числа, мы имитируем обычное школьное умножение.