浮動小数点計算用のライブラリを設計している際、ある開発者は共通の課題に直面しました。それは、floatにおける最下位セットビットを特定することです。ビット操作は標準的なアプローチですが、単純なアルゴリズムでは2のべき乗の場合に失敗するため、if文が必要になります。ハイパフォーマンスコンピューティングにおいて、このような分岐は一般的なケースを遅らせたり、分岐予測のミスを引き起こしたりすることでパフォーマンスを低下させる可能性があります。この分岐を排除するために、開発者はすべてのケースを自動的に処理できる単一の数式を求めましたが、手動で説得力のある最適なものを探すのには苦労しました。
この画像は、非自明な数学的ショートカットを発見することでFPUエミュレータをスーパーオプティマイズするプロジェクトを表している。
手動の推論や大規模言語モデル（LLM）に頼るのではなく、開発者は「非正統派」のブルートフォースアプローチを選択しました。目標は、すべての可能な演算の組み合わせを反復することで、数式を自動的に発見することでした。探索空間は、整数の加算/減算、ビット演算のAND/OR/XOR、および浮動小数点の減算という一連の有用な演算によって定義されました。帰納的探索手法を用いることで、開発者はゼロ演算から始めて数式を構築し、それらをより大きな式へと組み合わせていきました。これにより、異なる式が同一の出力を生成する場合の重複結果を枝刈りすることができ、スクリプトはわずか4分間で網羅的な探索を完了しました。
探索の結果、いくつかの5演算の数式が特定されました。特に注目すべき結果の一つは、一見すると非論理的に見えながらも、2のべき乗の問題をうまく回避する数式でした。興味深いことに、開発者はこれらの5演算の数式の1つが、部分式を再利用することでさらに最適化され、4演算のバージョンにできることを発見しました。この特定の書き換えには、浮動小数点の減算を否定と統合して演算を1つ節約する巧妙な操作が含まれていました。この自動的な発見は、ブルートフォース探索がいかに人間の直感や標準的なコンパイラ最適化を逃れるような、非自明な数学的ショートカットを見つけ出すことができるかを浮き彫りにしました。得られたコードは現在、制作中のFPU（浮動小数点演算ユニット）エミュレータに統合されています。