Mathematicians still don't know the fastest way to multiply numbers

Post by necovek » Tue, Jul 21, 2026, 5:51 PM UTC

avmich wrote: post #88

necovek wrote: post #34

Earlier quoted context omitted.

You mean like those guaranteed-always-compresses-by-at-least-one-bit algorithm patents gzip page made fun of? In your case, doing prime factoring is where the cost would be, wouldn't it?

Yes, but the point is to look for different representations, not necessarily use this specific one.

Yes, but the point is that getting to a different representation from a natural one (eg. binary one with computers or a decimal one for human use) is going to have some "external" overhead which is likely to negate the savings.

Yes, sometimes a neat trick like the one in the article of replacing one multiplication with substraction appears, but that is not as universal.

Post by Bratmon » Tue, Jul 21, 2026, 7:03 PM UTC

xtajv wrote: post #150

Bratmon wrote: post #114

Earlier quoted context omitted.

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?

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

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.

Re: Mathematicians still don't know the fastest way to multiply numbers

Re: Mathematicians still don't know the fastest way to multiply numbers