Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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



The 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.


Even 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.


Matrix multiplication is constantly getting improved but these methods aren’t improvements on practical implementation.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: