Sometimes a function is needed to find the integer square root of &nbsp; '''X''', &nbsp; where &nbsp; '''X''' &nbsp; can be a
real non─negative number.

Often &nbsp; '''X''' &nbsp; is actually a non─negative integer.

For the purposes of this task, &nbsp; '''X''' &nbsp; can be an integer or a real number, &nbsp; but if it
simplifies things in your computer programming language, &nbsp; assume it's an integer.


One of the most common uses of &nbsp; '''<code>Isqrt</code>''' &nbsp; is in the division of an integer by all factors &nbsp; (or
primes) &nbsp; up to the &nbsp; <big><span style="white-pace: nowrap; font-size:larger">
&radic;<span style="text-decoration:overline;">&nbsp;X&nbsp;</span></span> </big> &nbsp; of that
integer, &nbsp; either to find the factors of that integer, &nbsp; or to determine primality.


An alternative method for finding the &nbsp; '''<code>Isqrt</code>''' &nbsp; of a number is to
calculate: &nbsp; &nbsp; &nbsp; <big> floor( sqrt(X) ) </big>
::* &nbsp; where &nbsp;  '''sqrt''' &nbsp;&nbsp; is the &nbsp; square root &nbsp; function for non─negative real numbers, &nbsp; and
::* &nbsp; where &nbsp; '''floor''' &nbsp;       is the &nbsp; floor       &nbsp; function for real numbers.


If the hardware supports the computation of (real) square roots, &nbsp; the above method might be a faster method for
small numbers that don't have very many significant (decimal) digits.

However, floating point arithmetic is limited in the number of &nbsp; (binary or decimal) &nbsp; digits that it can support.


;Pseudo─code using quadratic residue:
For this task, the integer square root of a non─negative number will be computed using a version
of &nbsp; ''quadratic residue'', &nbsp; which has the advantage that no &nbsp; ''floating point'' &nbsp; calculations are
used, &nbsp; only integer arithmetic. 

Furthermore, the two divisions can be performed by bit shifting, &nbsp; and the one multiplication can also be be performed by bit shifting or additions.

The disadvantage is the limitation of the size of the largest integer that a particular computer programming language can support.


Pseudo─code of a procedure for finding the integer square root of &nbsp; '''X''' &nbsp; &nbsp; &nbsp; (all variables are integers):
          q ◄── 1                                /*initialize  Q  to unity.  */
                                   /*find a power of 4 that's greater than X.*/
                   perform  while q <= x         /*perform while  Q <= X.    */
                   q ◄── q * 4                   /*multiply  Q  by  four.    */
                   end  /*perform*/
                                                 /*Q  is now greater than  X.*/
          z ◄── x                                /*set  Z  to the value of X.*/
          r ◄── 0                                /*initialize  R  to zero.   */
                   perform  while q > 1          /*perform while  Q > unity. */
                   q ◄── q ÷ 4                   /*integer divide by  four.  */
                   t ◄── z - r - q               /*compute value of  T.      */
                   r ◄── r ÷ 2                   /*integer divide by  two.   */
                   if t >= 0  then do            
                                   z ◄── t       /*set  Z  to value of  T.   */
                                   r ◄── r + q   /*compute new value of  R.  */
                                   end
                   end  /*perform*/
                                                 /*R  is now the  Isqrt(X).  */
 
          /* Sidenote: Also, Z is now the remainder after square root (i.e.  */
          /*           R^2 + Z = X, so if Z = 0 then X is a perfect square). */

Another version for the (above) &nbsp; 1<sup>st</sup> &nbsp; '''perform''' &nbsp; is:
                   perform  until q > X          /*perform until  Q > X.     */
                   q ◄── q * 4                   /*multiply  Q  by  four.    */
                   end  /*perform*/


Integer square roots of some values:
 Isqrt( 0)  <small>is</small>   0               Isqrt(60)  <small>is</small>  7                Isqrt( 99)  <small>is</small>   9
 Isqrt( 1)  <small>is</small>   1               Isqrt(61)  <small>is</small>  7                Isqrt(100)  <small>is</small>  10
 Isqrt( 2)  <small>is</small>   1               Isqrt(62)  <small>is</small>  7                Isqrt(102)  <small>is</small>  10
 Isqrt( 3)  <small>is</small>   1               Isqrt(63)  <small>is</small>  7
 Isqrt( 4)  <small>is</small>   2               Isqrt(64)  <small>is</small>  8                Isqet(120)  <small>is</small>  10
 Isqrt( 5)  <small>is</small>   2               Isqrt(65)  <small>is</small>  8                Isqrt(121)  <small>is</small>  11
 Isqrt( 6)  <small>is</small>   2               Isqrt(66)  <small>is</small>  8                Isqrt(122)  <small>is</small>  11
 Isqrt( 7)  <small>is</small>   2               Isqrt(67)  <small>is</small>  8
 Isqrt( 8)  <small>is</small>   2               Isqrt(68)  <small>is</small>  8                Isqrt(143)  <small>is</small>  11
 Isqrt( 9)  <small>is</small>   3               Isqrt(69)  <small>is</small>  8                Isqrt(144)  <small>is</small>  12
 Isqrt(10)  <small>is</small>   3               Isqrt(70)  <small>is</small>  8                Isqrt(145)  <small>is</small>  12


;Task:
Compute and show all output here &nbsp; (on this page) &nbsp; for:
::* &nbsp; the <code>Isqrt</code> of the &nbsp; &nbsp; integers &nbsp; &nbsp; from &nbsp; &nbsp; '''0''' ───► '''65'''             &nbsp;&nbsp; (inclusive), shown in a       horizontal       format.
::* &nbsp; the <code>Isqrt</code> of the &nbsp; odd powers&nbsp;              from &nbsp;        '''7<sup>1</sup>''' ───► '''7<sup>73''' &nbsp; (inclusive), shown in a &nbsp; vertical &nbsp; format.
::* &nbsp; use commas in the displaying of larger numbers.


You can show more numbers for the 2<sup>nd</sup> requirement if the displays fits on one screen on Rosetta Code.
<br>If your computer programming language only supports smaller integers, &nbsp; show what you can.


;Related tasks:
:* &nbsp; [[Sequence_of_non-squares|sequence of non-squares]]
:* &nbsp; [[Integer_roots|integer roots]]
:* &nbsp; [[Square_Root_by_Hand|square root by hand]]
<br><br>

