3 ms·
The Chinese Remainder Theorem has a fascinating consequence, which is to enable the Residue Number System: https://en.wikipedia.org/wiki/Residue_number_system
by FartyMcFarter 5y ago
The Chinese Remainder Theorem has a fascinating consequence, which is to enable the Residue Number System:
https://en.wikipedia.org/wiki/Residue_number_system https://en.wikipedia.org/wiki/Residue_number_system
For example, since 2 and 3 are coprime, if you store the residues of any number N modulo 2 and 3 separately, you can do additions, subtractions and multiplication modulo 6 by doing the same operations on the two residues (independently of each other).
With this system it is possible to arithmetic on huge numbers in massively parallel fashion. The drawbacks are that division is hard (except when you know that the division is exact), overflow detection / comparison are hard, and converting from the residue number system to N is expensive.
- klyrs 5y agoA small gotcha you didn't mention: if you work modulo 2 and 3, then your results are only valid modulo 6 (generally, the product of your moduli). Unless you're happy with the assertion that 15*14==0, that is. I don't judge.
- FartyMcFarter 5y agoIf you know that you're working with numbers as big as 15 and 14, you could alternatively use more residues so that you can represent those numbers. If you don't know how big the numbers get, then you do run into the issue I mentioned of overflow detection being expensive.