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

Often   X   is actually a non─negative integer.

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



One of the most common uses of   Isqrt   is in the division of an integer by all factors   (or
primes)   up to the   
√ X     of that
integer,   either to find the factors of that integer,   or to determine primality.



An alternative method for finding the   Isqrt   of a number is to
calculate:        floor( sqrt(X) ) 

   where   sqrt    is the   square root   function for non─negative real numbers,   and
   where   floor   is the   floor   function for real numbers.


If the hardware supports the computation of (real) square roots,   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   (binary or decimal)   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   quadratic residue,   which has the advantage that no   floating point   calculations are
used,   only integer arithmetic.

Furthermore, the two divisions can be performed by bit shifting,   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   X       (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)   1st   perform   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)  is   0               Isqrt(60)  is  7                Isqrt( 99)  is   9
Isqrt( 1)  is   1               Isqrt(61)  is  7                Isqrt(100)  is  10
Isqrt( 2)  is   1               Isqrt(62)  is  7                Isqrt(102)  is  10
Isqrt( 3)  is   1               Isqrt(63)  is  7
Isqrt( 4)  is   2               Isqrt(64)  is  8                Isqet(120)  is  10
Isqrt( 5)  is   2               Isqrt(65)  is  8                Isqrt(121)  is  11
Isqrt( 6)  is   2               Isqrt(66)  is  8                Isqrt(122)  is  11
Isqrt( 7)  is   2               Isqrt(67)  is  8
Isqrt( 8)  is   2               Isqrt(68)  is  8                Isqrt(143)  is  11
Isqrt( 9)  is   3               Isqrt(69)  is  8                Isqrt(144)  is  12
Isqrt(10)  is   3               Isqrt(70)  is  8                Isqrt(145)  is  12



Task

Compute and show all output here   (on this page)   for:

   the Isqrt of the     integers     from     0 ───► 65    (inclusive), shown in a horizontal format.
   the Isqrt of the   odd powers  from   71 ───► 773   (inclusive), shown in a   vertical   format.
   use commas in the displaying of larger numbers.


You can show more numbers for the 2nd requirement if the displays fits on one screen on Rosetta Code.

If your computer programming language only supports smaller integers,   show what you can.



Related tasks

   sequence of non-squares
   integer roots
   square root by hand


:- module isqrt_in_mercury.
 
:- interface.
:- import_module io.
:- pred main(io, io).
:- mode main(di, uo) is det.
 
:- implementation.
:- import_module char.
:- import_module exception.
:- import_module int.
:- import_module integer.       % Integers of arbitrary size.
:- import_module list.
:- import_module string.
 
:- func four = integer.
four = integer(4).
 
:- func seven = integer.
seven = integer(7).
 
%% Find a power of 4 greater than X.
:- func pow4gtx(integer) = integer.
pow4gtx(X) = Q :- pow4gtx_(X, one, Q).
 
%% The tail recursion for pow4gtx.
:- pred pow4gtx_(integer, integer, integer).
:- mode pow4gtx_(in, in, out) is det.
pow4gtx_(X, A, Q) :- if (X < A) then (Q = A)
                     else (A1 = A * four,
                           pow4gtx_(X, A1, Q)).
 
%% Integer square root function.
:- func isqrt(integer) = integer.
isqrt(X) = Root :- isqrt(X, Root, _).
 
%% Integer square root and remainder.
:- pred isqrt(integer, integer, integer).
:- mode isqrt(in, out, out) is det.
isqrt(X, Root, Remainder) :-
  Q = pow4gtx(X),
  isqrt_(X, Q, zero, X, Root, Remainder).
 
%% The tail recursion for isqrt.
:- pred isqrt_(integer, integer, integer, integer, integer, integer).
:- mode isqrt_(in, in, in, in, out, out) is det.
isqrt_(X, Q, R0, Z0, R, Z) :-
  if (X < zero) then throw("isqrt of a negative integer")
  else if (Q = one) then (R = R0, Z = Z0)
  else (Q1 = Q // four,
        T = Z0 - R0 - Q1,
        (if (T >= zero)
         then (R1 = (R0 // two) + Q1,
               isqrt_(X, Q1, R1, T, R, Z))
         else (R1 is R0 // two,
               isqrt_(X, Q1, R1, Z0, R, Z)))).
 
%% Insert a character, every three digits, into (what presumably is)
%% an integer numeral. (The name "commas" is not very good.)
:- func commas(string, char) = string.
commas(S, Comma) = T :-
  RCL = to_rev_char_list(S),
  commas_(RCL, Comma, 0, [], CL),
  T = from_char_list(CL).
 
%% The tail recursion for commas.
:- pred commas_(list(char), char, int, list(char), list(char)).
:- mode commas_(in, in, in, in, out) is det.
commas_([], _, _, L, CL) :- L = CL.
commas_([C | Tail], Comma, I, L, CL) :-
  if (I = 3) then commas_([C | Tail], Comma, 0, [Comma | L], CL)
  else (I1 = I + 1,
        commas_(Tail, Comma, I1, [C | L], CL)).
 
:- pred roots_m_to_n(integer, integer, io, io).
:- mode roots_m_to_n(in, in, di, uo) is det.
roots_m_to_n(M, N, !IO) :-
  if (N < M) then true
  else (write_string(to_string(isqrt(M)), !IO),
        (if (M \= N) then write_string(" ", !IO)
         else true),
        M1 = M + one,
        roots_m_to_n(M1, N, !IO)).
 
:- pred roots_of_odd_powers_of_7(integer, integer, io, io).
:- mode roots_of_odd_powers_of_7(in, in, di, uo) is det.
roots_of_odd_powers_of_7(M, N, !IO) :-
  if (N < M) then true
  else (Pow7 = pow(seven, M),
        Isqrt = isqrt(Pow7),
        format("%2s %84s %43s",
               [s(commas(to_string(M), (','))),
                s(commas(to_string(Pow7), (','))),
                s(commas(to_string(Isqrt), (',')))],
               !IO),
        nl(!IO),
        M1 = M + two,
        roots_of_odd_powers_of_7(M1, N, !IO)).
 
main(!IO) :-
  write_string("isqrt(i) for 0 <= i <= 65:", !IO),
  nl(!IO), nl(!IO),
  roots_m_to_n(zero, integer(65), !IO),
  nl(!IO), nl(!IO), nl(!IO),
  write_string("isqrt(7**i) for 1 <= i <= 73, i odd:", !IO),
  nl(!IO), nl(!IO),
  format("%2s %84s %43s", [s("i"), s("7**i"), s("isqrt(7**i)")], !IO),
  nl(!IO),
  write_string(duplicate_char(('-'), 131), !IO),
  nl(!IO),
  roots_of_odd_powers_of_7(one, integer(73), !IO).
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Instructions for GNU Emacs--
%%% local variables:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%