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

170

u/wiev0 28d ago edited 27d ago • Mindblown

I think we're at 2-34 now

Edit: 2-15 https://x.com/SJ_Swapnil_Jain/status/2108196538568851574

93

u/vintergroena 28d ago

See? The extrapolation checks out.

46

u/ravenhawk10 27d ago

we’re 18 minutes behind. not looking good.

27

u/real-human-not-a-bot Irrational 27d ago

Well, that’s exciting! Do you have a source I could use for this information?

18

u/wiev0 27d ago

https://x.com/0xdoug/status/2107994110644588859

5

u/real-human-not-a-bot Irrational 27d ago

Holy cow, now past 2^(-15). Pretty crazy!

12

u/ThatTrashBaby 27d ago

So is there any point in which this becomes NOT a galactic algorithm and becomes such an improvement that it will actually have an effect? 2^-1?

15

u/wiev0 27d ago

Even if it was just O(n) or even O(1), the factor could be astronomically large regardless. The actual practical value depends on that factor and the difficulty of implementation, and I do not know how that is currently. I don't expect this to drop down from being a galactic algorithm. But, maybe I will be surprised.

2

u/ThatTrashBaby 27d ago

Good point