Ask HN: Residue Number Systems for GPU computing as indie-researcher. Thoughts?
by muragekibicho | 2025-05-19 17:26:19+00:00
I've been thinking about "Are there analogs to parallel computing rooted in number theory? Like a way to emulate a GPU on a regular CPU, but not through hardware. Rather by replacing GPU threads with concepts from prime numbers and finite field theory?" I know this sounds cookiesque.

However, I care about this question because, in a world where AI is becoming commonplace, being GPU-poor is somewhat akin to being locked out of the future. There must be some way to perform lots of matmuls (or at least an intelligence-evoking amount of muls) on consumer CPUs. Maybe we just haven't invented the right number system. I believe Math is mostly invented, rarely discovered. ie binary 1's and 0's are surely discovered. However, floating-point, and fixed-point, are human inventions tweaked for specific use cases.

In fact, researchers built Residue Number Systems(RNS) in the 1960's as an alt to binary Base-2 arithmetic for wildly parallel computing. However, they fell out of favor because finite field theory (the foundational math for RNS) supports addition and multiplication : neither division nor comparisons are supported. Here's the thing : matrix multiplications are merely mults and adds. RNS is great for general matmuls but fails at stuff like softmax and backprop.

I argue that solving the division, and comparison problem for RNS is the key to solving GPU poverty. RNS's foundational research was done in the 1960's. What if math invented in the 21st century is needed to solve this?.For context, only after the invention of new mathematics in the 20th century did Wiles prove Fermat's Last Theorem.

I know "Talk is Cheap" and that I need to "Be the change i want to see in the world".

So here's everything I attempted with the RNS problem and how it failed : *Please be lenient with criticism. I'm not VC funded so I do this during my nights and weekends after coming home from my day job.

1. Finite Field Gemm (Attempting to rewrite backpropagation within a residue number system)

It works in principle but in practice, it involves big integer multiplications and additions. So during the backward pass, the deltas are rather large making it impossible to converge towards a local minima. Link : https://leetarxiv.substack.com/p/ffgemm-finite-field-general-matrix

2. Mediant 32 (A fractional number system to get rid of explicit division in RNS) - We can't divide efficiently in an RNS so why not have an explicit integer and denominator? It works extremely well, honestly, I was impressed. The only difficulty is with handling overflow. The fractions tend to become quite large and the absence of division makes simplification difficult. Link : https://leetarxiv.substack.com/p/mediant32-intro 3. Discrete Logarithm Neural Networks (A network architecture built around big integers because my biggest challenge was dealing with big ints) - It actually works. I was surprised that it got a 74% accuracy on the Iris dataset. The problem is that training the network involves solving a discrete logarithm problem. So my network weights can only be found by brute force. I don't think I'll find a way to backpropagate. If I do then I would achieve the impossible : solving modern-day cryptography. Link : https://leetarxiv.substack.com/p/discrete-logarithm-neural-networks

Next steps: I'm looking at the Factorial Number System. The modulo function is pretty well defined and it supports floating-point and reals so I don't have to worry about the RNS division problem. I bet I can define an RNS using factorials and this will be easy to work with. I started by going down the Enumerative Combinatorics rabbit hole here Link : [What Every Programmer Should Know About Enumerative Combinatorics ] (https://leetarxiv.substack.com/p/counting-integer-compositions?r=2at73k)

Let me know what you guys think.