97 lines
6.2 KiB
Text
97 lines
6.2 KiB
Text
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 '''<code>Isqrt</code>''' is in the division of an integer by all factors (or
|
|
primes) up to the <big><span style="white-pace: nowrap; font-size:larger">
|
|
√<span style="text-decoration:overline;"> X </span></span> </big> of that
|
|
integer, either to find the factors of that integer, or to determine primality.
|
|
|
|
|
|
An alternative method for finding the '''<code>Isqrt</code>''' of a number is to
|
|
calculate: <big> floor( sqrt(X) ) </big>
|
|
::* 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) 1<sup>st</sup> '''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) <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 (on this page) for:
|
|
::* the <code>Isqrt</code> of the integers from '''0''' ───► '''65''' (inclusive), shown in a horizontal format.
|
|
::* the <code>Isqrt</code> of the odd powers from '''7<sup>1</sup>''' ───► '''7<sup>73''' (inclusive), shown in a vertical format.
|
|
::* 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, show what you can.
|
|
|
|
|
|
;Related tasks:
|
|
:* [[Sequence_of_non-squares|sequence of non-squares]]
|
|
:* [[Integer_roots|integer roots]]
|
|
:* [[Square_Root_by_Hand|square root by hand]]
|
|
<br><br>
|
|
|