title: Preventing overflows and preserving precision when scaling (long-)integers
body: <p>Let's say I have a position <em>pos</em> within a given <em>range</em>, such that:</p>
  
  <p>&nbsp; &nbsp;0 &lt;= <em>pos</em> &lt; <em>range</em></p>
  
  <p>This position within the range can consist in two different contexts, one where the range is an integer value, i.e. <em>pos</em> &lt; <em>range</em> &lt; 2<sup>31</sup>, and the other where the range is a long-integer, i.e. up to <em>pos</em> &lt; <em>range</em> &lt; 2<sup>63</sup>. If I want to move between these contexts, I need to scale the position to the new range such that it is correctly rounded down to the nearest (long-)integer value. So, technically, all I want to do is:</p>
  
  <p>&nbsp; &nbsp;<em>pos</em><sub> new</sub> = floor( <em>pos</em><sub> old</sub> * <em>range</em><sub> new</sub> / <em>range</em><sub> old</sub> )</p>
  
  <p>Unfortunately, this straight forward approach doesn't do the trick since it either overflows (as <em>pos</em><sub> old</sub> * <em>range</em><sub> new</sub> can be as large as ~2<sup>94</sup>) if I do the multiplication first or gives me rounding errors if I do the division first. Using floating point values to do the math doesn't help in general either, as they don't offer enough bits of precision and might therefore also lead to incorrect rounding (I only have double-precision available).</p>
  
  <p>I found a way to scale from the integer range to the long-integer range correctly:</p>
  
  <pre class="lang-java prettyprint-override"><code>public long scaleUp(int oldPos, int oldRange, long newRange) {
      return (newRange / oldRange) * oldPos + 
             (newRange % oldRange) * oldPos / oldRange;
  }
  </code></pre>
  
  <p>This ensures that the calculation neither overflows the limits of a long-integer at any point, nor looses accuracy due to premature rounding (the modulus captures the part lost to rounding in the first division).</p>
  
  <p>What I'm trying to figure out now, is a way to do the reverse scaling:</p>
  
  <pre class="lang-java prettyprint-override"><code>public int scaleDown(long oldPos, long oldRange, int newRange) {
      return ??? ;
  }
  </code></pre>
  
  <p>Not sure if this should be any more difficult than the other function, but somehow I'm not seeing it. </p>
  
  <p>A couple of remarks:</p>
  
  <ul>
  <li>I'd like to avoid using floating point arithmetic, since I always find it very hard to convince myself that it is truly not possible for a given formula to yield an unexpected result in some highly infrequent cases due to rounding</li>
  <li>I'd rather not use a BigInteger library</li>
  <li>While the code-samples here are Java, this really is a language-agnostic question</li>
  </ul>