title: How to multiply an integer by a fraction
body: <p>So my goal here is to have a function whose signature looks like this:</p>
  
  <pre><code>template&lt;typename int_t, int_t numerator, int_t denominator&gt;
  int_t Multiply(int_t x);
  </code></pre>
  
  <p>The type is an integral type, which is both the type of the one parameter and the return type.</p>
  
  <p>The other two template parameters are the numerator and denominator of a fraction.</p>
  
  <p>The goal of this function is to multiply a number "x" by an arbitrary fraction, which is in the two template values.  In general the answer should be:</p>
  
  <pre><code>floor(x*n/d) mod (int_t_max+1)
  </code></pre>
  
  <p>The naive way to do this is to first multiply "x" by the numerator and then divide.</p>
  
  <p>Looking at a specific case lets say that <code>int_t</code>=<code>uint8_t</code>, "x" is 30 and the numerator and denominator are 119 and 255 respectively.</p>
  
  <p>Taking this naive route fails because (30*119)mod 256 = 242, which divided by 255 and then floored is 0.  The real answer should be 14.</p>
  
  <p>The next step would be to just use a bigger integer size for the intermediate values.  So instead of doing the 30*119 calculation in mod 256 we would do it in mod 65536.  This does work to a certain extent, but it fails when we try to use the maximum integer size in the <code>Multiply</code> function.</p>
  
  <p>The next step would be to just use some <code>BigInt</code> type to hold the values so that it <em>can't</em> overflow.  This also would work, but the whole reason for having the template arguments, is so that this can be extremely fast, and using a <code>BigInt</code> would probably defeat that purpose.</p>
  
  <p>So here is the question:</p>
  
  <p>Is there an algorithm that only involves shifts, multiplication, division, addition, subtraction, and remainder operators, that can preform this mathematical function, without causing overflow issues?</p>