Человек, который знал бесконечность: кодирование такси Рамануджана
Вы видели фильм (или читали книгу) Человек, который знал бесконечность?
Этот новый фильм, в котором снимаются Дев Патель и Джереми Айронс, исследует индийского математика Шриниваса Рамануджана и его глубокое понимание, изобретательность и любовь к математике.
Фильм вдохновил меня как на интеллектуальном, так и на эмоциональном уровне. Но что действительно привлекло мое внимание, так это конкретная пятисекундная сцена.
Действие происходит в 1918 году. Наставник и друг Рамануджана Г.Х. Харди шутит, что он только что взял такси номер 1729, и находит номер «довольно скучным».
Рамануджан страстно отвечает: «Нет, Харди, это очень интересный номер! Это наименьшее число, которое можно выразить как сумму двух кубиков двумя разными способами ".
Рамануджан смог заглянуть за пределы простого номера такси в глубину выражения, стоящего за ним: a³ + b³ = c³ + d³… более известное как Такси Рамануджана. Я подумал, что эта проблема интересна, и подумал, как будет выглядеть реализация кода. Я и не подозревал, что в этом луковице алгоритма есть много уровней оптимизации.
Первая удача при внедрении такси Рамануджана
Я начал с простой реализации, написанной на Scala. Код с таймингами производительности можно найти на GitHub:
Мы начинаем с реализации методом перебора, перебирая все комбинации в цикле, чтобы найти, где a³ + b³ = c³ + d³. Мы достигаем производительности O (n⁴) благодаря четырем циклам, используемым для вычисления всех значений a³, b³, c³ и d³, равных или меньших, чем параметр n, который ограничивает поле поиска.
Эта реализация методом грубой силы с производительностью O (n⁴) отстой. Итак, как мы можем добиться большего?
Мы можем делать лучше
Первый вопрос, который следует задать: всегда ли нам нужно вычислять все значения a³, b³, c³ и d³? Помните, что мы используем уравнение a³ + b³ = c³ + d³. Если мы решим относительно d³, мы получим d³ = a³ + b³ - c³. Таким образом, когда мы знаем a³, b³ и c³, мы можем вычислить значение d³ напрямую, вместо того, чтобы перебирать все значения d³.
Моя следующая реализация, опять же на Scala, заменяет четвертый цикл вычислением d³ = a³ + b³ - c³:
Вторая версия имеет производительность O (n³), так как мы можем пропустить этот последний цикл. Аккуратный!
Третий раз очарование
Мы еще не закончили. Следует рассмотреть третье и самое лучшее усовершенствование. Что, если нам не нужно искать все значения не только d³, но и c³ тоже? Несколько вещей, которые нужно понять:
- Если мы вычислим все значения a³ и b³, равные или меньшие n, мы, по сути, получим все возможные значения не только a³ и b³, но также c³ и d³.
- Сумма a³ + b³ равна сумме c³ + d³.
- Если сумма пункта 2 выше для данной пары целых чисел (a³, b³) совпадает с суммой другой пары целых чисел (a³, b³), мы, по сути, нашли пару c³ и d³.
Если мы сохраним каждую комбинацию суммы a³ + b³ и соответствующей пары (a³, b³), любая сумма, имеющая две пары, означает, что мы нашли a³ + b³ = c³ + d³, где можно рассматривать первую пару в списке ( a³, b³) и следующий (c³, d³).
Например, если мы перебираем комбинации a³ + b³, мы сохраним сумму 1729 вместе с парой (1³, 12³). Продолжая итерацию, мы увидим, что возникает еще одна сумма 1729, но на этот раз с парой (9³, 10³). Поскольку у нас есть две разные пары, каждая из которых в сумме дает 1729, мы нашли Рамануджанское такси, которое решает для a³ + b³ = c³ + d³.
В третьей версии мы используем Hashmap для хранения суммы (ключа) и соответствующего списка пар как отсортированного набора (значения). Если в списке больше одной пары, значит, победитель!
Эта реализация имеет производительность O (n²), поскольку нам нужны только два цикла для вычисления комбинаций для a³ и b³. Очень аккуратный!
Я подозреваю, что есть четвертая оптимизация, при которой нам нужно только вычислить значения a³ и получить b³ из a³ (цикл «b» - это просто смещение цикла «a») с производительностью O (n).
Кроме того, еще одна проблема состоит в том, чтобы переписать реализации как шаблон функционального программирования. Я оставлю это на ваше усмотрение.
Удивительный фильм, удивительный человек
После просмотра «Человека, который знал бесконечность» я был в восторге от гения Рамануджана. Реализовав его алгоритм такси - с его несколькими оптимизациями производительности - я увидел красоту, которую он увидел в словах «Нет, Харди, это очень интересное число!»
Такси Рамануджана, которому почти столетие, все еще делает новые открытия. Математики из Университета Эмори обнаружили, что число 1729 относится к эллиптическим кривым и поверхностям K3 - объектам, важным сегодня в теории струн и квантовой физике.
Полагаю, мы только прикоснулись к номеру такси Рамануджана и его удивительному гению.
Об авторе: Джеффри Борн - генеральный директор компании RETIRETY, которая помогает людям на пенсии или близким к пенсии найти лучший способ выйти на пенсию.
