title: how to calculate (a times b) divided by c only using 32-bit integer types even if a times b would not fit such a type
body: <p>Consider the following as a reference implementation:</p>
  
  <pre><code>/* calculates (a * b) / c */
  uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c)
  {
      uint64_t x = a;
      x = x * b;
      x = x / c;
      return x;
  }
  </code></pre>
  
  <p>I am interested in an implementation (in C or pseudocode) that does not require a 64-bit integer type.</p>
  
  <p>I started sketching an implementation that outlines like this:</p>
  
  <pre><code>/* calculates (a * b) / c */
  uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c)
  {
      uint32_t d1, d2, d1d2;
      d1 = (1 &lt;&lt; 10);
      d2 = (1 &lt;&lt; 10);
      d1d2 = (1 &lt;&lt; 20); /* d1 * d2 */
      return ((a / d1) * (b /d2)) / (c / d1d2);
  }
  </code></pre>
  
  <p>But the difficulty is to pick values for d1 and d2 that manage to avoid the overflow ((a / d1) * (b / d2) &lt;= UINT32_MAX) and minimize the error of the whole calculation.</p>
  
  <p>Any thoughts?</p>