Preventing overflows and preserving precision when scaling (long-)integers

Question

Let's say I have a position pos within a given range, such that:

   0 <= pos < range

This position within the range can consist in two different contexts, one where the range is an integer value, i.e. pos < range < 2³¹, and the other where the range is a long-integer, i.e. up to pos < range < 2⁶³. 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:

   pos _new = floor( pos _old * range _new / range _old )

Unfortunately, this straight forward approach doesn't do the trick since it either overflows (as pos _old * range _new can be as large as ~2⁹⁴) 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).

I found a way to scale from the integer range to the long-integer range correctly:

public long scaleUp(int oldPos, int oldRange, long newRange) {
    return (newRange / oldRange) * oldPos + 
           (newRange % oldRange) * oldPos / oldRange;
}

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).

What I'm trying to figure out now, is a way to do the reverse scaling:

public int scaleDown(long oldPos, long oldRange, int newRange) {
    return ??? ;
}

Not sure if this should be any more difficult than the other function, but somehow I'm not seeing it.

A couple of remarks:

• 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
• I'd rather not use a BigInteger library
• While the code-samples here are Java, this really is a language-agnostic question

Answer 1

I figured out an answer that is not 100% complete, but covers all special cases that occur in my program. You can find the details of the derivation in the answer I posted to my corresponding question on the Mathematics StackExchange: https://math.stackexchange.com/q/433729/84557

Here's the rough outline:

public int scaleDown(long oldPos, long oldRange, int newRange) {
    if (oldPos <= Long.MAX_VALUE/newRange)
        return (int) (oldPos*newRange/oldRange);
    assert oldRange >= newRange*newRange : "Case not supported yet"; // Never happens in my code
    int newPos = (int) (oldPos / (oldRange/newRange));
    if (!isOk(newPos)) newPos--; // Check might be implementation specific
    return newPos;
}

Not complete, but maybe it's useful for someone anyways.

Answer 2

I am very, very late to this party, but I ran into the exact same problem.

Note that I have been using the terms x for your pos, y for your oldRange, and w for your newRange, i.e. solving for z in the equation x/y = z/w.

Here are the solutions I've considered:

I could use floating points, but then whether the accuracy is acceptable for 64-bit integers becomes entirely dependent on whether the platform supports floats with a mantissa of at least 64 bits. (Many platforms do not.)

I could redefine the the input domain to one that's smaller than the output range by no more than half and then scale up - i.e. q = y / w; scaleUp(x / q / 2, y / q / 2, w);, and in the worst case the lowest-order bit would be entirely lost and in the best case no information would be lost at all, but I don't want to lose the lower-order bit in any case.

I could use a sort of binary search to find the value to subtract from x / (y / w) in order to compensate for error, but I don't consider the performance impact of using a loop or recursion to be acceptable.

Right now I the best I've come up with is to normally compute x / (y / w) - (y % w) * x / y and when the multiplication would overflow - which, granted, should only be for a relatively small domain of inputs (certainly fewer inputs than just computing x * w / y) - use an algorithm such as this one to capture the high bits of the product.

But I still really feel like there has got to be a simpler way to do this.

Answer 3

EDIT: This solution is not correct, see discussion in the comments.

I have a solution without special cases. I don't have a proof of correctness, but it looks plausible and I couldn't find a counterexample.

int scaleDown2(long longPos, long longRange, int shortRange) {
    int p = longPos / (longRange / shortRange);
    return p - ((p * (longRange % shortRange)) / longRange);
}