4 ms·
This is essentially arithmetic encoding to do base conversion from binary to n-ary. Once you have enough bits, you're almost certainly not on the boundary of a
by Straw 5y ago
This is essentially arithmetic encoding to do base conversion from binary to n-ary. Once you have enough bits, you're almost certainly not on the boundary of a bucket. Funny how the same thing seems to have been reinvented...
- Someone 5y agoI don’t think that’s fair. The article clearly knows about prior art, and ‘only’ claims: “This PR introduces a novel algorithm that: - never divides - avoids rejection sampling entirely - achieves a theoretically optimal bound on the amount of randomness consumed to generate a sample - delivers actual performance improvements for most real cases”
- Straw 5y agoI don't mean it as a negative! Except perhaps I could have understand what they did faster if they described it as arithmetic encoding.
- stephencanon 5y agoThat's exactly right (in fact, thinking about AC is what prompted me to implement it).