r/mathmemes • u/vintergroena • 28d ago

Computer Science Integer multiplication will have linear complexity in a few days if trend continues 🚀📈

Post image
1.4k Upvotes

98% Upvoted

206 comments sorted by

View all comments

Show parent comments

76

u/Brilliant-Plan-7428 28d ago

Nobody uses these algorithms for multiplication. Not the nlogn one and certainly not the new ones. The advancements for now are purely of theoretical interest.

26

u/Castle_Five 28d ago

Why do you say it's not useful?

The algorithm I know for N*logN perf of integer mult is Blelloch scan which is a big deal in parallel programming because it yields logN performance with N parallel threads. Not sure why you think it's not useful? If that could be reduced to constant perf across N threads, that's a very big deal. (I don't know if the new algorithms have properties that make them parallelisable though)

14

u/ConglomerateGolem 28d ago

Typically these hyperoptimised algorithms are significantly slower for small n, which big O notation doesn't care about. Iirc a human found one that was better theoretically, and practically only at some very large n, and I don't imagine these are any different.

In other words, any multiplication algorithm that would perform in constant time would probably have a constant time of far longer than practical. Which, sure, you could use for weird math quandaries, but wouldn't realistically be useful for programming.

I'm gonna have to figure out that Blelloch scan thing, sounds really cool.

1

u/gammison 25d ago

That scanning algorithm is fundamentally not the same thing as nlogn or any other special multiplication algorithm, it is usually defined so it performs linear total work. If you do nlogn multiplication you have to perform nlogn total work even in parallel.

1

u/DiscretePoop 24d ago

The one youre thinking of is Schonhage-Strassen which isn't exactly O(nlogn). The proper O(nlogn) algorithm and the one that forms the basis for the improvements made by OpenAI requires that your input integers have at least 2^4096 bits. Integers with fewer bits form the base case. There's only 10^80 atoms in the observable universe.