NUnullc·May 20, 2022
At the heart of the opus audio codec is a maximally-encoding for combinations with replacement and sign[1], which is n-choose-k where n can be reused and there is a sign for each chosen dimension. Or stated another way, n dimensional integer vectors where the sum of absolute values add to k.
This enumeration can be implemented with the same kind of recursion as in the link, with a little bit of elaboration. Though interestingly, it (and the formula in the link) can also be be implemented with recursive table lookups quite efficiently, and for small fixed N with closed form formula (also true for the simpler combination code in the link).
These maximally dense algebraic codes can be designed for a great many possible applications.
For example, for a generational rolling cuckoo filter Pieter Wuille and I came up with an algebraic code for
Read the rest
coding 4 sorted generation numbers with the requirement that all 4 are within a window of half the total range[2]. In prior published work on cuckoo filters used a large table of all possible values of combinations with replacement (to efficiently pack small sorted numbers). We found the algebraic code to be faster than a big dumb table, presumably due to cache locality, even though our fastest encoder/decoder still use tables but only tiny ones (at least for the sizes we were considering).
A challenge for implementing these sorts of functions is that their inverses often require operations like integer square or cube roots which are not particularly fast unless the ranges are small enough to implement them with tables.
[1] https://github.com/xiph/opus/blob/master/celt/cwrs.c#L74
[2] https://github.com/sipa/bitcoin/blob/202006_cuckoo_filter/sr...