Editing Associative property (section)

== Non-associative operation==
A binary operation <math>*</math> on a set ''S'' that does not satisfy the associative law is called '''non-associative'''. Symbolically,

<math display="block">(x*y)*z\ne x*(y*z)\qquad\mbox{for some }x,y,z\in S.</math>

For such an operation the order of evaluation ''does'' matter. For example:
; [[Subtraction]]
:<math>
(5-3)-2 \, \ne \, 5-(3-2)
</math>
; [[Division (mathematics)|Division]]
:<math>
(4/2)/2 \, \ne \, 4/(2/2)
</math>
; [[Exponentiation]]
:<math>
2^{(1^2)} \, \ne \, (2^1)^2
</math>
; [[Vector cross product]]
:<math>\begin{align}
  \mathbf{i} \times (\mathbf{i} \times \mathbf{j}) &= \mathbf{i} \times \mathbf{k} = -\mathbf{j} \\
  (\mathbf{i} \times \mathbf{i}) \times \mathbf{j} &= \mathbf{0} \times \mathbf{j} = \mathbf{0}
\end{align}</math>

Also although addition is associative for finite sums, it is not associative inside infinite sums ([[series (mathematics)|series]]). For example,
<math display="block">
(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+\dots =  0
</math>
whereas
<math display="block">
1+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+\dots  =  1.
</math>

Some non-associative operations are fundamental in mathematics. They appear often as the multiplication in structures called [[non-associative algebra]]s, which have also an addition and a [[scalar multiplication]]. Examples are the [[octonion]]s and [[Lie algebra]]s. In Lie algebras, the multiplication satisfies [[Jacobi identity]] instead of the associative law; this allows abstracting the algebraic nature of [[infinitesimal transformation]]s.

Other examples are [[quasigroup]], [[quasifield]], [[non-associative ring]], and [[commutative non-associative magmas]].

===Nonassociativity of floating point calculation===

In mathematics, addition and multiplication of real numbers are associative.  By contrast, in computer science, addition and multiplication of [[floating point]] numbers are ''not'' associative, as different rounding errors may be introduced when dissimilar-sized values are joined in a different order.<ref>Knuth, Donald, [[The Art of Computer Programming]], Volume 3, section 4.2.2</ref>

To illustrate this, consider a floating point representation with a 4-bit [[significand]]:

{{block indent|1=(1.000<sub>2</sub>×2<sup>0</sup> + 1.000<sub>2</sub>×2<sup>0</sup>) +
1.000<sub>2</sub>×2<sup>4</sup> = 1.000<sub>2</sub>×2<sup>{{fontcolor|red|1}}</sup> + 1.000<sub>2</sub>×2<sup>4</sup> = 1.00{{fontcolor|red|1}}<sub>2</sub>×2<sup>4</sup>}}
{{block indent|1=1.000<sub>2</sub>×2<sup>0</sup> + (1.000<sub>2</sub>×2<sup>0</sup> +
1.000<sub>2</sub>×2<sup>4</sup>) = 1.000<sub>2</sub>×2<sup>{{fontcolor|red|0}}</sup> + 1.000<sub>2</sub>×2<sup>4</sup> = 1.00{{fontcolor|red|0}}<sub>2</sub>×2<sup>4</sup>}}

Even though most computers compute with 24 or 53 bits of significand,<ref>{{Cite book |title=IEEE Standard for Floating-Point Arithmetic |author=IEEE Computer Society |date=29 August 2008 |id=IEEE Std 754-2008|doi=10.1109/IEEESTD.2008.4610935 |ref=CITEREFIEEE_7542008 |isbn=978-0-7381-5753-5}}</ref> this is still an important source of rounding error, and approaches such as the [[Kahan summation algorithm]] are ways to minimise the errors. It can be especially problematic in parallel computing.<ref>{{Citation
| last1   = Villa
| first1   = Oreste
| last2   = Chavarría-mir
| first2   = Daniel
| last3   = Gurumoorthi
| first3   = Vidhya
| last4   = Márquez
| first4   = Andrés
| last5   = Krishnamoorthy
| first5   = Sriram
| title   = Effects of Floating-Point non-Associativity on Numerical Computations on Massively Multithreaded Systems
| url   = http://cass-mt.pnnl.gov/docs/pubs/pnnleffects_of_floating-pointpaper.pdf
| access-date   = 8 April 2014
| archive-url   = https://web.archive.org/web/20130215171724/http://cass-mt.pnnl.gov/docs/pubs/pnnleffects_of_floating-pointpaper.pdf
| archive-date   = 15 February 2013
| url-status   = dead
}}</ref><ref name="Goldberg_1991">{{cite journal|last=Goldberg|first=David|author-link=David Goldberg (PARC)|date=March 1991|title=What Every Computer Scientist Should Know About Floating-Point Arithmetic|url=http://perso.ens-lyon.fr/jean-michel.muller/goldberg.pdf|journal=[[ACM Computing Surveys]]|volume=23|issue=1|pages=5–48|doi=10.1145/103162.103163|s2cid=222008826|access-date=20 January 2016|url-status=live|archive-url=https://web.archive.org/web/20220519083509/http://perso.ens-lyon.fr/jean-michel.muller/goldberg.pdf|archive-date=2022-05-19}}</ref>

=== Notation for non-associative operations ===
{{main|Operator associativity}}

In general, parentheses must be used to indicate the [[order of operations|order of evaluation]] if a non-associative operation appears more than once in an expression (unless the notation specifies the order in another way, like <math>\dfrac{2}{3/4}</math>). However, [[mathematician]]s agree on a particular order of evaluation for several common non-associative operations. This is simply a notational convention to avoid parentheses.

A '''left-associative''' operation is a non-associative operation that is conventionally evaluated from left to right, i.e.,

<math display="block">
\left.
\begin{array}{l}
a*b*c=(a*b)*c
\\
a*b*c*d=((a*b)*c)*d
\\
a*b*c*d*e=(((a*b)*c)*d)*e\quad
\\
\mbox{etc.}
\end{array}
\right\}
\mbox{for all }a,b,c,d,e\in S
</math>

while a '''right-associative''' operation is conventionally evaluated from right to left:

<math display="block">
\left.
\begin{array}{l}
x*y*z=x*(y*z)
\\
w*x*y*z=w*(x*(y*z))\quad
\\
v*w*x*y*z=v*(w*(x*(y*z)))\quad\\
\mbox{etc.}
\end{array}
\right\}
\mbox{for all }z,y,x,w,v\in S
</math>

Both left-associative and right-associative operations occur. Left-associative operations include the following:
; Subtraction and division of real numbers<ref>George Mark Bergman [https://math.berkeley.edu/~gbergman/misc/numbers/ord_ops.html "Order of arithmetic operations"]</ref><ref>[http://eduplace.com/math/mathsteps/4/a/index.html "The Order of Operations"]. Education Place.</ref><ref>[https://www.khanacademy.org/math/pre-algebra/pre-algebra-arith-prop/pre-algebra-order-of-operations/v/introduction-to-order-of-operations "The Order of Operations"], timestamp [https://www.youtube.com/watch?v=ClYdw4d4OmA&t=5m40s 5m40s]. [[Khan Academy]].</ref><ref>[http://www.doe.virginia.gov/instruction/mathematics/middle/algebra_readiness/curriculum_companion/order-operations.pdf#page=3 "Using Order of Operations and Exploring Properties"] {{Webarchive|url=https://web.archive.org/web/20220716062834/http://www.doe.virginia.gov/instruction/mathematics/middle/algebra_readiness/curriculum_companion/order-operations.pdf#page=3 |date=2022-07-16 }}, section 9. Virginia Department of Education.</ref><ref name="Bronstein_1987">Bronstein, ''[[:de:Taschenbuch der Mathematik]]'', pages 115-120, chapter: 2.4.1.1, {{ISBN|978-3-8085-5673-3}}</ref>
:<math>x-y-z=(x-y)-z</math>
:<math>x/y/z=(x/y)/z</math>
; Function application
:<math>(f \, x \, y) = ((f \, x) \, y)</math>
This notation can be motivated by the [[currying]] isomorphism, which enables partial application.

Right-associative operations include the following:
; [[Exponentiation]] of real numbers in superscript notation
:<math>x^{y^z}=x^{(y^z)}</math><p>Exponentiation is commonly used with brackets or right-associatively because a repeated left-associative exponentiation operation is of little use. Repeated powers would mostly be rewritten with multiplication:</p>
:<math>(x^y)^z=x^{(yz)}</math><p>Formatted correctly, the superscript inherently behaves as a set of parentheses; e.g. in the expression <math>2^{x+3}</math> the addition is performed [[order of operations|before]] the exponentiation despite there being no explicit parentheses <math>2^{(x+3)}</math> wrapped around it. Thus given an expression such as <math>x^{y^z}</math>, the full exponent <math>y^z</math> of the base <math>x</math> is evaluated first. However, in some contexts, especially in handwriting, the difference between <math>{x^y}^z=(x^y)^z</math>, <math>x^{yz}=x^{(yz)}</math> and <math>x^{y^z}=x^{(y^z)}</math> can be hard to see. In such a case, right-associativity is usually implied.</p>
; [[Function (mathematics)|Function definition]]
:<math>\mathbb{Z} \rarr \mathbb{Z} \rarr \mathbb{Z} = \mathbb{Z} \rarr (\mathbb{Z} \rarr \mathbb{Z})</math>
:<math>x \mapsto y \mapsto x - y = x \mapsto (y \mapsto x - y)</math><p>Using right-associative notation for these operations can be motivated by the [[Curry–Howard correspondence]] and by the [[currying]] isomorphism.</p>

Non-associative operations for which no conventional evaluation order is defined include the following.
; Exponentiation of real numbers in infix notation<ref name="Codeplea_2016">[https://codeplea.com/exponentiation-associativity-options Exponentiation Associativity and Standard Math Notation] Codeplea. 23 August 2016. Retrieved 20 September 2016.</ref>
:<math>(x^\wedge y)^\wedge z\ne x^\wedge(y^\wedge z)</math>
; [[Knuth's up-arrow notation|Knuth's up-arrow operators]]
:<math> a \uparrow \uparrow (b \uparrow \uparrow c) \ne (a \uparrow \uparrow b) \uparrow \uparrow c</math>
:<math> a \uparrow \uparrow \uparrow (b \uparrow \uparrow \uparrow c) \ne (a \uparrow \uparrow \uparrow b) \uparrow \uparrow \uparrow c</math>
; Taking the [[cross product]] of three vectors
:<math>\vec a \times (\vec b \times \vec c) \neq (\vec a \times \vec b ) \times \vec c \qquad \mbox{ for some } \vec a,\vec b,\vec c \in \mathbb{R}^3</math>
; Taking the pairwise [[average]] of real numbers
:<math>{(x+y)/2+z\over2}\ne{x+(y+z)/2\over2} \qquad \mbox{for all }x,y,z\in\mathbb{R} \mbox{ with }x\ne z.</math>
; Taking the [[complement (set theory)|relative complement]] of sets 
:<math>(A\backslash B)\backslash C \neq A\backslash (B\backslash C)</math>.<p>(Compare [[material nonimplication]] in logic.)</p>