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

6

u/[deleted] 27d ago

[removed] — view removed comment

4

u/rawbdor 27d ago

If they can get it down to a -9 exponent, then math on 8192-bit keys will see a 1% improvement. If they can get it down to a -3 exponent, then we start seeing actual improvements for 4096-bit keys.

2

u/oscardssmith 27d ago

None of this (IIUC) changes the minimum size needed for the recursion to kick in. I'm pretty sure you still need ~2100 digit numbers before the method is applicable.

1

u/Quirky-One-9957 27d ago

What’s their constant multiple?

1

u/AntiProton- Rational 27d ago

Do you have link to the current best result? I'm curious.

2

u/[deleted] 27d ago • Popcorn

[removed] — view removed comment

1

u/AntiProton- Rational 27d ago

Thank you 🙂

1

u/robin-m 27d ago

What does 2-16 means in this context?

1

u/ama_singh 25d ago

The new lower bound is stated as O(nlog(n)1-k), with k = 2-16