{"id":849,"date":"2014-02-26T10:07:43","date_gmt":"2014-02-26T15:07:43","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/?p=849"},"modified":"2014-01-20T16:08:30","modified_gmt":"2014-01-20T21:08:30","slug":"arithmetic-associativity-not-so-fast","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2014\/02\/26\/arithmetic-associativity-not-so-fast\/","title":{"rendered":"Arithmetic Associativity &#8211; Not So Fast"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>Arithmetic is associative, right?  Well, in the world of paper and pencil, where you can often do calculations exactly, that can be true. However, in the computing world, where real numbers can't always be represented exactly because of working with finite precision datatypes, it turns out that you can't depend on the arithmetic to behave the way you were taught in grade school.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#1aed3f74-9dae-434f-9027-d28477c4bad5\">Let's Do Some Math<\/a><\/li><li><a href=\"#2391d584-d129-44f0-a1b1-5d446cc56e54\">Let's Try Another Example<\/a><\/li><li><a href=\"#eaecf369-7540-47ed-9fca-3ba6f3251872\">Have You Rewritten Expressions to Get Better Accuracy?<\/a><\/li><\/ul><\/div><h4>Let's Do Some Math<a name=\"1aed3f74-9dae-434f-9027-d28477c4bad5\"><\/a><\/h4><p>Suppose I want to check the following:<\/p><p>$$ \\sqrt {2} = 2\/\\sqrt {2} $$<\/p><p>I can do this analytically using the <a href=\"https:\/\/www.mathworks.com\/products\/symbolic\/\">Symbolic Math Toolbox<\/a>.<\/p><pre class=\"codeinput\">symsqrt2 = sqrt(sym(2));\r\nshouldBeZero = symsqrt2 - 2\/symsqrt2\r\n<\/pre><pre class=\"codeoutput\">shouldBeZero =\r\n0\r\n<\/pre><p>Now let's perform the same calculation numerically.<\/p><pre class=\"codeinput\">mightBeZero = sqrt(2) - 2\/sqrt(2)\r\n<\/pre><pre class=\"codeoutput\">mightBeZero =\r\n   2.2204e-16\r\n<\/pre><p>What is happening here is that we are seeing the influence of the accuracy of floating point numbers and calculations with them.  I discussed this in an <a href=\"https:\/\/blogs.mathworks.com\/loren\/2006\/08\/23\/a-glimpse-into-floating-point-accuracy\/\">earlier post<\/a> as well.<\/p><h4>Let's Try Another Example<a name=\"2391d584-d129-44f0-a1b1-5d446cc56e54\"><\/a><\/h4><p>Now let's try something a little different.  First, let's find out what the value of <a href=\"https:\/\/www.mathworks.com\/help\/matlab\/ref\/eps.html\"><tt>eps<\/tt><\/a> is for %sqrt {2}%.  This should be the smallest (in magnitude) floating point number which, when added to %sqrt {2}%, produces a number different than %sqrt {2}%.<\/p><pre class=\"codeinput\">sqrt2eps = eps(sqrt(2))\r\n<\/pre><pre class=\"codeoutput\">sqrt2eps =\r\n   2.2204e-16\r\n<\/pre><p>Next, we want a number smaller in magnitude than this to play with.  I'll use half its value.<\/p><pre class=\"codeinput\">halfsqrt2eps = sqrt2eps\/2\r\n<\/pre><pre class=\"codeoutput\">halfsqrt2eps =\r\n   1.1102e-16\r\n<\/pre><p>And now let's calculate the following expressions, symbolically and numerically.<\/p><p>$$expr1 = \\sqrt{2} - \\sqrt{2} + halfsqrt2eps$$<\/p><p>$$expr2 = (\\sqrt{2} - \\sqrt{2}) + halfsqrt2eps$$<\/p><p>$$expr3 = \\sqrt{2} + (-\\sqrt{2} + halfsqrt2eps)$$<\/p><p>First we do them all symbolically.<\/p><pre class=\"codeinput\">expr1 = symsqrt2 - symsqrt2 + sym(sqrt2eps)\/2\r\nexpr2 = (symsqrt2 - symsqrt2) + sym(sqrt2eps)\/2\r\nexpr3 = symsqrt2 + (-symsqrt2 + sym(sqrt2eps)\/2)\r\ndouble(expr1)\r\n<\/pre><pre class=\"codeoutput\">expr1 =\r\n1\/9007199254740992\r\nexpr2 =\r\n1\/9007199254740992\r\nexpr3 =\r\n1\/9007199254740992\r\nans =\r\n   1.1102e-16\r\n<\/pre><p>Symbolic results are all the same and return half the value of <tt>eps<\/tt>.<\/p><p>Now we'll calculate the same expressions numerically.<\/p><pre class=\"codeinput\">expr1 = sqrt(2) - sqrt(2) + halfsqrt2eps\r\nexpr2 = (sqrt(2) - sqrt(2)) + halfsqrt2eps\r\nexpr3 = sqrt(2) + (-sqrt(2) + halfsqrt2eps)\r\n<\/pre><pre class=\"codeoutput\">expr1 =\r\n   1.1102e-16\r\nexpr2 =\r\n   1.1102e-16\r\nexpr3 =\r\n   2.2204e-16\r\n<\/pre><p>So what's going on here?  As I stated earlier, this example illustrates that floating point arithmetic is not associative the way symbolic arithmetic is.  There's on reason to get upset about this.  But it is worth understanding.  And it might well be worth rewriting a computation occasionally, especially if you are trying to compute a very small difference between two large numbers.<\/p><h4>Have You Rewritten Expressions to Get Better Accuracy?<a name=\"eaecf369-7540-47ed-9fca-3ba6f3251872\"><\/a><\/h4><p>Have you found yourself in a situation where you needed to rewrite how to calculate a numeric result (like here, by different groupings) to ensure you got a more accurate solution.  Let me know about it <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=849#respond\">here<\/a>.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_6e3f2699936b42528926ff1121b0cde3() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='6e3f2699936b42528926ff1121b0cde3 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 6e3f2699936b42528926ff1121b0cde3';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2014 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_6e3f2699936b42528926ff1121b0cde3()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2013b<br><\/p><p class=\"footer\"><br>\r\n      Published with MATLAB&reg; R2013b<br><\/p><\/div><!--\r\n6e3f2699936b42528926ff1121b0cde3 ##### SOURCE BEGIN #####\r\n%% Arithmetic Associativity - Not So Fast\r\n% Arithmetic is associative, right?  Well, in the world of paper and\r\n% pencil, where you can often do calculations exactly, that can be true.\r\n% However, in the computing world, where real numbers can't always be\r\n% represented exactly because of working with finite precision datatypes,\r\n% it turns out that you can't depend on the arithmetic to behave the way\r\n% you were taught in grade school.\r\n\r\n%% Let's Do Some Math\r\n% Suppose I want to check the following:\r\n%\r\n% $$ \\sqrt {2} = 2\/\\sqrt {2} $$\r\n%\r\n% I can do this analytically using the\r\n% <https:\/\/www.mathworks.com\/products\/symbolic\/ Symbolic Math Toolbox>.\r\n\r\nsymsqrt2 = sqrt(sym(2));\r\nshouldBeZero = symsqrt2 - 2\/symsqrt2\r\n\r\n%%\r\n% Now let's perform the same calculation numerically.\r\nmightBeZero = sqrt(2) - 2\/sqrt(2)\r\n\r\n%%\r\n% What is happening here is that we are seeing the influence of the\r\n% accuracy of floating point numbers and calculations with them.  I\r\n% discussed this in an\r\n% <https:\/\/blogs.mathworks.com\/loren\/2006\/08\/23\/a-glimpse-into-floating-point-accuracy\/\r\n% earlier post> as well.\r\n\r\n%% Let's Try Another Example\r\n% Now let's try something a little different.  First, let's find out what\r\n% the value of\r\n% <https:\/\/www.mathworks.com\/help\/matlab\/ref\/eps.html |eps|>\r\n% is for %sqrt {2}%.  This should be the smallest (in magnitude) floating\r\n% point number which, when added to %sqrt {2}%, produces a number different\r\n% than %sqrt {2}%.\r\nsqrt2eps = eps(sqrt(2))\r\n%%\r\n% Next, we want a number smaller in magnitude than this to play with.  I'll\r\n% use half its value.\r\nhalfsqrt2eps = sqrt2eps\/2\r\n%%\r\n% And now let's calculate the following expressions, symbolically and\r\n% numerically.\r\n%\r\n% $$expr1 = \\sqrt{2} - \\sqrt{2} + halfsqrt2eps$$\r\n%\r\n% $$expr2 = (\\sqrt{2} - \\sqrt{2}) + halfsqrt2eps$$\r\n%\r\n% $$expr3 = \\sqrt{2} + (-\\sqrt{2} + halfsqrt2eps)$$\r\n%%\r\n% First we do them all symbolically.\r\nexpr1 = symsqrt2 - symsqrt2 + sym(sqrt2eps)\/2\r\nexpr2 = (symsqrt2 - symsqrt2) + sym(sqrt2eps)\/2\r\nexpr3 = symsqrt2 + (-symsqrt2 + sym(sqrt2eps)\/2)\r\ndouble(expr1)\r\n%%\r\n% Symbolic results are all the same and return half the value of |eps|.\r\n%% \r\n% Now we'll calculate the same expressions numerically.\r\nexpr1 = sqrt(2) - sqrt(2) + halfsqrt2eps\r\nexpr2 = (sqrt(2) - sqrt(2)) + halfsqrt2eps\r\nexpr3 = sqrt(2) + (-sqrt(2) + halfsqrt2eps)\r\n%%\r\n% So what's going on here?  As I stated earlier, this example illustrates\r\n% that floating point arithmetic is not associative the way symbolic\r\n% arithmetic is.  There's on reason to get upset about this.  But it is\r\n% worth understanding.  And it might well be worth rewriting a computation\r\n% occasionally, especially if you are trying to compute a very small\r\n% difference between two large numbers.\r\n%% Have You Rewritten Expressions to Get Better Accuracy?\r\n% Have you found yourself in a situation where you needed to rewrite how to\r\n% calculate a numeric result (like here, by different groupings) to ensure\r\n% you got a more accurate solution.  Let me know about it\r\n% <https:\/\/blogs.mathworks.com\/loren\/?p=849#respond here>.\r\n\r\n\r\n\r\n##### SOURCE END ##### 6e3f2699936b42528926ff1121b0cde3\r\n-->","protected":false},"excerpt":{"rendered":"<!--introduction--><p>Arithmetic is associative, right?  Well, in the world of paper and pencil, where you can often do calculations exactly, that can be true. However, in the computing world, where real numbers can't always be represented exactly because of working with finite precision datatypes, it turns out that you can't depend on the arithmetic to behave the way you were taught in grade school.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2014\/02\/26\/arithmetic-associativity-not-so-fast\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[26,1],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/849"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=849"}],"version-history":[{"count":5,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/849\/revisions"}],"predecessor-version":[{"id":857,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/849\/revisions\/857"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=849"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=849"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=849"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}