Computer algebra: Difference between revisions

Revision as of 12:43, 3 July 2023

Revision as of 13:34, 3 July 2023

Line 39:

==== Expressions ====

[[File:Cassidy.1985.015.gif|thumb|400px|Representation of the expression {{math|(8 − 6) × (3 + 1)}} as a [[Lisp (programming language)|Lisp]] tree, from a 1985 Master's Thesis.<ref>{{cite thesis | type=Master's thesis | url=https://commons.wikimedia.org/wiki/File:The_feasibility_of_automatic_storage_reclamation_with_concurrent_program_execution_in_a_LISP_environment._(IA_feasibilityofaut00cass).pdf | authorfirst=Kevin G. |last=Cassidy | title=The Feasibility of Automatic Storage Reclamation with Concurrent Program Execution in a LISP Environment | institution=Naval Postgraduate School, Monterey/CA | date=Dec 1985 |page=15 |id=ADA165184}}</ref>]]

Except for [[number]]s and [[variable (mathematics)|variables]], every [[Expression (mathematics)|mathematical expression]] may be viewed as the symbol of an operator followed by a [[sequence]] of operands. In computer algebra software, the expressions are usually represented in this way. This representation is very flexible, and many things that seem not to be mathematical expressions at first glance, may be represented and manipulated as such. For example, an equation is an expression with "=" as an operator, a matrix may be represented as an expression with "matrix" as an operator and its rows as operands.

Line 76:

To test the equality of two expressions, instead of designing specific algorithms, it is usual to put expressions in some ''[[canonical form]]'' or to put their difference in a ''normal form'', and to test the syntactic equality of the result.

In computer algebra, "canonical form" and "normal form" are not synonymous.<ref>{{cite book |last1=Davenport |first1=J. H. |last2=Siret |first2=Y. |last3=Tournier |first3=É. |title=Computer algebraAlgebra: Systems and Algorithms for Algebraic Computation |publisher=Academic |date=1988 |isbn=0-12-204230-1 |oclc=802584470 }}</ref> A ''canonical form'' is such that two expressions in canonical form are semantically equal if and only if they are syntactically equal, while a ''normal form'' is such that an expression in normal form is semantically zero only if it is syntactically zero. In other words, zero has a unique representation as an expression in normal form.

Normal forms are usually preferred in computer algebra for several reasons. Firstly, canonical forms may be more costly to compute than normal forms. For example, to put a polynomial in canonical form, one has to expand every product through [[distributivity]], while it is not necessary with a normal form (see below). Secondly, it may be the case, like for expressions involving radicals, that a canonical form, if it exists, depends on some arbitrary choices and that these choices may be different for two expressions that have been computed independently. This may make impracticable the use of a canonical form.