Умножение и деление: от таблицы до алгоритма Карацубы

Египтяне, Карацуба и один опровергнутый Колмогоров

Древние египтяне не знали таблицы умножения. Вместо этого - только **удвоение и сложение**. 13 x 17: удвоить 17 несколько раз, выбрать нужные строки, сложить. Это именно то, как работают современные процессоры - через сдвиги битов и сложения. Египетский метод - это бинарное умножение, открытое за 5000 лет до изобретения двоичной системы.

Алгоритм Карацубы используется в Python для больших целых чисел (bigint), в OpenSSL для RSA, в GMP - библиотеке GNU для точной арифметики. Каждый раз, когда Python считает 10**1000, работает Карацуба.

1960. Москва. Колмогоров публично объявляет: умножение n-значных чисел требует не менее n^2 операций - это математический предел. Через неделю аспирант Карацуба приносит алгоритм за n^1.58. Колмогоров отменяет семинар и публикует результат ученика. За каждым torch.mm, каждым CUDA-ядром и каждым RSA-ключом стоит этот момент.

• **GPU матрицы**: CUDA cores выполняют 10000+ параллельных умножений. Каждый forward pass трансформера - это тысячи GEMM-операций. Оптимизация умножения = оптимизация всего deep learning
• **RSA-4096**: умножение двух 1000-значных чисел наивно - 10^6 операций. Алгоритм Карацубы - ~10^4.75. Для ключа в 4096 бит разница - миллиарды операций на каждое шифрование
• **Python bigint**: `(10**500) * (10**500)` вычисляется через Карацубу автоматически - CPython переключается на него при числах больше ~70 цифр
• **NumPy broadcasting**: `np.dot(A, B)` для матриц 1000x1000 вызывает BLAS, который использует блочные алгоритмы и SIMD-инструкции - не наивный O(n^3)

Наивный алгоритм: школьный n-квадрат

**1960 год. Москва. Колмогоров - один из величайших математиков XX века - публично объявляет**: умножение двух n-значных чисел требует не менее n^2 операций. Это кажется очевидным: сложить 7 + 7 + 7 + 7 + 7 утомительно, поэтому пишут 7 × 5 = 35. Школьный алгоритм умножения в столбик именно так и работает - каждая цифра первого числа на каждую цифру второго. Два числа из k цифр: k × k = k^2 умножений.

**Умножение** - сокращённая запись повторного сложения: a × n = a + a + ... + a (n раз) где a - множимое, n - множитель, результат - **произведение**. **Школьный алгоритм**: умножаем каждую цифру первого числа на каждую цифру второго. Два числа по n цифр = O(n^2) элементарных умножений.

**Почему минус на минус даёт плюс?** Формально: (-1) × (-1) = 1, потому что это единственное значение, при котором сохраняется дистрибутивность. Неформально: долг в 3 группы долгов по 4 - это 12 единиц прибыли. Дистрибутивность - не договорённость, а следствие аксиом кольца целых чисел.

**NumPy под капотом**: `np.dot(a, b)` для двух матриц 1000x1000 - это 10^9 умножений. NumPy вызывает BLAS, который использует векторные инструкции CPU и кеш-оптимизацию - не наивный O(n^3), а оптимизированный блочный алгоритм. Школьный алгоритм умер на матрицах 10x10.

Деление: обратная операция и Newton-Raphson

**Деление** отвечает на вопрос: сколько раз одно число содержится в другом? Или: на сколько равных частей разделить? Это обратная операция к умножению - так же, как вычитание обратно сложению. Но есть тонкость: знание таблицы умножения автоматически даёт знание таблицы деления. А вот в процессорах деление реализуется отдельно - и работает значительно медленнее умножения.

**Деление** - операция, обратная умножению: a / b = c означает c x b = a где a - делимое, b - делитель, c - частное. **Важно:** на ноль делить нельзя! **На процессорах**: деление в 10-30 раз медленнее умножения. Поэтому компиляторы заменяют деление на умножение на обратное везде, где делитель известен заранее.

