How to resolve the algorithm Isqrt (integer square root) of X step by step in the ALGOL W programming language
How to resolve the algorithm Isqrt (integer square root) of X step by step in the ALGOL W 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 ALGOL W programming language
Source code in the algol programming language
begin % Integer square roots by quadratic residue %
% returns the integer square root of x - x must be >= 0 %
integer procedure iSqrt ( integer value x ) ;
if x < 0 then begin assert x >= 0; 0 end
else if x < 2 then x
else begin
% x is greater than 1 %
integer q, r, t, z;
% find a power of 4 that's greater than x %
q := 1;
while q <= x do q := q * 4;
% find the root %
z := x;
r := 0;
while q > 1 do begin
q := q div 4;
t := z - r - q;
r := r div 2;
if t >= 0 then begin
z := t;
r := r + q
end if_t_ge_0
end while_q_gt_1 ;
r
end isqrt;
% writes n in 14 character positions with separator commas %
procedure writeonWithCommas ( integer value n ) ;
begin
string(10) decDigits;
string(14) r;
integer v, cPos, dCount;
decDigits := "0123456789";
v := abs n;
r := " ";
r( 13 // 1 ) := decDigits( v rem 10 // 1 );
v := v div 10;
cPos := 12;
dCount := 1;
while cPos > 0 and v > 0 do begin
r( cPos // 1 ) := decDigits( v rem 10 // 1 );
v := v div 10;
cPos := cPos - 1;
dCount := dCount + 1;
if v not = 0 and dCount = 3 then begin
r( cPos // 1 ) := ",";
cPos := cPos - 1;
dCount := 0
end if_v_ne_0_and_dCount_eq_3
end for_cPos;
r( cPos // 1 ) := if n < 0 then "-" else " ";
writeon( s_w := 0, r )
end writeonWithCommas ;
begin % task test cases %
integer prevI, prevR, root, p7;
write( "Integer square roots of 0..65 (values the same as the previous one not shown):" );
write();
prevR := prevI := -1;
for i := 0 until 65 do begin
root := iSqrt( i );
if root not = prevR then begin
prevR := root;
prevI := i;
writeon( i_w := 1, s_w := 0, " ", i, ":", root )
end
else if prevI = i - 1 then writeon( "..." );
end for_i ;
write();
% integer square roots of odd powers of 7 %
write( "Integer square roots of 7^n, odd n" );
write( " n| 7^n| isqrt(7^n)" );
write( " -+--------------+--------------" );
p7 := 7;
for p := 1 step 2 until 9 do begin
write( i_w := 2, s_w := 0, p );
writeon( s_w := 0, "|" ); writeonWithCommas( p7 );
writeon( s_w := 0, "|" ); writeonWithCommas( iSqrt( p7 ) );
p7 := p7 * 49
end for_p
end task_test_cases
end.
You may also check:How to resolve the algorithm XML/XPath step by step in the Go programming language
You may also check:How to resolve the algorithm Sum digits of an integer step by step in the Racket programming language
You may also check:How to resolve the algorithm Pig the dice game step by step in the REXX programming language
You may also check:How to resolve the algorithm CSV data manipulation step by step in the Ring programming language
You may also check:How to resolve the algorithm HTTPS step by step in the C# programming language