Isqrt (integer square root) of X: Difference between revisions
Isqrt (integer square root) of X (view source)
Revision as of 12:06, 11 December 2023
, 5 months ago→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
| (140 intermediate revisions by 45 users not shown) | |||
Line 1:
{{
Sometimes a function is needed to find the integer square root of '''X''', where '''X''' can be a
Line 31:
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.
Line 55 ⟶ 57:
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:
Line 88 ⟶ 93:
;Related tasks:
:* [
:* [[Integer_roots|integer roots]]
:* [[Square_Root_by_Hand|square root by hand]]
<br><br>
=={{header|11l}}==
{{trans|D}}
<syntaxhighlight lang="11l">F commatize(number, step = 3, sep = ‘,’)
V s = reversed(String(number))
String r = s[0]
L(i) 1 .< s.len
I i % step == 0
r ‘’= sep
r ‘’= s[i]
R reversed(r)
F isqrt(BigInt x)
assert(x >= 0)
V q = BigInt(1)
L q <= x
q *= 4
V z = x
V r = BigInt(0)
L q > 1
q I/= 4
V t = z - r - q
r I/= 2
I t >= 0
z = t
r += q
R r
print(‘The integer square root of integers from 0 to 65 are:’)
L(i) 66
print(isqrt(BigInt(i)), end' ‘ ’)
print()
print(‘The integer square roots of powers of 7 from 7^1 up to 7^73 are:’)
print(‘power 7 ^ power integer square root’)
print(‘----- --------------------------------------------------------------------------------- -----------------------------------------’)
V pow7 = BigInt(7)
V bi49 = BigInt(49)
L(i) (1..73).step(2)
print(‘#2 #84 #41’.format(i, commatize(pow7), commatize(isqrt(pow7))))
pow7 *= bi49</syntaxhighlight>
{{out}}
<pre>
The integer square root of integers from 0 to 65 are:
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
The integer square roots of powers of 7 from 7^1 up to 7^73 are:
power 7 ^ power integer square root
----- --------------------------------------------------------------------------------- -----------------------------------------
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
</pre>
=={{header|Ada}}==
{{works with|Ada 2022}}
<syntaxhighlight lang="ada">with Ada.Text_Io;
with Ada.Numerics.Big_Numbers.Big_Integers;
with Ada.Strings.Fixed;
procedure Integer_Square_Root is
use Ada.Numerics.Big_Numbers.Big_Integers;
use Ada.Text_Io;
function Isqrt (X : Big_Integer) return Big_Integer is
Q : Big_Integer := 1;
Z, T, R : Big_Integer;
begin
while Q <= X loop
Q := Q * 4;
end loop;
Z := X;
R := 0;
while Q > 1 loop
Q := Q / 4;
T := Z - R - Q;
R := R / 2;
if T >= 0 then
Z := T;
R := R + Q;
end if;
end loop;
return R;
end Isqrt;
function Commatize (N : Big_Integer; Width : Positive) return String is
S : constant String := To_String (N, Width);
Image : String (1 .. Width + Width / 3) := (others => ' ');
Pos : Natural := Image'Last;
begin
for I in S'Range loop
Image (Pos) := S (S'Last - I + S'First);
exit when Image (Pos) = ' ';
Pos := Pos - 1;
if I mod 3 = 0 and S (S'Last - I + S'First - 1) /= ' ' then
Image (Pos) := ''';
Pos := Pos - 1;
end if;
end loop;
return Image;
end Commatize;
type Mode_Kind is (Tens, Ones, Spacer, Result);
begin
Put_Line ("Integer square roots of integers 0 .. 65:");
for Mode in Mode_Kind loop
for N in 0 .. 65 loop
case Mode is
when Tens => Put ((if N / 10 = 0
then " "
else Natural'Image (N / 10)));
when Ones => Put (Natural'Image (N mod 10));
when Spacer => Put ("--");
when Result => Put (To_String (Isqrt (To_Big_Integer (N))));
end case;
end loop;
New_Line;
end loop;
New_Line;
declare
package Integer_Io is new Ada.Text_Io.Integer_Io (Natural);
use Ada.Strings.Fixed;
N : Integer := 1;
P, R : Big_Integer;
begin
Put_Line ("| N|" & 80 * " " & "7**N|" & 30 * " " & "isqrt (7**N)|");
Put_Line (133 * "=");
loop
P := 7**N;
R := Isqrt (P);
Put ("|"); Integer_Io.Put (N, Width => 3);
Put ("|"); Put (Commatize (P, Width => 63));
Put ("|"); Put (Commatize (R, Width => 32));
Put ("|"); New_Line;
exit when N >= 73;
N := N + 2;
end loop;
Put_Line (133 * "=");
end;
end Integer_Square_Root;</syntaxhighlight>
{{out}}
<pre>
Integer square roots of integers 0 .. 65:
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
------------------------------------------------------------------------------------------------------------------------------------
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
| N| 7**N| isqrt (7**N)|
=====================================================================================================================================
| 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|
=====================================================================================================================================
</pre>
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Implements the task pseudo-code.
<
PR precision 200 PR
# returns the integer square root of x; x must be >= 0 #
Line 159 ⟶ 396:
p7 *:= 49
OD
END</
{{out}}
<pre>
Line 204 ⟶ 441:
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
</pre>
=={{header|ALGOL W}}==
Algol W integers are restricted to signed 32-bit, so only the roots of the powers of 7 up to 7^9 are shown (7^11 will fit in 32-bits but the smallest power of 4 higher than 7^11 will overflow).
<syntaxhighlight lang="algolw">
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.
</syntaxhighlight>
{{out}}
<pre>
Integer square roots of 0..65 (values the same as the previous one not shown):
0:0 1:1... 4:2... 9:3... 16:4... 25:5... 36:6... 49:7... 64:8...
Integer square roots of 7^n, odd n
n| 7^n| isqrt(7^n)
-+--------------+--------------
1| 7| 2
3| 343| 18
5| 16,807| 129
7| 823,543| 907
9| 40,353,607| 6,352
</pre>
=={{header|ALGOL-M}}==
The code presented here follows the task description. But be warned: there is a bug lurking in the algorithm as presented. The statement q := q * 4 in the first while loop will overflow the limits of ALGOL-M's integer data type (-16,383 to +16,383) for any value of x greater than 4095 and trigger an endless loop. The output has been put into columnar form to avoid what would otherwise be an ugly mess on a typical 80 column display.
<syntaxhighlight lang="algol">
BEGIN
COMMENT
RETURN INTEGER SQUARE ROOT OF N USING QUADRATIC RESIDUE
ALGORITHM. WARNING: THE FUNCTION WILL FAIL FOR X GREATER
THAN 4095;
INTEGER FUNCTION ISQRT(X);
INTEGER X;
BEGIN
INTEGER Q, R, Z, T;
Q := 1;
WHILE Q <= X DO
Q := Q * 4; % WARNING! OVERFLOW YIELDS 0 %
Z := X;
R := 0;
WHILE Q > 1 DO
BEGIN
Q := Q / 4;
T := Z - R - Q;
R := R / 2;
IF T >= 0 THEN
BEGIN
Z := T;
R := R + Q;
END;
END;
ISQRT := R;
END;
COMMENT - LET'S EXERCISE THE FUNCTION;
INTEGER I, COL;
WRITE("INTEGER SQUARE ROOT OF FIRST 65 NUMBERS:");
WRITE("");
COL := 1;
FOR I := 1 STEP 1 UNTIL 65 DO
BEGIN
WRITEON(ISQRT(I));
COL := COL + 1;
IF COL > 10 THEN
BEGIN
WRITE("");
COL := 1;
END;
END;
WRITE("");
WRITE(" N 7^N ISQRT");
WRITE("--------------------");
COMMENT - ODD POWERS OF 7 GREATER THAN 3 WILL CAUSE OVERFLOW;
FOR I := 1 STEP 2 UNTIL 3 DO
BEGIN
INTEGER POW7;
POW7 := 7**I;
WRITE(I, POW7, ISQRT(POW7));
END;
WRITE("THAT'S ALL. GOODBYE.");
END
</syntaxhighlight>
An alternative to the quadratic residue approach will allow calculation of the integer square root for the full range of signed integer values supported by ALGOL-M. (The output is identical.)
<syntaxhighlight lang="algol">
% RETURN INTEGER SQUARE ROOT OF N %
INTEGER FUNCTION ISQRT(N);
INTEGER N;
BEGIN
INTEGER R1, R2;
R1 := N;
R2 := 1;
WHILE R1 > R2 DO
BEGIN
R1 := (R1+R2) / 2;
R2 := N / R1;
END;
ISQRT := R1;
END;
</syntaxhighlight>
{{out}}
<pre>
INTEGER SQUARE ROOT OF FIRST 65 NUMBERS:
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
N 7^N ISQRT
--------------------
1 7 2
3 343 18
THAT'S ALL. GOODBYE.
</pre>
=={{header|AppleScript}}==
The odd-powers-of-7 part of the task is limited by the precision of AppleScript reals.
<syntaxhighlight lang="applescript">on isqrt(x)
set q to 1
repeat until (q > x)
set q to q * 4
end repeat
set z to x
set r to 0
repeat while (q > 1)
set q to q div 4
set t to z - r - q
set r to r div 2
if (t > -1) then
set z to t
set r to r + q
end if
end repeat
return r
end isqrt
-- Task code
on intToText(n, separator)
set output to ""
repeat until (n < 1000)
set output to separator & (text 2 thru 4 of ((1000 + (n mod 1000) as integer) as text)) & output
set n to n div 1000
end repeat
return (n as integer as text) & output
end intToText
on doTask()
-- Get the integer and power results.
set {integerResults, powerResults} to {{}, {}}
repeat with x from 0 to 65
set end of integerResults to isqrt(x)
end repeat
repeat with p from 1 to 73 by 2
set x to 7 ^ p
if (x > 1.0E+15) then exit repeat -- Beyond the precision of AppleScript reals.
set end of powerResults to "7^" & p & tab & "(" & intToText(x, ",") & "):" & (tab & tab & intToText(isqrt(x), ","))
end repeat
-- Format and output.
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to space
set output to {"Isqrts of integers from 0 to 65:", space & integerResults, ¬
"Isqrts of odd powers of 7 from 1 to " & (p - 2) & ":", powerResults}
set AppleScript's text item delimiters to linefeed
set output to output as text
set AppleScript's text item delimiters to astid
return output
end doTask
doTask()</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">"Isqrts of integers from 0 to 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
Isqrts of odd powers of 7 from 1 to 17:
7^1 (7): 2
7^3 (343): 18
7^5 (16,807): 129
7^7 (823,543): 907
7^9 (40,353,607): 6,352
7^11 (1,977,326,743): 44,467
7^13 (96,889,010,407): 311,269
7^15 (4,747,561,509,943): 2,178,889
7^17 (232,630,513,987,207): 15,252,229"</syntaxhighlight>
=={{header|APL}}==
Works in [[Dyalog APL]]
<syntaxhighlight lang="apl"> i←{x←⍵
q←(×∘4)⍣{⍺>x}⊢1
⊃{ r z q←⍵
q←⌊q÷4
t←(z-r)-q
r←⌊r÷2
z←z t[1+t≥0]
r←r+q×t≥0
r z q
}⍣{ r z q←⍺
q≤1
}⊢0 x q
}</syntaxhighlight>
{{output}}
<pre>
i¨⍳65
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
(⎕fr⎕pp)←1287 34
↑{⍵ (7*⍵) (i 7*⍵)}¨1,1+2×⍳10
1 7 2
3 343 18
5 16807 129
7 823543 907
9 40353607 6352
11 1977326743 44467
13 96889010407 311269
15 4747561509943 2178889
17 232630513987207 15252229
19 11398895185373143 106765608
21 558545864083284007 747359260
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">commatize: function [x][
reverse join.with:"," map split.every: 3 split reverse to :string x => join
]
isqrt: function [x][
num: new x
q: new 1
r: new 0
while [q =< num]-> shl.safe 'q 2
while [q > 1][
shr 'q 2
t: (num-r)-q
shr 'r 1
if t >= 0 [
num: t
r: new r+q
]
]
return r
]
print map 0..65 => isqrt
loop range 1 .step: 2 72 'n ->
print [n "\t" commatize isqrt 7^n]</syntaxhighlight>
{{out}}
<pre>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
1 2
3 18
5 129
7 907
9 6,352
11 44,467
13 311,269
15 2,178,889
17 15,252,229
19 106,765,608
21 747,359,260
23 5,231,514,822
25 36,620,603,758
27 256,344,226,312
29 1,794,409,584,184
31 12,560,867,089,291
33 87,926,069,625,040
35 615,482,487,375,282
37 4,308,377,411,626,977
39 30,158,641,881,388,842
41 211,110,493,169,721,897
43 1,477,773,452,188,053,281
45 10,344,414,165,316,372,973
47 72,410,899,157,214,610,812
49 506,876,294,100,502,275,687
51 3,548,134,058,703,515,929,815
53 24,836,938,410,924,611,508,707
55 173,858,568,876,472,280,560,953
57 1,217,009,982,135,305,963,926,677
59 8,519,069,874,947,141,747,486,745
61 59,633,489,124,629,992,232,407,216
63 417,434,423,872,409,945,626,850,517
65 2,922,040,967,106,869,619,387,953,625
67 20,454,286,769,748,087,335,715,675,381
69 143,180,007,388,236,611,350,009,727,669
71 1,002,260,051,717,656,279,450,068,093,686</pre>
=={{header|ATS}}==
Big integers are achieved via the GNU Multiple Precision interface, which enforces proper memory management, without the need for a garbage collector. I felt that, in ATS, using GMP would be almost as simple as writing isqrt only for machine-native integers. One has to try it, to see the advantage of using a compiler that tells you when you have left out an initialization or a "free".
One might note the construction of a "comma'd numeral" by consing of a linked list. This method will work in any Lisp, ML, etc., also. Here the lists are of type "list_vt" and so enforce proper memory management, even in absence of a garbage collector.
<syntaxhighlight lang="ats">(*
Compile with "myatscc isqrt.dats", thus obtaining an executable called
"isqrt".
##myatsccdef=\
patscc -O2 \
-I"${PATSHOME}/contrib/atscntrb" \
-IATS "${PATSHOME}/contrib/atscntrb" \
-D_GNU_SOURCE -DATS_MEMALLOC_LIBC \
-o $fname($1) $1 -lgmp
*)
#include "share/atspre_staload.hats"
(* An interface to GNU Multiple Precision. The type system will help
ensure that you do "mpz_clear" on whatever you allocate. *)
staload "atscntrb-hx-libgmp/SATS/gmp.sats"
(* As of this writing, gmp.dats is empty, but it does no harm to
staload it. *)
staload _ = "atscntrb-hx-libgmp/DATS/gmp.dats"
fn
find_a_power_of_4_greater_than_x
(x : &mpz, (* Input. *)
q : &mpz? >> mpz) (* Output. *)
: void =
let
fun
loop (x : &mpz, q : &mpz) : void =
if 0 <= mpz_cmp (x, q) then
begin
mpz_mul (q, 4u);
loop (x, q)
end
in
mpz_init_set (q, 1u);
loop (x, q)
end
fn
isqrt_and_remainder
(x : &mpz, (* Input. *)
r : &mpz? >> mpz, (* Output: square root. *)
z : &mpz? >> mpz) (* Output: remainder. *)
: void =
let
fun
loop (q : &mpz, z : &mpz, r : &mpz, t : &mpz) : void =
if 0 < mpz_cmp (q, 1u) then
begin
mpz_tdiv_q (q, 4u);
mpz_set_mpz (t, z);
mpz_sub (t, r);
mpz_sub (t, q);
mpz_tdiv_q (r, 2u);
if 0 <= mpz_cmp (t, 0u) then
begin
mpz_set_mpz (z, t);
mpz_add (r, q);
end;
loop (q, z, r, t);
end
var q : mpz
var t : mpz
in
find_a_power_of_4_greater_than_x (x, q);
mpz_init_set (z, x);
mpz_init_set (r, 0u);
mpz_init (t);
loop (q, z, r, t);
mpz_clear (q);
mpz_clear (t);
end
fn
isqrt (x : &mpz, (* Input. *)
r : &mpz? >> mpz) (* Output: square root. *)
: void =
let
var z : mpz
in
isqrt_and_remainder (x, r, z);
mpz_clear (z);
end
fn
print_n_spaces (n : uint) : void =
let
var i : [i : nat] uint i
in
for (i := 0u; i < n; i := succ i)
print! (" ")
end
fn
print_with_commas (n : &mpz,
num_columns : uint) : void =
let
fun
make_list (q : &mpz,
r : &mpz,
lst : List0_vt char,
i : uint) : List_vt char =
if mpz_cmp (q, 0u) = 0 then
lst
else
let
val _ = mpz_tdiv_qr (q, r, 10u)
val ones_place = mpz_get_int (r)
val digit = int2char0 (ones_place + char2i '0')
in
if i = 3u then
let
val lst = list_vt_cons (',', lst)
val lst = list_vt_cons (digit, lst)
in
make_list (q, r, lst, 1u)
end
else
let
val lst = list_vt_cons (digit, lst)
in
make_list (q, r, lst, succ i)
end
end
var q : mpz
var r : mpz
val _ = mpz_init_set (q, n)
val _ = mpz_init (r)
val char_lst = make_list (q, r, list_vt_nil (), 0u)
val _ = mpz_clear (q)
val _ = mpz_clear (r)
fun
print_and_consume_lst (char_lst : List0_vt char) : void =
case+ char_lst of
| ~ list_vt_nil () => ()
| ~ list_vt_cons (head, tail) =>
begin
print! (head);
print_and_consume_lst (tail);
end
prval _ = lemma_list_vt_param (char_lst)
val len = i2u (list_vt_length (char_lst))
in
assertloc (len <= num_columns);
print_n_spaces (num_columns - len);
print_and_consume_lst (char_lst)
end
fn
do_the_roots_of_0_to_65 () : void =
let
var i : mpz
in
mpz_init_set (i, 0u);
while (mpz_cmp (i, 65u) <= 0)
let
var r : mpz
in
isqrt (i, r);
fprint (stdout_ref, r);
print! (" ");
mpz_add (i, 1u);
mpz_clear (r);
end;
mpz_clear (i);
end
fn
do_the_roots_of_odd_powers_of_7 () : void =
let
var seven : mpz
var seven_raised_i : mpz
var i_mpz : mpz
var i : [i : pos] uint i
in
mpz_init_set (seven, 7u);
mpz_init (seven_raised_i);
mpz_init (i_mpz);
for (i := 1u; i <= 73u; i := succ (succ i))
let
var r : mpz
in
mpz_pow_uint (seven_raised_i, seven, i);
isqrt (seven_raised_i, r);
mpz_set_uint (i_mpz, i);
print_with_commas (i_mpz, 2u);
print! (" ");
print_with_commas (seven_raised_i, 84u);
print! (" ");
print_with_commas (r, 43u);
print! ("\n");
mpz_clear (r);
end;
mpz_clear (seven);
mpz_clear (seven_raised_i);
mpz_clear (i_mpz);
end
implement
main0 () =
begin
print! ("isqrt(i) for 0 <= i <= 65:\n\n");
do_the_roots_of_0_to_65 ();
print! ("\n\n\n");
print! ("isqrt(7**i) for 1 <= i <= 73, i odd:\n\n");
print! (" i 7**i sqrt(7**i)\n");
print! ("-----------------------------------------------------------------------------------------------------------------------------------\n");
do_the_roots_of_odd_powers_of_7 ();
end</syntaxhighlight>
{{out}}
<pre>$ myatscc isqrt.dats
$ ./isqrt
isqrt(i) for 0 <= i <= 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
isqrt(7**i) for 1 <= i <= 73, i odd:
i 7**i sqrt(7**i)
-----------------------------------------------------------------------------------------------------------------------------------
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</pre>
=={{header|BASIC256}}==
<syntaxhighlight lang="basic256">print "Integer square root of first 65 numbers:"
for n = 1 to 65
print ljust(isqrt(n),3);
next n
print : print
print "Integer square root of odd powers of 7"
print " n 7^n isqrt"
print "-"*36
for n = 1 to 21 step 2
pow7 = int(7 ^ n)
print rjust(n,3);rjust(pow7,20);rjust(isqrt(pow7),12)
next n
end
function isqrt(x)
q = 1
while q <= x
q *= 4
end while
r = 0
while q > 1
q /= 4
t = x - r - q
r /= 2
if t >= 0 then
x = t
r += q
end if
end while
return int(r)
end function</syntaxhighlight>
=={{header|C}}==
{{trans|C++}}
Up to 64-bit limits with no big int library.
<syntaxhighlight lang="c">#include <stdint.h>
#include <stdio.h>
int64_t isqrt(int64_t x) {
int64_t q = 1, r = 0;
while (q <= x) {
q <<= 2;
}
while (q > 1) {
int64_t t;
q >>= 2;
t = x - r - q;
r >>= 1;
if (t >= 0) {
x = t;
r += q;
}
}
return r;
}
int main() {
int64_t p;
int n;
printf("Integer square root for numbers 0 to 65:\n");
for (n = 0; n <= 65; n++) {
printf("%lld ", isqrt(n));
}
printf("\n\n");
printf("Integer square roots of odd powers of 7 from 1 to 21:\n");
printf(" n | 7 ^ n | isqrt(7 ^ n)\n");
p = 7;
for (n = 1; n <= 21; n += 2, p *= 49) {
printf("%2d | %18lld | %12lld\n", n, p, isqrt(p));
}
}</syntaxhighlight>
{{out}}
<pre>Integer square root for numbers 0 to 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
Integer square roots of odd powers of 7 from 1 to 21:
n | 7 ^ n | isqrt(7 ^ n)
1 | 7 | 2
3 | 343 | 18
5 | 16807 | 129
7 | 823543 | 907
9 | 40353607 | 6352
11 | 1977326743 | 44467
13 | 96889010407 | 311269
15 | 4747561509943 | 2178889
17 | 232630513987207 | 15252229
19 | 11398895185373143 | 106765608
21 | 558545864083284007 | 747359260</pre>
=={{header|C++}}==
{{libheader|Boost}}
<
#include <iostream>
#include <sstream>
Line 268 ⟶ 1,251:
}
return 0;
}</
{{out}}
<pre style="font-size: 11px">
Integer square root for numbers 0 to 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
Line 319 ⟶ 1,302:
=={{header|C#|CSharp}}==
{{libheader|System.Numerics}}
<
using static System.Console;
using BI = System.Numerics.BigInteger;
Line 344 ⟶ 1,327:
BI p = 7; for (int n = 1; n <= max; n += 2, p *= 49)
WriteLine (s, n, p, isqrt(p)); }
}</
{{Out}}
<pre>Integer square root for numbers 0 to 65:
Line 393 ⟶ 1,376:
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
</pre>
=={{header|CLU}}==
<syntaxhighlight lang="clu">% This program uses the 'bigint' cluster from PCLU's 'misc.lib'
% Integer square root of a bigint
isqrt = proc (x: bigint) returns (bigint)
% Initialize a couple of bigints we will reuse
own zero: bigint := bigint$i2bi(0)
own one: bigint := bigint$i2bi(1)
own two: bigint := bigint$i2bi(2)
own four: bigint := bigint$i2bi(4)
q: bigint := one
while q <= x do q := q * four end
t: bigint
z: bigint := x
r: bigint := zero
while q>one do
q := q / four
t := z - r - q
r := r / two
if t >= zero then
z := t
r := r + q
end
end
return(r)
end isqrt
% Format a bigint using commas
fmt = proc (x: bigint) returns (string)
own zero: bigint := bigint$i2bi(0)
own ten: bigint := bigint$i2bi(10)
if x=zero then return("0") end
out: array[char] := array[char]$[]
ds: int := 0
while x>zero do
array[char]$addl(out, char$i2c(bigint$bi2i(x // ten) + 48))
x := x / ten
ds := ds + 1
if x~=zero cand ds//3=0 then
array[char]$addl(out, ',')
end
end
return(string$ac2s(out))
end fmt
start_up = proc ()
po: stream := stream$primary_output()
% print square roots from 0..65
stream$putl(po, "isqrt of 0..65:")
for i: int in int$from_to(0, 65) do
stream$puts(po, fmt(isqrt(bigint$i2bi(i))) || " ")
end
% print square roots of odd powers
stream$putl(po, "\n\nisqrt of odd powers of 7:")
seven: bigint := bigint$i2bi(7)
for p: int in int$from_to_by(1, 73, 2) do
stream$puts(po, "isqrt(7^")
stream$putright(po, int$unparse(p), 2)
stream$puts(po, ") = ")
stream$putright(po, fmt(isqrt(seven ** bigint$i2bi(p))), 41)
stream$putl(po, "")
end
end start_up</syntaxhighlight>
{{out}}
<pre>isqrt of 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
isqrt of odd powers of 7:
isqrt(7^ 1) = 2
isqrt(7^ 3) = 18
isqrt(7^ 5) = 129
isqrt(7^ 7) = 907
isqrt(7^ 9) = 6,352
isqrt(7^11) = 44,467
isqrt(7^13) = 311,269
isqrt(7^15) = 2,178,889
isqrt(7^17) = 15,252,229
isqrt(7^19) = 106,765,608
isqrt(7^21) = 747,359,260
isqrt(7^23) = 5,231,514,822
isqrt(7^25) = 36,620,603,758
isqrt(7^27) = 256,344,226,312
isqrt(7^29) = 1,794,409,584,184
isqrt(7^31) = 12,560,867,089,291
isqrt(7^33) = 87,926,069,625,040
isqrt(7^35) = 615,482,487,375,282
isqrt(7^37) = 4,308,377,411,626,977
isqrt(7^39) = 30,158,641,881,388,842
isqrt(7^41) = 211,110,493,169,721,897
isqrt(7^43) = 1,477,773,452,188,053,281
isqrt(7^45) = 10,344,414,165,316,372,973
isqrt(7^47) = 72,410,899,157,214,610,812
isqrt(7^49) = 506,876,294,100,502,275,687
isqrt(7^51) = 3,548,134,058,703,515,929,815
isqrt(7^53) = 24,836,938,410,924,611,508,707
isqrt(7^55) = 173,858,568,876,472,280,560,953
isqrt(7^57) = 1,217,009,982,135,305,963,926,677
isqrt(7^59) = 8,519,069,874,947,141,747,486,745
isqrt(7^61) = 59,633,489,124,629,992,232,407,216
isqrt(7^63) = 417,434,423,872,409,945,626,850,517
isqrt(7^65) = 2,922,040,967,106,869,619,387,953,625
isqrt(7^67) = 20,454,286,769,748,087,335,715,675,381
isqrt(7^69) = 143,180,007,388,236,611,350,009,727,669
isqrt(7^71) = 1,002,260,051,717,656,279,450,068,093,686
isqrt(7^73) = 7,015,820,362,023,593,956,150,476,655,802</pre>
=={{header|COBOL}}==
The COBOL compiler used here is limited to 18-digit math, meaning 7^19 is the largest odd power of 7 that can be calculated.
<syntaxhighlight lang="cobol"> IDENTIFICATION DIVISION.
PROGRAM-ID. I-SQRT.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 QUAD-RET-VARS.
03 X PIC 9(18).
03 Q PIC 9(18).
03 Z PIC 9(18).
03 T PIC S9(18).
03 R PIC 9(18).
01 TO-65-VARS.
03 ISQRT-N PIC 99.
03 DISP-LN PIC X(22) VALUE SPACES.
03 DISP-FMT PIC Z9.
03 PTR PIC 99 VALUE 1.
01 BIG-SQRT-VARS.
03 POW-7 PIC 9(18) VALUE 7.
03 POW-N PIC 99 VALUE 1.
03 POW-N-OUT PIC Z9.
03 POW-7-OUT PIC Z(10).
PROCEDURE DIVISION.
BEGIN.
PERFORM SQRTS-TO-65.
PERFORM BIG-SQRTS.
STOP RUN.
SQRTS-TO-65.
PERFORM DISP-SMALL-SQRT
VARYING ISQRT-N FROM 0 BY 1
UNTIL ISQRT-N IS GREATER THAN 65.
DISP-SMALL-SQRT.
MOVE ISQRT-N TO X.
PERFORM ISQRT.
MOVE R TO DISP-FMT.
STRING DISP-FMT DELIMITED BY SIZE INTO DISP-LN
WITH POINTER PTR.
IF PTR IS GREATER THAN 22,
DISPLAY DISP-LN,
MOVE 1 TO PTR.
BIG-SQRTS.
PERFORM BIG-SQRT 10 TIMES.
BIG-SQRT.
MOVE POW-7 TO X.
PERFORM ISQRT.
MOVE POW-N TO POW-N-OUT.
MOVE R TO POW-7-OUT.
DISPLAY "ISQRT(7^" POW-N-OUT ") = " POW-7-OUT.
ADD 2 TO POW-N.
MULTIPLY 49 BY POW-7.
ISQRT.
MOVE 1 TO Q.
PERFORM MUL-Q-BY-4 UNTIL Q IS GREATER THAN X.
MOVE X TO Z.
MOVE ZERO TO R.
PERFORM ISQRT-STEP UNTIL Q IS NOT GREATER THAN 1.
MUL-Q-BY-4.
MULTIPLY 4 BY Q.
ISQRT-STEP.
DIVIDE 4 INTO Q.
COMPUTE T = Z - R - Q.
DIVIDE 2 INTO R.
IF T IS NOT LESS THAN ZERO,
MOVE T TO Z,
ADD Q TO R.</syntaxhighlight>
{{out}}
<pre> 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
ISQRT(7^ 1) = 2
ISQRT(7^ 3) = 18
ISQRT(7^ 5) = 129
ISQRT(7^ 7) = 907
ISQRT(7^ 9) = 6352
ISQRT(7^11) = 44467
ISQRT(7^13) = 311269
ISQRT(7^15) = 2178889
ISQRT(7^17) = 15252229
ISQRT(7^19) = 106765608</pre>
=={{header|Common Lisp}}==
{{trans|Scheme}}
The program is wrapped in a [https://roswell.github.io/ Roswell script]. On a POSIX system with Roswell installed, you can simply run the script.
The code is an "imperative" translation of the "functional" Scheme.
Side notes:
* Straight translations from Scheme to Common Lisp run the risk of running properly with some CL compilers but not others, due to the prevalence of tail calls in Scheme. Common Lisp does not require proper tail calls, although CL compilers do optimize such calls, to varying degrees depending on the compiler.
* The simple program here would not require tail call optimization at all; the depth of recursion would be too small. I felt it better to write the CL in "imperative" style nonetheless.
* Not all Scheme compilers make all tail calls proper, either, at least by default. This, however, is nonstandard behavior.
<syntaxhighlight lang="lisp">#!/bin/sh
#|-*- mode:lisp -*-|#
#|
exec ros -Q -- $0 "$@"
|#
(progn ;;init forms
(ros:ensure-asdf)
#+quicklisp(ql:quickload '() :silent t)
)
(defpackage :ros.script.isqrt.3860764029
(:use :cl))
(in-package :ros.script.isqrt.3860764029)
;;
;; The Rosetta Code integer square root task, in Common Lisp.
;;
;; I translate the tail recursions of the Scheme as regular loops in
;; Common Lisp, although CL compilers most often can optimize tail
;; recursions of the kind. They are not required to, however.
;;
;; As a result, the CL is actually closer to the task's pseudocode
;; than is the Scheme.
;;
;; (The Scheme, by the way, could have been written much as follows,
;; using "set!" where the CL has "setf", and with other such
;; "linguistic" changes.)
;;
(defun find-a-power-of-4-greater-than-x (x)
(let ((q 1))
(loop until (< x q)
do (setf q (* 4 q)))
q))
(defun isqrt+remainder (x)
(let ((q (find-a-power-of-4-greater-than-x x))
(z x)
(r 0))
(loop until (= q 1)
do (progn (setf q (/ q 4))
(let ((z1 (- z r q)))
(setf r (/ r 2))
(when (<= 0 z1)
(setf z z1)
(setf r (+ r q))))))
(values r z)))
(defun rosetta_code_isqrt (x)
(nth-value 0 (isqrt+remainder x)))
(defun main (&rest argv)
(declare (ignorable argv))
(format t "isqrt(i) for ~D <= i <= ~D:~2%" 0 65)
(loop for i from 0 to 64
do (format t "~D " (isqrt i)))
(format t "~D~3%" (isqrt 65))
(format t "isqrt(7**i) for ~D <= i <= ~D, i odd:~2%" 1 73)
(format t "~2@A ~84@A ~43@A~%" "i" "7**i" "sqrt(7**i)")
(format t "~A~%" (make-string 131 :initial-element #\-))
(loop for i from 1 to 73 by 2
for 7**i = (expt 7 i)
for root = (rosetta_code_isqrt 7**i)
do (format t "~2D ~84:D ~43:D~%" i 7**i root)))
;;; vim: set ft=lisp lisp:</syntaxhighlight>
{{out}}
<pre>$ sh isqrt.ros
isqrt(i) for 0 <= i <= 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
isqrt(7**i) for 1 <= i <= 73, i odd:
i 7**i sqrt(7**i)
-----------------------------------------------------------------------------------------------------------------------------------
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</pre>
=={{header|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
# Integer square root
sub isqrt(x: uint32): (x0: uint32) is
x0 := x >> 1;
if x0 == 0 then
x0 := x;
return;
end if;
loop
var x1 := (x0 + x/x0) >> 1;
if x1 >= x0 then
break;
end if;
x0 := x1;
end loop;
end sub;
# Power
sub pow(x: uint32, n: uint8): (r: uint32) is
r := 1;
while n > 0 loop
r := r * x;
n := n - 1;
end loop;
end sub;
# Print integer square roots of 0..65
var n: uint32 := 0;
var col: uint8 := 11;
while n <= 65 loop
print_i32(isqrt(n));
col := col - 1;
if col == 0 then
print_nl();
col := 11;
else
print_char(' ');
end if;
n := n + 1;
end loop;
# Cowgol only supports 32-bit integers out of the box, so only powers of 7
# up to 7^11 are printed
var x: uint8 := 0;
while x <= 11 loop
print("isqrt(7^");
print_i8(x);
print(") = ");
print_i32(isqrt(pow(7, x)));
print_nl();
x := x + 1;
end loop;</syntaxhighlight>
{{out}}
<pre>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
isqrt(7^0) = 1
isqrt(7^1) = 2
isqrt(7^2) = 7
isqrt(7^3) = 18
isqrt(7^4) = 49
isqrt(7^5) = 129
isqrt(7^6) = 343
isqrt(7^7) = 907
isqrt(7^8) = 2401
isqrt(7^9) = 6352
isqrt(7^10) = 16807
isqrt(7^11) = 44467</pre>
=={{header|Craft Basic}}==
<syntaxhighlight lang="basic">alert "integer square root of first 65 numbers:"
for n = 1 to 65
let x = n
gosub isqrt
print r
next n
alert "integer square root of odd powers of 7"
cls
cursor 1, 1
for n = 1 to 21 step 2
let x = 7 ^ n
gosub isqrt
print "isqrt of 7 ^ ", n, " = ", r
next n
end
sub isqrt
let q = 1
do
if q <= x then
let q = q * 4
endif
wait
loop q <= x
let r = 0
do
if q > 1 then
let q = q / 4
let t = x - r - q
let r = r / 2
if t >= 0 then
let x = t
let r = r + q
endif
endif
loop q > 1
let r = int(r)
return</syntaxhighlight>
{{out| Output}}<pre>integer square root of first 65 numbers:
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
integer square root of odd powers of 7:
isqrt of 7 ^ 1 = 2
isqrt of 7 ^ 3 = 18
isqrt of 7 ^ 5 = 129
isqrt of 7 ^ 7 = 907
isqrt of 7 ^ 9 = 6352</pre>
=={{header|D}}==
{{trans|Kotlin}}
<syntaxhighlight lang="d">import std.bigint;
import std.conv;
import std.exception;
import std.range;
import std.regex;
import std.stdio;
//Taken from the task http://rosettacode.org/wiki/Commatizing_numbers#D
auto commatize(in char[] txt, in uint start=0, in uint step=3, in string ins=",") @safe
in {
assert(step > 0);
} body {
if (start > txt.length || step > txt.length) {
return txt;
}
// First number may begin with digit or decimal point. Exponents ignored.
enum decFloField = ctRegex!("[0-9]*\\.[0-9]+|[0-9]+");
auto matchDec = matchFirst(txt[start .. $], decFloField);
if (!matchDec) {
return txt;
}
// Within a decimal float field:
// A decimal integer field to commatize is positive and not after a point.
enum decIntField = ctRegex!("(?<=\\.)|[1-9][0-9]*");
// A decimal fractional field is preceded by a point, and is only digits.
enum decFracField = ctRegex!("(?<=\\.)[0-9]+");
return txt[0 .. start] ~ matchDec.pre ~ matchDec.hit
.replace!(m => m.hit.retro.chunks(step).join(ins).retro)(decIntField)
.replace!(m => m.hit.chunks(step).join(ins))(decFracField)
~ matchDec.post;
}
auto commatize(BigInt v) {
return commatize(v.to!string);
}
BigInt sqrt(BigInt x) {
enforce(x >= 0);
auto q = BigInt(1);
while (q <= x) {
q <<= 2;
}
auto z = x;
auto r = BigInt(0);
while (q > 1) {
q >>= 2;
auto t = z;
t -= r;
t -= q;
r >>= 1;
if (t >= 0) {
z = t;
r += q;
}
}
return r;
}
void main() {
writeln("The integer square root of integers from 0 to 65 are:");
foreach (i; 0..66) {
write(sqrt(BigInt(i)), ' ');
}
writeln;
writeln("The integer square roots of powers of 7 from 7^1 up to 7^73 are:");
writeln("power 7 ^ power integer square root");
writeln("----- --------------------------------------------------------------------------------- -----------------------------------------");
auto pow7 = BigInt(7);
immutable bi49 = BigInt(49);
for (int i = 1; i <= 73; i += 2) {
writefln("%2d %84s %41s", i, pow7.commatize, sqrt(pow7).commatize);
pow7 *= bi49;
}
}</syntaxhighlight>
{{out}}
<pre>The integer square root of integers from 0 to 65 are:
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
The integer square roots of powers of 7 from 7^1 up to 7^73 are:
power 7 ^ power integer square root
----- --------------------------------------------------------------------------------- -----------------------------------------
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</pre>
=={{header|Delphi}}==
See [[#Pascal]].
=={{header|Draco}}==
Because all the intermediate values have to fit in a signed 32-bit integer, the largest power of 7
for which the square root can be calculated is 7^10.
<syntaxhighlight lang="draco">/* Integer square root using quadratic residue method */
proc nonrec isqrt(ulong x) ulong:
ulong q, z, r;
long t;
q := 1;
while q <= x do q := q << 2 od;
z := x;
r := 0;
while q > 1 do
q := q >> 2;
t := z - r - q;
r := r >> 1;
if t >= 0 then
z := t;
r := r + q
fi
od;
r
corp
proc nonrec main() void:
byte x;
ulong pow7;
/* print isqrt(0) ... isqrt(65) */
for x from 0 upto 65 do
write(isqrt(x):2);
if x % 11 = 10 then writeln() fi
od;
/* print isqrt(7^0) thru isqrt(7^10) */
pow7 := 1;
for x from 0 upto 10 do
writeln("isqrt(7^", x:2, ") = ", isqrt(pow7):5);
pow7 := pow7 * 7
od
corp</syntaxhighlight>
{{out}}
<pre> 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
isqrt(7^ 0) = 1
isqrt(7^ 1) = 2
isqrt(7^ 2) = 7
isqrt(7^ 3) = 18
isqrt(7^ 4) = 49
isqrt(7^ 5) = 129
isqrt(7^ 6) = 343
isqrt(7^ 7) = 907
isqrt(7^ 8) = 2401
isqrt(7^ 9) = 6352
isqrt(7^10) = 16807</pre>
=={{header|EasyLang}}==
{{trans|Lua}}
<syntaxhighlight lang=easylang>
func isqrt x .
q = 1
while q <= x
q *= 4
.
while q > 1
q = q div 4
t = x - r - q
r = r div 2
if t >= 0
x = t
r = r + q
.
.
return r
.
print "Integer square roots from 0 to 65:"
for n = 0 to 65
write isqrt n & " "
.
print ""
print ""
print "Integer square roots of 7^n"
p = 7
n = 1
while n <= 21
print n & " " & isqrt p
n = n + 2
p = p * 49
.
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
<
// Find Integer Floor sqrt of a Large Integer. Nigel Galloway: July 17th., 2020
let Isqrt n=let rec fN i g l=match(l>0I,i-g-l) with
Line 405 ⟶ 2,108:
[0I..65I]|>Seq.iter(Isqrt>>string>>printf "%s "); printfn "\n"
let fN n=7I**n in [1..2..73]|>Seq.iter(fN>>Isqrt>>printfn "%a" (fun n g -> n.Write("{0:#,#}", g)))
</syntaxhighlight>
{{out}}
<pre>
Line 448 ⟶ 2,151:
7,015,820,362,023,593,956,150,476,655,802
</pre>
=={{header|Factor}}==
The <code>isqrt</code> word is a straightforward translation of the pseudocode from the task description using lexical variables.
{{works with|Factor|0.99 2020-07-03}}
<
math.ranges prettyprint sequences tools.memory.private ;
Line 477 ⟶ 2,181:
"x" "7^x" "isqrt(7^x)" align
"-" "---" "----------" align
1 73 2 <range> [ show ] each</
{{out}}
<pre>
Line 523 ⟶ 2,227:
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
</pre>
=={{header|Fish}}==
A function (isolated stack; remove the 1[ and ] instructions to create "inline" version) that calculates and outputs the square root of the top of the stack/input number.
Código sacado de https://esolangs.org/wiki/Fish
<syntaxhighlight lang="fish">1[:>:r:@@:@,\;
]~$\!?={:,2+/n</syntaxhighlight>
=={{header|Forth}}==
Only handles odd powers of 7 up to 7^21.
<syntaxhighlight lang="forth">
: d., ( n -- ) \ write double precision int, commatized.
tuck dabs
<# begin 2dup 1.000 d> while # # # [char] , hold repeat #s rot sign #>
type space ;
: ., ( n -- ) \ write integer commatized.
s>d d., ;
: 4* s" 2 lshift" evaluate ; immediate
: 4/ s" 2 rshift" evaluate ; immediate
: isqrt-mod ( n -- z r ) \ n = r^2 + z
1 begin 2dup >= while 4* repeat
0 locals| r q z |
begin q 1 > while
q 4/ to q
z r - q - \ t
r 2/ to r
dup 0>= if
to z
r q + to r
else
drop
then
repeat z r ;
: isqrt isqrt-mod nip ;
: task1
." Integer square roots from 0 to 65:" cr
66 0 do i isqrt . loop cr ;
: task2
." Integer square roots of 7^n" cr
7 11 0 do
i 2* 1+ 2 .r 3 spaces
dup isqrt ., cr
49 *
loop ;
task1 cr task2 bye
</syntaxhighlight>
This version of the core word does not require locals.
<syntaxhighlight lang="text">: sqrt-rem ( n -- sqrt rem)
>r 0 1 begin dup r@ > 0= while 4 * repeat
begin \ find a power of 4 greater than TORS
dup 1 > \ compute while greater than unity
while
2/ 2/ swap over over + negate r@ + \ integer divide by 4
dup 0< if drop 2/ else r> drop >r 2/ over + then swap
repeat drop r> ( sqrt rem)
;
: isqrt-mod sqrt-rem swap ;</syntaxhighlight>
{{Out}}
<pre>
Integer square roots from 0 to 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
Integer square roots of 7^n
1 2
3 18
5 129
7 907
9 6,352
11 44,467
13 311,269
15 2,178,889
17 15,252,229
19 106,765,608
21 747,359,260
</pre>
=={{header|Fortran}}==
<syntaxhighlight lang="fortran">MODULE INTEGER_SQUARE_ROOT
IMPLICIT NONE
CONTAINS
! Convert string representation number to string with comma digit separation
FUNCTION COMMATIZE(NUM) RESULT(OUT_STR)
INTEGER(16), INTENT(IN) :: NUM
INTEGER(16) I
CHARACTER(83) :: TEMP, OUT_STR
WRITE(TEMP, '(I0)') NUM
OUT_STR = ""
DO I=0, LEN_TRIM(TEMP)-1
IF (MOD(I, 3) .EQ. 0 .AND. I .GT. 0 .AND. I .LT. LEN_TRIM(TEMP)) THEN
OUT_STR = "," // TRIM(OUT_STR)
END IF
OUT_STR = TEMP(LEN_TRIM(TEMP)-I:LEN_TRIM(TEMP)-I) // TRIM(OUT_STR)
END DO
END FUNCTION COMMATIZE
! Calculate the integer square root for a given integer
FUNCTION ISQRT(NUM)
INTEGER(16), INTENT(IN) :: NUM
INTEGER(16) :: ISQRT
INTEGER(16) :: Q, Z, R, T
Q = 1
Z = NUM
R = 0
T = 0
DO WHILE (Q .LE. NUM)
Q = Q * 4
END DO
DO WHILE (Q .GT. 1)
Q = Q / 4
T = Z - R - Q
R = R / 2
IF (T .GE. 0) THEN
Z = T
R = R + Q
END IF
END DO
ISQRT = R
END FUNCTION ISQRT
END MODULE INTEGER_SQUARE_ROOT
! Demonstration of integer square root for numbers 0-65 followed by odd powers of 7
! from 1-73. Currently this demo takes significant time for numbers above 43
PROGRAM ISQRT_DEMO
USE INTEGER_SQUARE_ROOT
IMPLICIT NONE
INTEGER(16), PARAMETER :: MIN_NUM_HZ = 0
INTEGER(16), PARAMETER :: MAX_NUM_HZ = 65
INTEGER(16), PARAMETER :: POWER_BASE = 7
INTEGER(16), PARAMETER :: POWER_MIN = 1
INTEGER(16), PARAMETER :: POWER_MAX = 73
INTEGER(16), DIMENSION(MAX_NUM_HZ-MIN_NUM_HZ+1) :: VALUES
CHARACTER(2) :: HEADER_1
CHARACTER(83) :: HEADER_2
CHARACTER(83) :: HEADER_3
INTEGER(16) :: I
HEADER_1 = " n"
HEADER_2 = "7^n"
HEADER_3 = "isqrt(7^n)"
WRITE(*,'(A, I0, A, I0)') "Integer square root for numbers ", MIN_NUM_HZ, " to ", MAX_NUM_HZ
DO I=1, SIZE(VALUES)
VALUES(I) = ISQRT(MIN_NUM_HZ+I)
END DO
WRITE(*,'(100I2)') VALUES
WRITE(*,*) NEW_LINE('A')
WRITE(*,'(A,A,A,A,A)') HEADER_1, " | ", HEADER_2, " | ", HEADER_3
WRITE(*,*) REPEAT("-", 8+83*2)
DO I=POWER_MIN,POWER_MAX, 2
WRITE(*,'(I2, A, A, A, A)') I, " | " // COMMATIZE(7**I), " | ", COMMATIZE(ISQRT(7**I))
END DO
END PROGRAM ISQRT_DEMO</syntaxhighlight>
<pre>
Integer square root for numbers 0 to 65
0 1 1 1 2 2 2 2 3 3 3 3 3 3 3 3 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 7 8 8
n | 7^n | isqrt(7^n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
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
</pre>
=={{header|FreeBASIC}}==
Odd powers up to 7^21 are shown; more would require an arbitrary precision library that would just add bloat without being illustrative.
<syntaxhighlight lang="freebasic">
function isqrt( byval x as ulongint ) as ulongint
dim as ulongint q = 1, r
dim as longint t
while q <= x
q = q shl 2
wend
while q > 1
q = q shr 2
t = x - r - q
r = r shr 1
if t >= 0 then
x = t
r += q
end if
wend
return r
end function
function commatize( byval N as string ) as string
dim as string bloat = ""
dim as uinteger c = 0
while N<>""
bloat = right(N,1) + bloat
N = left(N, len(N)-1)
c += 1
if c mod 3 = 0 and N<>"" then bloat = "," + bloat
wend
return bloat
end function
for i as ulongint = 0 to 65
print isqrt(i);" ";
next i
print
dim as string ns
for i as uinteger = 1 to 22 step 2
ns = str(isqrt(7^i))
print i, commatize(ns)
next i</syntaxhighlight>
{{out}}
<pre>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
1 2
3 18
5 129
7 907
9 6,352
11 44,467
13 311,269
15 2,178,889
17 15,252,229
19 106,765,608
21 747,359,260</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
include "NSLog.incl"
local fn IntSqrt( x as SInt64 ) as SInt64
SInt64 q = 1, z = x, r = 0, t
do
q = q * 4
until ( q > x )
while( q > 1 )
q = q / 4 : t = z - r - q : r = r / 2
if ( t > -1 ) then z = t : r = r + q
wend
end fn = r
SInt64 p
NSInteger n
CFNumberRef tempNum
CFStringRef tempStr
NSLog( @"Integer square root for numbers 0 to 65:" )
for n = 0 to 65
NSLog( @"%lld \b", fn IntSqrt( n ) )
next
NSLog( @"\n" )
NSLog( @"Integer square roots of odd powers of 7 from 1 to 21:" )
NSLog( @" n | 7 ^ n | fn IntSqrt(7 ^ n)" )
p = 7
for n = 1 to 21 step 2
tempNum = fn NumberWithLongLong( fn IntSqrt(p) )
tempStr = fn NumberDescriptionWithLocale( tempNum, fn LocaleCurrent )
NSLog( @"%2d | %18lld | %12s", n, p, fn StringUTF8String( tempStr ) )
p = p * 49
next
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
Integer square root for numbers 0 to 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
Integer square roots of odd powers of 7 from 1 to 21:
n | 7 ^ n | fn IntSqrt(7 ^ n)
1 | 7 | 2
3 | 343 | 18
5 | 16807 | 129
7 | 823543 | 907
9 | 40353607 | 6,352
11 | 1977326743 | 44,467
13 | 96889010407 | 311,269
15 | 4747561509943 | 2,178,889
17 | 232630513987207 | 15,252,229
19 | 11398895185373143 | 106,765,608
21 | 558545864083284007 | 747,359,260
</pre>
=={{header|Go}}==
Go's big.Int type already has a built-in integer square root function but, as the point of this task appears to be to compute it using a particular algorithm, we re-code it from the pseudo-code given in the task description.
<
import (
Line 585 ⟶ 2,619:
pow7.Mul(pow7, bi49)
}
}</
{{out}}
Line 635 ⟶ 2,669:
</pre>
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">import Data.Bits
isqrt :: Integer -> Integer
isqrt n = go n 0 (q `shiftR` 2)
where
q = head $ dropWhile (< n) $ iterate (`shiftL` 2) 1
go z r 0 = r
go z r q = let t = z - r - q
in if t >= 0
then go t (r `shiftR` 1 + q) (q `shiftR` 2)
else go z (r `shiftR` 1) (q `shiftR` 2)
main = do
print $ isqrt <$> [1..65]
mapM_ print $ zip [1,3..73] (isqrt <$> iterate (49 *) 7)</syntaxhighlight>
<pre>*Main> main
[0,1,1,1,2,2,2,2,3,3,3,3,3,3,3,3,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,7,8]
(1,2)
(3,18)
(5,129)
(7,907)
(9,6352)
(11,44467)
(13,311269)
(15,2178889)
(17,15252229)
(19,106765608)
(21,747359260)
(23,5231514822)
(25,36620603758)
(27,256344226312)
(29,1794409584184)
(31,12560867089291)
(33,87926069625040)
(35,615482487375282)
(37,4308377411626977)
(39,30158641881388842)
(41,211110493169721897)
(43,1477773452188053281)
(45,10344414165316372973)
(47,72410899157214610812)
(49,506876294100502275687)
(51,3548134058703515929815)
(53,24836938410924611508707)
(55,173858568876472280560953)
(57,1217009982135305963926677)
(59,8519069874947141747486745)
(61,59633489124629992232407216)
(63,417434423872409945626850517)
(65,2922040967106869619387953625)
(67,20454286769748087335715675381)
(69,143180007388236611350009727669)
(71,1002260051717656279450068093686)
(73,7015820362023593956150476655802)</pre>
=={{header|Icon}}==
<syntaxhighlight lang="icon">link numbers # For the "commas" procedure.
link printf
procedure main ()
write ("isqrt(i) for 0 <= i <= 65:")
write ()
roots_of_0_to_65()
write ()
write ()
write ("isqrt(7**i) for 1 <= i <= 73, i odd:")
write ()
printf ("%2s %84s %43s\n", "i", "7**i", "sqrt(7**i)")
write (repl("-", 131))
roots_of_odd_powers_of_7()
end
procedure roots_of_0_to_65 ()
local i
every i := 0 to 64 do writes (isqrt(i), " ")
write (isqrt(65))
end
procedure roots_of_odd_powers_of_7 ()
local i, power_of_7, root
every i := 1 to 73 by 2 do {
power_of_7 := 7^i
root := isqrt(power_of_7)
printf ("%2d %84s %43s\n", i, commas(power_of_7), commas(root))
}
end
procedure isqrt (x)
local q, z, r, t
q := find_a_power_of_4_greater_than_x (x)
z := x
r := 0
while 1 < q do {
q := ishift(q, -2)
t := z - r - q
r := ishift(r, -1)
if 0 <= t then {
z := t
r +:= q
}
}
return r
end
procedure find_a_power_of_4_greater_than_x (x)
local q
q := 1
while q <= x do q := ishift(q, 2)
return q
end</syntaxhighlight>
{{out}}
<pre>$ icont -s -u -o isqrt isqrt-in-Icon.icn && ./isqrt
isqrt(i) for 0 <= i <= 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
isqrt(7**i) for 1 <= i <= 73, i odd:
i 7**i sqrt(7**i)
-----------------------------------------------------------------------------------------------------------------------------------
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</pre>
=={{header|J}}==
Three implementations given. The floating point method is best for small square roots, Newton's method is fastest for extended integers. isqrt adapted from the page preamble. Note that the "floating point method" is exact when arbitrary precision integers or rational numbers are used.
<syntaxhighlight lang="j">
isqrt_float=: <.@:%:
isqrt_newton=: 9&$: :(x:@:<.@:-:@:(] + x:@:<.@:%)^:_&>~&:x:)
align=: (|.~ i.&' ')"1
comma=: (' ' -.~ [: }: [: , [: (|.) _3 (',' ,~ |.)\ |.)@":&>
While=: {{ u^:(0-.@:-:v)^:_ }}
isqrt=: 3 :0&>
y =. x: y
NB. q is a power of 4 that's greater than y. Append 0 0 under binary representation
q =. y (,&0 0x&.:#:@:])While>: 1x
z =. y NB. set z to the value of y.
r =. 0x NB. initialize r to zero.
while. 1 < q do. NB. perform while q > unity.
q =. _2&}.&.:#: q NB. integer divide by 4 (-2 drop under binary representation)
t =. (z - r) - q NB. compute value of t.
r =. }:&.:#: r NB. integer divide by two. (curtail under binary representation)
if. 0 <: t do.
z =. t NB. set z to value of t
r =. r + q NB. compute new value of r
end.
end.
NB. r is now the isqrt(y). (most recent value computed)
NB. Sidenote: Also, Z is now the remainder after square root
NB. ie. r^2 + z = y, so if z = 0 then x is a perfect square
NB. r , z
)
</syntaxhighlight>
The first line here shows that the simplest approach (the "floating point square root") is treated specially by J.
<pre> <.@%: 1000000000000000000000000000000000000000000000000x
1000000000000000000000000
(,. isqrt_float) 7x ^ 20 21x
79792266297612001 282475249
558545864083284007 747359260
(,. isqrt_newton) 7x ^ 20 21x
79792266297612001 282475249
558545864083284007 747359260
align comma (,. isqrt) 7 ^&x: 1 2 p. i. 37
7
2
343
18
16,807
129
823,543
907
40,353,607
6,352
1,977,326,743
44,467
96,889,010,407
311,269
4,747,561,509,943
2,178,889
232,630,513,987,207
15,252,229
11,398,895,185,373,143
106,765,608
558,545,864,083,284,007
747,359,260
27,368,747,340,080,916,343
5,231,514,822
1,341,068,619,663,964,900,807
36,620,603,758
65,712,362,363,534,280,139,543
256,344,226,312
3,219,905,755,813,179,726,837,607
1,794,409,584,184
157,775,382,034,845,806,615,042,743
12,560,867,089,291
7,730,993,719,707,444,524,137,094,407
87,926,069,625,040
378,818,692,265,664,781,682,717,625,943
615,482,487,375,282
18,562,115,921,017,574,302,453,163,671,207
4,308,377,411,626,977
909,543,680,129,861,140,820,205,019,889,143
30,158,641,881,388,842
44,567,640,326,363,195,900,190,045,974,568,007
211,110,493,169,721,897
2,183,814,375,991,796,599,109,312,252,753,832,343
1,477,773,452,188,053,281
107,006,904,423,598,033,356,356,300,384,937,784,807
10,344,414,165,316,372,973
5,243,338,316,756,303,634,461,458,718,861,951,455,543
72,410,899,157,214,610,812
256,923,577,521,058,878,088,611,477,224,235,621,321,607
506,876,294,100,502,275,687
12,589,255,298,531,885,026,341,962,383,987,545,444,758,743
3,548,134,058,703,515,929,815
616,873,509,628,062,366,290,756,156,815,389,726,793,178,407
24,836,938,410,924,611,508,707
30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943
173,858,568,876,472,280,560,953
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
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
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
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
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
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
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
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
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
NB. isqrt_float is exact for large integers
align comma (,.isqrt_float),7^73x
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
NB. Newton's method result matches isqrt
(isqrt_newton -: isqrt)7 ^&x: 1 2 p. i. 37
1
NB. An order of magnitude faster and one tenth the space, in j
timespacex 'isqrt_newton 7 ^&x: 1 2 p. i. 37'
0.038085 39552
timespacex 'isqrt 7 ^&x: 1 2 p. i. 37'
0.367744 319712
NB. but not as fast as isqrt_float, nor as space efficient
timespacex 'isqrt_float 7 ^&x: 1 2 p. i. 37'
0.0005145 152192</pre>
Note that isqrt_float (<code><.@%:</code>) is, mechanically, a different operation from floating point square root followed by floor. This difference is probably best thought of as a type issue. For example, <code><.%:7^73x</code> (without the <code>@</code>) produces a result which has the comma delimited integer representation of <tt>7,015,820,362,023,59<i>4,877,495,225,090</i></tt> rather than the <tt>7,015,820,362,023,59<b>3,956,150,476,655,802</b></tt> which we would get from integer square root.
=={{header|Java}}==
{{trans|Kotlin}}
<syntaxhighlight lang="java">import java.math.BigInteger;
public class Isqrt {
private static BigInteger isqrt(BigInteger x) {
if (x.compareTo(BigInteger.ZERO) < 0) {
throw new IllegalArgumentException("Argument cannot be negative");
}
var q = BigInteger.ONE;
while (q.compareTo(x) <= 0) {
q = q.shiftLeft(2);
}
var z = x;
var r = BigInteger.ZERO;
while (q.compareTo(BigInteger.ONE) > 0) {
q = q.shiftRight(2);
var t = z;
t = t.subtract(r);
t = t.subtract(q);
r = r.shiftRight(1);
if (t.compareTo(BigInteger.ZERO) >= 0) {
z = t;
r = r.add(q);
}
}
return r;
}
public static void main(String[] args) {
System.out.println("The integer square root of integers from 0 to 65 are:");
for (int i = 0; i <= 65; i++) {
System.out.printf("%s ", isqrt(BigInteger.valueOf(i)));
}
System.out.println();
System.out.println("The integer square roots of powers of 7 from 7^1 up to 7^73 are:");
System.out.println("power 7 ^ power integer square root");
System.out.println("----- --------------------------------------------------------------------------------- -----------------------------------------");
var pow7 = BigInteger.valueOf(7);
var bi49 = BigInteger.valueOf(49);
for (int i = 1; i < 74; i += 2) {
System.out.printf("%2d %,84d %,41d\n", i, pow7, isqrt(pow7));
pow7 = pow7.multiply(bi49);
}
}
}</syntaxhighlight>
{{out}}
<pre>The integer square root of integers from 0 to 65 are:
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
The integer square roots of powers of 7 from 7^1 up to 7^73 are:
power 7 ^ power integer square root
----- --------------------------------------------------------------------------------- -----------------------------------------
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</pre>
=={{header|jq}}==
{{trans|Julia}}
The following program takes advantage of the support for unbounded-precision
integer arithmetic provided by gojq, the Go implementation of jq, but it can also be run, with different numerical results, using the C implementation.<syntaxhighlight lang="jq"># For gojq
def idivide($j):
. as $i
| ($i % $j) as $mod
| ($i - $mod) / $j ;
# input should be non-negative
def isqrt:
. as $x
| 1 | until(. > $x; . * 4) as $q
| {$q, $x, r: 0}
| until( .q <= 1;
.q |= idivide(4)
| .t = .x - .r - .q
| .r |= idivide(2)
| if .t >= 0
then .x = .t
| .r += .q
else . end).r ;
def power($n):
. as $in
| reduce range(0;$n) as $i (1; . * $in);
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
## The task:
"The integer square roots of integers from 0 to 65 are:",
[range(0;66) | isqrt],
"",
"The integer square roots of odd powers of 7 from 7^1 up to 7^73 are:",
("power" + " "*16 + "7 ^ power" + " "*70 + "integer square root"),
(range( 1;74;2) as $i
| (7 | power($i)) as $p
| "\($i|lpad(2)) \($p|lpad(84)) \($p | isqrt | lpad(43))" )</syntaxhighlight>
{{out}}
Invocation: gojq -ncr -f isqrt.jq
<pre>
The integer square roots of integers from 0 to 65 are:
[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]
The integer square roots of odd powers of 7 from 7^1 up to 7^73 are:
power 7 ^ power integer square root
1 7 2
3 343 18
5 16807 129
7 823543 907
9 40353607 6352
11 1977326743 44467
13 96889010407 311269
15 4747561509943 2178889
17 232630513987207 15252229
19 11398895185373143 106765608
21 558545864083284007 747359260
23 27368747340080916343 5231514822
25 1341068619663964900807 36620603758
27 65712362363534280139543 256344226312
29 3219905755813179726837607 1794409584184
31 157775382034845806615042743 12560867089291
33 7730993719707444524137094407 87926069625040
35 378818692265664781682717625943 615482487375282
37 18562115921017574302453163671207 4308377411626977
39 909543680129861140820205019889143 30158641881388842
41 44567640326363195900190045974568007 211110493169721897
43 2183814375991796599109312252753832343 1477773452188053281
45 107006904423598033356356300384937784807 10344414165316372973
47 5243338316756303634461458718861951455543 72410899157214610812
49 256923577521058878088611477224235621321607 506876294100502275687
51 12589255298531885026341962383987545444758743 3548134058703515929815
53 616873509628062366290756156815389726793178407 24836938410924611508707
55 30226801971775055948247051683954096612865741943 173858568876472280560953
57 1481113296616977741464105532513750734030421355207 1217009982135305963926677
59 72574551534231909331741171093173785967490646405143 8519069874947141747486745
61 3556153025177363557255317383565515512407041673852007 59633489124629992232407216
63 174251498233690814305510551794710260107945042018748343 417434423872409945626850517
65 8538323413450849900970017037940802745289307058918668807 2922040967106869619387953625
67 418377847259091645147530834859099334519176045887014771543 20454286769748087335715675381
69 20500514515695490612229010908095867391439626248463723805607 143180007388236611350009727669
71 1004525211269079039999221534496697502180541686174722466474743 1002260051717656279450068093686
73 49221735352184872959961855190338177606846542622561400857262407 7015820362023593956150476655802
</pre>
=={{header|Julia}}==
{{trans|Go}}
Julia also has a built in isqrt() function which works on integer types, but the function integer_sqrt is shown for the task.
<
function integer_sqrt(x)
Line 670 ⟶ 3,233:
lpad(format(integer_sqrt(pow7^i), commas=true), 43))
end
</
<pre>
The integer square roots of integers from 0 to 65 are:
Line 716 ⟶ 3,279:
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
</pre>
=={{header|Kotlin}}==
{{trans|Go}}
<syntaxhighlight lang="scala">import java.math.BigInteger
fun isqrt(x: BigInteger): BigInteger {
if (x < BigInteger.ZERO) {
throw IllegalArgumentException("Argument cannot be negative")
}
var q = BigInteger.ONE
while (q <= x) {
q = q.shiftLeft(2)
}
var z = x
var r = BigInteger.ZERO
while (q > BigInteger.ONE) {
q = q.shiftRight(2)
var t = z
t -= r
t -= q
r = r.shiftRight(1)
if (t >= BigInteger.ZERO) {
z = t
r += q
}
}
return r
}
fun main() {
println("The integer square root of integers from 0 to 65 are:")
for (i in 0..65) {
print("${isqrt(BigInteger.valueOf(i.toLong()))} ")
}
println()
println("The integer square roots of powers of 7 from 7^1 up to 7^73 are:")
println("power 7 ^ power integer square root")
println("----- --------------------------------------------------------------------------------- -----------------------------------------")
var pow7 = BigInteger.valueOf(7)
val bi49 = BigInteger.valueOf(49)
for (i in (1..73).step(2)) {
println("%2d %,84d %,41d".format(i, pow7, isqrt(pow7)))
pow7 *= bi49
}
}</syntaxhighlight>
{{out}}
<pre>The integer square root of integers from 0 to 65 are:
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
The integer square roots of powers of 7 from 7^1 up to 7^73 are:
power 7 ^ power integer square root
----- --------------------------------------------------------------------------------- -----------------------------------------
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</pre>
=={{header|Lua}}==
{{trans|C}}
<syntaxhighlight lang="lua">function isqrt(x)
local q = 1
local r = 0
while q <= x do
q = q << 2
end
while q > 1 do
q = q >> 2
local t = x - r - q
r = r >> 1
if t >= 0 then
x = t
r = r + q
end
end
return r
end
print("Integer square root for numbers 0 to 65:")
for n=0,65 do
io.write(isqrt(n) .. ' ')
end
print()
print()
print("Integer square roots of oddd powers of 7 from 1 to 21:")
print(" n | 7 ^ n | isqrt(7 ^ n)")
local p = 7
local n = 1
while n <= 21 do
print(string.format("%2d | %18d | %12d", n, p, isqrt(p)))
----------------------
n = n + 2
p = p * 49
end</syntaxhighlight>
{{out}}
<pre>Integer square root for numbers 0 to 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
Integer square roots of oddd powers of 7 from 1 to 21:
n | 7 ^ n | isqrt(7 ^ n)
3 | 343 | 18
5 | 16807 | 129
7 | 823543 | 907
9 | 40353607 | 6352
11 | 1977326743 | 44467
13 | 96889010407 | 311269
15 | 4747561509943 | 2178889
17 | 232630513987207 | 15252229
19 | 11398895185373143 | 106765608
21 | 558545864083284007 | 747359260</pre>
=={{header|M2000 Interpreter}}==
Using various types up to 7^35
<syntaxhighlight lang="m2000 interpreter">
module integer_square_root (f=-2) {
function IntSqrt(x as long long) {
long long q=1, z=x, t, r
do q*=4&& : until (q>x)
while q>1&&
q|div 4&&:t=z-r-q:r|div 2&&
if t>-1&& then z=t:r+= q
end while
=r
}
long i
print #f, "The integer square root of integers from 0 to 65 are:"
for i=0 to 65
print #f, IntSqrt(i)+" ";
next
print #f
print #f, "Using Long Long Type"
print #f, "The integer square roots of powers of 7 from 7^1 up to 7^21 are:"
for i=1 to 21 step 2 {
print #f, "IntSqrt(7^"+i+")="+(IntSqrt(7&&^i))+" of 7^"+i+" ("+(7&&^I)+")"
}
print #f
function IntSqrt(x as decimal) {
decimal q=1, z=x, t, r
do q*=4 : until (q>x)
while q>1
q/=4:t=z-r-q:r/=2
if t>-1 then z=t:r+= q
end while
=r
}
print #f, "Using Decimal Type"
print #f, "The integer square roots of powers of 7 from 7^23 up to 7^33 are:"
decimal j,p
for i=23 to 33 step 2 {
p=1:for j=1 to i:p*=7@:next
print #f, "IntSqrt(7^"+i+")="+(IntSqrt(p))+" of 7^"+i+" ("+p+")"
}
print #f
function IntSqrt(x as double) {
double q=1, z=x, t, r
do q*=4 : until (q>x)
while q>1
q/=4:t=z-r-q:r/=2
if t>-1 then z=t:r+= q
end while
=r
}
print #f, "Using Double Type"
print #f, "The integer square roots of powers of 7 from 7^19 up to 7^35 are:"
for i=19 to 35 step 2 {
print #f, "IntSqrt(7^"+i+")="+(IntSqrt(7^i))+" of 7^"+i+" ("+(7^i)+")"
}
print #f
}
open "" for output as #f // f = -2 now, direct output to screen
integer_square_root
close #f
open "out.txt" for output as #f
integer_square_root f
close #f
win "notepad", dir$+"out.txt"
</syntaxhighlight>
{{out}}
<pre>
The integer square root of integers from 0 to 65 are:
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
Using Long Long Type
The integer square roots of powers of 7 from 7^1 up to 7^21 are:
IntSqrt(7^1)=2 of 7^1 (7)
IntSqrt(7^3)=18 of 7^3 (343)
IntSqrt(7^5)=129 of 7^5 (16807)
IntSqrt(7^7)=907 of 7^7 (823543)
IntSqrt(7^9)=6352 of 7^9 (40353607)
IntSqrt(7^11)=44467 of 7^11 (1977326743)
IntSqrt(7^13)=311269 of 7^13 (96889010407)
IntSqrt(7^15)=2178889 of 7^15 (4747561509943)
IntSqrt(7^17)=15252229 of 7^17 (232630513987207)
IntSqrt(7^19)=106765608 of 7^19 (11398895185373143)
IntSqrt(7^21)=747359260 of 7^21 (558545864083284007)
Using Decimal Type
The integer square roots of powers of 7 from 7^23 up to 7^33 are:
IntSqrt(7^23)=5231514822 of 7^23 (27368747340080916343)
IntSqrt(7^25)=36620603758 of 7^25 (1341068619663964900807)
IntSqrt(7^27)=256344226312 of 7^27 (65712362363534280139543)
IntSqrt(7^29)=1794409584184 of 7^29 (3219905755813179726837607)
IntSqrt(7^31)=12560867089291 of 7^31 (157775382034845806615042743)
IntSqrt(7^33)=87926069625040 of 7^33 (7730993719707444524137094407)
Using Double Type
The integer square roots of powers of 7 from 7^19 up to 7^35 are:
IntSqrt(7^19)=106765608 of 7^19 (1.13988951853731E+16)
IntSqrt(7^21)=747359260 of 7^21 (5.58545864083284E+17)
IntSqrt(7^23)=5231514822 of 7^23 (2.73687473400809E+19)
IntSqrt(7^25)=36620603758 of 7^25 (1.34106861966396E+21)
IntSqrt(7^27)=256344226312 of 7^27 (6.57123623635343E+22)
IntSqrt(7^29)=1794409584184 of 7^29 (3.21990575581318E+24)
IntSqrt(7^31)=12560867089291 of 7^31 (1.57775382034846E+26)
IntSqrt(7^33)=87926069625040 of 7^33 (7.73099371970744E+27)
IntSqrt(7^35)=615482487375282 of 7^35 (3.78818692265665E+29)
</pre>
=={{header|MAD}}==
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER
R INTEGER SQUARE ROOT OF X
INTERNAL FUNCTION(X)
ENTRY TO ISQRT.
Q = 1
FNDPW4 WHENEVER Q.LE.X
Q = Q * 4
TRANSFER TO FNDPW4
END OF CONDITIONAL
Z = X
R = 0
FNDRT WHENEVER Q.G.1
Q = Q / 4
T = Z - R - Q
R = R / 2
WHENEVER T.GE.0
Z = T
R = R + Q
END OF CONDITIONAL
TRANSFER TO FNDRT
END OF CONDITIONAL
FUNCTION RETURN R
END OF FUNCTION
R PRINT INTEGER SQUARE ROOTS OF 0..65
THROUGH SQ65, FOR N=0, 11, N.G.65
SQ65 PRINT FORMAT N11, ISQRT.(N), ISQRT.(N+1), ISQRT.(N+2),
0 ISQRT.(N+3), ISQRT.(N+4), ISQRT.(N+5), ISQRT.(N+6),
1 ISQRT.(N+7), ISQRT.(N+8), ISQRT.(N+9), ISQRT.(N+10)
VECTOR VALUES N11 = $11(I1,S1)*$
R MACHINE WORD SIZE ON IBM 704 IS 36 BITS
R PRINT UP TO AND INCLUDING ISQRT(7^12)
POW7 = 1
THROUGH SQ7P12, FOR I=0, 1, I.G.12
PRINT FORMAT SQ7, I, ISQRT.(POW7)
SQ7P12 POW7 = POW7 * 7
VECTOR VALUES SQ7 = $9HISQRT.(7^,I2,4H) = ,I6*$
END OF PROGRAM </syntaxhighlight>
{{out}}
<pre>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
ISQRT.(7^ 0) = 1
ISQRT.(7^ 1) = 2
ISQRT.(7^ 2) = 7
ISQRT.(7^ 3) = 18
ISQRT.(7^ 4) = 49
ISQRT.(7^ 5) = 129
ISQRT.(7^ 6) = 343
ISQRT.(7^ 7) = 907
ISQRT.(7^ 8) = 2401
ISQRT.(7^ 9) = 6352
ISQRT.(7^10) = 16807
ISQRT.(7^11) = 44467
ISQRT.(7^12) = 117649</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[ISqrt]
ISqrt[x_Integer?NonNegative] := Module[{q = 1, z, r, t},
While[q <= x,
q *= 4
];
z = x;
r = 0;
While[q > 1,
q = Quotient[q, 4];
t = z - r - q;
r /= 2;
If[t >= 0,
z = t;
r += q
];
];
r
]
ISqrt /@ Range[65]
Column[ISqrt /@ (7^Range[1, 73])]</syntaxhighlight>
{{out}}
<pre>{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}
2
7
18
49
129
343
907
2401
6352
16807
44467
117649
311269
823543
2178889
5764801
15252229
40353607
106765608
282475249
747359260
1977326743
5231514822
13841287201
36620603758
96889010407
256344226312
678223072849
1794409584184
4747561509943
12560867089291
33232930569601
87926069625040
232630513987207
615482487375282
1628413597910449
4308377411626977
11398895185373143
30158641881388842
79792266297612001
211110493169721897
558545864083284007
1477773452188053281
3909821048582988049
10344414165316372973
27368747340080916343
72410899157214610812
191581231380566414401
506876294100502275687
1341068619663964900807
3548134058703515929815
9387480337647754305649
24836938410924611508707
65712362363534280139543
173858568876472280560953
459986536544739960976801
1217009982135305963926677
3219905755813179726837607
8519069874947141747486745
22539340290692258087863249
59633489124629992232407216
157775382034845806615042743
417434423872409945626850517
1104427674243920646305299201
2922040967106869619387953625
7730993719707444524137094407
20454286769748087335715675381
54116956037952111668959660849
143180007388236611350009727669
378818692265664781682717625943
1002260051717656279450068093686
2651730845859653471779023381601
7015820362023593956150476655802</pre>
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">/* -*- Maxima -*- */
/*
The Rosetta Code integer square root task, in Maxima.
I have not tried to make the output conform quite to the task
description, because Maxima is not a general purpose programming
language. Perhaps someone else will care to do it.
I *do* check that the Rosetta Code routine gives the same results as
the built-in function.
*/
/* pow4gtx -- find a power of 4 greater than x. */
pow4gtx (x) := block (
[q],
q : 1, while q <= x do q : bit_lsh (q, 2),
q
) $
/* rosetta_code_isqrt -- find the integer square root. */
rosetta_code_isqrt (x) := block (
[q, z, r, t],
q : pow4gtx (x),
z : x,
r : 0,
while 1 < q do (
q : bit_rsh (q, 2),
t : z - r - q,
r : bit_rsh (r, 1),
if 0 <= t then (
z : t,
r : r + q
)
),
r
) $
for i : 0 thru 65 do (
display (rosetta_code_isqrt (i),
is (equal (rosetta_code_isqrt (i), isqrt (i))))
) $
for i : 1 thru 73 step 2 do (
display (7**i, rosetta_code_isqrt (7**i),
is (equal (rosetta_code_isqrt (7**i), isqrt (7**i))))
) $</syntaxhighlight>
{{out}}
<pre style="height:30em;overflow:auto">$ maxima -q -b isqrt.mac
(%i1) batch("isqrt.mac")
read and interpret /home/trashman/src/chemoelectric/rosettacode-contributions/isqrt.mac
(%i2) pow4gtx(x):=block([q],q:1,while q <= x do q:bit_lsh(q,2),q)
(%i3) rosetta_code_isqrt(x):=block([q,z,r,t],q:pow4gtx(x),z:x,r:0,
while 1 < q do
(q:bit_rsh(q,2),t:z-r-q,r:bit_rsh(r,1),
if 0 <= t then (z:t,r:r+q)),r)
(%i4) for i from 0 thru 65 do
display(rosetta_code_isqrt(i),
is(equal(rosetta_code_isqrt(i),isqrt(i))))
rosetta_code_isqrt(0) = 0
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(1) = 1
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(2) = 1
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(3) = 1
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(4) = 2
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(5) = 2
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(6) = 2
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(7) = 2
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(8) = 2
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(9) = 3
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(10) = 3
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(11) = 3
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(12) = 3
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(13) = 3
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(14) = 3
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(15) = 3
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(16) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(17) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(18) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(19) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(20) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(21) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(22) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(23) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(24) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(25) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(26) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(27) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(28) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(29) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(30) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(31) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(32) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(33) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(34) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(35) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(36) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(37) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(38) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(39) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(40) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(41) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(42) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(43) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(44) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(45) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(46) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(47) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(48) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(49) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(50) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(51) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(52) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(53) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(54) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(55) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(56) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(57) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(58) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(59) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(60) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(61) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(62) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(63) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(64) = 8
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(65) = 8
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
(%i5) for i step 2 thru 73 do
display(7^i,rosetta_code_isqrt(7^i),
is(equal(rosetta_code_isqrt(7^i),isqrt(7^i))))
1
7 = 7
rosetta_code_isqrt(7) = 2
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
3
7 = 343
rosetta_code_isqrt(343) = 18
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
5
7 = 16807
rosetta_code_isqrt(16807) = 129
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
7
7 = 823543
rosetta_code_isqrt(823543) = 907
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
9
7 = 40353607
rosetta_code_isqrt(40353607) = 6352
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
11
7 = 1977326743
rosetta_code_isqrt(1977326743) = 44467
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
13
7 = 96889010407
rosetta_code_isqrt(96889010407) = 311269
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
15
7 = 4747561509943
rosetta_code_isqrt(4747561509943) = 2178889
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
17
7 = 232630513987207
rosetta_code_isqrt(232630513987207) = 15252229
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
19
7 = 11398895185373143
rosetta_code_isqrt(11398895185373143) = 106765608
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
21
7 = 558545864083284007
rosetta_code_isqrt(558545864083284007) = 747359260
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
23
7 = 27368747340080916343
rosetta_code_isqrt(27368747340080916343) = 5231514822
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
25
7 = 1341068619663964900807
rosetta_code_isqrt(1341068619663964900807) = 36620603758
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
27
7 = 65712362363534280139543
rosetta_code_isqrt(65712362363534280139543) = 256344226312
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
29
7 = 3219905755813179726837607
rosetta_code_isqrt(3219905755813179726837607) = 1794409584184
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
31
7 = 157775382034845806615042743
rosetta_code_isqrt(157775382034845806615042743) = 12560867089291
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
33
7 = 7730993719707444524137094407
rosetta_code_isqrt(7730993719707444524137094407) = 87926069625040
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
35
7 = 378818692265664781682717625943
rosetta_code_isqrt(378818692265664781682717625943) = 615482487375282
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
37
7 = 18562115921017574302453163671207
rosetta_code_isqrt(18562115921017574302453163671207) = 4308377411626977
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
39
7 = 909543680129861140820205019889143
rosetta_code_isqrt(909543680129861140820205019889143) = 30158641881388842
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
41
7 = 44567640326363195900190045974568007
rosetta_code_isqrt(44567640326363195900190045974568007) = 211110493169721897
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
43
7 = 2183814375991796599109312252753832343
rosetta_code_isqrt(2183814375991796599109312252753832343) = 1477773452188053281
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
45
7 = 107006904423598033356356300384937784807
rosetta_code_isqrt(107006904423598033356356300384937784807) =
10344414165316372973
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
47
7 = 5243338316756303634461458718861951455543
rosetta_code_isqrt(5243338316756303634461458718861951455543) =
72410899157214610812
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
49
7 = 256923577521058878088611477224235621321607
rosetta_code_isqrt(256923577521058878088611477224235621321607) =
506876294100502275687
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
51
7 = 12589255298531885026341962383987545444758743
rosetta_code_isqrt(12589255298531885026341962383987545444758743) =
3548134058703515929815
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
53
7 = 616873509628062366290756156815389726793178407
rosetta_code_isqrt(616873509628062366290756156815389726793178407) =
24836938410924611508707
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
55
7 = 30226801971775055948247051683954096612865741943
rosetta_code_isqrt(30226801971775055948247051683954096612865741943) =
173858568876472280560953
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
57
7 = 1481113296616977741464105532513750734030421355207
rosetta_code_isqrt(1481113296616977741464105532513750734030421355207) =
1217009982135305963926677
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
59
7 = 72574551534231909331741171093173785967490646405143
rosetta_code_isqrt(72574551534231909331741171093173785967490646405143) =
8519069874947141747486745
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
61
7 = 3556153025177363557255317383565515512407041673852007
rosetta_code_isqrt(3556153025177363557255317383565515512407041673852007) =
59633489124629992232407216
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
63
7 = 174251498233690814305510551794710260107945042018748343
rosetta_code_isqrt(174251498233690814305510551794710260107945042018748343) =
417434423872409945626850517
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
65
7 = 8538323413450849900970017037940802745289307058918668807
rosetta_code_isqrt(8538323413450849900970017037940802745289307058918668807) =
2922040967106869619387953625
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
67
7 = 418377847259091645147530834859099334519176045887014771543
rosetta_code_isqrt(418377847259091645147530834859099334519176045887014771543
) = 20454286769748087335715675381
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
69
7 = 20500514515695490612229010908095867391439626248463723805607
rosetta_code_isqrt(20500514515695490612229010908095867391439626248463723805607
) = 143180007388236611350009727669
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
71
7 = 1004525211269079039999221534496697502180541686174722466474743
rosetta_code_isqrt(10045252112690790399992215344966975021805416861747224664747\
43) = 1002260051717656279450068093686
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
73
7 = 49221735352184872959961855190338177606846542622561400857262407
rosetta_code_isqrt(49221735352184872959961855190338177606846542622561400857262\
407) = 7015820362023593956150476655802
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
(%o6) /home/trashman/src/chemoelectric/rosettacode-contributions/isqrt.mac</pre>
=={{header|Mercury}}==
{{trans|Prolog}}
{{works with|Mercury|20.06.1}}
<syntaxhighlight lang="mercury">:- module isqrt_in_mercury.
:- interface.
:- import_module io.
:- pred main(io, io).
:- mode main(di, uo) is det.
:- implementation.
:- import_module char.
:- import_module exception.
:- import_module int.
:- import_module integer. % Integers of arbitrary size.
:- import_module list.
:- import_module string.
:- func four = integer.
four = integer(4).
:- func seven = integer.
seven = integer(7).
%% Find a power of 4 greater than X.
:- func pow4gtx(integer) = integer.
pow4gtx(X) = Q :- pow4gtx_(X, one, Q).
%% The tail recursion for pow4gtx.
:- pred pow4gtx_(integer, integer, integer).
:- mode pow4gtx_(in, in, out) is det.
pow4gtx_(X, A, Q) :- if (X < A) then (Q = A)
else (A1 = A * four,
pow4gtx_(X, A1, Q)).
%% Integer square root function.
:- func isqrt(integer) = integer.
isqrt(X) = Root :- isqrt(X, Root, _).
%% Integer square root and remainder.
:- pred isqrt(integer, integer, integer).
:- mode isqrt(in, out, out) is det.
isqrt(X, Root, Remainder) :-
Q = pow4gtx(X),
isqrt_(X, Q, zero, X, Root, Remainder).
%% The tail recursion for isqrt.
:- pred isqrt_(integer, integer, integer, integer, integer, integer).
:- mode isqrt_(in, in, in, in, out, out) is det.
isqrt_(X, Q, R0, Z0, R, Z) :-
if (X < zero) then throw("isqrt of a negative integer")
else if (Q = one) then (R = R0, Z = Z0)
else (Q1 = Q // four,
T = Z0 - R0 - Q1,
(if (T >= zero)
then (R1 = (R0 // two) + Q1,
isqrt_(X, Q1, R1, T, R, Z))
else (R1 is R0 // two,
isqrt_(X, Q1, R1, Z0, R, Z)))).
%% Insert a character, every three digits, into (what presumably is)
%% an integer numeral. (The name "commas" is not very good.)
:- func commas(string, char) = string.
commas(S, Comma) = T :-
RCL = to_rev_char_list(S),
commas_(RCL, Comma, 0, [], CL),
T = from_char_list(CL).
%% The tail recursion for commas.
:- pred commas_(list(char), char, int, list(char), list(char)).
:- mode commas_(in, in, in, in, out) is det.
commas_([], _, _, L, CL) :- L = CL.
commas_([C | Tail], Comma, I, L, CL) :-
if (I = 3) then commas_([C | Tail], Comma, 0, [Comma | L], CL)
else (I1 = I + 1,
commas_(Tail, Comma, I1, [C | L], CL)).
:- pred roots_m_to_n(integer, integer, io, io).
:- mode roots_m_to_n(in, in, di, uo) is det.
roots_m_to_n(M, N, !IO) :-
if (N < M) then true
else (write_string(to_string(isqrt(M)), !IO),
(if (M \= N) then write_string(" ", !IO)
else true),
M1 = M + one,
roots_m_to_n(M1, N, !IO)).
:- pred roots_of_odd_powers_of_7(integer, integer, io, io).
:- mode roots_of_odd_powers_of_7(in, in, di, uo) is det.
roots_of_odd_powers_of_7(M, N, !IO) :-
if (N < M) then true
else (Pow7 = pow(seven, M),
Isqrt = isqrt(Pow7),
format("%2s %84s %43s",
[s(commas(to_string(M), (','))),
s(commas(to_string(Pow7), (','))),
s(commas(to_string(Isqrt), (',')))],
!IO),
nl(!IO),
M1 = M + two,
roots_of_odd_powers_of_7(M1, N, !IO)).
main(!IO) :-
write_string("isqrt(i) for 0 <= i <= 65:", !IO),
nl(!IO), nl(!IO),
roots_m_to_n(zero, integer(65), !IO),
nl(!IO), nl(!IO), nl(!IO),
write_string("isqrt(7**i) for 1 <= i <= 73, i odd:", !IO),
nl(!IO), nl(!IO),
format("%2s %84s %43s", [s("i"), s("7**i"), s("isqrt(7**i)")], !IO),
nl(!IO),
write_string(duplicate_char(('-'), 131), !IO),
nl(!IO),
roots_of_odd_powers_of_7(one, integer(73), !IO).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Instructions for GNU Emacs--
%%% local variables:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%</syntaxhighlight>
{{out}}
<pre>$ mmc --warn-non-tail-recursion=self-and-mutual -o isqrt isqrt_in_mercury.m && ./isqrt
isqrt(i) for 0 <= i <= 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
isqrt(7**i) for 1 <= i <= 73, i odd:
i 7**i isqrt(7**i)
-----------------------------------------------------------------------------------------------------------------------------------
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</pre>
=={{header|Modula-2}}==
{{works with|TopSpeed (JPI) Modula-2 under DOSBox-X}}
Uses the algorithm in the task description, with two modifications:
(1) As noted in the ALGOL-M solution, the original algorithm can lead to integer overflow when trying to find a power of 4 greater than the argument X. The modified algorithm avoids overflow.
(2) In the original algorithm, the variable t can be negative. In the modified algorithm, all variables remain non-negative, and can therefore be declared as unsigned integers if desired.
TopSpeed Modula-2 supports no integers larger than unsigned 32-bit, which means that the second part of the task stops at 7^11. There seems to be no option to insert commas into long numbers as requested.
<syntaxhighlight lang="modula2">
MODULE IntSqrt;
IMPORT IO;
(* Procedure to find integer square root of a 32-bit unsigned integer. *)
PROCEDURE Isqrt( X : LONGCARD) : LONGCARD;
VAR
Xdiv4, q, r, s, z : LONGCARD;
BEGIN
Xdiv4 := X DIV 4;
q := 1;
WHILE q <= Xdiv4 DO q := 4*q; END;
z := X;
r := 0;
REPEAT
s := q + r;
r := r DIV 2;
IF z >= s THEN
DEC(z, s);
INC(r, q);
END;
q := q DIV 4;
UNTIL q = 0;
RETURN r;
END Isqrt;
(* Main program *)
CONST (* constants for Part 1 of the task *)
Max_n = 65;
NrPerLine = 22;
VAR
n : LONGCARD;
arr_n, arr_i : ARRAY[0..NrPerLine - 1] OF LONGCARD; (* for display *)
j, k : INTEGER;
BEGIN
(* Part 1 *)
k := 0; (* index into arrays *)
FOR n := 0 TO Max_n DO
arr_n[k] := n;
arr_i[k] := Isqrt(n);
INC(k);
IF (k = NrPerLine) OR (n = Max_n) THEN
IO.WrStr( 'Number: ');
FOR j := 0 TO k - 1 DO IO.WrLngCard(arr_n[j], 3); END;
IO.WrLn();
IO.WrStr( 'Isqrt: ');
FOR j := 0 TO k - 1 DO IO.WrLngCard(arr_i[j], 3); END;
IO.WrLn();
k := 0;
END;
END;
IO.WrLn();
(* Part 2 *)
IO.WrStr( 'Isqrt of odd powers of 7'); IO.WrLn();
n := 7;
FOR k := 1 TO 11 BY 2 DO
IF k > 1 THEN n := n*49; END;
IO.WrInt( k, 2); IO.WrStr( ' --> ');
IO.WrLngCard( n, 10); IO.WrStr(' --> ');
IO.WrLngCard( Isqrt(n), 5); IO.WrLn();
END;
END IntSqrt.
</syntaxhighlight>
{{out}}
<pre>
Number: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Isqrt: 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4
Number: 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
Isqrt: 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6
Number: 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
Isqrt: 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
Isqrt of odd powers of 7
1 --> 7 --> 2
3 --> 343 --> 18
5 --> 16807 --> 129
7 --> 823543 --> 907
9 --> 40353607 --> 6352
11 --> 1977326743 --> 44467
</pre>
=={{header|Nim}}==
{{libheader|bignum}}
This Nim implementation provides an <code>isqrt</code> function for signed integers and for big integers.
<syntaxhighlight lang="nim">import strformat, strutils
import bignum
func isqrt*[T: SomeSignedInt | Int](x: T): T =
## Compute integer square root for signed integers
## and for big integers.
when T is Int:
result = newInt()
var q = newInt(1)
else:
result = 0
var q = T(1)
while q <= x:
q = q shl 2
var z = x
while q > 1:
q = q shr 2
let t = z - result - q
result = result shr 1
if t >= 0:
z = t
result += q
when isMainModule:
echo "Integer square root for numbers 0 to 65:"
for n in 0..65:
stdout.write ' ', isqrt(n)
echo "\n"
echo "Integer square roots of odd powers of 7 from 7^1 to 7^73:"
echo " n" & repeat(' ', 82) & "7^n" & repeat(' ', 34) & "isqrt(7^n)"
echo repeat("—", 131)
var x = newInt(7)
for n in countup(1, 73, 2):
echo &"{n:>2} {insertSep($x, ','):>82} {insertSep($isqrt(x), ','):>41}"
x *= 49</syntaxhighlight>
{{out}}
<pre>Integer square root for numbers 0 to 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
Integer square roots of odd powers of 7 from 7^1 to 7^73:
n 7^n isqrt(7^n)
———————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
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</pre>
=={{header|ObjectIcon}}==
{{trans|Icon}}
The only changes needed to make the Icon version work in Object Icon were to "import io" and to import the IPL modules in a different way. ("write" and "writes" are supported by the io module, presumably for compatibility with Icon and to ease migration of the IPL.)
<syntaxhighlight lang="objecticon"># -*- ObjectIcon -*-
import io
import ipl.numbers # For the "commas" procedure.
import ipl.printf
procedure main ()
write ("isqrt(i) for 0 <= i <= 65:")
write ()
roots_of_0_to_65()
write ()
write ()
write ("isqrt(7**i) for 1 <= i <= 73, i odd:")
write ()
printf ("%2s %84s %43s\n", "i", "7**i", "sqrt(7**i)")
write (repl("-", 131))
roots_of_odd_powers_of_7()
end
procedure roots_of_0_to_65 ()
local i
every i := 0 to 64 do writes (isqrt(i), " ")
write (isqrt(65))
end
procedure roots_of_odd_powers_of_7 ()
local i, power_of_7, root
every i := 1 to 73 by 2 do {
power_of_7 := 7^i
root := isqrt(power_of_7)
printf ("%2d %84s %43s\n", i, commas(power_of_7), commas(root))
}
end
procedure isqrt (x)
local q, z, r, t
q := find_a_power_of_4_greater_than_x (x)
z := x
r := 0
while 1 < q do {
q := ishift(q, -2)
t := z - r - q
r := ishift(r, -1)
if 0 <= t then {
z := t
r +:= q
}
}
return r
end
procedure find_a_power_of_4_greater_than_x (x)
local q
q := 1
while q <= x do q := ishift(q, 2)
return q
end</syntaxhighlight>
{{out}}
<pre>$ oit -s -o isqrt isqrt-in-OI.icn && ./isqrt
isqrt(i) for 0 <= i <= 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
isqrt(7**i) for 1 <= i <= 73, i odd:
i 7**i sqrt(7**i)
-----------------------------------------------------------------------------------------------------------------------------------
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</pre>
=={{header|OCaml}}==
{{trans|Scheme}}
{{libheader|Zarith}}
<syntaxhighlight lang="ocaml">(* The Rosetta Code integer square root task, in OCaml, using Zarith
for large integers.
Compile with, for example:
ocamlfind ocamlc -package zarith -linkpkg -o isqrt isqrt.ml
Translated from the Scheme. *)
let find_a_power_of_4_greater_than_x x =
let open Z in
let rec loop q =
if x < q then q else loop (q lsl 2)
in
loop one
let isqrt x =
let open Z in
let rec loop q z r =
if q = one then
r
else
let q = q asr 2 in
let t = z - r - q in
let r = r asr 1 in
if t < zero then
loop q z r
else
loop q t (r + q)
in
let q0 = find_a_power_of_4_greater_than_x x in
let z0 = x in
let r0 = zero in
loop q0 z0 r0
let insert_separators s sep =
let rec loop revchars i newchars =
match revchars with
| [] -> newchars
| revchars when i = 3 -> loop revchars 0 (sep :: newchars)
| c :: tail -> loop tail (i + 1) (c :: newchars)
in
let revchars = List.rev (List.of_seq (String.to_seq s)) in
String.of_seq (List.to_seq (loop revchars 0 []))
let commas s = insert_separators s ','
let main () =
Printf.printf "isqrt(i) for 0 <= i <= 65:\n\n";
for i = 0 to 64 do
Printf.printf "%s " Z.(to_string (isqrt (of_int i)))
done;
Printf.printf "%s\n" Z.(to_string (isqrt (of_int 65)));
Printf.printf "\n\n";
Printf.printf "isqrt(7**i) for 1 <= i <= 73, i odd:\n\n";
Printf.printf "%2s %84s %43s\n" "i" "7**i" "isqrt(7**i)";
for i = 1 to 131 do Printf.printf "-" done;
Printf.printf "\n";
for j = 0 to 36 do
let i = j + j + 1 in
let power = Z.(of_int 7 ** i) in
let root = isqrt power in
Printf.printf "%2d %84s %43s\n"
i (commas (Z.to_string power)) (commas (Z.to_string root))
done
;;
main ()</syntaxhighlight>
{{out}}
<pre>$ ocamlfind ocamlc -package zarith -linkpkg -o isqrt isqrt.ml && ./isqrt
isqrt(i) for 0 <= i <= 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
isqrt(7**i) for 1 <= i <= 73, i odd:
i 7**i isqrt(7**i)
-----------------------------------------------------------------------------------------------------------------------------------
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</pre>
=={{header|Ol}}==
<syntaxhighlight lang="scheme">
(print "Integer square roots of 0..65")
(for-each (lambda (x)
(display (isqrt x))
(display " "))
(iota 66))
(print)
(print "Integer square roots of 7^n")
(for-each (lambda (x)
(print "x: " x ", isqrt: " (isqrt x)))
(map (lambda (i)
(expt 7 i))
(iota 73 1)))
(print)
</syntaxhighlight>
{{Out}}
<pre>
Integer square roots of 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
Integer square roots of 7^n
x: 7, isqrt: 2
x: 49, isqrt: 7
x: 343, isqrt: 18
x: 2401, isqrt: 49
x: 16807, isqrt: 129
x: 117649, isqrt: 343
x: 823543, isqrt: 907
x: 5764801, isqrt: 2401
x: 40353607, isqrt: 6352
x: 282475249, isqrt: 16807
x: 1977326743, isqrt: 44467
x: 13841287201, isqrt: 117649
x: 96889010407, isqrt: 311269
x: 678223072849, isqrt: 823543
x: 4747561509943, isqrt: 2178889
x: 33232930569601, isqrt: 5764801
x: 232630513987207, isqrt: 15252229
x: 1628413597910449, isqrt: 40353607
x: 11398895185373143, isqrt: 106765608
x: 79792266297612001, isqrt: 282475249
x: 558545864083284007, isqrt: 747359260
x: 3909821048582988049, isqrt: 1977326743
x: 27368747340080916343, isqrt: 5231514822
x: 191581231380566414401, isqrt: 13841287201
x: 1341068619663964900807, isqrt: 36620603758
x: 9387480337647754305649, isqrt: 96889010407
x: 65712362363534280139543, isqrt: 256344226312
x: 459986536544739960976801, isqrt: 678223072849
x: 3219905755813179726837607, isqrt: 1794409584184
x: 22539340290692258087863249, isqrt: 4747561509943
x: 157775382034845806615042743, isqrt: 12560867089291
x: 1104427674243920646305299201, isqrt: 33232930569601
x: 7730993719707444524137094407, isqrt: 87926069625040
x: 54116956037952111668959660849, isqrt: 232630513987207
x: 378818692265664781682717625943, isqrt: 615482487375282
x: 2651730845859653471779023381601, isqrt: 1628413597910449
x: 18562115921017574302453163671207, isqrt: 4308377411626977
x: 129934811447123020117172145698449, isqrt: 11398895185373143
x: 909543680129861140820205019889143, isqrt: 30158641881388842
x: 6366805760909027985741435139224001, isqrt: 79792266297612001
x: 44567640326363195900190045974568007, isqrt: 211110493169721897
x: 311973482284542371301330321821976049, isqrt: 558545864083284007
x: 2183814375991796599109312252753832343, isqrt: 1477773452188053281
x: 15286700631942576193765185769276826401, isqrt: 3909821048582988049
x: 107006904423598033356356300384937784807, isqrt: 10344414165316372973
x: 749048330965186233494494102694564493649, isqrt: 27368747340080916343
x: 5243338316756303634461458718861951455543, isqrt: 72410899157214610812
x: 36703368217294125441230211032033660188801, isqrt: 191581231380566414401
x: 256923577521058878088611477224235621321607, isqrt: 506876294100502275687
x: 1798465042647412146620280340569649349251249, isqrt: 1341068619663964900807
x: 12589255298531885026341962383987545444758743, isqrt: 3548134058703515929815
x: 88124787089723195184393736687912818113311201, isqrt: 9387480337647754305649
x: 616873509628062366290756156815389726793178407, isqrt: 24836938410924611508707
x: 4318114567396436564035293097707728087552248849, isqrt: 65712362363534280139543
x: 30226801971775055948247051683954096612865741943, isqrt: 173858568876472280560953
x: 211587613802425391637729361787678676290060193601, isqrt: 459986536544739960976801
x: 1481113296616977741464105532513750734030421355207, isqrt: 1217009982135305963926677
x: 10367793076318844190248738727596255138212949486449, isqrt: 3219905755813179726837607
x: 72574551534231909331741171093173785967490646405143, isqrt: 8519069874947141747486745
x: 508021860739623365322188197652216501772434524836001, isqrt: 22539340290692258087863249
x: 3556153025177363557255317383565515512407041673852007, isqrt: 59633489124629992232407216
x: 24893071176241544900787221684958608586849291716964049, isqrt: 157775382034845806615042743
x: 174251498233690814305510551794710260107945042018748343, isqrt: 417434423872409945626850517
x: 1219760487635835700138573862562971820755615294131238401, isqrt: 1104427674243920646305299201
x: 8538323413450849900970017037940802745289307058918668807, isqrt: 2922040967106869619387953625
x: 59768263894155949306790119265585619217025149412430681649, isqrt: 7730993719707444524137094407
x: 418377847259091645147530834859099334519176045887014771543, isqrt: 20454286769748087335715675381
x: 2928644930813641516032715844013695341634232321209103400801, isqrt: 54116956037952111668959660849
x: 20500514515695490612229010908095867391439626248463723805607, isqrt: 143180007388236611350009727669
x: 143503601609868434285603076356671071740077383739246066639249, isqrt: 378818692265664781682717625943
x: 1004525211269079039999221534496697502180541686174722466474743, isqrt: 1002260051717656279450068093686
x: 7031676478883553279994550741476882515263791803223057265323201, isqrt: 2651730845859653471779023381601
x: 49221735352184872959961855190338177606846542622561400857262407, isqrt: 7015820362023593956150476655802
</pre>
Line 721 ⟶ 5,046:
{{libheader|Velthuis.BigIntegers}}[https://github.com/rvelthuis/DelphiBigNumbers]
{{trans|C++}}
<syntaxhighlight lang="pascal">
//************************************************//
// //
Line 818 ⟶ 5,143:
CloseFile(f);
end.
</syntaxhighlight>
=={{header|
{{trans|Julia}}
<syntaxhighlight lang="perl"># 20201029 added Perl programming solution
use strict;
use warnings;
use bigint;
use CLDR::Number 'decimal_formatter';
sub integer_sqrt {
( my $x = $_[0]
my
while ($q <= $x) {
}
my ($z, $r) =
while ($q > 1)
$q >>=
my $t
if ($t >= 0)
$z =
}
print map { ( integer_sqrt $_ ) . ' ' } (0..65);
my $cldr = CLDR::Number->new();
my $decf = $cldr->decimal_formatter;
print "\nThe integer square roots of odd powers of 7 from 7^1 up to 7^73 are:\n";
print "power", " "x36, "7 ^ power", " "x60, "integer square root\n";
print "----- ", "-"x79, " ------------------------------------------\n";
for (my $i =
printf("%2s ", $i);
printf("%82s", $decf->format( 7**$i ) );
printf("%44s", $decf->format( integer_sqrt(7**$i) ) ) ;
print "\n";
}</syntaxhighlight>
{{out}}
<pre>
The integer square roots of integers from 0 to 65 are:
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
The integer square roots of odd powers of 7 from 7^1 up to 7^73 are:
power 7 ^ power integer square root
----- ------------------------------------------------------------------------------- ------------------------------------------
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
</pre>
=={{header|Phix}}==
See also [[Integer_roots#Phix]] for a simpler and shorter example using the mpz_root() routine, or better yet just use mpz_root() directly (that is, rather than the isqrt() below).
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">isqrt</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">crash</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"Argument cannot be negative."</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">z</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)<=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)></span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_fdiv_q_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_fdiv_q_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">>=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">mpz_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">star</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"*"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">))&</span><span style="color: #000000;">star</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The integer square roots of integers from 0 to 65 are:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">65</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s "</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">trim</span><span style="color: #0000FF;">(</span><span style="color: #000000;">isqrt</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)))})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n\npower 7 ^ power integer square root\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"----- --------------------------------------------------------- ----------------------------------------------------------\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">pow7</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">7</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9000</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">73</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;"><</span><span style="color: #000000;">100</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;"><</span><span style="color: #000000;">1000</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">or</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%4d %58s %61s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pow7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)),</span><span style="color: #000000;">isqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pow7</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pow7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pow7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
Perfect squares are denoted with an asterisk.
<pre style="font-size: 11px">
The integer square roots of integers from 0 to 65 are:
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
power 7 ^ power integer square root
Line 912 ⟶ 5,332:
85 681,292,175,541,205,...,256,581,907,552,807 (72 digits) 825,404,249,771,713,805,347,147,428,078,522,216
95 192,448,176,927,753,...,224,874,137,973,943 (81 digits) 13,872,569,225,913,193,926,469,506,823,715,722,892,042
100 3,234,476,509,624,75...,459,636,928,060,001 (85 digits) 1,798,465,042,647,41...,569,649,349,251,249 (43 digits)*
200 10,461,838,291,314,3...,534,637,456,120,001 (170 digits) 3,234,476,509,624,75...,459,636,928,060,001 (85 digits)*
300 33,838,570,200,749,1...,841,001,584,180,001 (254 digits) 5,817,092,933,824,34...,721,127,496,191,249 (127 digits)*
400 109,450,060,433,611,...,994,729,312,240,001 (339 digits) 10,461,838,291,314,3...,534,637,456,120,001 (170 digits)*
500 354,013,649,449,525,...,611,820,640,300,001 (423 digits) 18,815,250,448,759,0...,761,742,043,131,249 (212 digits)*
600 1,145,048,833,231,02...,308,275,568,360,001 (508 digits) 33,838,570,200,749,1...,841,001,584,180,001 (254 digits)*
700 3,703,633,553,458,98...,700,094,096,420,001 (592 digits) 60,857,485,599,217,6...,075,492,990,071,249 (296 digits)*
800 11,979,315,728,921,1...,403,276,224,480,001 (677 digits) 109,450,060,433,611,...,994,729,312,240,001 (339 digits)*
900 38,746,815,326,573,9...,033,821,952,540,001 (761 digits) 196,842,107,605,496,...,046,380,337,011,249 (381 digits)*
1000 125,325,663,996,571,...,207,731,280,600,001 (846 digits) 354,013,649,449,525,...,611,820,640,300,001 (423 digits)*
2000 15,706,522,056,181,6...,351,822,561,200,001 (1,691 digits) 125,325,663,996,571,...,207,731,280,600,001 (846 digits)*
3000 1,968,430,305,767,76...,432,273,841,800,001 (2,536 digits) 44,366,995,681,111,4...,787,731,920,900,001 (1,268 digits)*
4000 246,694,835,101,319,...,449,085,122,400,001 (3,381 digits) 15,706,522,056,181,6...,351,822,561,200,001 (1,691 digits)*
5000 30,917,194,013,597,6...,402,256,403,000,001 (4,226 digits) 5,560,323,193,268,32...,900,003,201,500,001 (2,113 digits)*
6000 3,874,717,868,664,96...,291,787,683,600,001 (5,071 digits) 1,968,430,305,767,76...,432,273,841,800,001 (2,536 digits)*
7000 485,601,589,689,818,...,117,678,964,200,001 (5,916 digits) 696,851,196,231,891,...,948,634,482,100,001 (2,958 digits)*
8000 60,858,341,665,667,3...,879,930,244,800,001 (6,761 digits) 246,694,835,101,319,...,449,085,122,400,001 (3,381 digits)*
9000 7,627,112,078,979,99...,578,541,525,400,001 (7,606 digits) 87,333,338,874,567,2...,933,625,762,700,001 (3,803 digits)*
</pre>
<small>(Note that pre-0.8.2 the "(NNN digits)" count includes commas)</small>
=={{header|Prolog}}==
{{works with|SWI-Prolog|8.5.9}}
<syntaxhighlight lang="prolog">%%% -*- Prolog -*-
%%%
%%% The Rosetta Code integer square root task, for SWI Prolog.
%%%
%% pow4gtx/2 -- Find a power of 4 greater than X.
pow4gtx(X, Q) :- pow4gtx(X, 1, Q), !.
pow4gtx(X, A, Q) :- X < A, Q is A.
pow4gtx(X, A, Q) :- A1 is A * 4,
pow4gtx(X, A1, Q).
%% isqrt/2 -- Find integer square root.
%% isqrt/3 -- Find integer square root and remainder.
isqrt(X, R) :- isqrt(X, R, _).
isqrt(X, R, Z) :- pow4gtx(X, Q),
isqrt(X, Q, 0, X, R, Z).
isqrt(_, 1, R0, Z0, R, Z) :- R is R0,
Z is Z0.
isqrt(X, Q, R0, Z0, R, Z) :- Q1 is Q // 4,
T is Z0 - R0 - Q1,
(T >= 0
-> R1 is (R0 // 2) + Q1,
isqrt(X, Q1, R1, T, R, Z)
; R1 is R0 // 2,
isqrt(X, Q1, R1, Z0, R, Z)).
roots(N) :- roots(0, N).
roots(I, N) :- isqrt(I, R),
write(R),
(I =:= N; write(" ")),
I1 is I + 1,
(N < I1, !; roots(I1, N)).
rootspow7(N) :- rootspow7(1, N).
rootspow7(I, N) :- Pow7 is 7**I,
isqrt(Pow7, R),
format("~t~D~2|~t~D~87|~t~D~131|~n",
[I, Pow7, R]),
I1 is I + 2,
(N < I1, !; rootspow7(I1, N)).
main :-
format("isqrt(i) for 0 <= i <= 65:~2n"),
roots(65),
format("~3n"),
format("isqrt(7**i) for 1 <= i <= 73, i odd:~2n"),
format("~t~s~2|~t~s~87|~t~s~131|~n",
["i", "7**i", "isqrt(7**i)"]),
format("-----------------------------------------------------------------------------------------------------------------------------------~n"),
rootspow7(73),
halt.
:- initialization(main).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Instructions for GNU Emacs--
%%% local variables:
%%% mode: prolog
%%% prolog-indent-width: 2
%%% end:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%</syntaxhighlight>
{{out}}
<pre>$ swipl isqrt.pl
isqrt(i) for 0 <= i <= 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
isqrt(7**i) for 1 <= i <= 73, i odd:
i 7**i isqrt(7**i)
-----------------------------------------------------------------------------------------------------------------------------------
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</pre>
=={{header|Python}}==
{{works with|Python|2.7}}
<syntaxhighlight lang="python">def isqrt ( x ):
q = 1
while q <= x :
q *= 4
z,r = x,0
while q > 1 :
q /= 4
t,r = z-r-q,r/2
if t >= 0 :
z,r = t,r+q
return r
print ' '.join( '%d'%isqrt( n ) for n in xrange( 66 ))
print '\n'.join( '{0:114,} = isqrt( 7^{1:3} )'.format( isqrt( 7**n ),n ) for n in range( 1,204,2 ))</syntaxhighlight>
{{out}}
<pre>
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
2 = isqrt( 7^ 1 )
18 = isqrt( 7^ 3 )
129 = isqrt( 7^ 5 )
907 = isqrt( 7^ 7 )
6,352 = isqrt( 7^ 9 )
44,467 = isqrt( 7^ 11 )
311,269 = isqrt( 7^ 13 )
2,178,889 = isqrt( 7^ 15 )
15,252,229 = isqrt( 7^ 17 )
106,765,608 = isqrt( 7^ 19 )
747,359,260 = isqrt( 7^ 21 )
5,231,514,822 = isqrt( 7^ 23 )
36,620,603,758 = isqrt( 7^ 25 )
256,344,226,312 = isqrt( 7^ 27 )
1,794,409,584,184 = isqrt( 7^ 29 )
12,560,867,089,291 = isqrt( 7^ 31 )
87,926,069,625,040 = isqrt( 7^ 33 )
615,482,487,375,282 = isqrt( 7^ 35 )
4,308,377,411,626,977 = isqrt( 7^ 37 )
30,158,641,881,388,842 = isqrt( 7^ 39 )
211,110,493,169,721,897 = isqrt( 7^ 41 )
1,477,773,452,188,053,281 = isqrt( 7^ 43 )
10,344,414,165,316,372,973 = isqrt( 7^ 45 )
72,410,899,157,214,610,812 = isqrt( 7^ 47 )
506,876,294,100,502,275,687 = isqrt( 7^ 49 )
3,548,134,058,703,515,929,815 = isqrt( 7^ 51 )
24,836,938,410,924,611,508,707 = isqrt( 7^ 53 )
173,858,568,876,472,280,560,953 = isqrt( 7^ 55 )
1,217,009,982,135,305,963,926,677 = isqrt( 7^ 57 )
8,519,069,874,947,141,747,486,745 = isqrt( 7^ 59 )
59,633,489,124,629,992,232,407,216 = isqrt( 7^ 61 )
417,434,423,872,409,945,626,850,517 = isqrt( 7^ 63 )
2,922,040,967,106,869,619,387,953,625 = isqrt( 7^ 65 )
20,454,286,769,748,087,335,715,675,381 = isqrt( 7^ 67 )
143,180,007,388,236,611,350,009,727,669 = isqrt( 7^ 69 )
1,002,260,051,717,656,279,450,068,093,686 = isqrt( 7^ 71 )
7,015,820,362,023,593,956,150,476,655,802 = isqrt( 7^ 73 )
49,110,742,534,165,157,693,053,336,590,618 = isqrt( 7^ 75 )
343,775,197,739,156,103,851,373,356,134,328 = isqrt( 7^ 77 )
2,406,426,384,174,092,726,959,613,492,940,298 = isqrt( 7^ 79 )
16,844,984,689,218,649,088,717,294,450,582,086 = isqrt( 7^ 81 )
117,914,892,824,530,543,621,021,061,154,074,602 = isqrt( 7^ 83 )
825,404,249,771,713,805,347,147,428,078,522,216 = isqrt( 7^ 85 )
5,777,829,748,401,996,637,430,031,996,549,655,515 = isqrt( 7^ 87 )
40,444,808,238,813,976,462,010,223,975,847,588,606 = isqrt( 7^ 89 )
283,113,657,671,697,835,234,071,567,830,933,120,245 = isqrt( 7^ 91 )
1,981,795,603,701,884,846,638,500,974,816,531,841,720 = isqrt( 7^ 93 )
13,872,569,225,913,193,926,469,506,823,715,722,892,042 = isqrt( 7^ 95 )
97,107,984,581,392,357,485,286,547,766,010,060,244,299 = isqrt( 7^ 97 )
679,755,892,069,746,502,397,005,834,362,070,421,710,095 = isqrt( 7^ 99 )
4,758,291,244,488,225,516,779,040,840,534,492,951,970,665 = isqrt( 7^101 )
33,308,038,711,417,578,617,453,285,883,741,450,663,794,661 = isqrt( 7^103 )
233,156,270,979,923,050,322,173,001,186,190,154,646,562,631 = isqrt( 7^105 )
1,632,093,896,859,461,352,255,211,008,303,331,082,525,938,421 = isqrt( 7^107 )
11,424,657,278,016,229,465,786,477,058,123,317,577,681,568,950 = isqrt( 7^109 )
79,972,600,946,113,606,260,505,339,406,863,223,043,770,982,651 = isqrt( 7^111 )
559,808,206,622,795,243,823,537,375,848,042,561,306,396,878,562 = isqrt( 7^113 )
3,918,657,446,359,566,706,764,761,630,936,297,929,144,778,149,940 = isqrt( 7^115 )
27,430,602,124,516,966,947,353,331,416,554,085,504,013,447,049,581 = isqrt( 7^117 )
192,014,214,871,618,768,631,473,319,915,878,598,528,094,129,347,071 = isqrt( 7^119 )
1,344,099,504,101,331,380,420,313,239,411,150,189,696,658,905,429,502 = isqrt( 7^121 )
9,408,696,528,709,319,662,942,192,675,878,051,327,876,612,338,006,515 = isqrt( 7^123 )
65,860,875,700,965,237,640,595,348,731,146,359,295,136,286,366,045,605 = isqrt( 7^125 )
461,026,129,906,756,663,484,167,441,118,024,515,065,954,004,562,319,241 = isqrt( 7^127 )
3,227,182,909,347,296,644,389,172,087,826,171,605,461,678,031,936,234,687 = isqrt( 7^129 )
22,590,280,365,431,076,510,724,204,614,783,201,238,231,746,223,553,642,811 = isqrt( 7^131 )
158,131,962,558,017,535,575,069,432,303,482,408,667,622,223,564,875,499,679 = isqrt( 7^133 )
1,106,923,737,906,122,749,025,486,026,124,376,860,673,355,564,954,128,497,756 = isqrt( 7^135 )
7,748,466,165,342,859,243,178,402,182,870,638,024,713,488,954,678,899,484,295 = isqrt( 7^137 )
54,239,263,157,400,014,702,248,815,280,094,466,172,994,422,682,752,296,390,067 = isqrt( 7^139 )
379,674,842,101,800,102,915,741,706,960,661,263,210,960,958,779,266,074,730,470 = isqrt( 7^141 )
2,657,723,894,712,600,720,410,191,948,724,628,842,476,726,711,454,862,523,113,293 = isqrt( 7^143 )
18,604,067,262,988,205,042,871,343,641,072,401,897,337,086,980,184,037,661,793,056 = isqrt( 7^145 )
130,228,470,840,917,435,300,099,405,487,506,813,281,359,608,861,288,263,632,551,397 = isqrt( 7^147 )
911,599,295,886,422,047,100,695,838,412,547,692,969,517,262,029,017,845,427,859,782 = isqrt( 7^149 )
6,381,195,071,204,954,329,704,870,868,887,833,850,786,620,834,203,124,917,995,018,479 = isqrt( 7^151 )
44,668,365,498,434,680,307,934,096,082,214,836,955,506,345,839,421,874,425,965,129,358 = isqrt( 7^153 )
312,678,558,489,042,762,155,538,672,575,503,858,688,544,420,875,953,120,981,755,905,510 = isqrt( 7^155 )
2,188,749,909,423,299,335,088,770,708,028,527,010,819,810,946,131,671,846,872,291,338,571 = isqrt( 7^157 )
15,321,249,365,963,095,345,621,394,956,199,689,075,738,676,622,921,702,928,106,039,370,003 = isqrt( 7^159 )
107,248,745,561,741,667,419,349,764,693,397,823,530,170,736,360,451,920,496,742,275,590,023 = isqrt( 7^161 )
750,741,218,932,191,671,935,448,352,853,784,764,711,195,154,523,163,443,477,195,929,130,162 = isqrt( 7^163 )
5,255,188,532,525,341,703,548,138,469,976,493,352,978,366,081,662,144,104,340,371,503,911,136 = isqrt( 7^165 )
36,786,319,727,677,391,924,836,969,289,835,453,470,848,562,571,635,008,730,382,600,527,377,954 = isqrt( 7^167 )
257,504,238,093,741,743,473,858,785,028,848,174,295,939,938,001,445,061,112,678,203,691,645,679 = isqrt( 7^169 )
1,802,529,666,656,192,204,317,011,495,201,937,220,071,579,566,010,115,427,788,747,425,841,519,758 = isqrt( 7^171 )
12,617,707,666,593,345,430,219,080,466,413,560,540,501,056,962,070,807,994,521,231,980,890,638,309 = isqrt( 7^173 )
88,323,953,666,153,418,011,533,563,264,894,923,783,507,398,734,495,655,961,648,623,866,234,468,168 = isqrt( 7^175 )
618,267,675,663,073,926,080,734,942,854,264,466,484,551,791,141,469,591,731,540,367,063,641,277,182 = isqrt( 7^177 )
4,327,873,729,641,517,482,565,144,599,979,851,265,391,862,537,990,287,142,120,782,569,445,488,940,274 = isqrt( 7^179 )
30,295,116,107,490,622,377,956,012,199,858,958,857,743,037,765,932,009,994,845,477,986,118,422,581,921 = isqrt( 7^181 )
212,065,812,752,434,356,645,692,085,399,012,712,004,201,264,361,524,069,963,918,345,902,828,958,073,452 = isqrt( 7^183 )
1,484,460,689,267,040,496,519,844,597,793,088,984,029,408,850,530,668,489,747,428,421,319,802,706,514,166 = isqrt( 7^185 )
10,391,224,824,869,283,475,638,912,184,551,622,888,205,861,953,714,679,428,231,998,949,238,618,945,599,162 = isqrt( 7^187 )
72,738,573,774,084,984,329,472,385,291,861,360,217,441,033,676,002,755,997,623,992,644,670,332,619,194,135 = isqrt( 7^189 )
509,170,016,418,594,890,306,306,697,043,029,521,522,087,235,732,019,291,983,367,948,512,692,328,334,358,945 = isqrt( 7^191 )
3,564,190,114,930,164,232,144,146,879,301,206,650,654,610,650,124,135,043,883,575,639,588,846,298,340,512,620 = isqrt( 7^193 )
24,949,330,804,511,149,625,009,028,155,108,446,554,582,274,550,868,945,307,185,029,477,121,924,088,383,588,341 = isqrt( 7^195 )
174,645,315,631,578,047,375,063,197,085,759,125,882,075,921,856,082,617,150,295,206,339,853,468,618,685,118,393 = isqrt( 7^197 )
1,222,517,209,421,046,331,625,442,379,600,313,881,174,531,452,992,578,320,052,066,444,378,974,280,330,795,828,756 = isqrt( 7^199 )
8,557,620,465,947,324,321,378,096,657,202,197,168,221,720,170,948,048,240,364,465,110,652,819,962,315,570,801,294 = isqrt( 7^201 )
59,903,343,261,631,270,249,646,676,600,415,380,177,552,041,196,636,337,682,551,255,774,569,739,736,208,995,609,059 = isqrt( 7^203 )
</pre>
=={{header|Quackery}}==
<syntaxhighlight lang="quackery"> [ dup size 3 / times
[ char , swap
i 1+ -3 * stuff ]
dup 0 peek char , =
if [ behead drop ] ] is +commas ( $ --> $ )
[ over size -
space swap of
swap join ] is justify ( $ n --> $ )
[ 1
[ 2dup < not while
2 << again ]
0
[ over 1 > while
dip
[ 2 >>
2dup - ]
dup 1 >>
unrot -
dup 0 < iff drop
else
[ 2swap nip
rot over + ]
again ]
nip swap ] is sqrt+ ( n --> n n )
( sqrt+ returns the integer square root and remainder )
( i.e. isqrt+ of 28 is 5 remainder 3 as (5^2)+3 = 28 )
( To make it task compliant change the last line to )
( "nip nip ] is sqrt+ ( n --> n )" )
66 times [ i^ sqrt+ drop echo sp ] cr cr
73 times
[ 7 i^ 1+ ** sqrt+ drop
number$ +commas 41 justify
echo$ cr
2 step ]</syntaxhighlight>
'''Output:'''
<pre>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
2
18
129
907
6,352
44,467
311,269
2,178,889
15,252,229
106,765,608
747,359,260
5,231,514,822
36,620,603,758
256,344,226,312
1,794,409,584,184
12,560,867,089,291
87,926,069,625,040
615,482,487,375,282
4,308,377,411,626,977
30,158,641,881,388,842
211,110,493,169,721,897
1,477,773,452,188,053,281
10,344,414,165,316,372,973
72,410,899,157,214,610,812
506,876,294,100,502,275,687
3,548,134,058,703,515,929,815
24,836,938,410,924,611,508,707
173,858,568,876,472,280,560,953
1,217,009,982,135,305,963,926,677
8,519,069,874,947,141,747,486,745
59,633,489,124,629,992,232,407,216
417,434,423,872,409,945,626,850,517
2,922,040,967,106,869,619,387,953,625
20,454,286,769,748,087,335,715,675,381
143,180,007,388,236,611,350,009,727,669
1,002,260,051,717,656,279,450,068,093,686
7,015,820,362,023,593,956,150,476,655,802
</pre>
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
;; Integer Square Root (using Quadratic Residue)
(define (isqrt x)
(define q-init ; power of 4 greater than x
(let loop ([acc 1])
(if (<= acc x) (loop (* acc 4)) acc)))
(define-values (z r q)
(let loop ([z x] [r 0] [q q-init])
(if (<= q 1)
(values z r q)
(let* ([q (/ q 4)]
[t (- z r q)]
[r (/ r 2)])
(if (>= t 0)
(loop t (+ r q) q)
(loop z r q))))))
r)
(define (format-with-commas str #:chunk-size [size 3])
(define len (string-length str))
(define len-mod (modulo len size))
(define chunks
(for/list ([i (in-range len-mod len size)])
(substring str i (+ i size))))
(string-join (if (= len-mod 0)
chunks
(cons (substring str 0 len-mod) chunks))
","))
(displayln "Isqrt of integers (0 -> 65):")
(for ([i 66])
(printf "~a " (isqrt i)))
(displayln "\n\nIsqrt of odd powers of 7 (7 -> 7^73):")
(for/fold ([num 7]) ([i (in-range 1 74 2)])
(printf "Isqrt(7^~a) = ~a\n"
i
(format-with-commas (number->string (isqrt num))))
(* num 49))
</syntaxhighlight>
{{out}}
<pre>
Isqrt of integers (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
Isqrt of odd powers of 7 (7 -> 7^73):
Isqrt(7^1) = 2
Isqrt(7^3) = 18
Isqrt(7^5) = 129
Isqrt(7^7) = 907
Isqrt(7^9) = 6,352
Isqrt(7^11) = 44,467
Isqrt(7^13) = 311,269
Isqrt(7^15) = 2,178,889
Isqrt(7^17) = 15,252,229
Isqrt(7^19) = 106,765,608
Isqrt(7^21) = 747,359,260
Isqrt(7^23) = 5,231,514,822
Isqrt(7^25) = 36,620,603,758
Isqrt(7^27) = 256,344,226,312
Isqrt(7^29) = 1,794,409,584,184
Isqrt(7^31) = 12,560,867,089,291
Isqrt(7^33) = 87,926,069,625,040
Isqrt(7^35) = 615,482,487,375,282
Isqrt(7^37) = 4,308,377,411,626,977
Isqrt(7^39) = 30,158,641,881,388,842
Isqrt(7^41) = 211,110,493,169,721,897
Isqrt(7^43) = 1,477,773,452,188,053,281
Isqrt(7^45) = 10,344,414,165,316,372,973
Isqrt(7^47) = 72,410,899,157,214,610,812
Isqrt(7^49) = 506,876,294,100,502,275,687
Isqrt(7^51) = 3,548,134,058,703,515,929,815
Isqrt(7^53) = 24,836,938,410,924,611,508,707
Isqrt(7^55) = 173,858,568,876,472,280,560,953
Isqrt(7^57) = 1,217,009,982,135,305,963,926,677
Isqrt(7^59) = 8,519,069,874,947,141,747,486,745
Isqrt(7^61) = 59,633,489,124,629,992,232,407,216
Isqrt(7^63) = 417,434,423,872,409,945,626,850,517
Isqrt(7^65) = 2,922,040,967,106,869,619,387,953,625
Isqrt(7^67) = 20,454,286,769,748,087,335,715,675,381
Isqrt(7^69) = 143,180,007,388,236,611,350,009,727,669
Isqrt(7^71) = 1,002,260,051,717,656,279,450,068,093,686
Isqrt(7^73) = 7,015,820,362,023,593,956,150,476,655,802
</pre>
=={{header|Raku}}==
See the [[Integer_roots#Raku|Integer roots]] Raku entry.
Quadratic residue algorithm follows:
<syntaxhighlight lang="raku" line>use Lingua::EN::Numbers;
sub isqrt ( \x ) { my ( $X, $q, $r, $t ) = x, 1, 0 ;
$q +<= 2 while $q ≤ $X ;
while $q > 1 {
$q +>= 2; $t = $X - $r - $q; $r +>= 1;
if $t ≥ 0 { $X = $t; $r += $q }
}
$r
}
say (^66)».&{ isqrt $_ }.Str ;
(1, 3…73)».&{ "7**$_: " ~ comma(isqrt 7**$_) }».say</syntaxhighlight>
{{out}}
<pre>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
7**1: 2
7**3: 18
7**5: 129
7**7: 907
7**9: 6,352
7**11: 44,467
7**13: 311,269
7**15: 2,178,889
7**17: 15,252,229
7**19: 106,765,608
7**21: 747,359,260
7**23: 5,231,514,822
7**25: 36,620,603,758
7**27: 256,344,226,312
7**29: 1,794,409,584,184
7**31: 12,560,867,089,291
7**33: 87,926,069,625,040
7**35: 615,482,487,375,282
7**37: 4,308,377,411,626,977
7**39: 30,158,641,881,388,842
7**41: 211,110,493,169,721,897
7**43: 1,477,773,452,188,053,281
7**45: 10,344,414,165,316,372,973
7**47: 72,410,899,157,214,610,812
7**49: 506,876,294,100,502,275,687
7**51: 3,548,134,058,703,515,929,815
7**53: 24,836,938,410,924,611,508,707
7**55: 173,858,568,876,472,280,560,953
7**57: 1,217,009,982,135,305,963,926,677
7**59: 8,519,069,874,947,141,747,486,745
7**61: 59,633,489,124,629,992,232,407,216
7**63: 417,434,423,872,409,945,626,850,517
7**65: 2,922,040,967,106,869,619,387,953,625
7**67: 20,454,286,769,748,087,335,715,675,381
7**69: 143,180,007,388,236,611,350,009,727,669
7**71: 1,002,260,051,717,656,279,450,068,093,686
7**73: 7,015,820,362,023,593,956,150,476,655,802</pre>
=={{header|REXX}}==
A fair amount of code was included so that the output aligns correctly.
<
numeric digits 200 /*insure 'nuff decimal digs for results*/
parse arg range power base . /*obtain optional arguments from the CL*/
Line 985 ⟶ 5,875:
end
end /*while*/
return r /*return the integer square root of X. */</
{{out|output|text= when using the default inputs:}}
<pre>
Line 1,031 ⟶ 5,921:
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
</pre>
=={{header|RPL}}==
Because RPL can only handle unsigned integers, a light change has been made in the proposed algorithm,
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
#1
'''WHILE''' DUP2 ≥ '''REPEAT'''
SL SL '''END'''
#0
'''WHILE''' OVER #1 > '''REPEAT'''
SWAP SR SR SWAP
DUP2 +
SWAP SR SWAP
'''IF''' 4 PICK SWAP DUP2 ≥ '''THEN'''
- 4 ROLL DROP ROT ROT
OVER +
'''ELSE''' DROP2 '''END'''
'''END''' ROT ROT DROP2
≫
´'''ISQRT'''’ STO
|
'''ISQRT''' ''( #n -- #sqrt(n) )''
q ◄── 1
perform while q <= x
q ◄── q * 4
z ◄── x
r ◄── 0
perform while q > 1
q ◄── q ÷ 4
u ◄── r + q
r ◄── r ÷ 2
if z >= u then do
z ◄── z - u
r ◄── r + q
else remove u and copy of z from stack
end perform, clean stack
|}
{{in}}
<pre>
≪ { } 0 65 FOR n n R→B ISQRT B→R + NEXT ≫ EVAL
≪ {} #7 1 11 START DUP ISQRT ROT SWAP + SWAP 49 * NEXT DROP ≫ EVAL
</pre>
{{out}}
<pre>
2: { 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 }
1: { # 2d # 18d # 129d # 907d # 6352d # 44467d # 311269d # 2178889d # 15252229d # 106765608d # 747359260d }
</pre>
=={{header|Ruby}}==
Ruby already has [https://ruby-doc.org/core-2.7.0/Integer.html#method-c-sqrt Integer.sqrt], which results in the integer square root of a positive integer. It can be re-implemented as follows:
<syntaxhighlight lang="ruby">module Commatize
refine Integer do
def commatize
self.to_s.gsub( /(\d)(?=\d{3}+(?:\.|$))(\d{3}\..*)?/, "\\1,\\2")
end
end
end
using Commatize
def isqrt(x)
q, r = 1, 0
while (q <= x) do q <<= 2 end
while (q > 1) do
q >>= 2; t = x-r-q; r >>= 1
if (t >= 0) then x, r = t, r+q end
end
r
end
puts (0..65).map{|n| isqrt(n) }.join(" ")
1.step(73, 2) do |n|
print "#{n}:\t"
puts
end
</syntaxhighlight>
{{out}}
<pre>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
Line 1,085 ⟶ 6,044:
73: 7,015,820,362,023,593,956,150,476,655,802
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">
use num::BigUint;
use num::CheckedSub;
use num_traits::{One, Zero};
fn isqrt(number: &BigUint) -> BigUint {
let mut q: BigUint = One::one();
while q <= *number {
q <<= &2;
}
let mut z = number.clone();
let mut result: BigUint = Zero::zero();
while q > One::one() {
q >>= &2;
let t = z.checked_sub(&result).and_then(|diff| diff.checked_sub(&q));
result >>= &1;
if let Some(t) = t {
z = t;
result += &q;
}
}
result
}
fn with_thousand_separator(s: &str) -> String {
let digits: Vec<_> = s.chars().rev().collect();
let chunks: Vec<_> = digits
.chunks(3)
.map(|chunk| chunk.iter().collect::<String>())
.collect();
chunks.join(",").chars().rev().collect::<String>()
}
fn main() {
println!("The integer square roots of integers from 0 to 65 are:");
(0_u32..=65).for_each(|n| print!("{} ", isqrt(&n.into())));
println!("\nThe integer square roots of odd powers of 7 from 7^1 up to 7^74 are:");
(1_u32..75).step_by(2).for_each(|exp| {
println!(
"7^{:>2}={:>83} ISQRT: {:>42} ",
exp,
with_thousand_separator(&BigUint::from(7_u8).pow(exp).to_string()),
with_thousand_separator(&isqrt(&BigUint::from(7_u8).pow(exp)).to_string())
)
});
}
</syntaxhighlight>
{{out}}
<pre>
The integer square roots of integers from 0 to 65 are:
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
The integer square roots of odd powers of 7 from 7^1 up to 7^74 are:
7^ 1= 7 ISQRT: 2
7^ 3= 343 ISQRT: 18
7^ 5= 16,807 ISQRT: 129
7^ 7= 823,543 ISQRT: 907
7^ 9= 40,353,607 ISQRT: 6,352
7^11= 1,977,326,743 ISQRT: 44,467
7^13= 96,889,010,407 ISQRT: 311,269
7^15= 4,747,561,509,943 ISQRT: 2,178,889
7^17= 232,630,513,987,207 ISQRT: 15,252,229
7^19= 11,398,895,185,373,143 ISQRT: 106,765,608
7^21= 558,545,864,083,284,007 ISQRT: 747,359,260
7^23= 27,368,747,340,080,916,343 ISQRT: 5,231,514,822
7^25= 1,341,068,619,663,964,900,807 ISQRT: 36,620,603,758
7^27= 65,712,362,363,534,280,139,543 ISQRT: 256,344,226,312
7^29= 3,219,905,755,813,179,726,837,607 ISQRT: 1,794,409,584,184
7^31= 157,775,382,034,845,806,615,042,743 ISQRT: 12,560,867,089,291
7^33= 7,730,993,719,707,444,524,137,094,407 ISQRT: 87,926,069,625,040
7^35= 378,818,692,265,664,781,682,717,625,943 ISQRT: 615,482,487,375,282
7^37= 18,562,115,921,017,574,302,453,163,671,207 ISQRT: 4,308,377,411,626,977
7^39= 909,543,680,129,861,140,820,205,019,889,143 ISQRT: 30,158,641,881,388,842
7^41= 44,567,640,326,363,195,900,190,045,974,568,007 ISQRT: 211,110,493,169,721,897
7^43= 2,183,814,375,991,796,599,109,312,252,753,832,343 ISQRT: 1,477,773,452,188,053,281
7^45= 107,006,904,423,598,033,356,356,300,384,937,784,807 ISQRT: 10,344,414,165,316,372,973
7^47= 5,243,338,316,756,303,634,461,458,718,861,951,455,543 ISQRT: 72,410,899,157,214,610,812
7^49= 256,923,577,521,058,878,088,611,477,224,235,621,321,607 ISQRT: 506,876,294,100,502,275,687
7^51= 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 ISQRT: 3,548,134,058,703,515,929,815
7^53= 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 ISQRT: 24,836,938,410,924,611,508,707
7^55= 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 ISQRT: 173,858,568,876,472,280,560,953
7^57= 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 ISQRT: 1,217,009,982,135,305,963,926,677
7^59= 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 ISQRT: 8,519,069,874,947,141,747,486,745
7^61= 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 ISQRT: 59,633,489,124,629,992,232,407,216
7^63= 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 ISQRT: 417,434,423,872,409,945,626,850,517
7^65= 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 ISQRT: 2,922,040,967,106,869,619,387,953,625
7^67= 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 ISQRT: 20,454,286,769,748,087,335,715,675,381
7^69= 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 ISQRT: 143,180,007,388,236,611,350,009,727,669
7^71= 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 ISQRT: 1,002,260,051,717,656,279,450,068,093,686
7^73= 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 ISQRT: 7,015,820,362,023,593,956,150,476,655,802
</pre>
=={{header|S-BASIC}}==
This follows the algorithm given in the task description. The q = q * 4 computation, however, will result in overflow (and an endless loop!) for large values of x.
<syntaxhighlight lang="basic">
comment
return integer square root of n using quadratic
residue algorithm. WARNING: the function will fail
for x > 16,383.
end
function isqrt(x = integer) = integer
var q, r, t = integer
q = 1
while q <= x do
q = q * 4 rem overflow may occur here!
r = 0
while q > 1 do
begin
q = q / 4
t = x - r - q
r = r / 2
if t >= 0 then
begin
x = t
r = r + q
end
end
end = r
rem - Exercise the function
var n, pow7 = integer
print "Integer square root of first 65 numbers"
for n=1 to 65
print using "#####";isqrt(n);
next n
print
print "Integer square root of odd powers of 7"
print " n 7^n isqrt"
print "------------------"
for n=1 to 3 step 2
pow7 = 7^n
print using "### #### ####";n; pow7; isqrt(pow7)
next n
end
</syntaxhighlight>
An alternate version of isqrt() that can handle the full range of S-BASIC integer values (well, almost: it will fail for 32,767) looks like this.
<syntaxhighlight lang="basic">
function isqrt(x = integer) = integer
var x0, x1 = integer
x1 = x
repeat
begin
x0 = x1
x1 = (x0 + x / x0) / 2
end
until x1 >= x0
end = x0
</syntaxhighlight>
{{out}}
The output for 7^5 will be shown only if the alternate version of the function is used.
<pre>
Integer square root of first 65 numbers
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
Integer square root of odd powers of 7
n 7^n isqrt
------------------
1 7 2
3 343 18
5 16807 129
</pre>
=={{header|Scheme}}==
{{works with|CHICKEN|5.3.0}}
{{libheader|r7rs}}
{{libheader|format}}
Adapting this to any given R7RS Scheme is probably mainly a matter of changing how output is done.
<syntaxhighlight lang="scheme">(import (scheme base))
(import (scheme write))
(import (format)) ;; Common Lisp formatting for CHICKEN Scheme.
(define (find-a-power-of-4-greater-than-x x)
(let loop ((q 1))
(if (< x q)
q
(loop (* 4 q)))))
(define (isqrt+remainder x)
(let loop ((q (find-a-power-of-4-greater-than-x x))
(z x)
(r 0))
(if (= q 1)
(values r z)
(let* ((q (truncate-quotient q 4))
(t (- z r q))
(r (truncate-quotient r 2)))
(if (negative? t)
(loop q z r)
(loop q t (+ r q)))))))
(define (isqrt x)
(let-values (((q r) (isqrt+remainder x)))
q))
(format #t "isqrt(i) for ~D <= i <= ~D:~2%" 0 65)
(do ((i 0 (+ i 1)))
((= i 65))
(format #t "~D " (isqrt i)))
(format #t "~D~3%" (isqrt 65))
(format #t "isqrt(7**i) for ~D <= i <= ~D, i odd:~2%" 1 73)
(format #t "~2@A ~84@A ~43@A~%" "i" "7**i" "sqrt(7**i)")
(format #t "~A~%" (make-string 131 #\-))
(do ((i 1 (+ i 2)))
((= i 75))
(let ((7**i (expt 7 i)))
(format #t "~2D ~84:D ~43:D~%" i 7**i (isqrt 7**i))))</syntaxhighlight>
{{out}}
<pre>$ csc -O3 -R r7rs isqrt.scm && ./isqrt
isqrt(i) for 0 <= i <= 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
isqrt(7**i) for 1 <= i <= 73, i odd:
i 7**i sqrt(7**i)
-----------------------------------------------------------------------------------------------------------------------------------
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</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program isqrt;
loop for i in [1..65] do
putchar(lpad(str isqrt(i), 5));
if i mod 13=0 then print(); end if;
end loop;
print();
loop for p in [1, 3..73] do
sqrtp := isqrt(7 ** p);
print("sqrt(7^" + lpad(str p,2) + ") = " + lpad(str sqrtp, 32));
end loop;
proc isqrt(x);
q := 1;
loop while q<=x do
q *:= 4;
end loop;
z := x;
r := 0;
loop while q>1 do
q div:= 4;
t := z-r-q;
r div:= 2;
if t>=0 then
z := t;
r +:= q;
end if;
end loop;
return r;
end proc;
end program;</syntaxhighlight>
{{out}}
<pre> 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
sqrt(7^ 1) = 2
sqrt(7^ 3) = 18
sqrt(7^ 5) = 129
sqrt(7^ 7) = 907
sqrt(7^ 9) = 6352
sqrt(7^11) = 44467
sqrt(7^13) = 311269
sqrt(7^15) = 2178889
sqrt(7^17) = 15252229
sqrt(7^19) = 106765608
sqrt(7^21) = 747359260
sqrt(7^23) = 5231514822
sqrt(7^25) = 36620603758
sqrt(7^27) = 256344226312
sqrt(7^29) = 1794409584184
sqrt(7^31) = 12560867089291
sqrt(7^33) = 87926069625040
sqrt(7^35) = 615482487375282
sqrt(7^37) = 4308377411626977
sqrt(7^39) = 30158641881388842
sqrt(7^41) = 211110493169721897
sqrt(7^43) = 1477773452188053281
sqrt(7^45) = 10344414165316372973
sqrt(7^47) = 72410899157214610812
sqrt(7^49) = 506876294100502275687
sqrt(7^51) = 3548134058703515929815
sqrt(7^53) = 24836938410924611508707
sqrt(7^55) = 173858568876472280560953
sqrt(7^57) = 1217009982135305963926677
sqrt(7^59) = 8519069874947141747486745
sqrt(7^61) = 59633489124629992232407216
sqrt(7^63) = 417434423872409945626850517
sqrt(7^65) = 2922040967106869619387953625
sqrt(7^67) = 20454286769748087335715675381
sqrt(7^69) = 143180007388236611350009727669
sqrt(7^71) = 1002260051717656279450068093686
sqrt(7^73) = 7015820362023593956150476655802</pre>
=={{header|Seed7}}==
Seed7 has integer [https://seed7.sourceforge.net/libraries/integer.htm#sqrt(in_integer) sqrt()] and bigInteger [https://seed7.sourceforge.net/libraries/bigint.htm#sqrt(in_var_bigInteger) sqrt()] functions.
These functions could be used if an integer square root is needed.
But this task does not allow using the language's built-in sqrt() function.
Instead the ''quadratic residue'' algorithm for finding the integer square root must be used.
<syntaxhighlight lang="seed7">$ 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;</syntaxhighlight>
{{out}}
<pre>
The integer square roots of integers from 0 to 65 are:
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
The integer square roots of powers of 7 from 7**1 up to 7**73 are:
power 7 ** power integer square root
----- --------------------------------------------------------------------------------- -----------------------------------------
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
</pre>
=={{header|Sidef}}==
Built-in:
<syntaxhighlight lang="ruby">var n = 1234
say n.isqrt
say n.iroot(2)</syntaxhighlight>
Explicit implementation for the integer k-th root of n:
<syntaxhighlight lang="ruby">func rootint(n, k=2) {
return 0 if (n == 0)
var (s, v) = (n, k - 1)
loop {
var u = ((v*s + (n // s**v)) // k)
break if (u >= s)
s = u
}
s
}</syntaxhighlight>
Implementation of integer square root of n (using the quadratic residue algorithm):
<syntaxhighlight lang="ruby">func isqrt(x) { var (q, r) = (1, 0); while (q <= x) { q <<= 2 }
while (q > 1) { q >>= 2; var t = x-r+q; r >>= 1
if (t >= 0) { (x, r) = (t, r+q) } } r }
say isqrt.map(0..65).join(' '); printf("\n")
for n in (1..73 `by` 2) {
printf("isqrt(7^%-2d): %42s\n", n, isqrt(7**n).commify) }</syntaxhighlight>
{{out}}
<pre>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
isqrt(7^1 ): 2
isqrt(7^3 ): 18
isqrt(7^5 ): 129
isqrt(7^7 ): 907
isqrt(7^9 ): 6,352
isqrt(7^11): 44,467
isqrt(7^13): 311,269
isqrt(7^15): 2,178,889
isqrt(7^17): 15,252,229
isqrt(7^19): 106,765,608
isqrt(7^21): 747,359,260
isqrt(7^23): 5,231,514,822
isqrt(7^25): 36,620,603,758
isqrt(7^27): 256,344,226,312
isqrt(7^29): 1,794,409,584,184
isqrt(7^31): 12,560,867,089,291
isqrt(7^33): 87,926,069,625,040
isqrt(7^35): 615,482,487,375,282
isqrt(7^37): 4,308,377,411,626,977
isqrt(7^39): 30,158,641,881,388,842
isqrt(7^41): 211,110,493,169,721,897
isqrt(7^43): 1,477,773,452,188,053,281
isqrt(7^45): 10,344,414,165,316,372,973
isqrt(7^47): 72,410,899,157,214,610,812
isqrt(7^49): 506,876,294,100,502,275,687
isqrt(7^51): 3,548,134,058,703,515,929,815
isqrt(7^53): 24,836,938,410,924,611,508,707
isqrt(7^55): 173,858,568,876,472,280,560,953
isqrt(7^57): 1,217,009,982,135,305,963,926,677
isqrt(7^59): 8,519,069,874,947,141,747,486,745
isqrt(7^61): 59,633,489,124,629,992,232,407,216
isqrt(7^63): 417,434,423,872,409,945,626,850,517
isqrt(7^65): 2,922,040,967,106,869,619,387,953,625
isqrt(7^67): 20,454,286,769,748,087,335,715,675,381
isqrt(7^69): 143,180,007,388,236,611,350,009,727,669
isqrt(7^71): 1,002,260,051,717,656,279,450,068,093,686
isqrt(7^73): 7,015,820,362,023,593,956,150,476,655,802
</pre>
=={{header|Standard ML}}==
{{trans|Scheme}}
{{trans|OCaml}}
{{works with|MLton}}
<syntaxhighlight lang="sml">(*
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: *)</syntaxhighlight>
{{out}}
<pre>$ mlton isqrt.sml && ./isqrt
isqrt(i) for 0 <= i <= 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
isqrt(7**i) for 1 <= i <= 73, i odd:
i 7**i sqrt(7**i)
-----------------------------------------------------------------------------------------------------------------------------------
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</pre>
=={{header|Swift}}==
{{trans|C++}}
Requires the attaswift BigInt package.
<
func integerSquareRoot<T: BinaryInteger>(_ num: T) -> T {
Line 1,148 ⟶ 6,816:
print("\(pad(string: String(n), width: 2)) |\(power) |\(isqrt)")
p *= 49
}</
{{out}}
<pre style="font-size: 11px">
Integer square root for numbers 0 to 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
Line 1,196 ⟶ 6,864:
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
</pre>
=={{Header|Tiny BASIC}}==
{{works with|TinyBasic}}
Tiny BASIC does not support string formatting or concatenation, and is limited to integer arithmetic on numbers no greater than 32,767. The isqrt of 0-65 and the first two odd powers of 7 are shown in column format. The algorithm itself (the interesting part) begins on line 100.
<syntaxhighlight lang="basic">10 LET X = 0
20 GOSUB 100
30 PRINT R
40 LET X = X + 1
50 IF X < 66 THEN GOTO 20
70 PRINT "---"
71 LET X = 7
72 GOSUB 100
73 PRINT R
77 LET X = 343
78 GOSUB 100
79 PRINT R
90 END
100 REM integer square root function
110 LET Q = 1
120 IF Q > X THEN GOTO 150
130 LET Q = Q * 4
140 GOTO 120
150 LET Z = X
160 LET R = 0
170 IF Q <= 1 THEN RETURN
180 LET Q = Q / 4
190 LET T = Z - R - Q
200 LET R = R / 2
210 IF T < 0 THEN GOTO 170
220 LET Z = T
230 LET R = R + Q
240 GOTO 170</syntaxhighlight>
=={{header|UNIX Shell}}==
{{works with|Bourne Again SHell}}
{{works with|Korn Shell}}
{{Works with|Zsh}}
<syntaxhighlight lang="sh">function isqrt {
typeset -i x
for x; do
typeset -i q=1
while (( q <= x )); do
(( q <<= 2 ))
if (( q <= 0 )); then
return 1
fi
done
typeset -i z=x
typeset -i r=0
typeset -i t
while (( q > 1 )); do
(( q >>= 2 ))
(( t = z - r - q ))
(( r >>= 1 ))
if (( t >= 0 )); then
(( z = t ))
(( r = r + q ))
fi
done
printf '%d\n' "$r"
done
}
# demo
printf 'isqrt(n) for n from 0 to 65:\n'
for i in {1..4}; do
for n in {0..65}; do
case $i in
1)
(( tens=n/10 ))
if (( tens )); then
printf '%2d' "$tens"
else
printf ' '
fi
;;
2) printf '%2d' $(( n%10 ));;
3) printf -- '--';;
4) printf '%2d' "$(isqrt "$n")";;
esac
done
printf '\n'
done
printf '\n'
printf 'isqrt(7ⁿ) for odd n up to the limit of integer precision:\n'
printf '%2s|%27sⁿ|%14sⁿ)\n' "n" "7" "isqrt(7"
for (( i=0;i<48; ++i )); do printf '-'; done; printf '\n'
for (( p=1; p<=73 && (n=7**p) > 0; p+=2)); do
if r=$(isqrt $n); then
printf "%2d|%'28d|%'16d\n" "$p" "$n" "$r"
else
break
fi
done</syntaxhighlight>
{{Out}}
The powers-of-7 table is limited by the built-in precision; on my system, both bash and zsh use signed 64-bit integers with a max value of 7²² < 9223372036854775807 < 7²³.
Ksh uses signed 32-bit integers with a max value of 7¹¹ < 2147483647 < 7¹²; if I remove the <tt>typeset -i</tt> integer restriction, the code will work to a much larger power of 7, but at that point it's doing floating-point arithmetic, which is against the spirit of the task.
<pre>isqrt(n) for n from 0 to 65:
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
------------------------------------------------------------------------------------------------------------------------------------
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
isqrt(7ⁿ) for odd n up to the limit of integer precision:
n| 7ⁿ| isqrt(7ⁿ)
------------------------------------------------
1| 7| 2
3| 343| 18
5| 16,807| 129
7| 823,543| 907
9| 40,353,607| 6,352 # ksh stops here
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</pre>
=={{header|Visual Basic .NET}}==
{{libheader|System.Numerics}}{{trans|C#}}
<
Imports System.Console
Imports BI = System.Numerics.BigInteger
Line 1,232 ⟶ 7,019:
End While
End Sub
End Module</
{{Out}}
<pre>Integer square root for numbers 0 to 65:
Line 1,280 ⟶ 7,067:
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
</pre>
=={{header|VTL-2}}==
The ISQRT routine starts at line 2000. As VTL-2 only has unsigned 16-bit arithmetic, only the roots of 7^1, 7^3 and 7^5 are shown as 7^7 is too large.
<syntaxhighlight lang="vtl2">
1000 X=0
1010 #=2000
1020 $=32
1030 ?=R
1040 X=X+1
1050 #=X=33=0*1070
1060 ?=""
1070 #=X<66*1010
1080 P=1
1090 X=7
1100 #=2000
1110 ?=""
1120 ?="Root 7^";
1130 ?=P
1140 ?="(";
1150 ?=X
1160 ?=") = ";
1170 ?=R
1180 X=X*49
1190 P=P+2
1200 #=P<6*1100
1210 #=9999
2000 A=!
2010 Q=1
2020 #=X>Q=0*2050
2030 Q=Q*4
2040 #=2020
2050 Z=X
2060 R=0
2070 #=Q<2*A
2080 Q=Q/4
2090 T=Z-R-Q
2100 I=Z<(R+Q)
2110 R=R/2
2120 #=I*2070
2130 Z=T
2140 R=R+Q
2150 #=2070
</syntaxhighlight>
{{out}}
<pre>
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
Root 7^1(7) = 2
Root 7^3(343) = 18
Root 7^5(16807) = 129
</pre>
Line 1,285 ⟶ 7,123:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
var isqrt = Fn.new { |x|
Line 1,322 ⟶ 7,160:
pow7 = pow7 * bi49
i = i + 2
}</
{{out}}
Line 1,371 ⟶ 7,209:
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
</pre>
=={{header|Yabasic}}==
<syntaxhighlight lang="freebasic">// Rosetta Code problem: https://rosettacode.org/wiki/Isqrt_(integer_square_root)_of_X
// by Jjuanhdez, 06/2022
print "Integer square root of first 65 numbers:"
for n = 1 to 65
print isqrt(n) using("##");
next n
print : print
print "Integer square root of odd powers of 7"
print " n | 7^n | isqrt "
print "----|--------------------|-----------"
for n = 1 to 21 step 2
pow7 = 7 ^ n
print n using("###"), " | ", left$(str$(pow7,"%20.1f"),18), " | ", left$(str$(isqrt(pow7),"%11.1f"),9)
next n
end
sub isqrt(x)
q = 1
while q <= x
q = q * 4
wend
r = 0
while q > 1
q = q / 4
t = x - r - q
r = r / 2
if t >= 0 then
x = t
r = r + q
end if
wend
return int(r)
end sub</syntaxhighlight>
| |||