В современных CPU деление реализуется через **алгоритм Newton-Raphson**: итеративно уточняется обратная величина 1/b, потом результат умножается на a. Это превращает медленное деление в серию быстрых умножений. Компилятор GCC и Clang делают именно это для констант - заменяют `x / 7` на `x * 0x24924925 >> 33` ещё на этапе компиляции.

Свойства и дистрибутивность: фундамент алгоритмов

Умножение обладает удобными свойствами. Деление, как и вычитание, их теряет. Но главное свойство - **дистрибутивность** - это не просто школьный трюк для устного счёта. Это фундамент алгоритма Карацубы, умножения матриц и работы FFT.

**Дистрибутивность** - ключевое свойство для устного счёта: 7 x 12 = 7 x (10 + 2) = 70 + 14 = 84 99 x 5 = (100 - 1) x 5 = 500 - 5 = 495 **Карацуба 1960**: именно дистрибутивность позволяет разбить умножение двух больших чисел на 3 умножения меньших вместо 4. Отсюда - n^1.58 вместо n^2.

**Алгоритм Карацубы в одном абзаце**: два числа A и B разбиваются пополам: A = a1·10^m + a0, B = b1·10^m + b0. Наивно: 4 умножения (a1b1, a0b0, a1b0, a0b1). Карацуба: вычислить a1b1, a0b0, и (a1+a0)(b1+b0) - из трёх произведений восстановить все четыре через сложение. Рекурсия даёт O(n^1.585). Через неделю после объявления Колмогорова - Карацуба принёс доказательство.

Деление с остатком и модулярная арифметика

17 конфет на 5 детей - каждому по 3, но 2 останутся. Это **деление с остатком**. Казалось бы, элементарно. Но остаток от деления - операция `%` - это фундамент хеш-таблиц, криптографии и кодов коррекции ошибок. RSA целиком живёт в модулярной арифметике.

**Деление с остатком:** a = b x q + r где a - делимое, b - делитель, q - неполное частное, r - остаток. **Условие:** 0 <= r < b (остаток меньше делителя)

Деление с остатком - основа **модулярной арифметики**. Шифрование RSA: зашифровать сообщение m с ключом e - это вычислить m^e mod n. Для 4096-битных чисел это тысячи операций умножения по модулю. Скорость криптографии напрямую зависит от скорости умножения.

Ключевые идеи

• Умножение - сокращённая запись повторного сложения; школьный алгоритм - O(n^2)
• Карацуба 1960: дистрибутивность даёт O(n^1.585) - в Python работает автоматически для bigint
• Деление - обратная операция, на CPU медленнее умножения в 10-30 раз; компиляторы заменяют константные делители
• Деление с остатком: a = b x q + r, 0 <= r < b - основа хешей, RSA и кодов коррекции

Связанные темы

Умножение и деление открывают дорогу к новым концепциям:

• Порядок операций — Умножение выполняется раньше сложения
• Делимость — Когда остаток равен нулю - НОД и НОК
• Дроби — Деление, которое не выполняется нацело
• Модулярная арифметика — Остатки как самостоятельная система чисел; основа RSA

Вопросы для размышления

• Почему умножение коммутативно (3 x 7 = 7 x 3), ведь «3 группы по 7» и «7 групп по 3» - разные картинки?
• Алгоритм Карацубы использует 3 умножения вместо 4 за счёт дистрибутивности. Можно ли довести до 2 умножений? Почему или почему нет?
• Компиляторы заменяют `x / 7` на умножение на магическую константу. Как именно работает этот трюк?

Связанные уроки

• ar-05-order — Порядок операций: умножение раньше сложения
• ar-13-divisibility — Делимость - остатки и факторизация
• ar-28-modular — Модулярная арифметика: основа криптографии
• ar-26-binary — Бинарное умножение - тот же египетский метод
• ar-44-crypto-intro — RSA-4096: умножение - узкое место
• ar-45-computer-arithmetic — BLAS, GPU GEMM - промышленное умножение
• prob-01-intro