4 ms·
I remember implementing strassen, only to be surprised that the naive implementation was actually faster, because it better exploited the machine architecture..
by asimpletune 8y ago
I remember implementing strassen, only to be surprised that the naive implementation was actually faster, because it better exploited the machine architecture... that is until I tried using absolutely huge numbers.
This recent innovation is very exciting.
- gowld 8y agothe past 12 years of algorithm optimizations remove a fator of log(log(n)) from Strassen -- which means multiplying 1million bit numbers is 20x faster, ignoring constant factors and cost of cache misses. Constant factors and hardware architecture are still hugely important in choosing the best practical implementations for a problem.
- thomasahle 8y agoStrassen is for multiplying matrices. This is integers.
- ahelwer 8y agoThey probably meant Schönhage–Strassen, which is for integers.