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

User · Answer

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  gt  0 00001   double square root of double value         assert value  gt   1        double lo   1 0       double hi   value        while  hi - lo  gt  0 00001                   double mid   lo    hi - lo    2             std  cout  lt  lt  lo  lt  lt       lt  lt  hi  lt  lt       lt  lt  mid  lt  lt  std  endl            if  mid   mid - value  gt  0 00001       this is the predictors we are using                            hi   mid              else                 lo   mid                           return lo

User · Answer

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

User · Answer

Depending on your needs  a simple divide-and-conquer strategy can be used  It won t converge as fast as some other methods but it may be a lot easier for a novice to understand  In addition  since it s an O log n  algorithm  halving the search space each iteration   the worst case for a 32-bit float will be 32 iterations   Let s say you want the square root of 62 104  You pick a value halfway between 0 and that  and square it  If the square is higher than your number  you need to concentrate on numbers less than the midpoint  If it s too low  concentrate on those higher   With real math  you could keep dividing the search space in two forever  if it doesn t have a rational square root   In reality  computers will eventually run out of precision and you ll have your approximation  The following C program illustrates the point    include  lt stdio h gt   include  lt stdlib h gt   int main  int argc  char  argv          float val  low  high  mid  oldmid  midsqr      int step   0          Get argument  force to non-negative       if  argc  lt  2            printf   Usage  sqrt  lt number gt  n            return 1            val   fabs  atof  argv 1             Set initial bounds and print heading       low   0      high   mid   val      oldmid   -1       printf    4s   10s   10s   10s   10s   10s     s n            Step    Number    Low    High    Mid    Square    Result            Keep going until accurate enough       while  fabs oldmid - mid   gt   0 00001            oldmid   mid              Get midpoint and see if we need lower or higher           mid    high   low    2          midsqr   mid   mid          printf    4d   10 4f   10 4f   10 4f   10 4f   10 4f                   step  val  low  high  mid  midsqr           if  mid   mid  gt  val                high   mid              printf   - too high n              else               low   mid              printf   - too low n                            Desired accuracy reached  print it       printf   sqrt   4f      4f n   val  mid       return 0      Here s a couple of runs so you hopefully get an idea how it works  For 77   pax gt  sqrt 77 Step      Number         Low        High         Mid      Square    Result    1     77 0000      0 0000     77 0000     38 5000   1482 2500  - too high    2     77 0000      0 0000     38 5000     19 2500    370 5625  - too high    3     77 0000      0 0000     19 2500      9 6250     92 6406  - too high    4     77 0000      0 0000      9 6250      4 8125     23 1602  - too low    5     77 0000      4 8125      9 6250      7 2188     52 1104  - too low    6     77 0000      7 2188      9 6250      8 4219     70 9280  - too low    7     77 0000      8 4219      9 6250      9 0234     81 4224  - too high    8     77 0000      8 4219      9 0234      8 7227     76 0847  - too low    9     77 0000      8 7227      9 0234      8 8730     78 7310  - too high   10     77 0000      8 7227      8 8730      8 7979     77 4022  - too high   11     77 0000      8 7227      8 7979      8 7603     76 7421  - too low   12     77 0000      8 7603      8 7979      8 7791     77 0718  - too high   13     77 0000      8 7603      8 7791      8 7697     76 9068  - too low   14     77 0000      8 7697      8 7791      8 7744     76 9893  - too low   15     77 0000      8 7744      8 7791      8 7767     77 0305  - too high   16     77 0000      8 7744      8 7767      8 7755     77 0099  - too high   17     77 0000      8 7744      8 7755      8 7749     76 9996  - too low   18     77 0000      8 7749      8 7755      8 7752     77 0047  - too high   19     77 0000      8 7749      8 7752      8 7751     77 0022  - too high   20     77 0000      8 7749      8 7751      8 7750     77 0009  - too high   21     77 0000      8 7749      8 7750      8 7750     77 0002  - too high   22     77 0000      8 7749      8 7750      8 7750     76 9999  - too low   23     77 0000      8 7750      8 7750      8 7750     77 0000  - too low sqrt 77 0000    8 7750   For 62 104   pax gt  sqrt 62 104 Step      Number         Low        High         Mid      Square    Result    1     62 1040      0 0000     62 1040     31 0520    964 2267  - too high    2     62 1040      0 0000     31 0520     15 5260    241 0567  - too high    3     62 1040      0 0000     15 5260      7 7630     60 2642  - too low    4     62 1040      7 7630     15 5260     11 6445    135 5944  - too high    5     62 1040      7 7630     11 6445      9 7037     94 1628  - too high    6     62 1040      7 7630      9 7037      8 7334     76 2718  - too high    7     62 1040      7 7630      8 7334      8 2482     68 0326  - too high    8     62 1040      7 7630      8 2482      8 0056     64 0895  - too high    9     62 1040      7 7630      8 0056      7 8843     62 1621  - too high   10     62 1040      7 7630      7 8843      7 8236     61 2095  - too low   11     62 1040      7 8236      7 8843      7 8540     61 6849  - too low   12     62 1040      7 8540      7 8843      7 8691     61 9233  - too low   13     62 1040      7 8691      7 8843      7 8767     62 0426  - too low   14     62 1040      7 8767      7 8843      7 8805     62 1024  - too low   15     62 1040      7 8805      7 8843      7 8824     62 1323  - too high   16     62 1040      7 8805      7 8824      7 8815     62 1173  - too high   17     62 1040      7 8805      7 8815      7 8810     62 1098  - too high   18     62 1040      7 8805      7 8810      7 8807     62 1061  - too high   19     62 1040      7 8805      7 8807      7 8806     62 1042  - too high   20     62 1040      7 8805      7 8806      7 8806     62 1033  - too low   21     62 1040      7 8806      7 8806      7 8806     62 1038  - too low   22     62 1040      7 8806      7 8806      7 8806     62 1040  - too high   23     62 1040      7 8806      7 8806      7 8806     62 1039  - too high sqrt 62 1040    7 8806   For 49   pax gt  sqrt 49 Step      Number         Low        High         Mid      Square    Result    1     49 0000      0 0000     49 0000     24 5000    600 2500  - too high    2     49 0000      0 0000     24 5000     12 2500    150 0625  - too high    3     49 0000      0 0000     12 2500      6 1250     37 5156  - too low    4     49 0000      6 1250     12 2500      9 1875     84 4102  - too high    5     49 0000      6 1250      9 1875      7 6562     58 6182  - too high    6     49 0000      6 1250      7 6562      6 8906     47 4807  - too low    7     49 0000      6 8906      7 6562      7 2734     52 9029  - too high    8     49 0000      6 8906      7 2734      7 0820     50 1552  - too high    9     49 0000      6 8906      7 0820      6 9863     48 8088  - too low   10     49 0000      6 9863      7 0820      7 0342     49 4797  - too high   11     49 0000      6 9863      7 0342      7 0103     49 1437  - too high   12     49 0000      6 9863      7 0103      6 9983     48 9761  - too low   13     49 0000      6 9983      7 0103      7 0043     49 0598  - too high   14     49 0000      6 9983      7 0043      7 0013     49 0179  - too high   15     49 0000      6 9983      7 0013      6 9998     48 9970  - too low   16     49 0000      6 9998      7 0013      7 0005     49 0075  - too high   17     49 0000      6 9998      7 0005      7 0002     49 0022  - too high   18     49 0000      6 9998      7 0002      7 0000     48 9996  - too low   19     49 0000      7 0000      7 0002      7 0001     49 0009  - too high   20     49 0000      7 0000      7 0001      7 0000     49 0003  - too high   21     49 0000      7 0000      7 0000      7 0000     49 0000  - too low   22     49 0000      7 0000      7 0000      7 0000     49 0001  - too high   23     49 0000      7 0000      7 0000      7 0000     49 0000  - too high sqrt 49 0000    7 0000

