Hoo*_*ked 15 computer-science symbolic-math
让我们说我采取的计算只涉及加法和乘法:
(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人群的见解和观点.
你需要的是有效地生成所有可能的等效代数表达式,并选择一个需要最少成本的步骤(添加X三次是大多数机器比乘以3 X便宜)号.
这样做是不切实际的,因为"等效"公式的数量是无限的.
然而,Pelegrí-Llopart找到了一种方案,在给定固定数量的代数重写规则(称为"BURS"(自下而上重写系统))的情况下生成最佳代码 .这已在一些代码生成器中实现.
实质上,他构建了一个大型自动机离线,其状态跟踪可能的应用重写集.每个州都知道它发生时要生成什么,因此代码生成的在线时间很便宜.