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

1994 год. Intel выпустил Pentium с багом в операции деления. Убыток - 475 миллионов долларов. Причина: ошибка в таблице частичных остатков, то есть в многоразрядном сложении. Каждый раз когда CPU складывает числа - он делает именно то, чему учат в школе столбиком. Только за наносекунды.

• **Квантизация нейросетей**: INT8/INT4 - замена float32 на целочисленные fixed-point сложения. Apple Neural Engine в M1 делает это для каждого слоя трансформера
• **Алгоритм Карацубы**: умножение больших чисел через рекурсивные сложения - основа Python BigInteger, Java BigDecimal. Быстрее наивного умножения для чисел длиннее ~70 цифр
• **Carry lookahead adder**: аппаратное ускорение столбика - параллельный предрасчёт переносов в TPU, Apple Neural Engine, FPGA для ML-инференса

Столбик и перенос разряда

1994 год. Intel выпускает Pentium. Убыток - 475 миллионов долларов из-за ошибки в операции деления. Причина: сбой в таблице частичных остатков, то есть в многоразрядном сложении. Каждый раз когда CPU складывает числа - он делает именно то, чему учат в школе столбиком. Только за наносекунды.

Столбик - это не школьный ритуал. Это алгоритм с переносом разряда, который живёт в каждом ALU (Arithmetic Logic Unit) на планете. Когда Apple Neural Engine складывает тысячи INT8-чисел при квантизации нейросети - он делает именно это, только параллельно в миллионах ячеек.

**Carry lookahead adder** в процессорах предвычисляет все переносы параллельно, не ожидая каждый предыдущий. Именно поэтому сложение 64-битных чисел занимает ~1 такт, а не 64. Алгоритм столбика из школьного учебника - прямой предок этой логики.

Квантизация нейросетей (INT8/INT4) заменяет float32 операции на целочисленные сложения fixed-point чисел. GPT-4 в inference-режиме делает миллиарды таких сложений. Точность квантизации определяется именно правильностью переноса разряда - тем же самым carry.

Вычитание через дополнение

Вычитание - не самостоятельная операция. Это сложение с дополнением. Схема работает одинаково в десятичной и в двоичной - именно поэтому процессор не имеет отдельной схемы вычитания. Вычитатель - это сумматор плюс инвертор.

Two's complement - не только экономия транзисторов. Это математическая элегантность: число кольца Z_n, где -k эквивалентно 2^n - k. Сложение работает автоматически, перенос при переполнении отбрасывается. Алгоритм Карацубы умножает большие числа через рекурсивные сложения - Python BigInteger и Java BigDecimal внутри используют именно его.

**Вычитание столбиком** - это то же дополнение, только в десятичной: при нехватке цифры берётся "в долг" из старшего разряда. Долг = 10 (единица старшего разряда). Дальше - простое сложение с дополненным числом.

Устный счёт: разбиение, округление, компенсация

Устный счёт - не про скорость. Про выбор правильного разложения. Это та же идея что в алгоритме Карацубы: большую задачу разбить на маленькие, которые решаются дешевле. Карацуба умножает 1000-значные числа через три сложения вместо четырёх - рекурсивно, до базового случая.

Все четыре приёма используют одно свойство: ассоциативность и коммутативность сложения. Вычитание этими свойствами не обладает - поэтому в приёме с дополнением важен порядок. 521 - 198 = 521 - 200 + 2, но не 521 + 200 - 2.

**Золотое правило:** превращай неудобные числа в круглые и компенсируй разницу. 99 + 47 = 100 + 47 - 1 = 146. Это не хитрость - это дистрибутивность в действии.

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

• Столбик = поразрядное сложение с переносом (carry); перенос - атомарная операция ALU
• Вычитание реализуется через дополнение: a - b = a + (-b); two's complement в CPU - та же логика
• Сложение коммутативно и ассоциативно; вычитание - нет; это определяет какие приёмы допустимы
• Приёмы устного счёта - дополнение до круглого, разбиение, компенсация - все строятся на ассоциативности

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

Сложение и вычитание - основа для более сложных операций:

• Умножение и деление — Умножение - повторное сложение; алгоритм Карацубы через рекурсивные сложения
• Целые числа и модуль — Знаки и абсолютное значение - основа для операций над Z
• Порядок операций — Когда применять +/- в составных выражениях
• Двоичная система — Столбик в базе 2 - язык процессора
• Компьютерная арифметика — Переполнение, carry lookahead, целочисленные операции в железе

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

• Pentium FDIV-баг был в делении, но его fix потребовал переработки всей арифметической pipeline. Почему ошибка в одной операции затрагивает сложение?
• Почему вычитание не коммутативно, а сложение - да? Что изменилось бы в алгебре если бы было наоборот?
• Алгоритм Карацубы умножает через рекурсивные сложения. Почему это быстрее прямого умножения?

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

• ar-02-integers — Целые числа и знаки - фундамент операций
• ar-04-multiplication — Умножение - повторное сложение; столбик масштабируется
• ar-05-order — Порядок операций определяет когда применять +/-
• ar-26-binary — Двоичное сложение - тот же алгоритм столбика в базе 2
• ar-28-modular — Модулярное сложение - перенос разряда по кольцу Z_n
• ar-45-computer-arithmetic — Carry lookahead adder - аппаратный столбик в ALU
• calc-01-sequences