How Brute Force Out-Thought a Programmer Inside an FPU Emulator

While building a floating-point library, the author needed a function that takes a float f and returns the value corresponding to its lowest set bit. The task can be done with bit twiddling, but the straightforward algorithm breaks on powers of two, forcing an if branch. That if was the irritant: it slowed down the common case and risked branch mispredictions.

The author wanted a formula that would handle powers of two automatically, but no convincingly optimal candidate turned up. So they made an unorthodox move.

Brute force instead of an LLM

The idea is simple: rather than summoning a swarm of language models, just brute-force every possible formula. Models, the author notes, can miss things or overindex on popular patterns; brute force can't.

How do you check correctness? Theorem provers are too slow, so a handful of representative test cases were used instead. If a formula has a counterexample, add it to the test set and repeat. By this point the author already had a six-operation algorithm, so they only needed to iterate over formulas with five operations or fewer.

The search space proved manageable: the ways to pick operations, place parentheses, and choose operands. For constants, the author used not random values but ones covering the various fields of a float's binary representation, trimming the list to 64.

Inductive search

To keep the search efficient, the formula set was built inductively: expressions of n operations come from combining expressions of k and n−1−k operations. This lets duplicates be pruned — for instance, (x+1)+2 and (x+2)+1 yield the same result, so only one need be kept. That is why the brute force finished in just four minutes. On the final iteration, deduplication was skipped to output every candidate.

The find

The search produced several five-operation formulas. No four-operation variant was found — but the method had a weakness: it didn't account for reusing computations. The author hoped one of the five-op formulas could collapse to four via reuse. Checking every formula by hand, they discovered the very last one had exactly this property.

The trick is that one subexpression, a - x.to_bits(), is equivalent to negating x & MANTISSA_MASK. Other formulas computed that value directly, while this one rewrote it as a subtraction and merged it with the negation, saving one operation. On powers of two it behaves slightly differently — flipping the sign bit, which the author doesn't care about.

The formula's logic makes no sense at first glance, and yet it works. The author admits to being flabbergasted by the search's ingenuity and concludes: you don't need an LLM to be amazed by what computers can invent — and this approach doesn't destroy any industries. The code now lives in their work-in-progress FPU emulator.

Source: Lobsters