User · Answer

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  lt  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

User · Answer

A simple  but not very fast  method to calculate the square root of X   squareroot x      if x lt 0 then Error     a   1     b   x     while  abs a-b  gt ErrorMargin           a    a b  2         b   x a     endwhile     return a    Example  squareroot 70000       a       b     1   70000 35001       2 17502       4  8753       8  4381      16  2199      32  1116      63   590     119   355     197   276     254   265     264   As you can see it defines an upper and a lower boundary for the square root and narrows the boundary until its size is acceptable   There are more efficient methods but this one illustrates the process and is easy to understand   Just beware to set the Errormargin to 1 if using integers else you have an endless loop

User · Answer

The inverse  as the name says  but sometimes  close enough  is  close enough   an interesting read anyway   Origin of Quake3 s Fast InvSqrt

User · Answer

use binary search  public class FindSqrt        public static void main String   strings             int num   10000          System out println sqrt num  0  num               private static int sqrt int num  int min  int max            int middle    min   max    2          int x   middle   middle          if  x    num                return middle            else if  x  lt  num                return sqrt num  middle  max             else               return sqrt num  min  middle

User · Answer

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  lt   precision      if diff  gt  0       upper   middle     else diff  lt  0       lower   middle     end      middle    upper   lower  2 0   end  end  puts sqroot precision 232 3  0 0000000001

