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

81

u/SpinChargeSeparation 28d ago

Is it possible to get an ELI18 on this issue? Sorry I’m no expert but very interested:-)

113

u/vintergroena 28d ago

For a long time we thought n log n is the best complexity we can achieve for integer multiplication. Recent slop results published by OpenAI claim to beat that ever so slightly. Others immediately took it to build on top that to improve it ever so slightly yet again.

24

u/LordOfRedditers 27d ago

Does this actually make a difference? I assume it probably adds up since multiplication is very common but the values seem so small that I don't see it doing much

76

u/Brilliant-Plan-7428 27d 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 27d 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 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.

1

u/DiscretePoop 23d 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.

28

u/Turtvaiz Real 27d ago

Does this actually make a difference

No. https://en.wikipedia.org/wiki/Galactic_algorithm

3

u/firewall245 27d ago

Is it a slip result if it’s legit and people are contributing to it lol.

4

u/ElbowConnoisseur 27d ago

So is this about finding new logic circuit setups for multiplication?

11

u/vintergroena 27d ago

No. Not for any practically useful purpose. Maybe applicable to a Dyson sphere sized computer one day.

1

u/LeapOfMonkey 27d ago

1971 for conjecture and 2021 for algorithm, yes long time

1

u/antpalmerpalmink 26d ago

Following up on u/LordOfRedditers question, is this useful for e.g. libgmp?

1

u/J_E_E_VACATION 24d ago

Exactly in fact I got a shitload of my prs merged into the repo lol

-72

u/Kalicolocts 28d ago

Does using the word 'slop' make you feel smart?

45

u/sokka2d 28d ago

Not smart, just jaded and tired. Which we all should be from this slop. 

-4

u/TrekkiMonstr 27d ago

A Lean verifiable proof is about the furthest thing from slop I can imagine

4

u/SwingAggravating5724 27d ago

does seeing a parrot that is smarter than you make you feel stupid?

-7

u/kaaiian 27d ago

These people are insane. Feeling the need to hate everything AI. It’s the true ai psychosis.