Предотвращение переполнения и сохранение точности при масштабировании (длинных) целых чисел

Я нашел ответ, который не является полным на 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;
}

Не полный, но может кому пригодится.

Я очень, очень опаздываю на эту вечеринку, но столкнулся с точно такой же проблемой.

Обратите внимание, что я использовал термины x для вашего pos, y для вашего oldRange и w для вашего newRange, то есть решая для z в уравнении 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) — использовать алгоритм например, этот, чтобы захватить старшие биты продукта.

Но я все еще чувствую, что должен быть более простой способ сделать это.

EDIT: Это решение неверно, см. обсуждение в комментариях.

У меня есть решение без особых случаев. У меня нет доказательства правильности, но это выглядит правдоподобно, и я не смог найти контрпример.

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