Search radius as a parameter for preimage simplification

[frostburn]

Babai's nearest plane isn't guaranteed to give the simplest form.

Add an optional "search radius" parameter to iteratively search for simpler forms inside local "bubbles" of comma space. In SonicWeave this seems to provide further reductions not found by Babai's.

[Sin-tel]

Interesting, this algorithm went through like 3 iterations before I settled on Babai's, since it gave me best results in all of my test cases. Of course you can never guarantee optimality in the strict sense if you want an efficient algorithm.

What is your suggested search algorithm? Just trying all possible combinations of vectors has some nasty combinatorial explosion but it might be worth it if it pays off.

On a side note, this feature can benefit from some test or benchmark set so we can compare algorithms more easily.

[frostburn]

Here's my implementation: https://github.com/xenharmonic-devs/sonic-weave/blob/e2afbff41b4c76802d3947f6f6bfe20b36131599/src/stdlib/builtin/temper.ts#L505

It builds all k-combinations of the commas and their inverses based on the "radius" k and iteratively brute-forces with those trying to simplify the fraction. It also has stuff related to eliminating nth-rooths, but you probably don't need to worry about that.

As a test case I try to simplify 60/49 to 49/40 using miracle's comma list [225/224, 1029/1024].

[frostburn]

That code was bad. The fixed version uses a solid hypercube of LLL reduced commas.