Как перебор формул обогнал программиста в FPU-эмуляторе

При разработке библиотеки для вычислений с плавающей точкой автору понадобилась функция, возвращающая по числу f значение, соответствующее его младшему установленному биту. Задача решается битовыми трюками, но прямолинейный алгоритм ломается на степенях двойки, поэтому приходилось вставлять ветвление if. Именно этот if и раздражал: он замедлял общий случай и грозил ошибками предсказания переходов.

Автор хотел найти формулу, которая обрабатывала бы степени двойки автоматически, но убедительно оптимального варианта подобрать не удавалось. Тогда он сделал нестандартный ход.

Брутфорс вместо нейросети

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

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

Пространство поиска оказалось обозримым: варианты расстановки операций, скобок и операндов. В качестве констант автор взял не произвольные значения, а те, что покрывают различные поля двоичного представления float, сократив список до 64 штук.

Индуктивный поиск

Чтобы перебор был эффективным, множество формул строилось по индукции: выражения из n операций получаются комбинированием выражений из k и n−1−k операций. Такой подход позволяет отбрасывать дубликаты — например, (x+1)+2 и (x+2)+1 дают одинаковый результат, и достаточно хранить лишь одно из них. Именно поэтому перебор завершился всего за четыре минуты. На последней итерации дедупликацию отключали, чтобы получить всех кандидатов.

Находка

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

Хитрость в том, что одно из подвыражений, a - x.to_bits(), эквивалентно отрицанию x & MANTISSA_MASK. Остальные формулы считали это значение напрямую, а найденная переписала его через вычитание и слила с отрицанием, сэкономив одну операцию. На степенях двойки она ведёт себя чуть иначе — переворачивает знаковый бит, что автору безразлично.

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

Источник: Lobsters