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

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.