Как стать автором
Обновить

Используем быстрое возведение матриц в степень для написания очень быстрого интерпретатора простого языка программирования

Время на прочтение 6 мин
Количество просмотров 35K
Всего голосов 173: ↑169 и ↓4 +165
Комментарии 55

Комментарии 55

Это просто замечательно. Никогда не подозревал ранее, что благодаря матрицам можно вытворять такое. Спасибо за полезные примеры.
У вас нотация довольно необычная. Обычно в математике используются векторы-столбцы и умножают матрицы на векторы а не наоборот. Потратил минуту чтобы понять, почему же матрица выглядит именно так.

А вообще довольно интересно.
Вообще-то в математике есть много чего, в том числе и row-vector наравне с column-vector (обычно их определяют как матрицы 1xN и Nx1).
Более того, столбцы можно считать обычными векторами, а строки — ковекторами (функционалами на векторах), тогда произведение строки на столбец будет соответствовать применению функционала к вектору, а столбца на строку — взятию тензорного произведения вектора на функционал (и получится линейный оператор).
Таки тензоры рулят:)
Можно, только без векторного пространства и преобразований координат в нём они ничем не отличаются от матриц 1xN и Nx1 )
Ну это один из способов записи (при фиксированном базисе). А тензорное произведение — это обобщение произведения матриц, которое, в свою очередь, обобщение, например, применения функционала к вектору.
А транспонирование матрицы — это свертка с \delta_i^j.
В общем, мне лично нравятся такие теории, которые выявляют общее в на первый взгляд существенно различных вещах.
Но это были так, мысли вслух)
Да, в такие моменты задумываешся, почему не ходил на пары с векторного и тензорного анализа… интересно блин, а понять ничего не могу… )
Если интересно — почитайте «Алгебру» Винберга, там хорошо эти темы изложены.
а теперь, то же самое для

loop 100000000
   psw = md5(psw + "salt")
end


:D
Гениально…

Когда читал про оптический компьютер, который фактически является укорителем перемножения матриц, то какраз думал про то, каким алгоритмом можно привести любой код к матричным вычислениям (а потом, получив их в виде математического выражения, а их можно упрощать, приводить к какому то другому виду, и т.п.)… осталось придумать, какой операция над матрицей должен стать операнд if then else… только ветвлений не хватает до полного катарсиса, а так же зависимость количества итераций цикла от значения операндов (одно следует из другого), чувствую это возможно, но как…

p.s. а теперь добавьте сюда параллельные вычисления ведь одновременные вычисления с разными переменными неплохо вписываются в одну операцию с матрицами…
Я думаю, что способа достигнуть катарсиса нет. Мы можем свести к перемножению матриц только линейные операторы в пространстве линейных форм над <1, a, b, c, d...>. А, скажем, умножение переменной на переменную уже дает не линейную, а квадратичную форму.
Спасибо за статью. Есть вопрос: можно ли реализовать(имеется ввиду через матричные преобразования) битовые операции: NOT, OR, AND (все операнды — переменные)?
если вместо сложения взять XOR, вместо умножения — AND, алгебраические тождества будут выполняться (получим вычисления в поле вычетов по модулю 2). NOT можно получить формулой NOT x = 1 XOR x

другой любопытный пример — пусть сложение OR, а умножение AND.
если взять матрицу A смежности графа (A[i,j]=1 если между i и j есть ребро), то A^2 — матрица достижимости пути за 2 шага, A^3 — за 3 и т.д… A^n — матрица связности (An[i,j]=1 если есть путь от i к j, n — число вершин графа, любой кратчайший путь от i к j не длинее n, поэтому степень выше n рассматривать избыточно). возведение в степень n для поиска матрицы связности тоже можно делать этим быстрым алгоритмом
Вот только матрицы перемножаются дольше, чем O(n^2), так что этот алгоритм будет работать дольше, чем O(n^2 log n), в то время как банальный поиск в ширину даст сложность O(n+m) для списка ребер (где m — количество ребер), или, для матрицы смежности, O(n^2).
но поиск в ширину/глубину — последовательный алгоритм (стек, очередь). распараллелить можно попробовать, но теории нет, чтобы сделать это формально, не задумываясь
Зато у него константа куда лучше, чем у быстрого перемножения матриц. И пригодные для практического использования алгоритмы умножения вроде бы имеют сложность O(n^{2+epsilon}) для, как правило, достаточно большого (>0.1) эпсилон.
Так что, поскольку это всё есть смысл обсуждать только для очень больших графов (десятки тысяч и больше вершин), то распараллеливание едва ли спасет алгоритм с худшей ассимптотикой и константой.
К тому же поиск пусть не в ширину, а в глубину вроде бы вполне красиво параллелится.
и всё-таки, у этого подхода есть практическое применение, опережающее обход в ширину.
это когда нужно найти матрицу расстояний для каждой пары i, j

