Finding square root without using sqrt function

Question

I was finding out the algorithm for finding out the square root without using sqrt function and then tried to put into programming  I end up with this working code in C         include  lt iostream gt      using namespace std       double SqrtNumber double num                     double lower bound 0                double upper bound num               double temp 0                        ek edited this line                  int nCount   50           while nCount    0                           temp  lower bound upper bound  2                 if temp temp  num                                           return temp                                  else if temp temp  gt  num                                           upper bound   temp                                  else                                         lower bound   temp                           nCount--                 return temp               int main               double num       cout lt  lt  Enter the number n        cin gt  gt num        if num  lt  0              cout lt  lt  Error  Negative number         return 0               cout lt  lt  Square roots are     lt  lt sqrtnum num  and  lt  lt   and -  lt  lt sqrtnum num        return 0            Now the problem is initializing the number of iterations nCount in the declaratione   here it is 50   For example to find out square root of 36 it takes 22 iterations  so no problem whereas finding the square root of 15625 takes more than 50 iterations  So it would return the value of temp after 50 iterations  Please give a solution for this

User · Accepted Answer

There is a better algorithm  which needs at most 6 iterations to converge to maximum precision for double numbers    include  lt math h gt   double sqrt double x        if  x  lt   0          return 0           if negative number throw an exception      int exp   0      x   frexp x   amp exp      extract binary exponent from x     if  exp  amp  1            we want exponent to be even         exp--          x    2            double y    1 x  2     first approximation     double z   0      while  y    z          yes  we CAN compare doubles here          z   y          y    y   x y    2            return ldexp y  exp 2      multiply answer by 2  exp 2      Algorithm starts with 1 as first approximation for square root value  Then  on each step  it improves next approximation by taking average between current value y and x y  If y   sqrt x   it will be the same  If y   sqrt x   then x y  lt  sqrt x  by about the same amount  In other words  it will converge very fast   UPDATE  To speed up convergence on very large or very small numbers  changed sqrt   function to extract binary exponent and compute square root from number in  1  4  range  It now needs frexp   from  lt math h gt  to get binary exponent  but it is possible to get this exponent by extracting bits from IEEE-754 number format without using frexp

User · Answer

Here is a very simple but unsafe approach to find the square-root of a number  Unsafe because it only works by natural numbers  where you know that the base respectively the exponent are natural numbers  I had to use it for a task where i was neither allowed to use the  include lt cmath gt  -library  nor i was allowed to use pointers   potency   base   exponent     FUNCTION  square-root int sqrt int x        int quotient   0      int i   0       bool resultfound   false      while  resultfound    false            if  i i    x              quotient   i            resultfound   true                    i              return quotient

User · Answer

Why not try to use the Babylonian method for finding a square root   Here is my code for it   double sqrt double number        double error   0 00001    define the precision of your result     double s   number       while   s - number   s   gt  error    loop until precision satisfied                s    s   number   s    2            return s      Good luck

User · Answer

if you need to find square root without using sqrt   use root pow x 0 5    Where x is value whose square root you need to find

User · Answer

long division method   include lt iostream gt  using namespace std  int main     int n  i   1  divisor  dividend  j   1  digit  cin  gt  gt  n  while  i   i  lt  n        i   i   1    i   i - 1  cout  lt  lt  i  lt  lt        divisor    2   i  dividend   n -  i   i    while  j  lt   5        dividend   dividend   100      digit   0      while   divisor   10   digit    digit  lt  dividend            digit   digit   1            digit   digit  - 1      cout  lt  lt  digit      dividend   dividend -   divisor   10   digit    digit       divisor   divisor   10   2 digit      j   j   1    cout  lt  lt  endl  return 0

User · Answer

This a very simple recursive approach   double mySqrt double v  double test        if  abs test   test - v   lt  0 0001            return test             double highOrLow   v   test      return mySqrt v   test   highOrLow    2 0     double mySqrt double v        return mySqrt v  v 2 0

User · Answer

As I found this question is old and have many answers but I have an answer which is simple and working great     define EPSILON 0 0000001    least minimum value for comparison double SquareRoot double  val        double low   0       double high    val      double mid   0        while  high - low  gt  EPSILON                mid   low    high - low    2     finding mid value             if  mid mid  gt   val                    high   mid                else                   low   mid                                 return mid      I hope it will be helpful for future users

User · Answer

Remove your nCount altogether  as there are some roots that this algorithm will take many iterations for    double SqrtNumber double num        double lower bound 0       double upper bound num      double temp 0       while fabs num -  temp   temp    gt  SOME SMALL VALUE                   temp    lower bound upper bound  2             if  temp temp  gt   num                                  upper bound   temp                          else                                 lower bound   temp                         return temp

User · Answer

Here is a very awesome code to find sqrt and even faster than original sqrt function   float InvSqrt  float x         float xhalf   0 5f x      int i     int   amp x      i   0x5f375a86 -  i gt  gt 1       x     float   amp i      x   x  1 5f - xhalf x x       x   x  1 5f - xhalf x x       x   x  1 5f - xhalf x x       x 1 x      return x

User · Answer

After looking at the previous responses  I hope this will help resolve any ambiguities  In case the similarities in the previous solutions and my solution are illusive  or this method of solving for roots is unclear  I ve also made a graph which can be found here   This is a working root function capable of solving for any nth-root   default is square root for the sake of this question    include  lt cmath gt      for  pow  function  double sqrt double A  double root   2        const double e   2 71828182846      return pow e  pow 10 0 9 0  root   1 0- pow A -pow 10 0 -9 0           Explanation    click here for graph  This works via Taylor series  logarithmic properties  and a bit of algebra   Take  for example   log A   N    x    Note  for square-root  N   2  for any other root you only need to change the one variable  N   1  Change the base  convert the base  x  log function to natural log   log A     gt    ln A  ln x    N    x   2  Rearrange to isolate ln x   and eventually just  x    ln A  N   ln x    3  Set both sides as exponents of  e    e  ln A  N    e  ln x     gt    e ln x     x    gt   e  ln A  N    x   4  Taylor series represents  ln  as an infinite series   ln x     k 1 Sigma   1 k  -1  k 1   k-1  n              lt     expanded     gt     x-1   -   1 2  x-1  2      1 3  x-1  3  -   1 4  x-1  4             Note  Continue the series for increased accuracy  For brevity  10 9 is used in my function which expresses the series convergence for the natural log with about 7 digits  or the 10-millionths place  for precision    ln x    10 9 1-x  -10  -9      5  Now  just plug in this equation for natural log into the simplified equation obtained in step 3   e    10 9  N  1-A  -10 -9     nth-root of  A    6  This implementation might seem like overkill  however  its purpose is to demonstrate how you can solve for roots without having to guess and check  Also  it would enable you to replace the pow function from the cmath library with your own pow function   double power double base  double exponent        if  exponent    0  return 1      int wholeInt    int exponent      double decimal   exponent -  double wholeInt      if  decimal            int powerInv   1 decimal          if   wholeInt  return root base powerInv           else return power root base powerInv  wholeInt true             return power base  exponent  true      double power double base  int exponent  bool flag        if  exponent  lt  0  return 1 power base -exponent true       if  exponent  gt  0  return base   power base exponent-1 true       else return 1     int root int A  int root        return power E  1000000000000 root   1- power A -0 000000000001

[c++] Finding square root without using sqrt function?

Examples related to c++

Examples related to algorithm

Examples related to math

Examples related to sqrt