4 ms·
> For a processor with well-documented microarchitecture, for which a programmer or a compiler can deterministically write an optimal program We don't even kno
by mjlee 1y ago
> For a processor with well-documented microarchitecture, for which a programmer or a compiler can deterministically write an optimal program
We don't even know the optimal algorithms! AlphaEvolve recently found "an algorithm to multiply 4x4 complex-valued matrices using 48 scalar multiplications, improving upon Strassen’s 1969 algorithm that was previously known as the best in this setting." - https://www.nature.com/articles/s41586-022-05172-4 https://www.nature.com/articles/s41586-022-05172-4
- hmry 1y agoFor those who don't want to read the article: The previous best was 49 scalar multiplications.
- mattkrause 1y agoAnd I believe some humans subsequently knocked it down to 47?
- adrian_b 1y agoI was not referring to algorithm designing, but to algorithm implementation on a given processor, which consists in things like register allocation, machine instruction selection and static instruction scheduling.