Уменьшите количество операций над простым выражением

Question

Допустим, я беру вычисления, которые включают только сложение и умножение:

(a+b)*(c+d)

что может быть сделано многими другими способами, например.

a*(c+d) + b*(c+d)
a*c + a*d + b*c + b*d

С точки зрения сложений и умножений количество операций, требуемых для каждого из трех показанных примеров, составляет (2,1) (3,2) (3,4) соответственно. Понятно, что если цель состоит в том, чтобы уменьшить общее количество операций, то первая будет лучше. Есть ли способ, учитывая произвольное выражение, чтобы найти порядок вычисления, который требует наименьшего количества операций?

Примечание: этот вопрос повторно задается в SE.math для понимания и перспективы толпы CS.

Answer 1

Вам нужно эффективно сгенерировать все возможные эквивалентные алгебраические выражения и выбрать то, которое требует наименьшего количества шагов (добавление X в три раза дешевле на большинстве машин, чем умножение X на 3).

Это нецелесообразно, поскольку число "эквивалентных" формул бесконечно.

Тем не менее, Пелегри-Льопарт разработал схему для генерации оптимального кода с фиксированным числом правил алгебраической перезаписи, называемую "BURS" (система перезаписи снизу вверх). Это было реализовано в некоторых генераторах кода.

По сути, он создает в автономном режиме большие автоматы, состояния которых отслеживают множество возможных прикладных переписываний. Каждое государство знает, что генерировать, когда это происходит, поэтому время генерации кода в сети дешево.

Answer 2

Игнорирование степеней переменных и целочисленных коэффициентов сводит к проблеме карты Карно.

K-карты могут быть представлены в виде суммы продуктов и формы продукта сумм, каждая из которых представляет двоичную схему. Форма "наименьшего количества операций" будет представлять собой оптимизированную двоичную схему, верно?

Answer 3

Существует правило Хорнера для эффективной оценки полиномов в мономиальной форме. Согласно ему, задан многочлен степени n

p (x) = a_n xⁿ + a_n-1 x^n-1 +... + a₁ x¹ + a₀

Необходимы только n умножений (не n+(n-1)+(n-2)+...+1 = n(n+1)/2, как это может показаться на первый взгляд). Это потому, что многочлен можно переписать как

p (x) = (((a_n x + a_n-1) x + a_n-2) x +... a₁) x + a₀

Answer 4

Одна идея - давайте рассмотрим переменные как логические значения и напишем текст ссылки на форму maxterm

Answer 5

Не уверен насчет общего случая, но кажется, что факторинг полиномов повышает производительность. Пример из далекого компьютерного курса:

a * x^2 + b * x + c

улучшается с учетом x:

x * (a * x + b) + c