User · Answer

Let s say we are trying to find the square root of 2  and you have an estimate of 1 5   We ll say a   2  and x   1 5  To compute a better estimate  we ll divide a by x  This gives a new value y   1 333333   However  we can t just take this as our next estimate  why not    We need to average it with the previous estimate  So our next estimate  xx will be  x   y    2  or 1 416666   Double squareRoot Double a  Double epsilon        Double x   0d      Double y   a      Double xx   0d          Make sure both x and y    0      while   x    0d    y    0d   amp  amp  y - x  gt  epsilon            xx    x   y    2           if  xx   xx  gt   a                y   xx            else               x   xx                       return xx      Epsilon determines how accurate the approximation needs to be  The function should return the first approximation x it obtains that satisfies abs x x - a   lt  epsilon  where abs x  is the absolute value of x   square root 2  1e-6  Output  1 4142141342163086

User · Answer

To calculate the square root of a number by help of inbuilt function     include iostream h    include conio h    include math h  void main     clrscr    float x  cout lt  lt  Enter the Number   cin gt  gt x    float squreroot float      float z squareroot x    cout lt  lt z    float squareroot int x           float s   s   pow x  5     return s

User · Answer

Here s a way of obtaining a square root using trigonometry   It s not the fastest algorithm by a longshot  but it is precise   Code is in javascript   var n   5    number to get the square root of var icr     n 1  2     intersecting circle radius var sqrt   Math cos Math asin  icr-1  icr   icr    square root of n alert sqrt

User · Answer

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  lt  0  return -1      if x    0    x    1  return x       int lowerbound   1      int upperbound   x      int root   lowerbound    upperbound - lowerbound  2       while root  gt  x root    root 1  lt   x  root 1            if root  gt  x root               upperbound   root            else               lowerbound   root                    root   lowerbound    upperbound - lowerbound  2            return root      You can test my code here  leetcode  sqrt x

User · Answer

Found a great article about Integer Square Roots   This is a slightly improved version that it presents there   unsigned long sqrt unsigned long a       int i      unsigned long rem   0      unsigned long root   0      for  i   0  i  lt  16  i             root  lt  lt   1          rem    rem  lt  lt  2     a  gt  gt  30           a  lt  lt   2          if root  lt  rem               root                rem -  root              root                        return root  gt  gt  1

User · Answer

Calculate square root with arbitrary precision in Python    usr bin env python import decimal  def sqrt n       assert n  gt  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

User · Answer