только уже не булевские операции надо использовать, а сложение обычное, а умножение — min
Ну да, для матрицы расстояний это получается обобщением алгоритма Флойда (который получается, если вместо быстрого перемножения матриц использовать обычное). Но для матрицы достижимости такой метод всё-таки неинтересен.
Кстати, а алгоритмы быстрого перемножения матриц не завязаны на, например, дистрибутивность умножения (я этого не помню, а смотреть и думать сейчас лень)?
в системах операций OR/AND, XOR/AND дистрибутивность выполняется
Я про минимум (для нахождения матрицы расстояний).
Флойдом можно найти матрицу достижимости за куб — на практике это должно быть всегда быстрее, чем возведение матрицы смежности в степень.
Нет, конечно. Быстрое умножение матриц имеет не такую уж большую константу.
Даже если при больших N быстрое возведение в степень с быстрым умножением будут быстрее, чем флойд, я бы все равно остановился на флойде, хотя бы из-за его простоты.
Вариант с поисками в ширину тоже приятный — у него тоже кубическая сложность на плотных графах (а на разряженных еще меньше), но зато его можно легко запустить на нескольких процессорах сразу. Аналогично, если надо найти не матрицу достижимости, а все кратчайшие пути, на современном железе, наверное, N дийкстр будут очень эффективны, потому что их можно тоже легко распараллелить, сохраняя все ту же кубическую сложность.
Угу. А пузырек вместо быстрой сортировки из-за его простоты Вы не выберете? Как и перемножение матриц «в лоб» вместо быстрых алгоритмов?)
Простота реализации важна в некоторых случаях, но далеко не во всех. Вы, думаю, не обрадуетесь видеокартам в 5 раз дороже и в 10 раз медленнее из-за того, что их разработчики, как и Вы, предпочитают медленные, но простые алгоритмы.
А все стандартные алгоритмы быстрого перемножения матриц вроде бы прекрасно параллелятся.
Я думаю причиной этого небольшого разногласия является мое устаревшее представление о быстром умножении. Лучшее, что я знаю, работает за степень примерно 2.7. На графе с 10000 вершин разница с кубом будет в 15 раз, но быстрое возведение в степень потребует еще логарифм, который от 10000 даст 14, и смысл потеряется, потому что у быстрого умножения костанта выше, чем у флойда.

Если есть алгоритм быстрого умножения заметно быстрее, чем за (N^2.7), то тогда мои размышления о флойде, вероятно, заметно отличались бы.
Из применимых на практике вроде бы быстрее всего прямые суммы Шенхаге, которые вроде бы работают примерно за n^2.52. Что дает выигрыш в 63 раза по сравнению с лобовым.
С учетом логарифма — выигрыш в 6 раз на 10000 и в 15 на 100. Что, скорее всего, с лихвой перекрывает константу.
Вообще я, быть может, высказался немного резко, приношу извинения. Просто мне очень уж не нравятся фразы вида «даже если по-другому будет лучше, всё равно сделаю как проще».
Асимптотически лучший алгоритм перемножения матриц имеет экспоненту 2.373 (т.е. сложность n2.373)
Вот только константа и затраты памяти там, вроде бы, совершенно ужасные.
Не «вроде бы», а точно :) Даже у Штрассена константа раз в 10-100 (зависит от реализации) больше, чем у алгоритма по формуле.
Есть задачи, которые решаются возведением матрицы смежности графа в степень.
Например: codeforces.ru/contest/147/problem/B.
Если конкретнее, то задача звучит так: кратчайшие пути между всеми всеми вершинами, состоящие ровно из N рёбер :)
Зависит от способа записи:)
NOT X при любом разумном способе записывается как 2^k — 1 — X.
А вот OR и AND, скорее всего, ни при какой разумной записи выразить будет нельзя. Разве что хранить вектор значений всех возможных функций наших переменных:)
я имел ввиду матрицы не из чисел, а из bool
Ну, в Z_2 AND вообще нелинейная операция и выразить ее линейно нельзя)
не понял утверждения.
умножение в действительных числах тоже не выражается через сложение.
Вопрос был «можно ли реализовать(имеется ввиду через матричные преобразования) битовые операции».
Насколько я понимаю, имелся в виду тот же метод, что и в статье, т.е. вектор из переменных (и, быть может, побочных значений) мы линейным преобразованием переделываем в вектор функций от этих переменных (и, быть может, побочных значений).
Утверждение было: преобразование (x, y) -> (x AND y, z(x, y)) нелинейно над Z_2^2 ни для какой функции z.
да, теперь понял. для данного примера нужно искать систему операций, где AND выполняла бы роль сложения
Z_2 операция AND и есть умножение
Произведение любых матриц ассоциативно, не только квадратных, разве нет?
Да вроде, да.
Оригинальный подход — за него однозначный плюс :) Хоть и малоприменим на практике, так как позволяет брать только уж совсем специфичные случаи.
Простая идея, простая реализация, молодец! Подобный DSL очень бы пригодился на всяких codeforces/topcoder :)
Отличная статья, приятно видеть такие на хабре. Она почти вернула мне веру в то, что математика в программировании таки небесполезна :)
Всегда знал, что матрицами можно «сворачивать» вычисления, использовал это и в расчетах четырехполюсников, и когда с 3D разбирался.

