Writing your own square root function

Question

How do you write your own function for finding the most accurate square root of an integer?

After googling it, I found this (archived from its original link), but first, I didn't get it completely, and second, it is approximate too.

Assume square root as nearest integer (to the actual root) or a float.

Answer 1

In general the square root of an integer (like 2, for example) can only be approximated (not because of problems with floating point arithmetic, but because they're irrational numbers which can't be calculated exactly).

Of course, some approximations are better than others. I mean, of course, that the value 1.732 is a better approximation to the square root of 3, than 1.7

The method used by the code at that link you gave works by taking a first approximation and using it to calculate a better approximation.

This is called Newton's Method, and you can repeat the calculation with each new approximation until it's accurate enough for you.

In fact there must be some way to decide when to stop the repetition or it will run forever.

Usually you would stop when the difference between approximations is less than a value you decide.

EDIT: I don't think there can be a simpler implementation than the two you already found.

Answer 2

A simple solution that can deal with float square root and arbitrary precision using binary search

coded in ruby

include Math

def sqroot_precision num, precision
  upper   = num
  lower   = 0
  middle  = (upper + lower)/2.0

  while true do
    diff = middle**2 - num

    return middle if diff.abs <= precision

    if diff > 0
      upper = middle
    else diff < 0
      lower = middle
    end

    middle = (upper + lower)/2.0
  end 
end

puts sqroot_precision 232.3, 0.0000000001

Answer 3

Calculate square root with arbitrary precision in Python

#!/usr/bin/env python
import decimal

def sqrt(n):
    assert n > 0
    with decimal.localcontext() as ctx:
        ctx.prec += 2 # increase precision to minimize round off error
        x, prior = decimal.Decimal(n), None
        while x != prior: 
            prior = x
            x = (x + n/x) / 2 # quadratic convergence 
    return +x # round in a global context


decimal.getcontext().prec = 80 # desirable precision
r = sqrt(12345)
print r
print r == decimal.Decimal(12345).sqrt()

Output:

111.10805551354051124500443874307524148991137745969772997648567316178259031751676
True

Answer 4

The first thing comes to my mind is: this is a good place to use Binary search (inspired by this great tutorials.)

To find the square root of vaule ,we are searching the number in (1..value) where the predictor is true for the first time. The predictor we are choosing is number * number - value > 0.00001.

double square_root_of(double value)
{
     assert(value >= 1);
     double lo = 1.0;
     double hi = value;

     while( hi - lo > 0.00001)
     {
          double mid = lo + (hi - lo) / 2 ;
          std::cout << lo << "," << hi << "," << mid << std::endl;
          if( mid * mid - value > 0.00001)    //this is the predictors we are using 
          {
              hi = mid;
          } else {
              lo = mid;
          }

     }

    return lo;
 }

Answer 5

It's a common interview question asked by Facebook etc. I don't think it's a good idea to use the Newton's method in an interview. What if the interviewer ask you the mechanism of the Newton's method when you don't really understand it?

I provided a binary search based solution in Java which I believe everyone can understand.

public int sqrt(int x) {

    if(x < 0) return -1;
    if(x == 0 || x == 1) return x;

    int lowerbound = 1;
    int upperbound = x;
    int root = lowerbound + (upperbound - lowerbound)/2;

    while(root > x/root || root+1 <= x/(root+1)){
        if(root > x/root){
            upperbound = root;
        } else {
            lowerbound = root;
        }
        root = lowerbound + (upperbound - lowerbound)/2;
    }
    return root;
}

You can test my code here: leetcode: sqrt(x)

Answer 6

There is an algorithm that I studied in school that you can use to compute exact square roots (or of arbitrarily large precision if the root is an irrational number). It is definitely slower than Newton's algorithms but it is exact. Lets say you want to compute the square root of 531.3025

First thing is you divide your number starting from the decimal point into groups of 2 digits:
{5}{31}.{30}{25}
Then:
1) Find the closest square root for first group that is smaller or equal to the actual square root of first group: sqrt({5}) >= 2. This square root is the first digit of your final answer. Lets denote the digits we have already found of our final square root as B. So at the moment B = 2.
2) Next compute the difference between {5} and B^2: 5 - 4 = 1.
3) For all subsequent 2 digit groups do the following:
Multiply the remainder by 100, then add it to the second group: 100 + 31 = 131.
Find X - next digit of your root, such that 131 >=((B*20) + X)*X. X = 3. 43 * 3 = 129 < 131. Now B = 23. Also because you have no more 2-digit groups to the left of decimal points, you have found all integer digits of your final root.
4)Repeat the same for {30} and {25}. So you have:
{30} : 131 - 129 = 2. 2 * 100 + 30 = 230 >= (23*2*10 + X) * X -> X = 0 -> B = 23.0
{25} : 230 - 0 = 230. 230 * 100 + 25 = 23025. 23025 >= (230 * 2 * 10 + X) * X -> X = 5 -> B = 23.05
Final result = 23.05.
The algorithm looks complicated this way but it is much simpler if you do it on paper using the same notation you use for "long division" you have studied in school, except that you don't do division but instead compute the square root.