Post #1604052

When working on my game probability computation project https://github.com/dpiponi/dice-nine I wanted to do high precision computations with exact rationals. It seems pretty straightforward seeing as the host language, Python, natively supports arbitrary precision integers and has a rationals library. But I was using numpy (and previously pytorch and tensorflow) for my computation and using Python integers in a numpy array loses you performance advantages. But I noticed that when doing probability theory you're almost always working in the semiring of rationals. And it's well known you can use the Chinese remainder theorem to work efficiently with high precision in the (semi)ring of integers by working modulo a set of large primes until the very last step. But I needed rationals and some occasional division too. So I conjectured that if you can fix a bound on the numerator and denominator you can use the same trick to work over the rationals working in multiple fields Z/pZ. Turns out I was correct and there are a few papers on it: https://www.cecm.sfu.ca/~monaganm/teaching/TopicsinCA21/MQIRR.pdf Anyway, it ought be be as well known as the ring based approach. It makes many kinds of high precision algorithms easy to implement on GPUs.