gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-04 08:45:19 25 4
gpt4 key购买 nike

我正在开发一个应用程序,用于解决涉及圆和线 ( 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 个平方根的可构造数字来说足够准确,但我对第二意见很感兴趣。有什么想法吗?

最佳答案

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

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

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

关于math - 如何比较 a + b*sqrt(c) 形式的数字而不会使中间整数越来越大?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14189603/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com