Hacker News Reader

The fastest way to encode these dense bitpackings is almost certainly with the Chinese remainder theorem.

Kind of. The Chinese Remainder Theorem tells that you that there exists a number that satisfies, and that the number is unique, but it doesn't tell you how to calculate it.

The standard way is to do it recursively - you can see my implementation here: https://github.com/hcarver/Netflix/blob/2136aa5d28a209f902d4...

CRT is often given with a closed form for the satisfying solution, although requiring computing multiplicative inverses mod each of the n_i (your primes). Since all of these values are known at design time, they can be precomputed and the run time for encoding becomes a constant M multiplications, M-1 additions and one mod at the end where M is the number of items you are encoding.

https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Gene...

For example, the 3, 5, 7 packing yields a closed form of 70a_1+21a_2+15a_3 (mod 105). Plugging in 2, 4, 3 like your example yields 59 directly.

Reply on news.ycombinator.com