less_retarded_wiki/sqrt.md

Square Root

Square root (sometimes shortened to sqrt) of 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 math and programming, e.g. for computing distances, solving quadratic equations etc. Square root is a special case of finding Nth 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 irrational number (i.e. it can't be expressed as a fraction of two integers, for example square root of two is approximately 1.414...); and it doesn't even have to be a real number (e.g. square root of -1 is 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 function (notice it's a 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 look up table with precomputed values.

Within desired precision square root can be relatively quickly computed iteratively by binary search. Here is a simple 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 approximation of integer square root in 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));
}