优化算术表达式计算的算法

Question

优化算术表达式计算的算法

algorithmoptimizationexpression

4

假设我有一个由整数变量和算术运算（加法、减法和乘法）组成的表达式。我知道每个乘法需要 M 秒，而每个加法/减法需要 A 秒。是否有一种算法能够以任意分配给变量的最高效方式计算表达式？（假设我只能在内存中存储一个数字）

例子:

M=10

A=1

表达式: a*a+a*b+b*b.

起初，它具有 3 个乘法和 2 个加法，因此总时间为 3*M+2*A=32.

然而，我们可以构建一个等价的表达式 (a+b)*(a+b)-a*b，其中只有 2 个乘法和 3 个加法，因此总计算时间将为 2*M+3*A=23.

- Evgenii.Balai

我们需要考虑计算解决方案所使用的每个M和A吗？ ;) - גלעד ברקן

是的，每个乘法操作的成本为M，每个加法操作的成本为。您不能重复使用获得的结果。（假设您正在使用逆波兰表示法，并逐步计算每个+或*步骤）。 - Evgenii.Balai

我不确定您是否理解我的问题--例如，在您的示例中，您将总计算时间描述为2*M+3*A=23。我想知道用于计算您的解决方案2*M+3*A=23中使用的M和A。也许需要另外3M和15A来计算23的解。在那种情况下，总数将是23+45... - גלעד ברקן

不，我们不需要考虑时间（23）的计算，假设我们有一个计时器来测量它。23是我们需要计算aa+ab+bb的时间，对于任意（整数）分配给a和b，使用等效形式（a+b）（a+b）-a*b。我想知道是否有一种算法（可以是任意复杂的），可以提出一个等效的形式，从而导致最快的计算。 - Evgenii.Balai

2个回答

1

您想应用总积算法。

请参见：

http://www.isiweb.ee.ethz.ch/papers/docu/aloe-2001-1.pdf

- Owen

我认为这不适用于这里。首先，它用于计算因子积的边际，而不是变量。其次，它不能保证在操作数量方面的最优性，并且取决于您选择的变量顺序。如果我错了，您能否展示如何在上述示例中使用它？ - Evgenii.Balai

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Abhishek Bansal · Accepted Answer

你基本上想减少乘法的数量。一种方法是以下步骤（我不知道结果成本是否能够证明算法的复杂性和成本）：

对于允许使用运算符优先级的所有操作数执行加法。
形成必须进行乘法的操作数对。
在这些对中，取出公共操作数并将其替换为它们的对应项。
更新这些对并返回步骤3。
当不存在这样的公共对时停止。然后只需进行剩余的计算。

例如： a*b + a*c + d*(e+f) 对 e 和 f 进行加法运算（假设 g = e + f） a*b + a*c + d*g 对：(a,b) (a,c) (d,g) a 在前两个对中是公共的，所以我们将 b 和 c 相加。