Back in 2024, I was trying to optimize PostgreSQL's NUMERIC data type, which is base-10000, using Karatsuba. The problem of finding the optimal threshold of when to switch to Karatsuba turned out to be really hard, since it depends on the size of both factors combined. After some hundreds of hours, I gave up, and started thinking about if there could be a simpler solution. I came to think about another idea I'd had before but abandoned, about 64-bit modernizing the digit base from 10k to 100M, but that would be a challenge due to existing data on disk. Desperate of finding a solution, I wondered if it could be fast enough to do on-the-fly conversion back and forth between base-10k and base-100M, and then realized that, yes, of course, it will be fast already for quite small N (testing shows already between 3-6 base digits). The trick basically reduced the N in O(N^2) into half, i.e. O((N/2)^2), with some O(2*N) cost for the conversion back and forth.

I had a lot of fun hacking on this idea together with the maintainer of the NUMERIC data type, and after two months the patch finally was ready and got committed:

https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit...