Возьмем произведение двух матриц 3x3 A*B=C
. Наивно это требует 27 умножений с использованием стандартного алгоритма. Если бы кто-то был умным, вы могли бы сделать это, используя только 23 умножения, результат, найденный в 1973 году Ладерманом . Техника предполагает сохранение промежуточных шагов и их правильное комбинирование.
Теперь давайте исправим язык и тип, скажем, C++ с элементами double
. Если бы алгоритм Ладермана был жестко закодирован по сравнению с простым двойным циклом, могли ли мы ожидать, что производительность современного компилятора сгладит различия алгоритмов?
Примечания к этому вопросу:Это сайт по программированию, и вопрос задан в контексте передовой практики для критичного ко времени внутреннего цикла; преждевременная оптимизация это не так. Советы по реализации приветствуются в качестве комментариев.