title: (a * b) / c MulDiv and dealing with overflow from intermediate multiplication
body: <p>I need to do the following arithmetic:</p>
  
  <pre><code>long a,b,c;
  long result = a*b/c;
  </code></pre>
  
  <p>While the result is guaranteed to fit in <code>long</code>, the multiplication is not, so it can overflow.</p>
  
  <p>I tried to do it step by step (first multiply and then divide) while dealing with the overflow by splitting the intermediate result of <code>a*b</code> into an int array in size of max 4 ( much like the BigInteger is using its <code>int[] mag</code> variable).</p>
  
  <p>Here I got stuck with the division. I cannot get my head around the bitwise shifts required to do a precise division. All I need is the quotient (don't need the remainder).</p>
  
  <p>The hypothetical method would be:</p>
  
  <pre><code>public static long divide(int[] dividend, long divisor)
  </code></pre>
  
  <p>Also, I am not considering using <code>BigInteger</code> as this part of the code needs to be fast ( I would like to stick to using primitives and primitive arrays).</p>
  
  <p>Any help would be much appreciated!</p>
  
  <p>Edit:
  I am not trying to implement the whole <code>BigInteger</code> myself. What I am trying to do is to solve a specific problem (<code>a*b/c</code>, where <code>a*b</code> can overflow) faster than using the generic <code>BigInteger</code>.</p>
  
  <p>Edit2: It would be ideal if it could be done in a <em>clever</em> way, by not getting overflow at all, some tips surfaced in the comments, but I am still looking for one that is correct.</p>
  
  <p><strong>Update:</strong>
  I tried to port BigInteger code to my specific needs, without object creation, and in the first iteration, I got ~46% improvement in speed comparing to using BigInteger (on my development pc).</p>
  
  <p>Then I tried a bit modified @David Eisenstat solution, which gave me ~56 % (I ran 100_000_000_000 random inputs from <code>Long.MIN_VALUE</code> to <code>Long.MAX_VALUE</code>) reduced run times(more than 2x) comparing to BigInteger (that is ~18% compared to my adapted BigInteger algo).</p>
  
  <p>There will be more iterations on optimization and testing, but at this point, I think I must accept this answer as the best.</p>