Isqrt (integer square root) of X
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.
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 divisions and multiplication can be performed by bit shifting.
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:
/*═══════find Isqrt(x)══════*/ /*all variables are integers*/ q ◄── 1 /*initialize Q to unity. */ /*find a power of 4 that */ /*is 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 /*if T is >= zero then···*/ 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). */
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
Computer 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 powers from 71 ───► 773 (inclusive), shown in a vertical format. - use commas in the displaying of larger numbers.
- the
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
Factor
The isqrt
word is a straightforward translation of the pseudocode from the task description using lexical variables.
<lang factor>USING: formatting io kernel locals math math.functions math.ranges prettyprint sequences tools.memory.private ;
- isqrt ( x -- n )
1 :> q! [ q x > ] [ q 4 * q! ] until x 0 :> ( z! r! ) [ q 1 > ] [ q 4 /i q! z r - q - :> t! r -1 shift r! t 0 >= [ t z! r q + r! ] when ] while r ;
"Integer square root for numbers 0 to 65 (inclusive):" print 66 <iota> [ bl ] [ isqrt pprint ] interleave nl nl
- align ( str str str -- ) "%2s%85s%44s\n" printf ;
- show ( n -- ) dup 7 swap ^ dup isqrt [ commas ] tri@ align ;
"x" "7^x" "isqrt(7^x)" align "-" "---" "----------" align 1 73 2 <range> [ show ] each</lang>
- Output:
Integer square root for numbers 0 to 65 (inclusive): 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 x 7^x isqrt(7^x) - --- ---------- 1 7 2 3 343 18 5 16,807 129 7 823,543 907 9 40,353,607 6,352 11 1,977,326,743 44,467 13 96,889,010,407 311,269 15 4,747,561,509,943 2,178,889 17 232,630,513,987,207 15,252,229 19 11,398,895,185,373,143 106,765,608 21 558,545,864,083,284,007 747,359,260 23 27,368,747,340,080,916,343 5,231,514,822 25 1,341,068,619,663,964,900,807 36,620,603,758 27 65,712,362,363,534,280,139,543 256,344,226,312 29 3,219,905,755,813,179,726,837,607 1,794,409,584,184 31 157,775,382,034,845,806,615,042,743 12,560,867,089,291 33 7,730,993,719,707,444,524,137,094,407 87,926,069,625,040 35 378,818,692,265,664,781,682,717,625,943 615,482,487,375,282 37 18,562,115,921,017,574,302,453,163,671,207 4,308,377,411,626,977 39 909,543,680,129,861,140,820,205,019,889,143 30,158,641,881,388,842 41 44,567,640,326,363,195,900,190,045,974,568,007 211,110,493,169,721,897 43 2,183,814,375,991,796,599,109,312,252,753,832,343 1,477,773,452,188,053,281 45 107,006,904,423,598,033,356,356,300,384,937,784,807 10,344,414,165,316,372,973 47 5,243,338,316,756,303,634,461,458,718,861,951,455,543 72,410,899,157,214,610,812 49 256,923,577,521,058,878,088,611,477,224,235,621,321,607 506,876,294,100,502,275,687 51 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 3,548,134,058,703,515,929,815 53 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 24,836,938,410,924,611,508,707 55 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 173,858,568,876,472,280,560,953 57 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 1,217,009,982,135,305,963,926,677 59 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 8,519,069,874,947,141,747,486,745 61 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 59,633,489,124,629,992,232,407,216 63 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 417,434,423,872,409,945,626,850,517 65 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 2,922,040,967,106,869,619,387,953,625 67 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 20,454,286,769,748,087,335,715,675,381 69 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 143,180,007,388,236,611,350,009,727,669 71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686 73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802
REXX
A fair amount of code was included so that the output aligns correctly. <lang rexx>/*REXX program computes and displays the Isqrt (integer square root) of some integers.*/ numeric digits 200 /*insure 'nuff decimal digs for results*/ parse arg range power base . /*obtain optional arguments from the CL*/ if range== | range=="," then range= 0..65 /*Not specified? Then use the default.*/ if power== | power=="," then power= 1..73 /* " " " " " " */ if base == | base =="," then base = 7 /* " " " " " " */ parse var range rLO '..' rHI; if rHI== then rHI= rLO /*handle a range? */ parse var power pLO '..' pHI; if pHI== then pHI= pLO /* " " " */ $=
do j=rLO to rHI while rHI>0 /*compute Isqrt for a range of integers*/ $= $ commas( Isqrt(j) ) /*append the Isqrt to a list for output*/ end /*j*/
$= strip($) /*elide the leading blank in the list. */ say center(' Isqrt for numbers: ' rLO " ──► " rHI' ', length($), "─") say strip($) /*$ has a leading blank for 1st number*/ say z= base ** pHI /*compute max. exponentiation product.*/ Lp= max(30, length( commas( z) ) ) /*length of " " " */ Lr= max(20, length( commas( Isqrt(z) ) ) ) /* " " " " " Isqrt of above.*/ say 'index' center(base"**index", Lp) center('Isqrt', Lr) /*show a title.*/ say '─────' copies("─", Lp) copies('─', Lr) /* " " header*/
do j=pLO to pHI by 2 while pHI>0; x= base ** j say center(j, 5) right( commas(x), Lp) right( commas( Isqrt(x) ), Lr) end /*j*/ /* [↑] show a bunch of powers & Isqrt.*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _ /*──────────────────────────────────────────────────────────────────────────────────────*/ Isqrt: procedure; parse arg x /*obtain the only passed argument X. */
x= x % 1 /*convert possible real X to an integer*/ /* ◄■■■■■■■ optional. */ q= 1 /*initialize the Q variable to unity.*/ do until q>x /*find a Q that is greater than X. */ q= q * 4 /*multiply Q by four. */ end /*until*/ r= 0 /*R: will be the integer sqrt of X. */ do while q>1 /*keep processing while Q is > than 1*/ q= q % 4 /*divide Q by four (no remainder). */ _= x - r - q /*compute a temporary variable. */ r= r % 2 /*divide R by two (no remainder). */ if _ >= 0 then do /*if _ is non-negative ... */ x= _ /*recompute the value of X */ r= r + q /* " " " " R */ end end /*while*/ return r /*return the integer square root of X. */</lang>
- output when using the default inputs:
───────────────────────────────────────────────── Isqrt for numbers: 0 ──► 65 ────────────────────────────────────────────────── 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 index 7**index Isqrt ───── ────────────────────────────────────────────────────────────────────────────────── ───────────────────────────────────────── 1 7 2 3 343 18 5 16,807 129 7 823,543 907 9 40,353,607 6,352 11 1,977,326,743 44,467 13 96,889,010,407 311,269 15 4,747,561,509,943 2,178,889 17 232,630,513,987,207 15,252,229 19 11,398,895,185,373,143 106,765,608 21 558,545,864,083,284,007 747,359,260 23 27,368,747,340,080,916,343 5,231,514,822 25 1,341,068,619,663,964,900,807 36,620,603,758 27 65,712,362,363,534,280,139,543 256,344,226,312 29 3,219,905,755,813,179,726,837,607 1,794,409,584,184 31 157,775,382,034,845,806,615,042,743 12,560,867,089,291 33 7,730,993,719,707,444,524,137,094,407 87,926,069,625,040 35 378,818,692,265,664,781,682,717,625,943 615,482,487,375,282 37 18,562,115,921,017,574,302,453,163,671,207 4,308,377,411,626,977 39 909,543,680,129,861,140,820,205,019,889,143 30,158,641,881,388,842 41 44,567,640,326,363,195,900,190,045,974,568,007 211,110,493,169,721,897 43 2,183,814,375,991,796,599,109,312,252,753,832,343 1,477,773,452,188,053,281 45 107,006,904,423,598,033,356,356,300,384,937,784,807 10,344,414,165,316,372,973 47 5,243,338,316,756,303,634,461,458,718,861,951,455,543 72,410,899,157,214,610,812 49 256,923,577,521,058,878,088,611,477,224,235,621,321,607 506,876,294,100,502,275,687 51 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 3,548,134,058,703,515,929,815 53 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 24,836,938,410,924,611,508,707 55 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 173,858,568,876,472,280,560,953 57 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 1,217,009,982,135,305,963,926,677 59 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 8,519,069,874,947,141,747,486,745 61 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 59,633,489,124,629,992,232,407,216 63 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 417,434,423,872,409,945,626,850,517 65 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 2,922,040,967,106,869,619,387,953,625 67 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 20,454,286,769,748,087,335,715,675,381 69 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 143,180,007,388,236,611,350,009,727,669 71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686 73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802