math - 如何比较 a + b*sqrt(c) 形式的数字而不会使中间整数越来越大？

Question

我正在开发一个应用程序，用于解决涉及圆和线 ( Constructable Numbers ) 的二维欧几里得几何中的二次约束并以图形方式表示结果。我找到了 this paper在二叉树中表示此类问题，但我遇到了一个实现问题:

我需要比较形式 a + b*sqrt(c) 的数字用于小于、大于和等于的标准关系运算。 c 的值我的申请仅限于 2 , 3 , 5 , 6 , 10 , 15 , 或 30 .例如(类似 C 的伪代码，^ 是“to the power of”运算符):

boolean CompareConstructibleNumbers(int a1, b1, c1, a2, b2, c2)
{
    return a1plusb1sqrtc1_is_greater_than_a2plusb2sqrtc2 = 
        4 * ((a1 - a2)^2) * (b1^2) * c1
          > ((b2^2) * c2 - (b1^2) * c1 - (a1 - a2)^2)^2;
        // Not sure if I have the direction right for >
}

这个简单的实现需要我多次相乘，所以 32 位整数变成 64 位整数，然后变成 128 位等等。我不想在我的实现中使用自定义 BigInteger 来存储仅用于的临时值比较。

我也不想使用浮点数，并希望避免在尝试直接计算 sqrt(c) 时出现舍入错误的风险。作为 float 。我需要为此应用程序进行精确计算，不一定是无限精度，但我想避免舍入误差并确保结果正确。

我如何去比较形式为 a + b * sqrt(c) 的可构造数字不需要巨大的中间整数值？我对 a 的初始值和 b都在 32 位范围内。

****更新****
感谢大家的回应。遵循追求连分数的建议，我能够使用 Fundamental Recurrence Formulas生成任意精确的平方根近似值。

我还找到了 this paper它讨论了通过整数与定点表示的实数近似值相乘的误差累积。幸运的是，我感兴趣的所有平方根的整数部分最多为 6(只需要 3 位)，因此我有很多位可用于表示近似值的小数部分。对于乘以 32 位整数，我需要一个最小定点近似值 Q3.32位以在乘法后将错误保持为 1 位。

所以虽然 53 位精度 double足以存储足够准确的平方根近似值，但在乘以 32 位整数后存储结果是不够的，因为这需要至少 67 位的精度以最小化误差。对 c 使用 64 位整数(比如 Q16.48)中的定点表示和一个 32 位整数 b ，我计划使用多字算法与 96 或 128 位数字进行比较，没有足够的错误来甩掉结果。我相信这对于比较仅使用这 7 个平方根的可构造数字来说足够准确，但我对第二意见很感兴趣。有什么想法吗？

Answer 1

我认为没有一个公式可以让您保持在 64 位以内进行精确比较，假设您的值使用完整的 32 位。我看到的问题是 a+b*sqrt(c) 形式的数字在实数中是密集的(假设 c 不是正方形)，所以你会得到非常微妙的比较，需要很多精度。因此，您基本上需要通过平方来消除平方根，这将使用 3 次乘法。

这种情况下的 BigInt 实现实际上并没有那么糟糕，因为您只需要实现乘法、加法、减法和比较。这些可以用很少的代码行有效地实现。通常情况下，实现起来很烦人的是除法。此外，您知道您的数字永远不会溢出具有两个 64 位单元的数组，因此您实际上不需要跟踪乘积中的位数。

编辑:关于 Thomas 和 Nemo 对此的评论建议使用 double 数，实际上很容易通过使用连分数表示在 sqrt(2) 的 2^{-53} 范围内找到使用 32 位整数的近似值。