algorithm - 由部首定义的数字的正常形式？

Question

我正在编写一个允许基本算术运算和根式的小型计算机代数系统。所以表达式是二叉树，其中内部节点是运算符 + - */^ 叶子是有理数。现在我想像其他 CAS 一样，简化表达式，例如它是

(5+sqrt(2)+sqrt(8)) / (1+sqrt(2)) = 1 + sqrt(8)

如果您从左侧开始，您可以将其重写为 RHS 并不明显。那么其他CAS是怎么做的呢？这些表达式是否有一个范式，使得每个表达式都可以唯一地写成一个范式？是否有一种确定性算法可以将任何表达式重写为正常形式？

Answer 1

我不知道 CAS 是如何制作的，但我认为简化过程可以通过状态空间搜索来完成。你可以有一组规则如何将一个表达式转录成另一个等价物。这些规则的应用是搜索图中的边，节点是表达式树。然后，您可以搜索此图以找到尽可能小的树(或足够小，或者可能没有规则无法进一步应用的树)。

一个更简单的任务可能是微分过程，它实际上只是应用规则而(几乎)不需要实际进行任何搜索。它可以很容易地用 prolog 编写(虽然我从来没有这样做过，只有我们大学的 prolog 老师告诉我们)。