减少简单表达式的运算次数
假设我进行的计算仅涉及加法和乘法：
(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 人群的洞察力和观点。
Lets say I take a computation that involves only addition and multiplication:
(a+b)*(c+d)
which can be done in many other ways, eg.
a*(c+d) + b*(c+d)
a*c + a*d + b*c + b*d
In terms of additions and multiplications the number of operations required for each of the three examples shown are (2,1) (3,2) (3,4) respectively. Clearly, if the goal is to reduce the total number of operations the first is superior. Is there a way, given an arbitrary expression to find the computation order that requires the least number of operations?
Note: This question is being re-asked from SE.math for the insight and perspective of the CS crowd.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
您想要的是有效地生成所有可能的等价代数表达式，并选择花费最少步骤数的代数表达式（在大多数机器上，将 X 加三倍比将 X 乘以 3 便宜）。
这样做是不切实际的，因为“等效”公式的数量是无限的。
然而，Pelegrí-Llopart 找到了一种方案，可以在给定固定数量的代数重写规则的情况下生成最佳代码，称为 “BURS”（自下而上的重写系统）。这已在一些代码生成器中实现。
本质上，他离线构建了一个大型自动机，其状态跟踪可能应用的重写集。每个状态都知道在发生时要生成什么，因此代码生成的在线时间很便宜。
What you want is to effectively generate all possible equivalent algebraic expressions, and choose the one that takes the least costly number of steps (adding X three times is cheaper on most machines than multiplying X by 3).
It is impractical to do this, as the number of "equivalent" formulas is infinite.
However, Pelegrí-Llopart figured out a scheme to generate optimal code given a fixed number of algebraic rewrite rules, called "BURS" (bottom-up rewrite system). This has been implemented in some code generators.
In essence, he constructs offline a big automata whose states track the set of possible applied rewrites. Each state knows what to generate when it occurs, so the online time for code generation is cheap.
忽略变量和整数系数的幂，这会简化为卡诺图问题。
K-Map 可以用乘积和形式和和乘积形式表示，每种形式都代表一个二进制电路。 “最少操作”形式代表优化的二进制电路，对吧？
Ignoring powers of variables and integer coefficients, this reduces to a Karnaugh Map problem.
K-Maps can be represented in sum-of-products form and product-of-sums form, each of which represents a binary circuit. A "fewest operations" form would represent an optimized binary circuit, right?
有一个霍纳规则，用于有效评估单项式形式的多项式。据此，给定 n 次多项式
p(x) = anxn + an-1xn -1 + ... + a1x1 + a0
只需要 n 次乘法（而不是 n+(n- 1)+(n-2)+...+1 = n(n+1)/2，乍一看似乎如此）。这是因为多项式可以重写为
p(x) = (((anx + an-1)x + an-2< /sub>)x + ... a1)x + a0
There is a Horner's Rule for the efficient evaluation of polynomials in monomial form. According to it, given a polynomial of degree n
p(x) = anxn + an-1xn-1 + ... + a1x1 + a0
Only n multiplications are needed (not n+(n-1)+(n-2)+...+1 = n(n+1)/2, as it may seem from the first glance). That is because the polinomial can be rewritten as
p(x) = (((anx + an-1)x + an-2)x + ... a1)x + a0
一个想法 - 让我们将变量视为布尔值并编写 maxterm 形式
链接文本
One idea - let's consider the variables as boolean values and write the maxterm form
link text
不确定一般情况，但分解多项式似乎确实可以提高性能。远程计算机科学课程中的一个示例：
通过分解 x 进行改进：
Not sure about the general case, but it does seem that factoring polynomials improves performance. An example from a distant comp sci course:
is improved by factoring out x: