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

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

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

Answer 5

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

a * x^2 + b * x + c

улучшен с учетом x:

x * (a * x + b) + c