Ниже — краткое сравнение практичных алгоритмов сложения больших целых (миллионы цифр) по времени и памяти и объяснение, почему «школьный» по-символьный приём часто неэффективен.
Алгоритмы (описание, асимптотика, требования по памяти)
- Школьный посимвольный (символ за символом, base 10):
- Время: $T=\Theta (n)$ операций над символами, но константа велика (конвертация символ→число, ветвления, обработка ASCII).
- Память: хранение строк ~ $O(n)$ байт на число.
- Минус: тяжёлые константы, плохое использование машинного слова и кэша.
- Лимбовое (word-based) последовательное (рекомендуемая базовая реализация):
- Представление: разбить число на лимбы длиной $w$ бит (или $k$ десятичных цифр; база $B=2^w$ или $10^k$).
- Число лимбов: с десятичных цифр $n$ можно взять $m=\lceil n/k\rceil$ (или битово $m=\lceil \frac{n{\log }_{2}10}{w}\rceil$).
- Время: $T=C\cdot m=\Theta (m)$ (один сложение+перенос на лимб), где $C$ — небольшая константа (исп. инструкция ADC).
- Память: $O(m)$ машинных слов на операнд и $O(m)$ на результат (итого ≈ $3m$ слов если хранить всё).
- Плюс: малые константы, хорошая кэш-локальность.
- SIMD/векторизация:
- Выполняем параллельно несколько лимбов за инструкцию; требуется дополнительно решать переносы.
- Время практическое: уменьшение константы на лимб; полное разрешение переносов через параллельный префикс (см. ниже).
- Параллельный (разделяй-и-властвуй + префикс для переносов):
- Идея: разбить на блоки, в каждом блоке посчитать частичную сумму и флаги переполнения, затем вычислить переносы префикс-алгоритмом.
- Время на $p$ процессорах: $T=O(m/p+\log m)$. На PRAM с $p=m$: $T=O(\log m)$.
- Память: $O(m)$ + дополнительный буфер для флагов/сумм блоков.
- Полезно для многопроцессорных/графических ускорителей, но реализация сложнее из‑за сложности переносов.
- Carry-save для суммы многих чисел (когда суммируете $t$ больших чисел):
- Использовать дерево carry-save аддеров, откладывая переносы, затем один завершающий проход с переносами.
- Время: глубина дерева $O(\log t)$ для сложения $t$ чисел; итоговый проход $O(m)$.
- Память: временные суммарные буферы $O(m)$.
- Внешняя память (out-of-core, числа не помещаются в ОЗУ):
- Разбить на большие блоки, которые загружаются/записываются на диск; обрабатывать блоки от младших к старшим, хранить и передавать один перенос между блоками.
- I/O сложность доминирует: число блоков $\lceil m/B_{blk}\rceil$ где $B_{blk}$ — размер блока в лимбах.
- Память: $O(B_{blk})$.
Почему классический школьный приём неэффективен на больших данных
- Константы: школьный метод посимвольно использует операции над байтами/символами и конвертацию, тогда как лимбовый использует одну машинную инструкцию на $w$ бит.
- Плохое использование машинного слова: при $w=64$ вы упаковываете $64$ бита в одно слово — это даёт ~64× выигрыш против по-символьной обработки.
- Кэш и локальность: обработка побайтно часто приводит к большему числу обращений и к худшей локальности, увеличивая время.
- Переносы: при очень большом числе цифр последовательное побитовое/посимвольное распространение переноса остаётся по сути линейным, но с большими накладными расходами; для многопотоков требуется префиксный алгоритм.
- Память и формат: хранение как ASCII строк потребляет ~10× больше места, чем плотное представление лимбами; это увеличивает I/O и замедляет работу.
Рекомендации (практика)
- Использовать лимбовую репрезентацию с базой $B=2^{32}$ или $2^{64}$ (в зависимости от архитектуры).
- Для двух чисел: последовательное добавление по лимбам с инструкцией ADC — оптимально по простоте и скорости.
- Для многопроцессорных реализаций: блокировать данные, считать локальные суммы, затем префикс для переносов (время $O(m/p+\log m)$).
- Для сумм многих чисел: применять carry-save дерево, затем один завершающий проход.
- Для данных, не помещающихся в ОЗУ: блоковое внешнее сложение, стриминг младших блоков и передача переноса между блоками.
- Для практических нужд используйте готовые библиотеки (GMP, libbf), они уже оптимизированы и используют описанные подходы.
Короткая сводка сложностей
- Последовательное лимбовое: $T=\Theta (m)$, память $O(m)$.
- Параллельное (p ядер): $T=O(m/p+\log m)$.
- Внешняя память: I/O ≈ $O(\lceil m/B_{blk}\rceil )$ блоков; CPU ≈ $O(m)$.
Если нужно, могу привести пример структуры представления и псевдокод для эффективной лимбовой реализации.