8

我正在开发一个应用程序，用于解决涉及圆和线（可构造数字）的二维欧几里得几何中的二次约束并以图形方式表示结果。我发现这篇关于在二叉树中表示此类问题的论文，但我遇到了一个实现问题：

我需要比较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 位精度才能最小化错误。c使用 64 位整数（比如 Q16.48）和 32 位整数中的定点表示b，我计划使用 96 位或 128 位数字的多字算术来进行比较，而不会产生足够的错误结果。我相信这对于比较仅使用这 7 个平方根的可构造数字来说足够准确，但我对第二意见感兴趣。有什么想法吗？

4

1 回答 1

3

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

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

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

于 2013-01-07T05:37:38.257 回答