TAOCP 2.3.2 Exercise 17

Section 2.3.2: Binary Tree Representation of Trees

Exercise 17. [M40] Write a program to do algebraic simplification capable of reducing, for example, (20) or (21) to (22). [Hints: Include a new field with each node, representing its coefficient (for summands) or its exponent (for factors in a product). Apply algebraic identities, like replacing \ln(u ↑ v) by v \ln u; remove the operations -, /, ↑, and neg when possible by using equivalent addition or multiplication operations. Make + and × into n-ary instead of binary operators; collect like terms by sorting their operands in tree order (exercise 8); some sums and products will now reduce to zero or unity, presenting perhaps further simplifications. Other adjustments, like replacing a sum of logarithms by the logarithm of a product, also suggest themselves.]

Verified: yes
Solve time: 1m37s

Setup

The exercise asks for a program that performs algebraic simplification on the tree representation of formulas described in Section 2.3.2. The objective is to transform derivatives obtained by repeated application of rules (11)-(19), such as (20) or (21), into substantially simpler equivalent formulas, for example (22).

Since no unique notion of "best" simplification exists, the problem is to design a systematic procedure that applies algebraic identities and canonicalization rules until no further reduction is possible. The hints specify the principal mechanisms:

Associate with each term a coefficient and with each factor an exponent.
Replace operators -, /, \uparrow, and neg whenever equivalent additive or multiplicative forms exist.
Treat + and \times as $n$-ary operators.
Collect like terms after sorting operands into a canonical order.
Apply algebraic identities such as

$$ \ln(u\uparrow v)=v\ln u. $$

The solution therefore consists of a normalization algorithm together with a proof that it produces equivalent formulas and performs the desired simplifications.

Solution

Represent every expression by a tree whose internal nodes are only the operators $+$ , $\times$ , and $\ln$ . Each operand of a $+$ node carries an integer or symbolic coefficient; each operand of a $\times$ node carries an exponent.

The simplification program repeatedly applies the following transformations.

First, eliminate subtraction, division, unary negation, and powers:

$$ u-v ;\mapsto; u+((-1)v), $$

$$ u/v ;\mapsto; u\times v^{-1}, $$

$$ \operatorname{neg}(u);\mapsto; (-1)u, $$

$$ u\uparrow v ;\mapsto; u^v. $$

The power notation is retained only as an exponent attached to a factor. No binary operator node $\uparrow$ remains.

Second, flatten all sums and products. If a child of a $+$ node is itself a $+$ node, replace the two levels by a single $+$ node containing all summands. If a child of a $\times$ node is itself a $\times$ node, replace the two levels by a single $\times$ node containing all factors. Hence every sum and product becomes $n$-ary.

Third, move coefficients and exponents into the operand records. Thus

$$ 3x+5x $$

is represented as two copies of $x$ with coefficients $3$ and $5$, while

$$ x^2x^{-5} $$

is represented as two copies of $x$ with exponents $2$ and $-5$.

Fourth, apply elementary identities:

$$ 0+u=u, $$

$$ u+0=u, $$

$$ 0u=0, $$

$$ 1u=u, $$

$$ u^0=1, $$

$$ u^1=u, $$

$$ \ln(1)=0, $$

$$ \ln(u^v)=v\ln u. $$

Whenever a transformation creates a new opportunity for simplification, the expression is reprocessed.

Fifth, sort the operands of every $n$-ary sum and product into a canonical tree order, as suggested by exercise 8. Equal subtrees then become adjacent.

Sixth, collect like terms in sums. Suppose

$$ c_1t+c_2t+\cdots+c_mt $$

occurs, where all copies of $t$ have identical canonical tree representations. Replace them by

$$ (c_1+c_2+\cdots+c_m)t. $$

If the resulting coefficient is $0$, delete the term.

Seventh, collect like factors in products. Suppose

$$ u^{e_1}u^{e_2}\cdots u^{e_m} $$

occurs with identical canonical factor $u$. Replace them by

$$ u^{e_1+e_2+\cdots+e_m}. $$

If the resulting exponent is $0$, remove the factor; if it is $1$, remove the exponent annotation.

Eighth, apply logarithmic identities recursively. For example,

$$ \ln(u^v)\mapsto v\ln u. $$

After flattening products, this rule converts many logarithmic expressions into factors that can participate in coefficient and exponent collection.

The simplification cycle

$$ \text{normalize} \rightarrow \text{sort} \rightarrow \text{collect} \rightarrow \text{reduce identities} $$

is repeated until one complete pass makes no change.

To illustrate, begin with (21):

$$ 3(1/(x+1)) - \bigl(-(a(2x))/(x^2)^2\bigr). $$

Division becomes multiplication by a negative exponent:

$$ 3(x+1)^{-1} + a(2x)(x^2)^{-2}. $$

The factor $2$ is absorbed into the coefficient:

$$ 3(x+1)^{-1} + 2ax(x^2)^{-2}. $$

Exponent collection gives

$$ x(x^2)^{-2} = x^{1-4} = x^{-3}. $$

Hence the result is

$$ 3(x+1)^{-1} + 2ax^{-3}, $$

which is formula (22).

Verification

Each transformation preserves the value of the represented formula.

The replacements

$$ u-v=u+((-1)v), $$

$$ u/v=u\times v^{-1}, $$

and

$$ \operatorname{neg}(u)=(-1)u $$

are algebraic identities.

Flattening $n$-ary sums and products changes only the grouping of associative operations. Therefore the represented expression is unchanged.

Sorting operands merely changes their order. Since addition and multiplication are commutative, the represented value is unchanged.

Combining

$$ c_1t+\cdots+c_mt $$

into

$$ (c_1+\cdots+c_m)t $$

uses the distributive law. Combining

$$ u^{e_1}\cdots u^{e_m} $$

into

$$ u^{e_1+\cdots+e_m} $$

uses the laws of exponents.

Each elementary reduction listed above is a valid algebraic identity. Consequently every pass through the simplifier preserves equivalence.

The canonical ordering guarantees that equal terms and equal factors appear consecutively. Therefore every possible collection of like terms and like factors is detected. When a complete pass produces no change, every applicable simplification rule has already been exhausted.

Thus the program transforms formulas such as (20) and (21) into substantially simpler equivalent forms, including the reduction

$$ 3(1/(x+1)) - \bigl(-(a(2x))/(x^2)^2\bigr) ;\Longrightarrow; 3(x+1)^{-1}+2ax^{-3}. $$

Therefore the final simplified result for the example is

$$ \boxed{3(x+1)^{-1}+2ax^{-3}}. $$

Notes

The representation by $n$-ary sums and products is the essential structural improvement. Binary trees force repeated reassociation during simplification, while $n$-ary nodes permit coefficient collection, exponent collection, operand sorting, and elimination of neutral elements in a single uniform framework. This is precisely the direction suggested by the hints in the exercise.