How to resolve the algorithm Isqrt (integer square root) of X step by step in the Standard ML programming language

Published on 12 May 2024 09:40 PM
#Standard ml

How to resolve the algorithm Isqrt (integer square root) of X step by step in the Standard ML programming language

Table of Contents

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:

Step by Step solution about How to resolve the algorithm Isqrt (integer square root) of X step by step in the Standard ML programming language

Source code in the standard programming language

(*

  The Rosetta Code integer square root task, in Standard ML.

  Compile with, for example:

     mlton isqrt.sml

*)

val zero = IntInf.fromInt (0)
val one = IntInf.fromInt (1)
val seven = IntInf.fromInt (7)
val word1 = Word.fromInt (1)
val word2 = Word.fromInt (2)

fun
find_a_power_of_4_greater_than_x (x) =
let
  fun
  loop (q) =
  if x < q then
    q
  else
    loop (IntInf.<< (q, word2))
in
  loop (one)
end;

fun
isqrt (x) =
let
  fun
  loop (q, z, r) =
  if q = one then
    r
  else
    let
      val q = IntInf.~>> (q, word2)
      val t = z - r - q
      val r = IntInf.~>> (r, word1)
    in
      if t < zero then
        loop (q, z, r)
      else
        loop (q, t, r + q)
    end
in
  loop (find_a_power_of_4_greater_than_x (x), x, zero)
end;

fun
insert_separators (s, sep) =
(* Insert separator characters (such as #",", #".", #" ") in a numeral
   that is already in string form. *)
let
  fun
  loop (revchars, i, newchars) =
  case (revchars, i) of
      ([], _) => newchars
    | (revchars, 3) => loop (revchars, 0, sep :: newchars)
    | (c :: tail, i) => loop (tail, i + 1, c :: newchars)
in
  implode (loop (rev (explode s), 0, []))
end;

fun
commas (s) =
(* Insert commas in a numeral that is already in string form. *)
insert_separators (s, #",");

val pad_with_spaces = StringCvt.padLeft #" "

fun
main () =
let
  val i = ref 0
in
  print ("isqrt(i) for 0 <= i <= 65:\n\n");

  i := 0;
  while !i < 65 do (
    print (IntInf.toString (isqrt (IntInf.fromInt (!i))));
    print (" ");
    i := !i + 1
  );
  print (IntInf.toString (isqrt (IntInf.fromInt (65))));
  print ("\n\n\n");

  print ("isqrt(7**i) for 1 <= i <= 73, i odd:\n\n");
  print (pad_with_spaces 2 "i");
  print (pad_with_spaces 85 "7**i");
  print (pad_with_spaces 44 "sqrt(7**i)");
  print ("\n");

  i := 1;
  while !i <= 131 do (
    print ("-");
    i := !i + 1
  );
  print ("\n");

  i := 1;
  while !i <= 73 do (
    let
      val pow7 = IntInf.pow (seven, !i)
      val root = isqrt (pow7)
    in
      print (pad_with_spaces 2 (Int.toString (!i)));
      print (pad_with_spaces 85 (commas (IntInf.toString pow7)));
      print (pad_with_spaces 44 (commas (IntInf.toString root)));
      print ("\n");
      i := !i + 2
    end
  )
end;

main ();

(* local variables: *)
(* mode: sml *)
(* sml-indent-level: 2 *)
(* sml-indent-args: 2 *)
(* end: *)

You may also check:How to resolve the algorithm Guess the number/With feedback step by step in the FutureBasic programming language
You may also check:How to resolve the algorithm Multiple regression step by step in the Fortran programming language
You may also check:How to resolve the algorithm Loops/Do-while step by step in the PARI/GP programming language
You may also check:How to resolve the algorithm Formatted numeric output step by step in the Maple programming language
You may also check:How to resolve the algorithm HTTPS/Client-authenticated step by step in the Perl programming language