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

For an even faster algorithm, http://arxiv.org/pdf/0801.1416v3.pdf and its prequel http://www.cse.psu.edu/~furer/Papers/mult.pdf both beat strassen.


I don't think this is terrible practical. Just as SSA wasn't efficient until the advent of modern computers and for integers of about millions of bits, so Furer's algorithm probably isn't efficient until integers are so large that their number of bits takes million of bits to write down. I won't say never, but it isn't going to be practical any century soon.

The multimodular version is likewise pretty useless in practice.


in practice, certainly! The devil's in those constant factors etc :)




Consider applying for YC's Summer 2026 batch! Applications are open till May 4

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

Search: