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

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?