Problem Statement

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

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.

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): Another version for the (above)   1st   perform   is:

Integer square roots of some values:

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

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.

Let's start with the solution:

$ include "seed7_05.s7i";
  include "bigint.s7i";

const func string: commatize (in bigInteger: bigNum) is func
  result
    var string: stri is "";
  local
    var integer: index is 0;
  begin
    stri := str(bigNum);
    for index range length(stri) - 3 downto 1 step 3 do
      stri := stri[.. index] & "," & stri[succ(index) ..];
    end for;
  end func;

const func bigInteger: isqrt (in bigInteger: x) is func
  result
    var bigInteger: r is 0_;
  local
    var bigInteger: q is 1_;
    var bigInteger: z is 0_;
    var bigInteger: t is 0_;
  begin
    while q <= x do
      q *:= 4_;
    end while;
    z := x;
    while q > 1_ do
      q := q mdiv 4_;
      t := z - r - q;
      r := r mdiv 2_;
      if t >= 0_ then
        z := t;
        r +:= q;
      end if;
    end while;
  end func;

const proc: main is func
  local
    var integer: number is 0;
    var bigInteger: pow7 is 7_;
  begin
    writeln("The integer square roots of integers from 0 to 65 are:");
    for number range 0 to 65 do
      write(isqrt(bigInteger(number)) <& " ");
    end for;
    writeln("\n\nThe integer square roots of powers of 7 from 7**1 up to 7**73 are:");
    writeln("power                                    7 ** power                                                integer square root");
    writeln("----- --------------------------------------------------------------------------------- -----------------------------------------");
    for number range 1 to 73 step 2 do
        writeln(number lpad 2 <& commatize(pow7) lpad 85 <& commatize(isqrt(pow7)) lpad 42);
        pow7 *:= 49_;
    end for;
  end func;