integer - 缩放(长)整数时防止溢出并保持精度

Question

假设我在给定的范围内有一个位置pos，这样:

0 <= 位置 <范围

范围内的这个位置可以包含两种不同的上下文，一种是范围是整数值，即 pos <range < 2³¹，另一个范围是长整数，即最大 pos <range < 2⁶³。如果我想在这些上下文之间移动，我需要将位置缩放到新范围，以便它正确地向下舍入到最接近的(长)整数值。所以，从技术上讲，我想做的就是:

pos _new = floor( pos _old * range_新的/范围 _旧的 )

不幸的是，这种直接的方法并不能解决问题，因为它要么溢出(如 pos _old * range _new 可以大到 ~2⁹⁴) 如果我先做乘法或者如果我先做除法会给我舍入误差。使用浮点值进行数学运算通常也无济于事，因为它们没有提供足够的精度，因此也可能导致不正确的舍入(我只有 double 可用)。

我找到了一种从整数范围正确缩放到长整数范围的方法:

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

这可确保计算既不会在任何时候溢出长整数的限制，也不会因过早舍入而失去准确性(模数会捕获在第一除法中因舍入而丢失的部分)。

我现在想弄清楚的是一种进行反向缩放的方法:

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

不确定这是否应该比其他函数更难，但不知何故我没有看到它。

几点说明:

• 我想避免使用浮点运算，因为我总是发现很难说服自己，给定的公式在某些非常罕见的情况下确实不可能由于四舍五入而产生意想不到的结果
• 我不想使用 BigInteger 库
• 虽然这里的代码示例是 Java，但这确实是一个与语言无关的问题

Answer 1

我找到了一个不是 100% 完整的答案，但涵盖了我的程序中出现的所有特殊情况。您可以在我在 Mathematics StackExchange 上发布的相应问题的答案中找到推导的详细信息:https://math.stackexchange.com/q/433729/84557

这是粗略的概述:

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;
}

不完整，但也许对某些人有用。