Computer algebra: Difference between revisions

Revision as of 00:27, 5 April 2023

Revision as of 15:30, 9 April 2023

Line 58:

A difficulty occurs with [[associative operation]]s like addition and multiplication. The standard way to deal with associativity is to consider that addition and multiplication have an arbitrary number of operands, that is that {{math|''a'' + ''b'' + ''c''}} is represented as {{math|"+"(''a'', ''b'', ''c'')}}. Thus {{math|''a'' + (''b'' + ''c'')}} and {{math|(''a'' + ''b'') + ''c''}} are both simplified to {{math|"+"(''a'', ''b'', ''c'')}}, which is displayed {{math|''a'' + ''b'' + ''c''}}. In the case of expressions such as {{math|''a'' − ''b'' + ''c''}}, the simplest way is to systematically rewrite {{math|−''E''}}, {{math|''E'' − ''F''}}, {{math|''E''/''F''}} as, respectively, {{math|(−1)⋅''E''}}, {{math|''E'' + (−1)⋅''F''}}, {{math|''E''⋅''F''^−1}}. In other words, in the internal representation of the expressions, there is no subtraction nor division nor unary minus, outside the representation of the numbers.

Another difficulty occurs with the [[commutativity]] of addition and multiplication. The problem is to quickly recognize the [[like terms]] in order to combine or cancel them. Testing every pair of terms is costly with very long sums and products. To address this, [[Macsyma]] sorts the operands of sums and products into an order that places like terms in consecutive places, allowing easy detection. In [[Maple (software)|Maple]], a [[hash function]] is designed for generating collisions when like terms are entered, allowing thethem to be combined as soon as they are introduced. This allows subexpressions that appear several times in a computation to be immediately recognized and stored only once. This saves memory and speeds up computation by avoiding repetition of the same operations on identical expressions.

Some rewriting rules sometimes increase and sometimes decrease the size of the expressions to which they are applied. This is the case of [[distributivity]] or [[Trigonometric identity#Product-to-sum and sum-to-product identities|trigonometric identities]]. For example, the distributivity law allows rewriting <math>(x+1)^4 \rightarrow x^4+4x^3+6x^2+4x+1</math> and <math>(x-1)(x^4+x^3+x^2+x+1) \rightarrow x^5-1.</math> As there is no way to make a good general choice of applying or not such a rewriting rule, such rewriting is done only when explicitly invoked by the user. For the distributivity, the computer function that applies this rewriting rule is typically called "expand". The reverse rewriting rule, called "factor", requires a non-trivial algorithm, which is thus a key function in computer algebra systems (see [[Polynomial factorization]]).