[JoelJacobson]

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

[wormslayer666]

A bit tangential, but the folks behind the GNU Multiple Precision Library (GMPLib) have the problem of choosing algorithms more or less fleshed out. They've got some fairly approachable manual pages[1] for the various algorithms they use as operand sizes scale up, where Karatsuba is only the second of six options in terms of operational complexity.

[1] https://gmplib.org/manual/Multiplication-Algorithms

[inigyou]

This really demonstrates the utility of pulling in a library written by experts in the field the library handles.

[Bratmon]

This is a problem I have a lot in modern programming ecosystems: How do I tell the difference between a library written by a team of experts who have spent decades optimizing everything to do with the task and a library written by one guy that's an unnecessary straightforward wrapper over the obvious implementation?

[dspillett]

Or increasingly, a library written by an LLM referencing a pile of such “one guy” projects of varying levels of suck (from actually good to good-got-it-is-full-of-suck).

[spullara]

What I have been seeing recently is having a great LLM rewrite the library leads to fewer bugs and also optimized for your use case. More expensive for sure than pulling something like epub.js but when the library has infinite open issues it can be a lot better.

[xtajv]

1. Read the code 2. Don't. Encapsulate and put yourself in a position to swap out the implementation at will.

(Maybe you'll swap out an unnecessary dependency for a simple helper function of your own).

[Bratmon]

But if I followed that advice here, I would say "Obviously I don't need a library to multiply numbers" and miss the decades of research and optimization.

[layer8]

You defer to the advice of experts you trust. Which somehow have become harder to come by in terms of signal to noise than 20-30 years ago.

[JoelJacobson]

Here is the full pgsql-hackers mailing list thread where you can follow our work from initial idea to commit: https://www.postgresql.org/message-id/flat/9d8a4a42-c354-41f...

[sureglymop]

Love this, thank you for providing the context!

[kurlberg]

It's complicated. :-)

There is a nice picture of the "best" choice for different ranges of sizes of numbers to be multiplied at http://gmplib.org/devel/log.i7.1024.png

More context and explanation can be found at: http://gmplib.org/devel/