Disagreement on operator precedence for 2^3^4

February 6th, 2012 | Categories: general math, Maple, math software, mathcad, mathematica, matlab, python, R | Tags:

My attention was recently drawn to a Google+ post by JerWei Zhang where he evaluates 2^3^4 in various packages and notes that they don’t always agree.  For example, in MATLAB 2010a we have 2^3^4 = 4096 which is equivalent to putting (2^3)^4 whereas Mathematica 8 gives 2^3^4 = 2417851639229258349412352 which is the same as putting 2^(3^4).  JerWei’s post gives many more examples including Excel, Python and Google and the result is always one of these two (although to varying degrees of precision).

What surprised me was the fact that they disagreed at all since I thought that the operator precendence rules were an agreed standard across all software packages.  In this case I’d always use brackets since _I_ am not sure what the correct interpretation of 2^3^4 should be but I would have taken it for granted that there is a standard somewhere and that all of the big hitters in the numerical world would adhere to it.

Looks like I was wrong!

  1. Ian Cottam
    February 6th, 2012 at 11:26
    Reply | Quote | #1

    The property that these packages dispute is associativity (not precedence).
    Wikipedia thinks ^ is right associative.
    http://en.wikipedia.org/wiki/Associative_property
    -Ian

  2. MySchizoBuddy
    February 6th, 2012 at 11:45
    Reply | Quote | #2

    most programming languages use the pow() function which takes only 2 arguments. So 2^3^4 implemented in these languages will always be 2^(3^4)

  3. Ian Cottam
    February 6th, 2012 at 12:04
    Reply | Quote | #3

    “always’?

    pow( pow(2, 3), 4)

    pow( 2, pow(3, 4) )

    -Ian

  4. February 6th, 2012 at 14:39
    Reply | Quote | #4

    I support the wikipedia right-associativity interpretation. For example, I think you’d be permitted to write 2^{x^n+1} without the parentheses when written in normal math display format. The interpretation there is unambiguous. If that’s true, than 2^{x^n}, again written without parentheses in display format, should be unambiguously interpreted too. To see this difference, go here:

    http://latex.codecogs.com/gif.latex?\LARGE&space;\begin{align*}&space;&2^{x^n+1}\\&space;&2^{x^n}&space;\end{align*}

    I believe that both of the expressions should be interpreted in the same way.

    That being said, I’m sympathetic to the left-associativity interpretation, since that would mean evaluating the operators from left to right, which is somewhat reasonable.

  5. February 6th, 2012 at 14:40
    Reply | Quote | #5

    Sorry my link didn’t come through correctly… please copy and paste with all the parameters.

  6. February 6th, 2012 at 15:44
    Reply | Quote | #6

    Excel and VBA have different ideas on operator precedence, in what Microsoft market as an integrated solution. Try -1^2 in both, and you get different results.

    There are other niggling issues like log() in VBA = ln() in Excel

  7. Steve L
    February 6th, 2012 at 17:10
    Reply | Quote | #7

    From the documentation for MATLAB:

    http://www.mathworks.com/help/techdoc/matlab_prog/f0-40063.html#f0-38155

    “Within each precedence level, operators have equal precedence and are evaluated from left to right.”

    Since ^ and ^ are obviously on the same precedence level, 2^3^4 is evaluated left-to-right to yield the same result as (2^3)^4.

    While we’re on the topic of associativity, keep in mind that associativity can break down where floating-point arithmetic is involved. In the code below, d is half the distance between 2 and the next representable double precision number.

    d = eps(2)/2;
    x1 = (2+d)+d;
    x2 = 2+(d+d);
    x1 == x2 % Correctly returns false

    x1 is exactly 2, since (2+d) is 2. x2 is one bit in the last place larger than 2, since d+d = eps(2) and 2+eps(2) is greater than 2 by the definition of eps.

    http://www.mathworks.com/help/techdoc/ref/eps.html

    You can see this by displaying x1 and x2 using FORMAT HEX:

    http://www.mathworks.com/help/techdoc/ref/format.html

    The example in Sim Con’s post (-1^2) that will return -1 in MATLAB. The operator ^ has higher precedence (level 2) than unary minus (level 3) as described on the documentation page to which I linked above, so -1^2 is interpreted as -(1^2). Again, one solution is parentheses: (-1)^2. Another solution is to use a variable:

    x = -1;
    y = x^2 % returns y = 1.

  8. February 6th, 2012 at 18:33
    Reply | Quote | #8

    I guess I immediately associate 2^3^4 with the following display form:

    http://latex.codecogs.com/gif.latex?\LARGE&space;2^{3^4}

    Do we agree that the above display-version is unambiguous?

  9. Martin Cohen
    February 7th, 2012 at 01:12
    Reply | Quote | #9

    Here is my take on why exponentiation should be right associative rather than left:

    If it were left associative, a^b^c = (a^b)^c = a^(b*c), so we could get the result without a second exponentiation, just by multiplying the exponents.

    Right associative give a result that cannot be written another way.

  10. Carlos
    February 7th, 2012 at 17:03

    It seems that many of the commentors here are making the mistake of confusing an orthograpic instruction with an operation. That is, they are reading ^ to mean “superscript” rather than “exponentiate.” Superscripting forms an visual grouping in the same way that parentheses do, and affects precedence in the same way. When converted to an inline equation, that visual grouping needs to be represented differently not ignored.

    I need some LaTex here to illustrate, so please follow the link. http://mathbin.net/88713

    Short summary: because putting 3x in a superscript means doing multiplication before exponentiation, a superscript has an inherent parenthesis. To be consistent with this, The correct way to write superscripts inline is ^(), not ^, which means that superscript and ^ have slightly different mathematical meanings.

  11. jVincent
    February 18th, 2012 at 02:44

    Carlos, You seem to be arguing based on the assumption that exponentiation is left associative, which to my knowledge it is not. The initial definition of MATLABs method of handling precedence seems to indicate that MATLAB assumes that all operators are left associative which is definitely not a mathematical truth. So in a sense MATLABs implementation is flawed. It’s not that people misinterpret what x^y^z translates into.

  12. February 18th, 2012 at 08:52

    “… there is a standard somewhere and that all of the big hitters in the numerical world would adhere to it.”

    I assumed the same thing about graphs, but here is one function the “big hitters” do not agree on:

    Which is the correct graph of arccot(x)?

  13. Nick Barnes
    February 19th, 2012 at 01:06

    Mathematicians have been universally clear on this for many years, for an excellent reason. If you see a tower of exponents (which is the mathematical equivalent of writing 2^3^4 or 2**3**4), the meaning is that the upper (right-hand) exponents are evaluated first (the equivalent of the operator being right-associative). Parentheses are seldom used because everybody understands this meaning.

    The reason is that the left-associative meaning, (a^b)^c, may be unambiguously written a^(b.c).

    So any language which has an infix exponentiation operator, and which left-associates it, is fundamentally broken to a mathematician.

  14. Carlos
    February 21st, 2012 at 08:40

    jVincent:
    I am not arguing based on the assumption that exponentiation is left associative. I’m saying that associativity is a convention, that there is a choice of convention to be made and that in arguing the choice, it is relevant to consider the reasons why that 2 superscript{3x} places operator precedence on multiplication over exponentiation while 2^3*4 places operator precedence on exponentiation over multiplication.

    Imagine that there two explanations for why 2 superscript 3 supersuperscript 4 is right associative:
    A) Exponentiation is right associative: in which case 2^3^4 is 2^(3^4)
    B) Superscript is inherently parenthetical: in which case 2^3^4 is not (yet) determined.

    Then, from considering those two alternatives, the following argument can be made:

    Option A does not explain why 2 superscript{3x} places presence on the multiplication of 3*x before 2.
    Option B does. Therefore, if we adopt Option A as a rule, we also need option B as an additional rule.

    Since Option B does the work of Option A, Option A is unnecessary. We discard Option A.

    Given option B, the associativity of ^ is undefined. The default associativity for binary operators is left associative, so in the spirit of having the fewest number of rules for the most elegant system, it would behoove us to CHOOSE ^ to be left associative (although there is nothing preventing us from CHOOSING ^ as right associative other than aesthetics).

    At no point is there an apriori assumption that ^ must be left associative, rather this is an argument in favor of adopting a convention, since there currently isn’t one (as evidenced by excel, mathematica, and latex all treating 2^3^4 differently).

    Put more succinctly: If we choose exponentiation as right associative, then our system needs three rules:
    1) Binary operators are left associative.
    2) Except exponentiation is right associative
    3) Superscript acts as parentheses (in order to account for 2 superscript{3x})

    If we choose exponentiation as left associative, then our system needs two rules:
    1) Binary operators are left associative
    3) Superscript acts as parentheses.

    Both systems of rules generate the exact same behavior for the pretty print version of 2 superscript 3 supersuperscript 4, (both make superscript right associative), but the second system is simpler. Therefore I propose adopting the second system as a convention of usage.

    If I were making an assumption about associativity of ^ (which I’m not), it would be the following: The associativity of exponentiation depends on the orthography used to represent exponentiation and the culture in which that orthography is used. (Note that this says nothing about inherent left or right associativity)

    What I mean by that assumption is this: Superscript is mathematical usage, embedded in mathematics culture, and by mathematical convention is right associative as long as the superscripts are nested. ^ is more frequently computer science usage (it comes from a non-pretty print tradition), and by computer science convention is left associative for ease/elegance of coding. Then the argument would be that the superscript as parentheses interpretation is a way of reconciling two different traditions so that they no longer conflict, while simultaneously accounting for the precedence of multiplication in 2 superscript {3x}.

  15. Carlos
    February 21st, 2012 at 09:31

    In discussing issues of operations and notation, it’s worth pointing out that operator precedence is NEVER inherent to the operator and always a part of the notation. For example, reverse polish notation has NO precedence of operator types, instead all operators are evaluated from left to right in the order that they occur, no matter what type of operator it is. And yet it is a fully functional notational system.

    The point of the RPN example is that order of operations depends on the notation that the actual operations are written in. Pretty print and infix notation are different notations. They write exponentiation differently (one uses superscript, and the other uses ^). It is not at all unreasonable that two different notations would have different operator precedence. In fact, the example of RPN proves existence.