Hacker News Reader

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...

View on HN

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