假设我进行了仅涉及加法和乘法的计算：
(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 人群的洞察力和观点。
问问题
680 次
5 回答
9
您想要的是有效地生成所有可能的等效代数表达式，并选择所需步骤最少的一个（在大多数机器上，将 X 添加三倍比将 X 乘以 3 便宜） 。
这样做是不切实际的，因为“等效”公式的数量是无限的。
然而，Pelegrí-Llopart 想出了一种方案，可以在给定固定数量的代数重写规则的情况下生成最优代码，称为 “BURS”（自下而上的重写系统）。这已在一些代码生成器中实现。
实质上，他离线构建了一个大型自动机，其状态跟踪一组可能的应用重写。每个状态都知道当它发生时要生成什么，因此代码生成的在线时间很便宜。
于 2010-12-22T10:53:22.170 回答
4
有一个霍纳规则 可以有效地评估单项形式的多项式。根据它，给定一个 n 次多项式
p(x) = a n x n + a n-1 x n-1 + ... + a 1 x 1 + a 0
只需要 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 1 )x + a 0
于 2010-12-20T11:08:00.753 回答
1
一个想法 - 让我们将变量视为布尔值并编写 maxterm 表单 链接文本
于 2010-12-21T09:32:34.467 回答
0
不确定一般情况，但似乎分解多项式确实可以提高性能。来自遥远的comp sci课程的一个例子：
a * x^2 + b * x + c
通过分解 x 得到改进：
x * (a * x + b) + c
于 2010-12-07T21:33:01.517 回答