{"id":5205,"date":"2019-06-12T12:49:26","date_gmt":"2019-06-12T12:49:26","guid":{"rendered":"https:\/\/www.dyalog.com\/blog\/?p=5205"},"modified":"2019-06-12T12:49:26","modified_gmt":"2019-06-12T12:49:26","slug":"tolerated-comparison-part-2","status":"publish","type":"post","link":"https:\/\/www.dyalog.com\/blog\/2019\/06\/tolerated-comparison-part-2\/","title":{"rendered":"Tolerated Comparison, Part 2"},"content":{"rendered":"<p>This post might be more difficult than our usual fare. You won&#8217;t find any interesting APL coding insights here\u2014instead we&#8217;ll be focused on the tricky topic of floating-point error analysis. If that&#8217;s not your thing, feel free to skip this one! Although if you plan to use tolerated comparison in a real application, you really do need to know this stuff.<\/p>\n<p>In <a href=\"https:\/\/www.dyalog.com\/blog\/2018\/11\/tolerated-comparison-part-1\/\">Tolerated Comparison, Part 1<\/a>, I discussed the structure of tolerant inequality with one argument fixed, and showed that<\/p>\n<ul>\n<li>For any real number <code class=\"language-apl\">B<\/code>, there&#8217;s another number <code class=\"language-apl\">b<\/code> so that a number is <em>tolerantly<\/em> less than or equal to <code class=\"language-apl\">B<\/code> if and only if it is <em>intolerantly<\/em> less than or equal to <code class=\"language-apl\">b<\/code>.<\/li>\n<li>This number is equal to <code class=\"language-apl\">B\u00f71-\u2395CT<\/code> when <code class=\"language-apl\">B&lt;0<\/code>, and <code class=\"language-apl\">B\u00d71-\u2395CT<\/code> otherwise.<\/li>\n<\/ul>\n<p>But these results were proven only for mathematical real numbers, which have many properties among which is the complete inability to be implemented in a silicon chip. To actually apply the technique in Dyalog APL, we must know that it works for IEEE floats like Dyalog uses (we have not implemented tolerated comparison for the decimal floating point numbers used when <code class=\"language-apl\">\u2395FR<\/code> is 1287, and there are serious concerns regarding precision which might make it impossible to tolerate values efficiently).<\/p>\n<p>Why should we care if a tolerated value is off by one or a few units in the last place? It&#8217;s certainly unlikely to cause widespread chaos. But we think programmers should be able to expect, for instance, that after setting <code class=\"language-apl\">i\u2190v\u2373x<\/code> it is always safe to assume that <code class=\"language-apl\">v[i]=x<\/code>. A language that behaves otherwise can easily cause &#8220;impossible&#8221; bugs in programs that are provably correct according to Dyalog&#8217;s specification. And finding a value that lies just on the boundary of equality with <code class=\"language-apl\">x<\/code> is not as obscure an issue as it may appear. With the default value <code class=\"language-apl\">\u2395CT\u21901E\u00af14<\/code>, there are at most about 180 numbers which are tolerantly equal to a typical floating-point number <code class=\"language-apl\">x<\/code>. So it&#8217;s not much of a stretch to think that a program which handles a lot of similar values will eventually run into a problem with an inaccurate version of tolerated equality. And this is a really scary problem to debug\u2014even the slightest difference in the values used would make it disappear, frustrating any efforts to track down the cause. We&#8217;ve dealt with tolerant comparison issues in the past and this kind of problem is certainly not something we want to stumble on in the future.<\/p>\n<p>On to floating-point numbers. I&#8217;m afraid this is not a primer on the subject, although I can point any interested readers to the excellent <a href=\"https:\/\/docs.oracle.com\/cd\/E19957-01\/806-3568\/ncg_goldberg.html\">What Every Computer Scientist Should Know About Floating-Point Arithmetic<\/a>. In brief, Dyalog&#8217;s floating-point numbers use 64 bits to represent a particular set of real numbers chosen to cover many orders of magnitude and to satisfy some nice mathematical properties. We need to know only a surprisingly small number of things about these numbers, though\u2014see the short list below. Here we consider only <em>normal<\/em> numbers, and not denormal numbers, which appear at extremely small magnitudes. The important result of this post is still valid for denormal numbers, which have higher tolerance for error than normal numbers, but we will not demonstrate this detail here.<\/p>\n<p><strong>Definitions<\/strong>: In the discussion below, <code class=\"language-apl\">q<\/code> is used as a short name for the value <code class=\"language-apl\">\u2395CT<\/code>. Unless stated otherwise, formulas below are to be interpreted <em>not<\/em> as floating-point calculations but as mathematical expressions\u2014there is no rounding and all comparisons in formulas are intolerant. Evaluation order follows APL except that <code class=\"language-apl\">=<\/code> is used as in mathematics: it has lower precedence and can be used multiple times in chains to show that many values are all equal to each other. The word &#8220;error&#8221; indicates absolute error, that is, the absolute distance of a computed value from some desired value. The value <code class=\"language-apl\">ulp<\/code> (from &#8220;Unit in the Last Place&#8221;) is used to indicate what some might denote ULP(1), the distance from 1 to the next higher floating point number. It is equal to <code class=\"language-apl\">2*\u00af52<\/code>, and it is an upper bound on the error between two adjacent normal floating-point numbers divided by the smaller of their magnitudes.<\/p>\n<p>We will require the following <strong>facts about floating point numbers<\/strong>:<\/p>\n<ol>\n<li>Two adjacent (normal, nonzero) floating-point numbers <code class=\"language-apl\">a<\/code> and <code class=\"language-apl\">b<\/code> differ by at least <code class=\"language-apl\">0.5\u00d7(|a)\u00d7ulp<\/code> and at most <code class=\"language-apl\">(|a)\u00d7ulp<\/code>.<\/li>\n<li>Consequently, the error introduced by exact rounding in a computation whose exact result is <code class=\"language-apl\">x<\/code> is at most <code class=\"language-apl\">(|x)\u00d70.5\u00d7ulp<\/code>. The operations <code class=\"language-apl\">+-\u00d7\u00f7<\/code> are all exactly rounded.<\/li>\n<li>Sterbenz&#8217;s lemma: If <code class=\"language-apl\">x<\/code> and <code class=\"language-apl\">y<\/code> are two floating-point numbers with <code class=\"language-apl\">x\u22642\u00d7y<\/code> and <code class=\"language-apl\">y\u22642\u00d7x<\/code>, then the difference <code class=\"language-apl\">x-y<\/code> is exactly equal to a floating-point number. Theorem 11 in the link above is closely related, and its proof indicates how one would prove this fact.<\/li>\n<li>Given a floating-point number, the next lower or next higher number can be efficiently computed (in fact, provided the initial number is nonzero, their binary representations differ from that number by exactly 1 when considered as 64-bit integers).<\/li>\n<\/ol>\n<p>We&#8217;ll need <strong>one other fact<\/strong>, which Dyalog APL guarantees (other APLs might not). The maximum value of <code class=\"language-apl\">\u2395CT<\/code> is <code class=\"language-apl\">2*\u00af32<\/code>, chosen so that two 32-bit integers can&#8217;t be tolerantly equal to each other. Otherwise, integers couldn&#8217;t be compared using the typical CPU instructions, which would be a huge performance problem. The value of <code class=\"language-apl\">ulp<\/code> is <code class=\"language-apl\">2*\u00af52<\/code> for IEEE doubles, so <code class=\"language-apl\">\u2395CT*2<\/code> is at most <code class=\"language-apl\">ulp\u00f72*12<\/code>. The proof below holds for <code class=\"language-apl\">\u2395CT*2<\/code> as high as <code class=\"language-apl\">ulp\u00f79<\/code>, but not for <code class=\"language-apl\">\u2395CT*2<\/code> higher than <code class=\"language-apl\">ulp\u00f78<\/code>.<\/p>\n<h2>Our task<\/h2>\n<p>In the following discussion, we will primarily consider the case <code class=\"language-apl\">B&gt;0<\/code>. We want to define a function <code class=\"language-apl\">tolerateLE<\/code> which, given <code class=\"language-apl\">B<\/code>, returns the greatest floating-point value tolerantly less than or equal to <code class=\"language-apl\">B<\/code>, and to show that every value smaller than <code class=\"language-apl\">tolerateLE B<\/code> is also tolerantly less than or equal to <code class=\"language-apl\">B<\/code>. The last post analysed this situation on real (not floating-point) numbers, and showed that in that case <code class=\"language-apl\">tolerateLE B<\/code> is equal to <code class=\"language-apl\">B\u00f71-q<\/code>.<\/p>\n<p>The case <code class=\"language-apl\">B&lt;0<\/code> is substantially simpler to analyse, because the formula <code class=\"language-apl\">B\u00d71-q<\/code> for this case is more tractable. This case is not described fully but can be handled using the same techniques. Also not included is the case <code class=\"language-apl\">B=0<\/code>. <code class=\"language-apl\">tolerateLE 0<\/code> is zero, since comparison with zero is already intolerant.<\/p>\n<h2>Error analysis: <span style='font-family:\"APL385 Unicode\"'>B\u00f71-q<\/span><\/h2>\n<p>(This section isn&#8217;t necessary for our proof. But it&#8217;s useful to see why the obvious formula isn&#8217;t good enough, and serves as a nice warmup before the more difficult computations later.)<\/p>\n<p>When we compute <code class=\"language-apl\">B\u00f71-q<\/code> on a computer, how does that differ from the result of computing <code class=\"language-apl\">B\u00f71-q<\/code> using the mathematician&#8217;s technique of not actually computing it? There are two operations here, and each is subject to floating-point rounding afterwards. To compute the final error we must use an alternating procedure: for each operation, first find the greatest error that could happen if the operation was computed exactly, based on the error in its arguments. Then add another error term for rounding, which is based on the size of the operation&#8217;s result.<\/p>\n<p>It&#8217;s helpful to know first how inverting a number close to 1 affects its error. Suppose <code class=\"language-apl\">x<\/code> is such a number, and it has a maximum error <code class=\"language-apl\">x\u00d7r<\/code>. We&#8217;ll get the largest possible error by comparing <code class=\"language-apl\">y\u00f7x\u00d71-r<\/code> to the exact value <code class=\"language-apl\">y\u00f7x<\/code> (you can verify this by re-doing the calculation below using <code class=\"language-apl\">1+r<\/code> instead). The error is<\/p>\n<pre><code class=\"language-apl\">err = | (y\u00f7x) - y\u00f7x\u00d71-r\r\n    = (y\u00f7x) \u00d7 | 1 - \u00f71-r\r\n    = (y\u00f7x) \u00d7 | r\u00f71-r<\/code><\/pre>\n<p>Assuming <code class=\"language-apl\">r&lt;0.5<\/code>, which will be wildly conservative for our uses, we know that <code class=\"language-apl\">(1-r)&gt;0.5<\/code> and hence <code class=\"language-apl\">(\u00f71-r)&lt;2<\/code>. So if the absolute error in <code class=\"language-apl\">x<\/code> is at most <code class=\"language-apl\">x\u00d7r<\/code>, then the absolute error in <code class=\"language-apl\">y\u00f7x<\/code> (assuming <code class=\"language-apl\">y<\/code> is exact, and before any rounding) is at most:<\/p>\n<pre><code class=\"language-apl\">err &lt; (y\u00f7x) \u00d7 2\u00d7r<\/code><\/pre>\n<p>Now we can figure out the error when evaluating <code class=\"language-apl\">B\u00f71-q<\/code>. At each step the rounding error is at most <code class=\"language-apl\">0.5\u00d7ulp<\/code> times the current value.<\/p>\n<pre><code class=\"language-apl\">\u235dcomputation     error before rounding     error after rounding\r\n1-q              0                         (1-q)\u00d70.5\u00d7ulp\r\nB\u00f71-q            (B\u00f71-q) \u00d7 2\u00d70.5\u00d7ulp       (B\u00f71-q)\u00d71.5\u00d7ulp<\/code><\/pre>\n<p>The actual upper bound on error has a coefficient substantially less than <code class=\"language-apl\">1.5<\/code>, since the error estimate for <code class=\"language-apl\">B\u00f71-q<\/code> was very conservative. But the important thing is that it&#8217;s definitely greater than <code class=\"language-apl\">1<\/code>. The value we compute could be one of the two closest to <code class=\"language-apl\">B\u00f71-q<\/code>, but it could also be further out. Obviously we can&#8217;t guarantee this is the exact value that <code class=\"language-apl\">tolerateLE B<\/code> should return. But what kind of bounds can we set on that value, anyway?<\/p>\n<h2>Evaluating tolerant inequality<\/h2>\n<p>The last post showed that, when <code class=\"language-apl\">B&gt;0<\/code>, a value <code class=\"language-apl\">a<\/code> is tolerantly less than or equal to <code class=\"language-apl\">B<\/code> if and only if it is exactly less than or equal to <code class=\"language-apl\">B\u00f71-q<\/code>. But that was based on perfectly accurate real numbers. What actually happens around this value for IEEE floats? Let&#8217;s say <code class=\"language-apl\">B<\/code> is some positive floating-point number and <code class=\"language-apl\">at<\/code> is the exact value of <code class=\"language-apl\">B\u00f71-q<\/code> (which might not be a floating-point number). Then suppose <code class=\"language-apl\">a<\/code> is another floating-point number, and define <code class=\"language-apl\">e<\/code> (another possibly-non-floating-point number) so that <code class=\"language-apl\">a = at+e<\/code>. What is the result of evaluating the tolerant less-than formula below?<\/p>\n<pre><code class=\"language-apl\">(a-B) \u2264 q \u00d7 0\u2308a\u2308-B<\/code><\/pre>\n<p>The left-hand side turns out to be very easy to analyse due to Sterbenz&#8217;s lemma, which states that if <code class=\"language-apl\">x<\/code> and <code class=\"language-apl\">y<\/code> are two floating-point numbers with <code class=\"language-apl\">x\u22642\u00d7y<\/code> and <code class=\"language-apl\">y\u22642\u00d7x<\/code>, then the difference <code class=\"language-apl\">x-y<\/code> is exactly equal to a floating-point number, meaning that it will not be rounded at all when it is computed. It&#8217;s easy to show that if <code class=\"language-apl\">a&gt;2\u00d7B<\/code> then <code class=\"language-apl\">a<\/code> is tolerantly greater than <code class=\"language-apl\">B<\/code>, and that if <code class=\"language-apl\">B&gt;2\u00d7a<\/code> then <code class=\"language-apl\">a<\/code> is tolerantly less than or equal to <code class=\"language-apl\">B<\/code>. So in the interesting case, where <code class=\"language-apl\">a<\/code> is close to <code class=\"language-apl\">B<\/code>, we know that the following chain of equalities holds exactly:<\/p>\n<pre><code class=\"language-apl\">a-B = e + at-B\r\n    = e + (B\u00f71-q)-B\r\n    = e + B\u00d7(\u00f71-q)-1\r\n    = e + B\u00d7q\u00f71-q<\/code><\/pre>\n<p>Now what about the right-hand side? Because <code class=\"language-apl\">B&gt;0<\/code> and (by our simplifying assumption in the previous paragraph) <code class=\"language-apl\">a\u2265B\u00f72<\/code>, <code class=\"language-apl\">a<\/code> is the largest of the three numbers in <code class=\"language-apl\">0\u2308a\u2308-B<\/code>. Floating-point maximum is always exact (since it&#8217;s equal to one of its arguments), so the right-hand side simplifies to <code class=\"language-apl\">q\u00d7a<\/code>. This expression does end up rounding. Its value before rounding can be expressed in terms of <code class=\"language-apl\">a-B<\/code> and <code class=\"language-apl\">e<\/code>:<\/p>\n<pre><code class=\"language-apl\">q\u00d7a = (q\u00d7at) + q\u00d7e\r\n    = (B\u00d7q\u00f71-q) + q\u00d7e\r\n    = (e + B\u00d7q\u00f71-q) - (e - q\u00d7e)\r\n    = (a-B) - e\u00d71-q<\/code><\/pre>\n<p>It&#8217;s very helpful here to know that <code class=\"language-apl\">a-B<\/code> is exactly a floating-point number! <code class=\"language-apl\">q\u00d7a<\/code> will round to a value that is smaller than <code class=\"language-apl\">a-B<\/code> (thus making the tolerant inequality <code class=\"language-apl\">a\u2264B<\/code> come out false) when it is closer to the next-smallest floating-point number than to <code class=\"language-apl\">a-B<\/code> (if it is halfway between, it could round either way depending on the last bit of <code class=\"language-apl\">a-B<\/code>). This happens as long as <code class=\"language-apl\">e\u00d71-q<\/code> is larger than half the distance to that predecessor. The floating-point format guarantees that, as long as <code class=\"language-apl\">a-B<\/code> is a normal number, this distance is between <code class=\"language-apl\">0.25\u00d7ulp\u00d7a-B<\/code> and <code class=\"language-apl\">0.5\u00d7ulp\u00d7a-B<\/code>, where <code class=\"language-apl\">ulp<\/code> is the difference between 1 and the next floating-point number. Consequently, if <code class=\"language-apl\">e<\/code> is less than <code class=\"language-apl\">0.25\u00d7ulp\u00d7a-B<\/code>, we are sure that <code class=\"language-apl\">a<\/code> will be found tolerantly less than or equal to <code class=\"language-apl\">B<\/code>, and if <code class=\"language-apl\">e<\/code> is greater than <code class=\"language-apl\">0.5\u00d7ulp\u00d7a-B<\/code>, it won&#8217;t be. If it falls in that range, we can&#8217;t be sure.<\/p>\n<p><a href=\"https:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2018\/08\/fig3.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2018\/08\/fig3.png\" alt=\"\" width=\"620\" height=\"200\" class=\"aligncenter size-full wp-image-5250\" srcset=\"https:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2018\/08\/fig3.png 620w, https:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2018\/08\/fig3-300x97.png 300w, https:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2018\/08\/fig3-500x161.png 500w\" sizes=\"auto, (max-width: 620px) 100vw, 620px\" \/><\/a><\/p>\n<p>The zone of uncertainty for the value <code class=\"language-apl\">B\u21902*\u00f75<\/code> is illustrated above. It contains all the values of <code class=\"language-apl\">a<\/code> for which we can&#8217;t say for sure whether <code class=\"language-apl\">a<\/code> is tolerantly less than or equal to <code class=\"language-apl\">B<\/code>, or greater, without actually doing the computation and rounding (that is, the result will depend on specifics of the floating-point format and not just <code class=\"language-apl\">ulp<\/code>). It&#8217;s very small! It will almost never contain an actual floating point value (one of the black ticks), but it could.<\/p>\n<p>If there isn&#8217;t a floating point number in the zone of uncertainty, then <code class=\"language-apl\">tolerateLE B<\/code> has to be the first floating point number to its left. But if there is one, say <code class=\"language-apl\">c<\/code>, then the value depends on whether <code class=\"language-apl\">c<\/code> is tolerantly less than or equal to <code class=\"language-apl\">B<\/code>: if it is, then <code class=\"language-apl\">c = tolerateLE B<\/code>. If not, then that obviously can&#8217;t be the case, and <code class=\"language-apl\">tolerateLE B<\/code> is again the nearest floating point value to the left of the zone of uncertainty.<\/p>\n<h2>Error analysis: <span style='font-family:\"APL385 Unicode\"'>B+q\u00d7B<\/span><\/h2>\n<p>How can we compute <code class=\"language-apl\">B\u00f71-q<\/code> more accurately than our first try? One good way of working with the expression <code class=\"language-apl\">\u00f71-x<\/code> when x is between 0 and 1 is to use its well-known expansion as in infinite polynomial. A mathematically-inclined APLer (who prefers <code class=\"language-apl\">\u2395IO\u21900<\/code>) might write<\/p>\n<pre><code class=\"language-apl\">(\u00f71-x) = +\/x*\u2373\u221e<\/code><\/pre>\n<p>where the right-hand side represents the infinite series 1+x+x\u00b2+x\u00b3+\u2026. One fact that seems more obvious when thinking about the series than about the reciprocal is that, defining <code class=\"language-apl\">z\u2190\u00f71-x<\/code>, we know <code class=\"language-apl\">z = 1+x\u00d7z<\/code>. So similarly,<\/p>\n<pre><code class=\"language-apl\">(B\u00f71-q) = B+q\u00d7B\u00f71-q<\/code><\/pre>\n<p>But it turns out to be much easier than that! The difference between <code class=\"language-apl\">1<\/code> and <code class=\"language-apl\">\u00f71-q<\/code> is fairly close to <code class=\"language-apl\">q<\/code>. So if we replace <code class=\"language-apl\">\u00f71-q<\/code> by <code class=\"language-apl\">1<\/code>, then we end up off by about <code class=\"language-apl\">B\u00d7q\u00d7q<\/code>. Knowing that <code class=\"language-apl\">q*2<\/code> is much smaller than <code class=\"language-apl\">ulp<\/code>, we see that this difference is miniscule compared to <code class=\"language-apl\">B<\/code>. So why don&#8217;t we try the expression <code class=\"language-apl\">B+q\u00d7B<\/code>?<\/p>\n<p>The error in using <code class=\"language-apl\">B<\/code> instead of <code class=\"language-apl\">B\u00f71-q<\/code> is<\/p>\n<pre><code class=\"language-apl\">(|B - B\u00f71-q) = |B \u00d7 1-\u00f71-q\r\n             = |B \u00d7 ((1-q)-1)\u00f71-q\r\n             = B \u00d7 q\u00f71-q<\/code><\/pre>\n<p>Multiplying by <code class=\"language-apl\">q<\/code>, the absolute error of <code class=\"language-apl\">q\u00d7B<\/code> is <code class=\"language-apl\">q\u00d7B \u00d7 q\u00f71-q<\/code>, which, knowing that <code class=\"language-apl\">(\u00f71-q)&lt;2<\/code>, is less than <code class=\"language-apl\">B \u00d7 2\u00d7q*2<\/code>, and consequently less than, say, <code class=\"language-apl\">B\u00d70.05\u00d7ulp<\/code>.<\/p>\n<pre><code class=\"language-apl\">\u235dcomputation   relative to    err before rounding   err after rounding\r\nq\u00d7B            q\u00d7B\u00f71-q        B\u00d70.05\u00d7ulp            B\u00d7(0.05+q)\u00d7ulp\r\nB+q\u00d7B          B\u00f71-q          B\u00d70.06\u00d7ulp<\/code><\/pre>\n<p>That&#8217;s pretty close: the unrounded error is substantially less than the error that will be introduced by the final rounding (about <code class=\"language-apl\">B\u00d70.5\u00d7ulp<\/code>). Chances are, it&#8217;s the closest floating point number to <code class=\"language-apl\">B\u00f71-q<\/code>. But it could wind up on either side of that value, so we will need to perform a final adjustment to obtain <code class=\"language-apl\">tolerateLE B<\/code>.<\/p>\n<p>Note that the new formula <code class=\"language-apl\">B+q\u00d7B<\/code> is very similar to the formula <code class=\"language-apl\">B\u00d71-q<\/code> which is used when <code class=\"language-apl\">B<\/code> is negative. In fact, calculating the latter value with the expression <code class=\"language-apl\">B+q\u00d7-B<\/code> will also have a very low error. That means we can use <code class=\"language-apl\">B+q\u00d7|B<\/code> for both cases! However, we will still need to distinguish between them when testing whether the value that we get is actually tolerantly less than or equal to <code class=\"language-apl\">B<\/code>.<\/p>\n<h2>Polishing up<\/h2>\n<p><a href=\"https:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2018\/08\/fig4.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2018\/08\/fig4.png\" alt=\"\" width=\"620\" height=\"130\" class=\"aligncenter size-full wp-image-5255\" srcset=\"https:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2018\/08\/fig4.png 620w, https:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2018\/08\/fig4-300x63.png 300w, https:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2018\/08\/fig4-500x105.png 500w\" sizes=\"auto, (max-width: 620px) 100vw, 620px\" \/><\/a><\/p>\n<p>After we calculate <code class=\"language-apl\">a\u2190B+q\u00d7B<\/code>, we still don&#8217;t know which way <code class=\"language-apl\">a\u2264B<\/code> will go. There&#8217;s just too much error to make sure it falls on one side or the other of the critical band. But we do know about the numbers just next to it: a value adjacent to <code class=\"language-apl\">a<\/code> must be separated from the unrounded value of <code class=\"language-apl\">B+q\u00d7B<\/code> by at least <code class=\"language-apl\">0.25\u00d7B\u00d7(1+q)\u00d7ulp<\/code>, or else we would have rounded <code class=\"language-apl\">a<\/code> towards it. That unrounded value differs from the true value <code class=\"language-apl\">B\u00f71-q<\/code> by only <code class=\"language-apl\">0.06\u00d7B\u00d7ulp<\/code> at most, so we know that these neighbors are at least <code class=\"language-apl\">((0.25\u00d71+q)-0.06)\u00d7B\u00d7ulp<\/code> or (rounding down some) <code class=\"language-apl\">0.15\u00d7B\u00d7ulp<\/code> from <code class=\"language-apl\">at<\/code>. But that&#8217;s way outside of the zone of uncertainty, which goes out only to <code class=\"language-apl\">0.5\u00d7ulp\u00d7a-B<\/code>, since <code class=\"language-apl\">a-B<\/code> is somewhere around <code class=\"language-apl\">q\u00d7B<\/code>.<\/p>\n<p>So we know that the predecessor to <code class=\"language-apl\">a<\/code> must be tolerantly less than or equal to <code class=\"language-apl\">B<\/code>, and its sucessor must not be. That leaves us with only two possibilities: either <code class=\"language-apl\">a<\/code> is tolerantly less than or equal to <code class=\"language-apl\">B<\/code>, in which case it is the largest floating-point number with this property, or it isn&#8217;t, in which case its predecessor is that number. In the diagram above, we can see that the range for <code class=\"language-apl\">a<\/code> is a little bigger than the gap between ticks, but it&#8217;s small enough that the ranges for its predecessor <code class=\"language-apl\">P(a)<\/code> and successor <code class=\"language-apl\">S(a)<\/code> don&#8217;t overlap with <code class=\"language-apl\">B\u00f71-\u2395CT<\/code> or the invisibly small zone of uncertainty to its right. In this case <code class=\"language-apl\">a<\/code> rounds left, so <code class=\"language-apl\">a = tolerateLE B<\/code>, but if it rounded right, then we would have <code class=\"language-apl\">(P(a)) = tolerateLE B<\/code>.<\/p>\n<p>So that&#8217;s the algorithm! Just compute <code class=\"language-apl\">B+q\u00d7|B<\/code>, and compare to see if it is tolerantly less than or equal to <code class=\"language-apl\">B<\/code>. If it is, return it, and otherwise, return its predecessor, the next floating point number in the direction of negative infinity. We also add checks to the Dyalog interpreter&#8217;s debug mode to make sure the number returned is actually tolerantly less than or equal to <code class=\"language-apl\">B<\/code>, and that the next larger one isn&#8217;t.<\/p>\n<h2>APL model<\/h2>\n<p>The following code implements the ideas above in APL. Note that it can give a domain error for numbers near the edges of the floating-point range; Dyalog&#8217;s internal C implementation has checks to handle these cases properly. <code class=\"language-apl\">adjFP<\/code> does some messy work with the binary representation of a floating-point value in order to add or subtract one from the integer it represents. Once that&#8217;s out of the way, tolerated inequalities are very simple!<\/p>\n<pre><code class=\"language-apl\">\u235d Return the next smaller floating-point number if \u237a is \u00af1, or the\r\n\u235d next larger if \u237a is 1 (default).\r\n\u235d Not valid if \u2375=0.\r\nadjFP \u2190 {\r\n  \u237a\u21901 \u22c4 x\u2190(\u237a\u22650)\u2260\u2375\u22650\r\n  bo\u2190,\u2218\u233d(8 8\u2218\u2374)\u2363(~\u228383 \u2395DR 256) \u235d Order bits little-endian (self-inverse)\r\n  \u2283645\u2395DR bo (\u22a2\u2260\u00af1\u21931,(\u2227\\x\u2260\u22a2)) bo 11\u2395DR \u22830 645\u2395DR \u2375\r\n}\r\n\r\n\u235d Tolerate the right-hand side of an inequality.\r\n\u235d tolerateLE increases its argument while tolerantGE decreases it.\r\n\u235d tolerantEQ returns the smallest and largest values equal to its argument.\r\ntolerateLE \u2190 { \u00af1 adjFP\u2363(t&gt;\u2375)\u22a2 t\u2190\u2375+\u2395ct\u00d7|\u2375 }\r\ntolerateGE \u2190 -\u2218tolerateLE\u2218-\r\ntolerateEQ \u2190 tolerateGE , tolerateLE<\/code><\/pre>\n<p>We can see below that tolerateEQ returns values which are tolerantly equal to the original argument, but which are adjacent to other values that aren&#8217;t.<\/p>\n<pre><code class=\"language-apl\">      (\u22a2=tolerateEQ) 2*\u00f75\r\n1 1\r\n      (\u22a2=\u00af1 1 adjFP\u00a8 tolerateEQ) 2*\u00f75\r\n0 0<\/code><\/pre>\n<p>Of course, using <code class=\"language-apl\">tolerateEQ<\/code> followed by intolerant comparison won&#8217;t speed anything up in version 17.0: that&#8217;s already been done!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>This post might be more difficult than our usual fare. You won&#8217;t find any interesting APL coding insights here\u2014instead we&#8217;ll be focused on the tricky topic of floating-point error analysis. If that&#8217;s not your thing, feel free to skip this &hellip; <a href=\"https:\/\/www.dyalog.com\/blog\/2019\/06\/tolerated-comparison-part-2\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":27,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[33],"tags":[],"class_list":["post-5205","post","type-post","status-publish","format-standard","hentry","category-implementation"],"_links":{"self":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/5205","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/users\/27"}],"replies":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/comments?post=5205"}],"version-history":[{"count":27,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/5205\/revisions"}],"predecessor-version":[{"id":5900,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/5205\/revisions\/5900"}],"wp:attachment":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/media?parent=5205"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/categories?post=5205"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/tags?post=5205"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}