2

这是我过去的任意精度有理数 C++ 分配中的一个未解决的问题。

为了计算，我使用了 Wikipedia 中的这个表达式（a是初始猜测，r是余数）：

平方根的连分数

我最终通过实验猜测，采用了这种方法：

  1. 在分子/分母上使用整数平方根函数，将其用作猜测
  2. 迭代连分数直到分母的二进制长度至少是目标精度

这足以让我通过官方测试，但是，从我的测试来看，精度太高（有时几乎翻倍）——即代码效率低下——而且我没有证据证明它在任何输入上都有效（因此没有信心在代码中）。

代码的简化摘录（natural/rational存储任意长度的数字，假设所有操作都以最简单的形式返回分数）：

rational sqrt(rational input, int precision) {
  rational guess(isqrt(input.numerator), isqrt(input.denominator));  // a
  rational remainder = input - power(guess, 2);                      // r
  rational result = guess;

  rational expansion;
  while (result.denominator.size() <= precision) {
    expansion = remainder / (2 * guess + expansion);
    result = guess + expansion;

    // Handle rational results
    if (power(root, 2) == input) {
      break;
    }
  }
  return result;
}

可以做得更好吗？如果是这样，怎么做？

4

1 回答 1

1

平方根可以通过一般连分数 (GCF) 轻松且非常准确地计算。一般意味着它可以有任何正数作为分子，而在常规或简单连分数 (RCF) 中，分子都是 1。为了从整体上理解答案，最好从头开始。

n用于通过 GFC ( a + x)求解任何正数的平方根的方法a是积分和连x小数部分，是：

                                                              n − a^2
√n = a + x ⇒ n = a^2 + 2ax + x^2 ⇒ n − a^2 = x(2a + x) ⇒ x = _______
                                                              2a + x

此刻你有一个 GCF，因为它x很好地放在了分母上，一旦你x用它的定义替换，你就会得到一个无限扩展的x. 关于a，您可以在小于 的整数中自由选择√n。因此，如果您想找到√11thena可以在 1、2 或 3 中进行选择。但是最好选择最大的一个，以便能够在下一阶段将 GCF 简化为 RCF。

请记住x = (n − a^2) / (2a + x)和n = 11。a = 3现在，如果我们写出前两项，那么我们可以将 GCF 简化为 RCF，所有分子都为 1。

      2         2        divide both            1
x = _____ ⇒ _________ ⇒ numerator and    ⇒ _________ = x
    6 + x   6 +   2      denominator by 2   3 +   1
                _____                           _____
                6 + x                           6 + x

因此，我们对 √11 的 RCF 是；

                        1            ___
√11 = 3 + x ⇒ 3 + _____________ = [3;3,6]
                          1
                  3 + _________
                            1
                      6 + _____
                              1
                          3 + _....
                              6

[3; 3, 6, 3, 6, ...]请注意在这种特殊情况下类似于无限数组的系数符号。这就是 RCF 用系数表示法表示的方式，第一项是 ，a后面;是 的 RCF 系数x。这两个就足够了，因为我们已经知道在 RCF 中所有分子都固定为 1。

回到你的精确度问题。你现在有√11 = 3 + x你x的 RCF 作为[3;3,6,3,6,3,6...]. 通常，您可以尝试选择深度并从右侧减少，就像[3,3,6,3,6,3,6...].reduceRight((p,c) => c + 1/p)在 JS 中所做的那样。不够精确的结果。？然后从另一个深度再试一次。这实际上是在链接的维基百科主题中描述为自下而上的方式。然而，通过一个接一个地计算中间收敛，从左到右（从上到下）会非常有效。每个下一个中间收敛都会为您测试和决定天气停止或继续提供更好的精度。当你达到足够的系数时，就停在那里。话虽如此，一旦达到所需的系数，您可能仍然通过增加或减少该系数来进行一些微调。减少偶数索引处的系数或增加奇数索引处的系数会降低收敛性，反之亦然。

因此，为了能够进行从左到右（从上到下）的分析，有一个特殊规则：

n2/d2 = (xn * n1 + n0)/(xn * d1 + d0)
  1. 我们需要知道最后两个临时收敛点 (n0/d0和n1/d1) 以及当前系数xn，以便能够计算下一个收敛点 ( n2/d2)。
  2. 我们将从两个初始收敛Infinity（n0/d0= 1/0）和a我们上面选择的（记住√n = a + x）开始，它是 3 所以（n1/d1= 3/1）。知道分号之前的 3 实际上是a，我们的第一个xn是系数数组中分号之后的 3 [3;»» 3 ««,6,3,6,3,6...]。
  3. 在我们计算n2/d2并进行测试之后，如果需要，下一步我们将把我们的收敛器向左移动，以便我们准备好最后两个来计算下一个收敛器。n0/d0 <- n1/d1 <- n2/d2

在这里，我展示了n2/d2 = (xn * n1 + n0)/(xn * d1 + d0)规则表。

n0/d0  n1/d1   xn  index   n2/d2    decimal val.
_____  ______  __  _____  ________  ____________
 1/0     3/1    3  1 odd    10/3    3.33333333..
 3/1    10/3    6  2 evn    63/19   3.31578947..
10/3    63/19   3  3 odd   199/60   3.31666666..
63/19  199/60   6  4 evn  1257/379  3.31662269..
  .       .     .    .        .           .
  .       .     .    .        .           .

因此，您可能会注意到，我们很快就接近了√11注意3.31662479...，由于级联倒数，奇数指数过冲和偶数下冲。由于√11是非理性的，这将继续无限期地收敛，直到我们说够了。

请记住，如前所述，一旦达到所需的系数，您仍然可以通过增加或减少该系数 (xn) 来进行微调。减少偶数索引处的系数或增加奇数索引处的系数会降低收敛性，反之亦然。

这里的问题是，并不是所有的都√n可以通过如上所示的简单除法简单地变成 RCF。有关从任何生成 RCF 的更通用的方法，√n您可以查看我的更新的答案。

于 2022-02-22T17:33:42.737 回答