Изменение уравнения для расширения целочисленного переполнения

Определение проблемы

У меня есть двухмерный сценарий, представленный набором точек (x, y), где x и y — 64-битные целые числа. Оба значения x и y находятся в диапазоне [0, R] (минимально возможное значение x равно 0, а максимальное значение равно R. То же правило применяется для y).

В какой-то момент в моем коде я выполняю следующую операцию.

// Returns true if point P is inside circle defined by points A, B, C.
private bool InCircle(Long2 A, Long2 B, Long2 C, Long2 P)
{
    Long2 AP = P - A;
    Long2 BP = P - B;
    Long2 CP = P - C;
    return AP.SquareMagnitude * Long2.Det(BP, CP) + BP.SquareMagnitude * Long2.Det(CP, AP) + CP.SquareMagnitude * Long2.Det(AP, BP) > 0;
}

// Notes:
SquareMagnitude = x * x + y * y
Long2.Det(a, b) = a.x * b.y - a.y * b.x

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

  • A = (0, 0)
  • B = (R, 0)
  • C = (0, R)
  • P = (R, R)

Эти точки приводят к:

  • AP = (R, R)
  • BP = (0, R)
  • CP = (R, 0)

Если эти значения выполняются в методе, мы получаем:

  • AP.SquareMagnitude = R² + R²
  • Long2.Det(BP, CP) = R²
  • BP.SquareMagnitude = R²
  • Long2.Det(CP, AP) = R²
  • CP.SquareMagnitude = R²
  • Long2.Det(AP, BP) = R²

И в результате получается:

  • (2 * R² * R²) + (R² * R²) + (R² * R²) > 0

Что то же самое, что:

  • 4 * (R^4) > 0

Если мы не хотим, чтобы 64-битное целое число переполнялось, то:

  • 4 * (R^4) <= (2^63)

Таким образом, максимальное значение R равно 2^15 = 32768. (На самом деле это 2^15,25, но мы округлим до 2^15).

Вопрос

Есть ли способ увеличить максимальное значение R без переполнения с использованием 64-битных целых чисел? Что-то вроде разбиения уравнения на более мелкие значения и сравнения их по отдельности.

Мои мысли до сих пор

Я думал изменить уравнение на:

return AP.SquareMagnitude * Long2.Det(BP, CP) > -BP.SquareMagnitude * Long2.Det(CP, AP) - CP.SquareMagnitude * Long2.Det(AP, BP);

Что привело бы к:

  • 2 * R² * R² > -(R² * R²) - (R² * R²)
  • 2 * (R^4) <= 2^63
  • R ‹ = 2 ^ 15,5 (которое все еще округляется до 2 ^ 15. Недостаточно хорошо)

Кроме того, я не знаю, безопасно ли это делать. Это?

Предполагается использование целых чисел, и точность вывода является обязательной.

Я знаю об этой библиотеке:

https://www.cs.cmu.edu/~quake/robust.html< /а>

Но я хочу использовать целые числа, а не числа с плавающей запятой. Используемый здесь метод устойчив к ограничению переполнения целых чисел. Желательно только расширить это ограничение переполнения.


overflow integer long-integer integer-overflow biginteger
person MathiasDG    schedule 21.08.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Поэтому я подумал о том, чтобы запустить проверенную целочисленную арифметику и, если она переполняется, преобразовать 64-битные целые числа в десятичные числа.

// Returns true if point P is inside circle defined by points A, B, C.
private bool InCircle(Long2 A, Long2 B, Long2 C, Long2 P)
{
    Long2 AP = P - A;
    Long2 BP = P - B;
    Long2 CP = P - C;
    try 
    {
        long a = checked(AP.SquareMagnitude * Long2.Det(BP, CP));
        long b = checked(BP.SquareMagnitude * Long2.Det(CP, AP));
        long c = checked(CP.SquareMagnitude * Long2.Det(AP, BP));
        long lhs = checked(checked(a + b) + c);
        return lhs > 0;
    }
    catch (System.OverflowException)
    {
        decimal a1 = new decimal(AP.SquareMagnitude);
        decimal a2 = new decimal(Long2.Det(BP, CP));
        decimal b1 = new decimal(BP.SquareMagnitude);
        decimal b2 = new decimal(Long2.Det(CP, AP);
        decimal c1 = new decimal(CP.SquareMagnitude);
        decimal c2 = new decimal(Long2.Det(AP, BP);
        decimal lhs = a1 * a2 + b1 * b2 + c1 * c2;
        return lhs > 0;
    }
}

// Notes:
SquareMagnitude = x * x + y * y
Long2.Det(a, b) = a.x * b.y - a.y * b.x

Десятичные числа могут точно представлять целые числа ‹ 2^96, если я не ошибаюсь. Итак, чтобы избежать потери точности и переполнения:

  • 4 * (R^4) <= 2^96
  • R ‹ = 2 ^ 23 (на самом деле 2 ^ 23,5)

И чтобы избежать переполнения в операциях с целыми числами, (R² + R²) является самой большой операцией:

  • R² + R² <= 2^63
  • 2 * R² <= 2^63
  • R <= 2^31

При использовании этого метода максимальное значение R становится равным 2^23, и это здорово.

Еще одна мысль: будет ли код работать в среднем быстрее, если метод не будет пытаться выполнять проверенную целочисленную арифметику, а вместо этого будет преобразовывать значения в десятичные числа и выполнять математические вычисления с десятичными числами с самого начала?

Это сработает? Я сделал что-то не так?

person MathiasDG    schedule 21.08.2016