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

Question

我正在开发一个应用程序,用于解决涉及圆和直线(可构造数字)的二维欧几里德几何中的二次约束,并以图形方式表示结果.我发现这篇文章是在二叉树中表示这些问题,但我遇到了一个实现问题:

我需要比较a + b*sqrt(c)小于,大于和相等的标准关系操作的表单编号.的价值c为我的应用仅限于2,3,5,6,10,15,或30.例如(类似于C的伪代码,^是"对于运算符的幂"):

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)为浮点数时出现舍入错误的风险.我需要精确计算这个应用程序,不一定是无限精度,但我想避免舍入误差并确保正确的结果.

如何在a + b * sqrt(c)不需要巨大的中间整数值的情况下比较表单的可构造数字？我的初始值a和b在32位范围.

****更新****感谢大家的回复.继续追求连续分数的建议,我能够使用基本递推公式来生成平方根的任意精确近似.

我还发现这篇论文讨论了实数近似乘法与整数定点表示的误差累积.幸运的是,我感兴趣的所有平方根的整数部分最多为6(仅需要3位),因此我有很多位可用于表示近似的小数部分.为了乘以32位整数,我需要Q3.32位的最小定点近似值,以便在乘法后将误差保持为1位.

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

Answer 1

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

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

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