Искусство счёта

как вычисление превратилось из ремесла в устройство

Сюжет в одном абзаце

Индийские цифры приходят в Европу через алжирскую факторию (Пиза, 1202) — счёт пером вытесняет жетоны на доске — ручной счёт доходит до своего физического предела (Самарканд, 1424) — и дальше три века математика занята не тем, чтобы считать лучше, а тем, чтобы считать меньше: десятичная дробь (Лейден, 1585), логарифм, превращающий умножение в сложение (Мерчистон, 1614), линейка, где сложение выполнено заранее (Лондон, 1622), зубчатое колесо вместо человека (Руан, 1642), конвейер из людей вместо вычислителя (Париж, 1794), машина вместо конвейера (Лондон, 1822). Затем машина появляется взаправду — и приносит с собой задачи, которых не было, пока считали руками: решение, у которого нет формулы (Гёттинген, 1901), ошибка округления как предмет теории (Принстон, 1947; Теддингтон, 1961), рекурсия, сбивающая показатель степени (Мюррей-Хилл, 1965; Цюрих, 1969), и наконец данные, которые больше, чем место, куда их можно положить (1984, 1996).

О чём эта линия на самом деле

Остальные линии карты рассказывают, как математика узнавала новое. Эта — как она избавлялась от работы.

Вопрос, который её держит, звучит непривычно для учебника: сколько стоит вычисление? Не «верен ли ответ», а «сколько человеко-часов, ошибок и зрения он стоит». Двадцать лет жизни Непера ушли на то, чтобы астроном тратил на одно умножение минуту вместо получаса. Ал-Каши считал шестнадцать знаков $\pi$ многоугольником с восемьюстами миллионами сторон — и это был потолок, дальше человек не проходит. Прони посадил за таблицы восемьдесят человек, умевших только складывать и вычитать. Каждый раз ответ был известен в принципе — недоступной была цена.

Отсюда три особенности, которых нет в других линиях.

Первая: здесь ценят не теорему, а приём. Почти ни одна точка этой линии не отмечена доказательством нового факта. Отмечены — удачные способы записи, удачные таблицы, удачные механизмы, удачные алгоритмы. Это не значит, что математики здесь второго сорта: логарифм окажется одной из важнейших функций анализа, а позиционная запись — условием, без которого алгебра невозможна. Но открыты они были не ради теории.

Вторая: обозначение здесь и есть содержание. Позиционная цифра, десятичная запятая, логарифмическая шкала — способы переложить часть мышления на бумагу, чтобы дальше действовать не думая. Хорошая нотация выполняет работу за нас; половина линии про это.

Третья: дефицит всё время меняется. Сначала дорого действие, потом дробь, умножение, таблица, человек, понимание, надёжность. Затем — когда машина появилась — дорогими становятся точность, время, размерность и, наконец, самый взгляд на данные. Каждый раз кто-то обнаруживает, что дорого не то, что казалось, и переносит трудность в другое место: в нотацию, в дерево, в металл, в организацию труда, в теорию ошибок, в рекурсию, в случайность.

Почему эта линия появилась поздно

Её не было в первоначальном плане сайта, и это не случайность: разделы карты нарезаны по математическим дисциплинам, а искусство счёта — не дисциплина. Логарифм не принадлежит ни алгебре, ни анализу, ни теории чисел; он принадлежит практике. Ровно поэтому его и не оказалось ни в одной линии, хотя каждая на него опирается.

Несколько точек этой линии живут и в других разделах — Канторович и Карацуба в дискретной математике, Монте-Карло в теории вероятностей, PageRank там же, откуда пришёл. Это не дубликаты: одно и то же событие видно из разных линий под разным углом, и здесь оно видно со стороны цены.

Открыть на карте

1

Багдад ок. 820 г.
Аль-Хорезми: книга, давшая имя алгебре
Откуда взялось слово «алгоритм»

«Аль-джабр» из названия трактата стало словом «алгебра», а имя автора в латинской передаче — словом «алгоритм». Впервые уравнения не решаются по случаю, а классифицируются и разбираются исчерпывающе.
2

Пиза 1202 (2-я редакция 1228)
Фибоначчи: девять индийских знаков
Европа учится считать пером

Купеческий учебник, который принёс в Европу индийские цифры, нуль и счёт пером вместо жетонов на доске. Кролики из двенадцатой главы — побочная задача, которую прославили через шестьсот пятьдесят лет.
3

Самарканд 1424
Ал-Каши: шестнадцать знаков числа π
Предел ручного счёта: шестнадцать знаков π

Задача поставлена по-инженерному: чтобы у окружности диаметром в шестьсот тысяч земных ошибка не превышала толщины волоса. Точность, которую Европа догнала только в конце XVI века. Рядом — десятичные дроби «Ключа арифметики» и обсерватория Улугбека.
4

Лейден 1585
Стевин: конец обыкновенной дроби
Дробь становится позиционной