Well there are already quite a few answers  but here goes mine It s the most simplest piece of code   for me    here is the algorithm for it    And code in python 2 7   from   future   import division  val   81 x   10 def sqr data x       temp   x -    x  2 - data   2 x       if temp    x          print temp         return     else          x   temp         return sqr data x       x  temp       sqr data x  sqr val x

User · Answer

Of course it s approximate  that is how math with floating-point numbers work   Anyway  the standard way is with Newton s method   This is about the same as using Taylor s series  the other way that comes to mind immediately

User · Answer

Let me point out an extremely interesting method of calculating an inverse square root 1 sqrt x  which is a legend in the world of game design because it is mind-boggingly fast  Or wait  read the following post   http   betterexplained com articles understanding-quakes-fast-inverse-square-root   PS  I know you just want the square root but the elegance of quake overcame all resistance on my part     By the way  the above mentioned article also talks about the boring Newton-Raphson approximation somewhere

User · Answer

Fastest way I found  an  extreme  C  unrolled version of     http   www hackersdelight org hdcodetxt isqrt c txt          isqrt4      It s quite a lot of code  basically a binary search  the  if  statements     followed by an unrolled loop  the labels      Most important  it s fast  twice as fast as  Math Sqrt      On my pc  Math Sqrt  35 ns  sqrt  lt 16 ns  mean  lt 14 ns   private static uint sqrt uint x        uint y  z      if  x  lt  1u  lt  lt  16                if  x  lt  1u  lt  lt  08                        if  x  lt  1u  lt  lt  04  return x  lt  1u  lt  lt  02   x   3u  gt  gt  2   x   15u  gt  gt  3              else                               if  x  lt  1u  lt  lt  06                    y   1u  lt  lt  03  x -  1u  lt  lt  04  if  x  gt   5u  lt  lt  02    x -  5u  lt  lt  02  y    1u  lt  lt  02    goto L0                    else                   y   1u  lt  lt  05  x -  1u  lt  lt  06  if  x  gt   5u  lt  lt  04    x -  5u  lt  lt  04  y    1u  lt  lt  04    goto L1                                    else                                                slower  on my pc        y   3u  lt  lt  04    goto L1                          if  x  lt  1u  lt  lt  12                                if  x  lt  1u  lt  lt  10                    y   1u  lt  lt  07  x -  1u  lt  lt  08  if  x  gt   5u  lt  lt  06    x -  5u  lt  lt  06  y    1u  lt  lt  06    goto L2                    else                   y   1u  lt  lt  09  x -  1u  lt  lt  10  if  x  gt   5u  lt  lt  08    x -  5u  lt  lt  08  y    1u  lt  lt  08    goto L3                              else                               if  x  lt  1u  lt  lt  14                    y   1u  lt  lt  11  x -  1u  lt  lt  12  if  x  gt   5u  lt  lt  10    x -  5u  lt  lt  10  y    1u  lt  lt  10    goto L4                    else                   y   1u  lt  lt  13  x -  1u  lt  lt  14  if  x  gt   5u  lt  lt  12    x -  5u  lt  lt  12  y    1u  lt  lt  12    goto L5                                      else               if  x  lt  1u  lt  lt  24                        if  x  lt  1u  lt  lt  20                                if  x  lt  1u  lt  lt  18                    y   1u  lt  lt  15  x -  1u  lt  lt  16  if  x  gt   5u  lt  lt  14    x -  5u  lt  lt  14  y    1u  lt  lt  14    goto L6                    else                   y   1u  lt  lt  17  x -  1u  lt  lt  18  if  x  gt   5u  lt  lt  16    x -  5u  lt  lt  16  y    1u  lt  lt  16    goto L7                              else                               if  x  lt  1u  lt  lt  22                    y   1u  lt  lt  19  x -  1u  lt  lt  20  if  x  gt   5u  lt  lt  18    x -  5u  lt  lt  18  y    1u  lt  lt  18    goto L8                    else                   y   1u  lt  lt  21  x -  1u  lt  lt  22  if  x  gt   5u  lt  lt  20    x -  5u  lt  lt  20  y    1u  lt  lt  20    goto L9                                    else                       if  x  lt  1u  lt  lt  28                                if  x  lt  1u  lt  lt  26                    y   1u  lt  lt  23  x -  1u  lt  lt  24  if  x  gt   5u  lt  lt  22    x -  5u  lt  lt  22  y    1u  lt  lt  22    goto La                    else                   y   1u  lt  lt  25  x -  1u  lt  lt  26  if  x  gt   5u  lt  lt  24    x -  5u  lt  lt  24  y    1u  lt  lt  24    goto Lb                              else                               if  x  lt  1u  lt  lt  30                    y   1u  lt  lt  27  x -  1u  lt  lt  28  if  x  gt   5u  lt  lt  26    x -  5u  lt  lt  26  y    1u  lt  lt  26    goto Lc                    else                   y   1u  lt  lt  29  x -  1u  lt  lt  30  if  x  gt   5u  lt  lt  28    x -  5u  lt  lt  28  y    1u  lt  lt  28                                        z   y   1u  lt  lt  26  y    2  if  x  gt   z    x -  z  y    1u  lt  lt  26    Lc  z   y   1u  lt  lt  24  y    2  if  x  gt   z    x -  z  y    1u  lt  lt  24    Lb  z   y   1u  lt  lt  22  y    2  if  x  gt   z    x -  z  y    1u  lt  lt  22    La  z   y   1u  lt  lt  20  y    2  if  x  gt   z    x -  z  y    1u  lt  lt  20    L9  z   y   1u  lt  lt  18  y    2  if  x  gt   z    x -  z  y    1u  lt  lt  18    L8  z   y   1u  lt  lt  16  y    2  if  x  gt   z    x -  z  y    1u  lt  lt  16    L7  z   y   1u  lt  lt  14  y    2  if  x  gt   z    x -  z  y    1u  lt  lt  14    L6  z   y   1u  lt  lt  12  y    2  if  x  gt   z    x -  z  y    1u  lt  lt  12    L5  z   y   1u  lt  lt  10  y    2  if  x  gt   z    x -  z  y    1u  lt  lt  10    L4  z   y   1u  lt  lt  08  y    2  if  x  gt   z    x -  z  y    1u  lt  lt  08    L3  z   y   1u  lt  lt  06  y    2  if  x  gt   z    x -  z  y    1u  lt  lt  06    L2  z   y   1u  lt  lt  04  y    2  if  x  gt   z    x -  z  y    1u  lt  lt  04    L1  z   y   1u  lt  lt  02  y    2  if  x  gt   z    x -  z  y    1u  lt  lt  02    L0  return x  gt  y   y   2   1u   y   2

User · Answer

The following computes floor sqrt N   for N   0   x   2 ceil numbits N  2  loop      y   floor  x   floor N x   2      if y  gt   x         return x     x   y   This is a version of Newton s method given in Crandall  amp  Pomerance   Prime Numbers  A Computational Perspective   The reason you should use this version is that people who know what they re doing have proven that it converges exactly to the floor of the square root  and it s simple so the probability of making an implementation error is small  It s also fast  although it s possible to construct an even faster algorithm -- but doing that correctly is much more complex   A properly implemented binary search can be faster for very small N  but there you may as well use a lookup table   To round to the nearest integer  just compute t   floor sqrt 4N   using the algorithm above  If the least significant bit of t is set  then choose x    t 1  2  otherwise choose t 2  Note that this rounds up on a tie  you could also round down  or round to even  by looking at whether the remainder is nonzero  i e  whether t 2    4N    Note that you don t need to use floating-point arithmetic  In fact  you shouldn t  This algorithm should be implemented entirely using integers  in particular  the floor   functions just indicate that regular integer division should be used

[algorithm] Writing your own square root function

Examples related to algorithm

Examples related to function

Examples related to math

Examples related to square-root

Examples related to newtons-method