4 ms·
I already know about fast multiplication algorithms, but it seems there's still no proof that a faster algorithm absolutely cannot exist. In other words, we don
by jdw64 3mo ago
I already know about fast multiplication algorithms, but it seems there's still no proof that a faster algorithm absolutely cannot exist. In other words, we don't know where the limit is yet.
If that gets proven, would programming multiplication algorithms become faster? I'm curious
- TimTheTinker 3mo agoThe O(n log n) algorithm is galactic (only becomes more efficient when multiplying massive numbers) So for numbers we normally work with, no. Maybe with cryptographic operations though.
- jason_s 3mo agoEven crypto isn't that large: 2^4096 is kind of the norm here. Some mathematical researchers are working in the million, billion, or even trillion-bit range.
- groundzeros2015 3mo agoMatrix multiplication is constantly getting improved but these methods aren’t improvements on practical implementation.