Square root of a number... Accurate up to n precision [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

I could not understand the above method. Can someone please explain? I have done some code but its is limited to some hard coded precision and seems to consume too much resource of computer.

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

What is the Algorithm or C++ code for square root of a number upto n precision? n can be taken from user if required.

Answer 1

There are algorithms that are much better suited to computer evaluation. I learned the one in the question in the 1960's, as a way of manually calculating a square root digit-by-digit using a process rather like long division.

The objective, during calculation of the nth digit of the result, is to find the largest prefix string such that the square is less than or equal to the first 2n digits of the input.

The key underlying idea is that (a+b)^2 = a^2 + b^2 + 2ab. In the algorithm, a is the partial result so far, and b is the new digit. It accounts for factors of 100 in the square and 10 in the root by moving two places in the input for one generated digit in the result.

Let p be the partial result before appending digit d. We have already subtracted p^2 from the input. We need to also subtract d^2 + 2pd, to maintain subtraction of the square of the new partial result. Equivalently, subtract d(2p+d). We keep p already doubled, append d, and multiply by d. Before going on to the next step, we need to double d as well.

Answer 2

Here is a piece of C++ code, although it is not arbitrary precision, it may be useful to you. It is a little closer to a complete solution then your BASIC code:

#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;
}

As for help in understanding your algorithm, the best approach is to begin at the begging and work through each step. Try with small values like 4, 16 and 64. Go through the algorithm step by step with a piece of paper and a pencil and write down the parts for each step.

If your goal is only to calculate a number to N precision, then you would probably be better using an already made solution, change your problem so you don't need N precision or take a look at some of the other comments/answers.