c++ - 数字的平方根...精确到 n 精度

Question

我无法理解上述方法。有人可以解释一下吗？我已经做了一些代码，但它仅限于一些硬编码的精度，并且似乎消耗了太多的计算机资源。

R = 0.00001
INPUT N
WHILE R*R != N
        R = R + 0.00001
ENDWHILE
PRINT R

精度高达 n 的数字的平方根的算法或 C++ 代码是什么？如果需要，可以从用户处获取 n。

Answer 1

有些算法更适合计算机评估。我在 1960 年代学习了这个问题，作为一种使用类似于长除法的过程手动逐位计算平方根的方法。

在计算结果的第 n 位时，目标是找到最大的前缀字符串，使得平方小于或等于输入的前 2n 位。

关键的基本思想是(a+b)^2 = a^2 + b^2 + 2ab. 在算法中，a是目前为止的部分结果，b是新的数字。它通过将输入中的两个位置移动到结果中的一个生成数字来计算平方的 100 和根中的 10 的因数。

让p是 附加 digit 之前的部分结果d。我们已经p^2从输入中减去。我们还需要减去d^2 + 2pd，以保持新部分结果的平方的减法。等效地，减去d(2p+d)。我们保持p已经加倍、追加d和乘以d。在继续下一步之前，我们还需要加倍d。

Answer 2

这是一段 C++ 代码，虽然它不是任意精度，但它可能对您有用。它比你的 BASIC 代码更接近一个完整的解决方案：

#include <iostream>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <climits>

const unsigned g_unPlaces = 8;

int main(int argc, char** argv)
{
  if (argc != 2)
  {
    std::cerr << "USAGE: " << *argv << " NUMBER" << std::endl;
    return 1;
  }

  std::vector<unsigned> vecInteger;
  std::vector<unsigned> vecDecimal;
  char *pDecimal = strchr(argv[1], '.');

  // Read integer part of NUMBER
  if (pDecimal == NULL) pDecimal = argv[1] + strlen(argv[1]);
  if ((pDecimal - argv[1]) % 2) vecInteger.push_back(0);
  for (char *pCurrent = argv[1]; pCurrent < pDecimal; ++pCurrent)
  {
    int nValue = *pCurrent - '0';
    if (nValue >= 10 || nValue < 0)
    {
      std::cerr << "Error: Invalid character in input!" << std::endl;
      return 1;
    }
    vecInteger.push_back((unsigned) nValue);
  }

  // Read decimal part of NUMBER
  if (*pDecimal != '\0')
  {
    for (++pDecimal; *pDecimal != '\0'; ++pDecimal)
    {
      if (*pDecimal == '.')
      {
        std::cerr << "Error: Multiple decimals in input!" << std::endl;
        return 1;
      }

      int nValue = *pDecimal - '0';
      if (nValue >= 10 || nValue < 0)
      {
        std::cerr << "Error: Invalid character in input!" << std::endl;
        return 1;
      }
      vecDecimal.push_back((unsigned) nValue);
    }
    if (vecDecimal.size() % 2) vecDecimal.push_back(0);
  }

  const unsigned unInteger = vecInteger.size();
  const unsigned unDecimal = vecDecimal.size();

  std::vector<unsigned> vecValues;

  unsigned x, y = 0, c = 0, p = 0;
  for (unsigned i = 0; i < g_unPlaces; ++i)
  {
    if (2*i < unInteger-1)
    {
      c = (c*100 - y*100) + vecInteger[i*2]*10 + vecInteger[i*2+1];
    }
    else if (2*i < unInteger+unDecimal-1)
    {
      c = (c*100 - y*100) + vecDecimal[i*2-unInteger]*10
          + vecDecimal[i*2+1-unInteger];
    }
    else
    {
      c = c*100 - y*100;
    }

    if (c == 0) break;

    y = 0;
    for (x = 1; x < 10; ++x)
    {
      unsigned temp = x*(20*p + x);
      if (temp > c) { --x; break; }
      y = temp;
    }

    p = 10*p + x;
    vecValues.push_back(x);
  }

  // Write the result
  for (unsigned i = 0; i < unInteger/2; ++i)
  {
    std::cout << vecValues[i];
  }
  std::cout << '.';
  for (unsigned i = unInteger/2; i < vecValues.size(); ++i)
  {
    std::cout << vecValues[i];
  }
  std::cout << std::endl;

  return 0;
}

至于帮助理解你的算法，最好的方法是从乞讨开始，逐步完成每一步。尝试使用较小的值，例如 4、16 和 64。用一张纸和一支铅笔逐步完成算法，并写下每个步骤的部分。

如果您的目标只是计算 N 精度的数字，那么您可能会更好地使用已经制定的解决方案，更改您的问题，以便您不需要 N 精度或查看其他一些评论/答案。