title: Faster divisibility test than % operator?
body: <p>I noticed a curious thing on my computer.<sup>*</sup> The handwritten divisibility test is significantly faster than the <code>%</code> operator. Consider the minimal example:</p>
  
  <p><sup>*<sub> AMD Ryzen Threadripper 2990WX, GCC 9.2.0</sub></sup>  </p>
  
  <pre class="lang-c prettyprint-override"><code>static int divisible_ui_p(unsigned int m, unsigned int a)
  {
      if (m &lt;= a) {
          if (m == a) {
              return 1;
          }
  
          return 0;
      }
  
      m += a;
  
      m &gt;&gt;= __builtin_ctz(m);
  
      return divisible_ui_p(m, a);
  }
  </code></pre>
  
  <p>The example is limited by odd <code>a</code> and <code>m &gt; 0</code>. However, it can be easily generalized to all <code>a</code> and <code>m</code>. The code just converts the division to a series of additions.</p>
  
  <p>Now consider the test program compiled with <code>-std=c99 -march=native -O3</code>:</p>
  
  <pre class="lang-c prettyprint-override"><code>    for (unsigned int a = 1; a &lt; 100000; a += 2) {
          for (unsigned int m = 1; m &lt; 100000; m += 1) {
  #if 1
              volatile int r = divisible_ui_p(m, a);
  #else
              volatile int r = (m % a == 0);
  #endif
          }
      }
  </code></pre>
  
  <p>... and the results on my computer:</p>
  
  <pre><code>| implementation     | time [secs] |
  |--------------------|-------------|
  | divisible_ui_p     |    8.52user |
  | builtin % operator |   17.61user |
  </code></pre>
  
  <p>Therefore more than 2 times faster.</p>
  
  <p>The question: Can you tell me how the code behaves on your machine? Is it missed optimization opportunity in GCC? Can you do this test even faster?</p>
  
  <hr>
  
  <p><strong>UPDATE:</strong>
  As requested, here is a minimal reproducible example:</p>
  
  <pre class="lang-c prettyprint-override"><code>#include &lt;assert.h&gt;
  
  static int divisible_ui_p(unsigned int m, unsigned int a)
  {
      if (m &lt;= a) {
          if (m == a) {
              return 1;
          }
  
          return 0;
      }
  
      m += a;
  
      m &gt;&gt;= __builtin_ctz(m);
  
      return divisible_ui_p(m, a);
  }
  
  int main()
  {
      for (unsigned int a = 1; a &lt; 100000; a += 2) {
          for (unsigned int m = 1; m &lt; 100000; m += 1) {
              assert(divisible_ui_p(m, a) == (m % a == 0));
  #if 1
              volatile int r = divisible_ui_p(m, a);
  #else
              volatile int r = (m % a == 0);
  #endif
          }
      }
  
      return 0;
  }
  </code></pre>
  
  <p>compiled with <code>gcc -std=c99 -march=native -O3 -DNDEBUG</code> on AMD Ryzen Threadripper 2990WX with</p>
  
  <pre><code>gcc --version
  gcc (Gentoo 9.2.0-r2 p3) 9.2.0
  </code></pre>
  
  <hr>
  
  <p><strong>UPDATE2:</strong> As requested, the version that can handle any <code>a</code> and <code>m</code> (if you also want to avoid integer overflow, the test has to be implemented with integer type twice as long as the input integers):</p>
  
  <pre class="lang-c prettyprint-override"><code>int divisible_ui_p(unsigned int m, unsigned int a)
  {
  #if 1
      /* handles even a */
      int alpha = __builtin_ctz(a);
  
      if (alpha) {
          if (__builtin_ctz(m) &lt; alpha) {
              return 0;
          }
  
          a &gt;&gt;= alpha;
      }
  #endif
  
      while (m &gt; a) {
          m += a;
          m &gt;&gt;= __builtin_ctz(m);
      }
  
      if (m == a) {
          return 1;
      }
  
  #if 1
      /* ensures that 0 is divisible by anything */
      if (m == 0) {
          return 1;
      }
  #endif
  
      return 0;
  }
  </code></pre>