pages tagged c wok http://wok.oblomov.eu/tag/c/ wok's tag/c ikiwiki 2021-02-12T22:56:38Z (How to) avoid division by zero (in C) http://wok.oblomov.eu/tecnologia/avoid-division-by-zero/ Oblomov 2021-02-12T22:56:38Z 2021-02-12T22:55:00Z <p>Let's say we're collecting some data, and we want to compute an average of the values. Or we computed the absolute error, and we want the relative error. This requires the division of some number (e.g. the sum of the values, or the absolute error) by some other number (e.g. the number of values, the reference value).</p> <p>Catastrophe arises when the number we want to divide by is 0: if the list of values we want to average is empty, for example, we would end up with an expression such as 0/0 (undefined).</p> <p>Programmatically, we would like to avoid such corner cases with as little hassle as possible. The standard way to handle these cases is by using <em>conditional</em> expressions: <em>if the value we want to divide for is zero, do something special, otherwise do the division we're actually interested in</em>.</p> <p>This can be cumbersome.</p> <p>In what follows, we'll assume that the special handling of the zero division case would be to return the numerator unchanged: we want [itex]<mstyle><mi>r</mi><mo>=</mo><mfrac><mi>a</mi><mi>b</mi></mfrac></mstyle>[/itex] if [itex]<mstyle><mi>b</mi></mstyle>[/itex] is non-zero, otherwise [itex]<mstyle><mi>r</mi><mo>=</mo><mi>a</mi></mstyle>[/itex] will do. In (C) code, this could be written:</p> <pre><code>if (b != 0) r = a/b; else r = a;</code></pre> <p>We can write this more succinctly using the ternary operator:</p> <pre><code>r = b != 0 ? a/b : a;</code></pre> <p>or, leveraging the fact that any non-zero value is “true”:</p> <pre><code>r = b ? a/b : a;</code></pre> <p>I'll leave it to the reader to decide if this expression is more readable or not, but the fundamental issue remains that this kind of conditional handling is still not nice. Worse, if this is done in a loop (e.g. to convert a set of absolute errors into a set of relative errors, dividing each by the corresponding —potentially null!— reference value) It can even produce sub-optimal code on modern machines with vector capabilities: since the expression for the two sides is different, and there is no way to know (until the program is running) which elements will follow which path, the compiler will have to produce sub-optimal scalar code instead of potentially much faster vectorized code.</p> <p>Ideally, we would want to have the same operation done on both sides of the conditional. This can, in fact, be achieved by remarking that <code>a</code> is the same as <code>a/1</code>. We can thus write:</p> <pre><code>r = a/(b ? b : 1);</code></pre> <p>The advantage of this expression is that, as the body of a loop, it leads to better vectorization opportunities, delegating the conditional to the construction of the divisor.</p> <p>But we can do better! There's a nifty trick we can employ (at least in C), leveraging the fact that <em>the boolean negation of any non-zero value is 0</em>, and <em>the boolean negation of 0 is 1</em>. The trick is:</p> <pre><code>r = a/(b + !b);</code></pre> <h2 id="whydoesthiswork">Why does this work?</h2> <p>If <code>b == 0</code>, then <code>!b == 1</code>, and <code>b + !b == 0 + 1 == 1</code>.</p> <p>If <code>b != 0</code>, then <code>!b == 0</code>, and <code>b + !b == b + 0 == b</code>.</p> <p>The result of <code>b + !b</code> is thus exactly the same as <code>b ? b : 1</code>, without using conditionals.</p> Our lives are short http://wok.oblomov.eu/tecnologia/short-lives/ Oblomov 2013-08-23T12:22:12Z 2013-08-23T12:15:00Z <p>Some time ago someone on <a href="http://www.friendfeed.com">FriendFeed</a> asked if anybody (else) would celebrate their kid's 1000th day. Among the negative answers, someone remarked that they'd rather celebrate the 1024th. And as hardened computer geek, that was my first thought as well.</p> <p>But why stop there? Or rather: if your baby is young, why <em>start</em> there?</p> <p>So we started collecting the other power-of-two dates (power-of-two-versaries<a href="http://wok.oblomov.eu/tag/c/#fn:naming" id="fnref:naming:1" title="see footnote" class="footnote">1</a>?) for our baby, and after asking about a few from <a href="http://www.wolframalpha.com">WolframAlpha</a>, I set up to write a Ruby script to do the computations for me, and the first question that arose was: what's the <em>highest</em> (integer) power of two that should be considered?</p> <p>Since the script wasn't ready yet, I asked WolframAlpha again, to quickly discover that the best we can do comes significantly short of 2<sup>16</sup> days, which is almost 180 years (179 years, 5 months, and a few days, with the actual number of days depending on how many leap years are covered by the timespan)<a href="http://wok.oblomov.eu/tag/c/#fn:3adults" id="fnref:3adults:1" title="see footnote" class="footnote">2</a>.</p> <p>Now, as it happens, 16 bits is the (minimum) width of the <code>short</code> data type in the C family of programming languages; in fact, on most platforms and systems, 16 bits its <em>exactly</em> the width of the <code>short</code> data type.</p> <p>As it turns out, our lives are indeed (unsigned) short.</p> <div class="footnotes"> <hr /> <ol> <li id="fn:naming"><p>if anybody has a better name for them, please tell.<a href="http://wok.oblomov.eu/tag/c/#fnref:naming:1" title="return to article" class="reversefootnote">&#160;&#8617;</a></p></li> <li id="fn:3adults"><p>most modern-day human adults can aspire at hitting three power-of-two-versaries at best: 2<sup>13</sup> (22 years, 5 months, and the usual bunch of days) as a young adult, 2<sup>14</sup> (44 years, 10 months and a week, day more day less) and finally 2<sup>15</sup> (89 years, 8 months and a half), <a href="http://en.wikipedia.org/wiki/Life_expectancy#Human_life_expectancy_patterns">for the lucky ones</a>.<a href="http://wok.oblomov.eu/tag/c/#fnref:3adults:1" title="return to article" class="reversefootnote">&#160;&#8617;</a></p></li> </ol> </div>