Но никогда не понимал, ПОЧЕМУ это работает? ПОЧЕМУ блин так происходит, А?

То есть, я пользуюсь аппаратом, но не понимаю, почему он работает.

Я уже считаю, что это какое-то непознанное свойство материи или там пространства-времени, которое так отображается в математике нашего мира.
«Почему» — очень сложный вопрос. То, что он работает, можно доказать. Является ли это свойством реальности или лишь свойством нашей теории — сказать, скорее всего, невозможно.
Причем описание матрицами линейных преобразований — это еще очень простой аппарат. Вот то, что работают дифференциальные формы, тензорный анализ на гильбертовых пространствах, обобщенные функции и т.д. — гораздо удивительнее.
Пользуясь случаем, в очередной раз прорекламирую статью «Непостижимая эффективность математики в естественных науках».
Это действительно замечательно и я всерьёз намерен использовать это для ускорения вычислений. Жаль, правда, что такой язык не обладает полнотой, т.к. может работать только с циклами, для которых точно известно количество итераций, что даёт очень узкий класс решаемых задач (это даже не примитивно-рекурсивные, для которых известно максимальное количество итераций — ещё уже). И поэтому, наверное, языком программирования это вообще называться не может. Или я что-то проглядел?
Алгоритм кстати на столько прост, что его можно автоматически внедрять в код, подставляя его в код вместо циклов… ведь во время выполнения больше случаев, когда количество итераций известно…

p.s. я считаю идею нужно развивать, ведь математические выражения можно упрощать не только через возведения в степень (правда алгоритм получается не совсем тривиальным)… основная польза от этого — нереально крутые возможности по распараллеливанию кода (матричные вычисления этому очень способствуют).
Любобытно.
Возникла идея: а что если расширить цикл и на нецелые числа и вычислять степени матриц с помощью разложения в ряд Тейлора? Тогда возможно будет вычислять корни.
Например вот так: loop 0.5. Не уверен, что это корректная операция, но попробовать стоит.
Вычислять корни не получится — умножать-то можно только на константу.
умножение (только на константу)
Вы внимательно прочитали, что я написал?
Я говорил про возведение матриц в дробную степень и умножение переменных на константу тут совсем не при чем.
Ну расскажите мне, как умножив на какую-либо константу половину раза, Вы сможете вычислить корень из переменной (корни из констант, очевидно, не нужны — это те же константы).

Предположим, что мы как-то придумали возведение в степень. Скомбинировали тысячу различных извращений (включая ряды Тейлора, Маклорена, Лорана — кого пожелаете) и получили его (а точнее — её, чудесно-волшебную матрицу, возводящую элементы любого вектора в некоторую степень, допустим, 3). Т.е. мы получили для вектора v (пусть он будет таким: [ a b 1 ]) матрицу M, такую, что v * M = [ a³ … … ]. Тогда имеем для произвольного λ:
λ[ a b 1 ] * M = [ λa λb λ ] * M = [ (λa)³ … … ]
с другой стороны
λ[ a b 1 ] * M = λ ([ a b 1 ] * M) = λ [ a³ … … ] = [ λa³ … … ]
Таким образом, λa³ = (λa)³, a = 0 (возводить нули в степень скучно) => λ = λ³, но у нас-то λ любое!

Очевидно, что если бы такая матрица M существовала, но она должна была бы зависеть от текущих переменных, т.е. являться функцией вектора M(v). А это ломает всё, что мы здесь придумали — цепочку вычислений
v = v * M1v
v = v * M2v

v = v * Mnv
(для упрощения скобки у вызовов функции опущены) Мы уже не сможем «свернуть» так же просто, как в статье. Разве что

v = v * M1v * M2(v * M1v) * M3(v * M1v * M2(v * M1v)) * … * Mn(v * M1v * M2(v * M1v) * … * Mn-1(…))
однако вычислять это в таком виде — очевидно, феерическая глупость.
Привет — два года спустя пользователь hx0 написал подробную статьи про свой модуль оптимизации байт-кода Python, основанный на алгоритме из твоей статьи. Оставляю этот комментарий, чтобы поместить линк на более новую статью: «Автоматическая оптимизация алгоритмов с помощью быстрого возведения матриц в степень».
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории