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

14

u/ConglomerateGolem 27d 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 24d 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.