Книжка в сорок страниц, предложившая считать десятичной дробью всё и всегда. Сами дроби были известны за полтора века до неё; новым было требование сделать их всеобщей практикой — и приложение, где за двести десять лет до Парижа изложен принцип метрической системы.
5

Мерчистон (Эдинбург) 1614
Непер: умножение становится сложением
Двадцать лет ради чужого времени

Шотландский помещик, считавший главным трудом жизни толкование Апокалипсиса, двадцать лет считал таблицу, чтобы всякий следующий вычислитель тратил на умножение минуту вместо получаса. Лаплас потом скажет, что логарифмы удвоили жизнь астронома.
6

Лондон 1617 и 1624
Бриггс: логарифм получает основание
Мантисса и характеристика: таблица сжимается

Основание десять — не косметика: дробная часть логарифма перестаёт зависеть от порядка числа, и бесконечный диапазон умещается в одну страницу мантисс. Ради этого Бриггс пятьдесят четыре раза подряд извлекал корень из десяти с тридцатью знаками.
7

Прага 1620 (найдено ок. 1588)
Бюрги: тот же ответ, никем не прочитанный
Независимое открытие, опоздавшее на тридцать лет

Придворный часовщик, не знавший латыни, пришёл к логарифмам от зубчатой передачи за четверть века до Непера — и тридцать лет молчал. Таблицы вышли в Праге в год битвы на Белой горе и не разошлись.
8

Лондон 1622
Отред: сложение, записанное на дереве
Логарифм становится предметом

Две шкалы Гюнтера, сдвигаемые одна вдоль другой, — и складывать больше не надо: сложение выполняет дерево. Первый случай, когда из головы в предмет вынесен не результат вычисления, а сама операция.
9

Руан 1642–1645
Паскалина: перенос разряда в металле
Действие поручено механизму

Девятнадцатилетний сын налогового чиновника решает задачу переноса разряда падающим грузом — и механизм впервые не хранит вычисление, а выполняет его. Тюбингенская машина Шиккарда была на девятнадцать лет раньше, но сгорела, и триста лет первой считалась руанская.
10

Лондон 1 февраля 1673
Лейбниц: ступенчатый валик
Умножение — тоже механизму

Деталь, позволившая умножать за один приём, прожила два с половиной века — до механических калькуляторов 1970-х. Сама машина при этом толком не работала, а свою двоичную арифметику Лейбниц с ней так и не соединил.
11

Париж 1794–1801
Прони: вычисление как разделение труда
Вычислитель становится должностью

Глава Бюро кадастра прочитал у Адама Смита про булавочную фабрику и собрал вычислительный конвейер из восьмидесяти человек, умевших только складывать. Из вычисления впервые изъято понимание — и сразу стало видно, что исполнителю необязательно быть человеком.
12

Лондон 1822
Бэббидж: «я желал бы, чтобы это делалось паром»
Конвейер поручают машине

Разностная машина: раз на нижнем ярусе конвейера Прони выполняются только сложения, человек там не нужен. Достроена не была — но собранная в 1991 году по его чертежам считает безупречно, так что подвели не идеи, а деньги и терпение.
13

Гёттинген 1895–1901
Рунге и Кутта: решение, которого нет в формулах
Ответом становится таблица, а не формула

Большинство дифференциальных уравнений не решается в известных функциях — и не потому, что приёма не нашли. Здесь согласились считать решением таблицу значений с доказанной оценкой погрешности, и это сменило само представление о том, что такое ответ.
14

Санкт-Петербург 1939
Канторович: оптимизация раскроя фанеры
Оптимальный план — вычислительная задача

Лаборатория фанерного треста спросила, как распределить работу между станками. Ответом оказался новый раздел математики — линейное программирование, а вместе с ним двойственные оценки, которые в СССР пришлось называть словами, не похожими на слово «цены».
15

Филадельфия «First Draft of a Report on the EDVAC» — 30 июня 1945
«Первый набросок»: программа переезжает в память
Машина, у которой программа лежит там же, где числа

Сто одна страница незаконченного черновика, разосланного 30 июня 1945 года, задали устройство почти всех машин, построенных с тех пор: команды лежат в той же памяти и в том же виде, что и числа. На титуле стояло одно имя — из-за этого конструкция стала общественным достоянием, а её авторы рассорились навсегда.
16

Лос-Аламос 1946–1949
Улам и фон Нейман: вычислять вероятностью
Считать не формулой, а случайной игрой

Станислав Улам, раскладывая пасьянс во время болезни, понимает: вместо того чтобы вычислять вероятность комбинаторно, проще разыграть партии и посчитать. Поворот на 180 градусов — теперь не математика служит случаю, а случай служит математике.
17

Принстон 1947
Число обусловленности: когда виновата задача, а не метод
Ошибка становится предметом теории

Машина выписывает сколько угодно знаков, но верны из них не все. Фон Нейман и Голдстайн отделили трудность, принадлежащую самой задаче, от кривизны алгоритма — и с этого различения начался численный анализ как дисциплина.
18

