?

Log in

Удивительное рядом - 301 Moved Permanently
September 12th, 2014
10:44 am
[User Picture]

[Link]

Previous Entry Share Next Entry
Удивительное рядом
tl;dr опять про математику

А знаете ли вы, что неизвестно, какое минимальное количество умножений нужно совершить для того, чтобы умножить две матрицы 3x3? В 1976 году был придуман алгоритм с 23 умножениями. Позволю себе процитировать часть статьи:

The algorithm in this paper was produced by finding an integer solution to the following system of 729 nonlinear algebraic equations involving 621 unknowns

[...]

No use of computers was made in solving this system of equations.
Через 35 лет был придуман другой алгоритм с 23 умножениями. Алгоритма с 22 умножениями (как и доказательства того, что его не существует), насколько мне известно, нет.

Для матриц 2x2 нужно 7 умножений; есть и алгоритм, и доказательство. herereplycomment count unavailablecomments

Current Mood: contemplativecontemplative
Tags:

(2 comments | Leave a comment)

Comments
 
[User Picture]
From:k_shemyak
Date:September 16th, 2014 03:34 pm (UTC)
(Link)
А у этого факта есть практическое значение - в смысле, помимо эстетического? Сейчас же процессоры за один такт и складывают, и умножают, так что не количество умножений важно - правильно?
[User Picture]
From:avysk
Date:September 16th, 2014 04:03 pm (UTC)
(Link)
Не знаю, но думаю, что практическое значение может быть -- элементы матриц могут не помещаться в регистр CPU, например; или не быть вещественными числами вообще (например, они могут быть кватернионами, матрицами, символьными выражениями…).
Unnkerr blog Powered by LiveJournal.com