Square Root

   Square root (sometimes shortened to sqrt) of [1]number a is such a number
   b that b^2 = a, for example 3 is a square root of 9 because 3^2 = 9.
   Finding square root is one of the most basic and important operations in
   [2]math and [3]programming, e.g. for computing [4]distances, solving
   [5]quadratic equations etc. Square root is a special case of finding Nth
   [6]root of a number for N = 2. Square root of a number doesn't have to be
   a whole number; in fact if the square isn't a whole number, it is always
   an [7]irrational number (i.e. it can't be expressed as a fraction of two
   integers, for example square root of [8]two is approximately 1.414...);
   and it doesn't even have to be a [9]real number (e.g. square root of -1 is
   [10]i). Strictly speaking there may exist multiple square roots of a
   number, for example both 5 and -5 are square roots of 25 -- the positive
   square root is called principal square root; principal square root of x is
   the same number we get when we raise x to 1/2, and this is what we are
   usually interested in -- from now on by square root we will implicitly
   mean principal square root. Programmers write square root of x as sqrt(x)
   (which should give the same result as raising to 1/2, i.e. pow(x,0.5)),
   mathematicians write it as:

   _    1/2
 \/x = x

   Here is the graph of square root [11]function (notice it's a [12]parabola
   flipped by the diagonal axis, for square root is an inverse function to
   the function x^2):

       ^ sqrt(x)
       |       :       :       :       :       :
     3 + ~ ~ ~ + ~ ~ ~ + ~ ~ ~ + ~ ~ ~ + ~ ~ ~ + ~
       |       :       :       :       :       :
       |       :       :       :       :       ___....--
     2 + ~ ~ ~ + ~ ~ ~ + ~ ~ ~ + ~ __..---'"""": ~
       |       :       : __..--""""    :       :
       |       :  __.--'"      :       :       :
     1 + ~ ~ _--'" ~ ~ + ~ ~ ~ + ~ ~ ~ + ~ ~ ~ + ~
       |  _-"  :       :       :       :       :
       | /     :       :       :       :       :
   ----+"------|-------|-------|-------|-------|----> x
       |0      1       2       3       4       5
       |

   TODO

Programming

   TODO

   If we need extreme speed, we may use a [13]look up table with precomputed
   values.

   Within desired precision square root can be relatively quickly computed
   iteratively by [14]binary search. Here is a simple [15]C function
   computing integer square root this way:

 unsigned int sqrt(unsigned int x)
 {
   unsigned int l = 0, r = x / 2, m;
  
   while (1)
   {
     if (r - l <= 1)
       break;

     m = (l + r) / 2;
    
     if (m * m > x)
       r = m;
     else
       l = m;
   }

   return (r * r <= x ? r : l) + (x == 1);
 }

   TODO: Heron's method

   The following is a non-iterative [16]approximation of integer square root
   in [17]C that has acceptable accuracy to about 1 million (maximum error
   from 1000 to 1000000 is about 7%): { Painstakingly made by me. ~drummyfish
   }

 int32_t sqrtApprox(int32_t x)
 {
   return
     (x < 1024) ?
     (-2400 / (x + 120) + x / 64 + 20) :
       ((x < 93580) ?
        (-1000000 / (x + 8000) + x / 512 + 142) :
        (-75000000 / (x + 160000) + x / 2048 + 565));
 }

Links:
1. number.md
2. math.md
3. programming.md
4. distance.md
5. quadratic_equation.md
6. root.md
7. irrational_number.md
8. two.md
9. real_number.md
10. i.md
11. function.md
12. parabola.md
13. lut.md
14. binary_search.md
15. c.md
16. approximation.md
17. c.md