Вашингтон лето 1947
Данциг: симплекс-метод
Оптимум ищут по рёбрам многогранника

Вершин у многогранника ограничений больше, чем атомов во Вселенной, а метод доходит до оптимума за десятки шагов, идя по рёбрам. Почему он так хорош, толком объяснили только в 2001 году — в худшем случае он экспоненциален.
19

Сиэтл 1956
Конечные элементы: расчёт того, для чего нет уравнения
Численный ответ как единственно возможный

Крыло самолёта разрезают на тысячи простых кусков, для каждого выписывают элементарную жёсткость и сшивают в разреженную систему. Метод придумали инженеры «Боинга»; математическое обоснование подвели через пятнадцать лет.
20

Москва 1960
Карацуба: быстрее, чем учили в школе
Умножение дешевеет во второй раз

Колмогоров предположил на семинаре, что умножать быстрее, чем в столбик, невозможно. Двадцатитрёхлетний студент опроверг гипотезу за неделю. Способ, которым он это сделал, оказался первым примером того, что «естественный» алгоритм бывает не лучшим, — и с него началась привычка спрашивать, сколько стоит вычисление.
21

Теддингтон 1961–1965
Уилкинсон: точный ответ на слегка другой вопрос
Обратный анализ: ошибку переносят во вход

Вместо «насколько наш ответ неверен» спросили «для какой задачи он был бы совершенно верен» — и оценки, не выводившиеся прямым путём, стали выводиться в несколько строк. Плюс многочлен, у которого от изменения коэффициента на 2⁻²³ корни сходят с вещественной прямой.
22

Мюррей-Хилл (Bell Labs) 1965
БПФ: алгоритм, опередивший потребность
N log N вместо N² — и Гаусс за сто шестьдесят лет до

Ускорение в пятьдесят тысяч раз на миллионе точек — не «быстрее», а «стало возможным». Полный алгоритм есть у Гаусса в работе 1805 года, написанной раньше мемуара Фурье и пролежавшей непрочитанной сто восемнадцать лет: он опередил не публикацию, а потребность.
23

Цюрих 1969
Штрассен: гауссово исключение не оптимально
Семь умножений вместо восьми

Искал доказательство, что быстрее n³ нельзя, и нашёл опровержение — ровно как Карацуба девятью годами раньше и по той же схеме. Точное значение показателя не известно до сих пор; снизу известно только тривиальное n².
24

Беркли Миллер — 1976, Соловей и Штрассен — 1977, Рабин — 1980
Соловей и Штрассен: монетка вместо доказательства
Тот же Штрассен: случайность становится вычислительным инструментом

Поворот, ради которого стоило разбираться со случайностью: она оказалась не помехой, а ресурсом. Чтобы узнать, простое ли число, делители искать не нужно — достаточно взять наугад свидетеля и проверить одно равенство по модулю. Составное число случайный свидетель уличает с вероятностью не меньше половины, так что двести попыток делают ошибку менее вероятной, чем отказ процессора. Ответ «да» здесь не доказан, а лишь очень вероятен, — и на этом с тех пор держится всякая выдача ключей.
25

Нью-Хейвен 1984
Лемма Джонсона — Линденштрауса: размерность, которой можно пренебречь
Сжать миллион признаков в сотню

Любые n точек укладываются в пространство размерности порядка log n с сохранением всех попарных расстояний — и целевая размерность не зависит от исходной вообще. Доказывалась как техническая лемма функционального анализа; прикладную жизнь получила через пятнадцать лет.
26

Мюррей-Хилл (Bell Labs) доклад на симпозиуме FOCS — ноябрь 1994; журнальная версия — 1997
Шор: разложение на множители за полином — но не на этой машине
Дешевеет не приём, а сама машина

Разложить число на множители — то же самое, что найти период ряда его степеней, а искать период умеет преобразование Фурье. Питер Шор собрал из этого квантовый алгоритм, которому взлом ключа стоит куба его длины вместо астрономической величины. Машины нужного размера нет и, возможно, не будет — но записанное сегодня можно расшифровать через двадцать лет.
27

Стэнфорд 1996–1998
PageRank: линейная алгебра съедает веб
Линейная алгебра размером с интернет

Двое аспирантов предложили считать важность веб-страницы собственным вектором матрицы гигантского графа ссылок. Математика — теорема Перрона — Фробениуса 1907 года, ждавшая приложения девяносто лет, и цепь Маркова, придуманная для «Евгения Онегина». На этом заканчивается наша линия — и, пожалуй, заканчивается разделение математики на чистую и прикладную.
28

Мюррей-Хилл (Bell Labs) 1996
Скетчи: сосчитать, не запоминая
Дорог не счёт, а взгляд на данные

Данных больше, чем места, куда их положить: поток идёт мимо, и второй раз посмотреть нельзя. Точный подсчёт доказуемо невозможен, приближённый — требует логарифма памяти: миллиард различных элементов считается с ошибкой в два процента в полутора килобайтах.