3 ms·
The fastest way to encode these dense bitpackings is almost certainly with the Chinese remainder theorem.
by periodontal 11y ago
The fastest way to encode these dense bitpackings is almost certainly with the Chinese remainder theorem.
- hywel 11y agoKind 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/2136aa5d28a209f902d4bbb2da8cfe731547bf5e/NetflixDataNG.cpp#L944 https://github.com/hcarver/Netflix/blob/2136aa5d28a209f902d4...
- periodontal 11y agoCRT 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#General_case 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.