3

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

   0 <=位置<范围

范围内的这个位置可以包含在两种不同的上下文中，一种是范围是整数值，即pos < range < 2 31，另一种是范围是长整数，即高达pos < range < 2 63 . 如果我想在这些上下文之间移动，我需要将位置缩放到新范围，以便正确地向下舍入到最接近的（长）整数值。所以，从技术上讲，我想做的就是：

   pos new = floor( pos old * range new / range old )

不幸的是，这种直截了当的方法并不能解决问题，因为如果我先进行乘法运算，它会溢出（因为pos old * range new可以大到 ~2 94），或者如果我先进行除法运算，则会出现舍入错误。使用浮点值进行数学运算通常也无济于事，因为它们不能提供足够的精度位，因此也可能导致不正确的舍入（我只有双精度可用）。

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

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，但这确实是一个与语言无关的问题
4

3 回答 3

0

我想出了一个不是 100% 完整的答案，但涵盖了我的程序中发生的所有特殊情况。您可以在我在数学 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;
}

不完整，但无论如何它可能对某人有用。

于 2013-07-05T08:39:01.943 回答
0

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);
}
于 2020-04-18T08:41:06.947 回答
0

我参加这个聚会非常非常晚，但我遇到了完全相同的问题。

请注意，我一直在使用术语xfor your pos、yfor youroldRange和wfor your newRange，即z在方程中求解 for x/y = z/w。

以下是我考虑过的解决方案：

我可以使用浮点数，但是对于 64 位整数，精度是否可以接受完全取决于平台是否支持尾数至少为 64 位的浮点数。（许多平台没有。）

我可以将输入域重新定义为比输出范围小不超过一半的域，然后按比例放大 - 即q = y / w; scaleUp(x / q / 2, y / q / 2, w);，在最坏的情况下，最低位将完全丢失，在最好的情况下，不会有任何信息完全丢失，但无论如何我都不想丢失低位。

我可以使用一种二分搜索来找到要减去的值以x / (y / w)补偿错误，但我不认为使用循环或递归对性能的影响是可以接受的。

现在我想出的最好的方法是正常计算x / (y / w) - (y % w) * x / y，当乘法溢出时——当然，这应该只适用于相对较小的输入域（当然输入比计算少x * w / y）——使用算法，例如这个是为了捕捉产品的高位。

但我仍然觉得必须有一种更简单的方法来做到这一点。

于 2017-02-20T00:02:33.630 回答