6

所以这是我的情况：我有两个包含变量（x、y、z 等）的数学表达式。我已经使用分流场算法将它们编译为后缀以执行，现在我需要一种方法来测试它们是否在数学上相等。

例子：

x+5==5+x
x*2==x+x
4/(x/2)==8/x

我最初的想法是只抛出几千个不同的随机输入，看看评估结果是否相同。

我用这种方法预见的问题：精度问题、NaN 情况和可能的溢出。

所有的计算都是用 Java 的 double 类型完成的。

有任何想法吗？:)

编辑：由于这是一款休闲游戏，解决方案不需要完美，只要足够好！

4

3 回答 3

5

对于您提供的示例表达式，您可以转换函数以生成一个多项式除以另一个多项式，除数的系数最高，并且没有公因数。这会给你一个规范的形式——如果有区别，这两个函数真的会不同。但是，您还需要将系数表示为任意精度有理数或在这里也遇到精度问题，到那时您将编写大部分基本计算机代数系统，例如http://en.wikipedia.org中列出的那些/wiki/List_of_computer_algebra_systems - 其中包括一些免费系统。

于 2013-01-27T12:30:56.983 回答
4

根据维基百科关于这个主题：

http://en.wikipedia.org/wiki/Symbolic_computation

“数学表达式有两个相等的概念。句法相等是表达式的相等，这意味着它们以相同的方式编写（或在计算机中表示）。因为微不足道，数学家很少考虑它，但它是唯一容易用程序测试的等式。语义等式是两个表达式表示相同的数学对象，如

众所周知，可能不存在确定表示数字的两个表达式在语义上是否相等、表达式中是否允许指数和对数的算法。因此，（语义）相等性只能在某些类型的表达式上进行测试，例如多项式和有理分数。

为了测试两个表达式的相等性，而不是设计一个特定的算法，通常将它们置于某种规范形式或将它们的差异置于正常形式并测试结果的句法相等性。”

这似乎是最佳做法。

于 2013-01-27T12:26:42.123 回答
2

当我在这里结束时，我试图写基本相同的问题。但是我发现了一些这里没有提到的想法。首先，我同意@nelshh 的观点，即在某些特定情况下，您可以找到允许测试表达式相等性的规范形式。

我发现了一些规范形式的例子：

  • 最著名的可能是布尔代数中的最小项规范形式，例如用于电路综合或验证。
  • 多项式表达式也承认作为单项式之和的规范形式。这可以解决您的示例：
  • 有理数的规范形式是不可约分数。

你的例子：

  1. 两者都已经是规范形式，您只需要通过增加程度对它们进行排序。
  2. 2*x是其规范形式，x+x不是（因为加法的两个操作数具有相同的度数）。
  3. 两者都已经是规范形式（-1 次的单项式），除了其中的系数4/(x/2)不是4/(1/2)有理数的规范形式。

如果您仍然对此感兴趣，我建议您尝试使用计算机代数系统，例如 python 的 sympy（它可能也存在于 java 中）。但是，我也认为您应该删除标签java和floating-point（它与计算机如何存储实数无关），并添加标签computer-science。

例如 sympy 能够告诉这样的事情：

>>> Rational(3,4)*(x+y)**2
         2
3⋅(x + y) 
──────────
    4     
>>> Rational(3,4)*(x**2+y**2)+Rational(1,4)*2*x*y+Rational(4,8)*2*x*y
   2              2
3⋅x    3⋅x⋅y   3⋅y 
──── + ───── + ────
 4       2      4  
>>> expand(Rational(3,4)*(x+y)**2)==expand(Rational(3,4)*(x**2+y**2)+Rational(1,4)*2*x*y+Rational(4,8)*2*x*y)
True
于 2015-11-18T09:45:02.193 回答