Multiplying integer by rational without intermediate overflow
<p>I have a struct representing a nonnegative rational number p/q:</p>

<pre><code>struct rational {
    uint64_t p;
    uint64_t q; // invariant: always &gt; 0
};
</code></pre>

<p>I would like to multiply my rational by a uint64 <code>n</code> and get an integer result, rounded down. That is, I would like to calculate:</p>

<pre><code>uint64_t m = (n * r.p)/r.q;
</code></pre>

<p>while avoiding intermediate overflow in <code>n * r.p</code>. (Of course the final result may overflow, which is acceptable.)</p>

<p>How can I do this? Is there a way to do it without a high-multiply?</p>

<p>(I looked at boost::rational but it does not appear to provide this feature.)</p>