pages tagged cwokhttp://wok.oblomov.eu/tag/c/wok's tag/cikiwiki2021-02-12T22:56:38Z(How to) avoid division by zero (in C)http://wok.oblomov.eu/tecnologia/avoid-division-by-zero/Oblomov2021-02-12T22:56:38Z2021-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 <math><mstyle><mi>r</mi><mo>=</mo><mfrac><mi>a</mi><mi>b</mi></mfrac></mstyle></math> if <math><mstyle><mi>b</mi></mstyle></math> is non-zero,
otherwise <math><mstyle><mi>r</mi><mo>=</mo><mi>a</mi></mstyle></math> 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 shorthttp://wok.oblomov.eu/tecnologia/short-lives/Oblomov2013-08-23T12:22:12Z2013-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"> ↩</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"> ↩</a></p></li>
</ol>
</div>