简化表达式的运算次数

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重新发问，旨在获取计算机科学群体的见解和观点。

- Hooked

---

鉴于优化矩阵乘法所面临的困难，我强烈怀疑这是一个未解决的问题。 - RBarryYoung

如果目标真的是减少总操作数，那为什么要使用计算机来计算呢？我只是说一下。 - Zac Thompson

Answer 1

你需要的是有效地生成所有可能等价的代数表达式，并选择需要步骤最少的一种（在大多数机器上，将X加三次比将X乘以3更便宜）。

由于“等价”公式的数量是无限的，因此这是不切实际的。

然而，Pelegrí-Llopart想出了一种方案来生成最佳代码，称为"BURS" (自底向上重写系统)。 这已经在一些代码生成器中实现了。

本质上，他离线构建了一个大型自动机，其状态跟踪可能应用的重写集合。 每个状态都知道何时发生时要生成什么，因此代码生成的在线时间很便宜。

- Ira Baxter

---

这就是我一直在寻找的！我猜答案来自编译器优化技巧，这并不奇怪。 - Hooked

Answer 2

忽略变量的幂和整数系数，这可以简化为一个 卡诺图 问题。

K-Map 可以表示为与积和积形式，每种形式都代表了一个二进制电路。 "最少操作" 形式将代表一个 优化的二进制电路，对吗？

- Daniel

---

我看不到联系。你能补充一些细节吗？ - Draco Ater

我的观点是，由于电路最小化问题被认为是不可解的[Wikipedia]，因此没有过程性程序能够在多项式时间内找到最优解。二进制表达式(a+b)(c+d)的计算结果为TRUE，如果(either a OR b is TRUE) AND (either c OR d is TRUE)。在这个意义上，只涉及+（OR）和（AND）的算术运算，其中每个变量都是0或1，代表一个二进制电路。 - Daniel

但是，你可以离线预先计算特定集合的最优解，并在线应用该答案。请参阅我的回答。 - Ira Baxter

哇，我很惊讶这样的优化已经被实现了，考虑到这种方法所需的计算能力和内存空间。 - Daniel

这里的“难以处理”是一个技术术语，意思是如果你提出了一个比指数级更好的解决方案，那么全球所有的数学家都会比听到上帝从天而降对他们说话更惊讶。（或者，用数学家的话来说，微笑着说，“这是否可能仍然是一个未解之谜”。）但是小规模的例子可以轻松解决，没有问题。 - Evgeni Sergeev

Answer 3

有一种霍纳规则可以高效地计算单项式形式的多项式。根据该规则，给定一个n次多项式

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

只需要n次乘法（不是n+(n-1)+(n-2)+...+1 = n(n+1)/2，尽管从第一眼看上去是这样）。这是因为多项式可以重写为

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

- Draco Ater

Answer 4

一个想法 - 让我们将变量视为布尔值，并编写最大项式形式 链接文本

- HamoriZ

---

同时计算SumOfProduct和ProductOfSum，看哪个更短。 - ktharsis

Answer 5

不确定一般情况，但似乎分解多项式可以提高性能。来自一个遥远的计算机科学课程的例子：

a * x^2 + b * x + c

通过分解x来改进：

x * (a * x + b) + c

- Chris

---

明显地，分解多项式是一个很好的启发式方法，但我对于“最佳可能”的情况感兴趣，这使得它成为了一个明确定义的（尽管困难？）最小化问题。 - Hooked

是的，我明白了。您的示例和我的示例都通过因式分解得出了最佳结果。另一个例子：abc+bcd+ade; 有三种因式分解方法：bc(a+d)+ade，a(bc+de)+bcd，d(bc+ae)+abc。显然需要更多的努力。假设这是正确的方向，我会采用暴力优化的方式。也许其他人会提出更加优雅的解决方案。 - Chris