Есть задачи, где стандартных типов данных просто не хватает. Нужно посчитать факториал числа 1000, зашифровать сообщение с ключом из 2048 бит, или проверить, является ли число из 300 цифр простым. Переменная типа long long в C++ вмещает максимум около 9.2 × 1018 — и это всё. Дальше начинается переполнение, потеря данных и неверные результаты.

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

Зачем нужна длинная арифметика

Это не академическая абстракция — длинная арифметика работает в реальных системах каждый день. Вот где она используется:

  • в криптографии: алгоритмы RSA, DSA, ECDSA оперируют числами длиной от 512 до 4096 бит;
  • в математических вычислениях: точный подсчёт факториалов, биномиальных коэффициентов, чисел Фибоначчи;
  • в финансовых системах: там, где недопустимо округление и нужна абсолютная точность;
  • в компиляторах и интерпретаторах: Python, Ruby, Haskell поддерживают целые числа произвольной длины нативно;
  • в научных расчётах: вычисление констант (числа π, e) до миллионов знаков.

Python, к слову, использует длинную арифметику "из коробки" — тип int в этом языке не имеет фиксированного ограничения. Напишите 2 ** 10000 — и получите точный ответ. В C++ или Java это потребует отдельной реализации или библиотеки.

Как хранить большое число

Первый вопрос при реализации длинной арифметики — представление числа в памяти. Чаще всего используют массив цифр или массив "слов" в некотором основании.

Самый понятный способ — хранить цифры в массиве, каждая в основании 10. Число 123456 превращается в массив [6, 5, 4, 3, 2, 1] (младший разряд первый — это удобнее для операций). Но это неэффективно по памяти и медленно на практике.

Профессиональные реализации используют основание 10^9 или 2^32 — каждый элемент массива хранит не одну цифру, а целый "блок" из девяти десятичных цифр или 32 бита. Это позволяет задействовать аппаратные возможности процессора по максимуму.

// Пример: представление числа в основании 10^9
typedef long long ll;
typedef vector<ll> BigInt;
const ll BASE = 1000000000LL; // 10^9

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

Основные операции и их алгоритмы

Сложение и вычитание

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

BigInt add(const BigInt& a, const BigInt& b) {
 BigInt result;
 ll carry = 0;
 for (int i = 0; i < max(a.size(), b.size()) || carry; i++) {
 ll cur = carry;
 if (i < a.size()) cur += a[i];
 if (i < b.size()) cur += b[i];
 result.push_back(cur % BASE);
 carry = cur / BASE;
 }
 return result;
}

Сложность — O(n), где n — количество "блоков" в числе. Вычитание аналогично, только вместо переноса работает заём (borrow).

Умножение: от O(n²) к O(n log n)

Умножение — вот где начинается интересное. Наивный алгоритм "в столбик" имеет сложность O(n²) и для чисел из тысяч цифр работает медленно.

Алгоритм Карацубы, предложенный математиком Анатолием Карацубой в 1960 году, снижает сложность до O(nlog₂3) ≈ O(n1.585). Идея — разбить каждое число на две половины и рекурсивно свести 4 умножения к 3.

Если \( A = A_1 \cdot B^m + A_0 \) и \( B = B_1 \cdot B^m + B_0 \), то:

$$A \cdot B = A_1 B_1 \cdot B^{2m} + \left[(A_1 + A_0)(B_1 + B_0) - A_1 B_1 - A_0 B_0\right] \cdot B^m + A_0 B_0$$

Три умножения вместо четырёх — на больших числах это даёт ощутимый прирост скорости.

Для ещё более длинных чисел (тысячи и миллионы цифр) применяют умножение через быстрое преобразование Фурье (FFT) — сложность O(n log n log log n). Это основа библиотек вроде GMP (GNU Multiple Precision Arithmetic Library).

Деление

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

Для очень больших чисел применяют метод Ньютона для нахождения обратного числа: если нужно вычислить \( \frac{A}{B} \), то находят приближение \( \frac{1}{B} \) итерационно, а потом умножают на A. Это быстрее для чисел в тысячи цифр.

Почему алгоритм Карацубы стал революцией
До 1960 года считалось, что умножение n-значных чисел принципиально требует O(n²) операций — это казалось нижней границей, заложенной в саму природу задачи. Андрей Колмогоров даже сформулировал это как гипотезу на семинаре в 1960 году. Карацуба, будучи студентом, опроверг её за неделю, придумав свой алгоритм. Колмогоров был настолько удивлён, что сам опубликовал результат от имени Карацубы. Этот случай стал одним из примеров того, как "очевидные" нижние оценки сложности могут оказаться неверными.

Типичные ошибки при реализации

Длинная арифметика — область, где легко ошибиться даже при понимании алгоритма. Вот наиболее распространённые проблемы.

Ведущие нули

После операций в старших позициях массива могут оставаться нули. Число [0, 0, 5] и [5] математически одинаковы, но при сравнении или выводе дадут разные результаты. Нужно всегда "нормализовывать" результат — удалять ведущие нули, оставляя минимум один элемент.

Ошибки со знаком

Если не разделять работу со знаком и с модулем числа — вычитание превращается в источник трудноуловимых багов. Классика: a - b при a < b даёт неверный результат, если знак не обрабатывается явно.

Переполнение промежуточных значений

При умножении двух элементов массива в основании 10^9 промежуточное произведение достигает 10^18 — это уже на границе long long. Если добавить перенос, можно выйти за пределы. Выход — использовать __int128 для промежуточных вычислений или аккуратно контролировать переполнение.

Неверный порядок цифр

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

Забытая нормализация после вычитания

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

Готовые инструменты или своя реализация

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

  • GMP (C/C++) — де-факто стандарт для высокопроизводительной арифметики произвольной точности;
  • Java BigInteger — встроен в стандартную библиотеку, удобен и достаточно быстр;
  • Python int — нативная поддержка без дополнительных библиотек;
  • OpenSSL BN — оптимизирован для криптографических операций.

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

Хорошо написанная реализация длинной арифметики на C++ для олимпиадных задач умещается в 100-150 строк кода и покрывает все базовые операции — сложение, вычитание, умножение, деление и сравнение.

Длинная арифметика — это не только про "большие числа ради больших чисел". Это про точность там, где она критична, про понимание архитектурных ограничений стандартных типов и про умение выбрать правильный алгоритм под задачу. Если вы когда-нибудь задавались вопросом, как браузер проверяет SSL-сертификат сайта — часть ответа лежит именно здесь, в операциях с числами длиной в тысячи бит. Что думаете: стоит ли знать внутреннее устройство таких алгоритмов рядовому разработчику, или достаточно просто уметь подключить библиотеку? Напишите в комментариях.

Оценка - 5.0 (1)
 Похожие публикации
2026-04-18 • Просмотров [ 19 ]