наука не стоит на месте

[avva]

(это будет интересно только программистам/компьютерщикам, зато они-то визжать будут от восторга)

Скотт Ааронсон рассказал потрясающее. Как вы помните, уже 20 лет лучший алгоритм для умножения двух матриц n x n делает эту неблагодарную работу за время O(n^2.376) - результат Копперсмита и Винограда. Так вот, появилась новая статья, в которой эта верхняя граница снижена - до O(n^2.373)!!!

Все подробности в этой статье (в ее введении есть также полезный обзор всей истории алгоритмов умножения матриц). Я сегодня, подозреваю, уснуть не смогу от возбуждения...

Comments

[dmpogo.livejournal.com]

Тем не менее N^3 не стоит пользоваться даже в реальных аппликациях

[ygam.livejournal.com]

Даже с матрицами 3x3?

[dmpogo.livejournal.com]

Разве 3x3 вы не умножаете в уме ??

[izard.livejournal.com]

В уме не выходит, только в L1D кэше.