# Isqrt (integer square root) of X

Isqrt (integer square root) of X
You are encouraged to solve this task according to the task description, using any language you may know.

Sometimes a function is needed to find the integer square root of   X,   where   X   can be a real non─negative number.

Often   X   is actually a non─negative integer.

For the purposes of this task,   X   can be an integer or a real number,   but if it simplifies things in your computer programming language,   assume it's an integer.

One of the most common uses of   `Isqrt`   is in the division of an integer by all factors   (or primes)   up to the    X    of that integer,   either to find the factors of that integer,   or to determine primality.

An alternative method for finding the   `Isqrt`   of a number is to calculate:       floor( sqrt(X) )

•   where   sqrt    is the   square root   function for non─negative real numbers,   and
•   where   floor   is the   floor   function for real numbers.

If the hardware supports the computation of (real) square roots,   the above method might be a faster method for small numbers that don't have very many significant (decimal) digits.

However, floating point arithmetic is limited in the number of   (binary or decimal)   digits that it can support.

For this task, the integer square root of a non─negative number will be computed using a version of   quadratic residue,   which has the advantage that no   floating point   calculations are used,   only integer arithmetic.   Furthermore, the divisions and multiplication can be performed by bit shifting.

The disadvantage is the limitation of the size of the largest integer that a particular computer programming language can support.

Pseudo─code of a procedure for finding the integer square root of   X       (all variables are integers):

```         q ◄── 1                                /*initialize  Q  to unity.  */
/*find a power of 4 that's greater than X.*/
perform  while q <= x         /*perform while  Q <= X.    */
q ◄── q * 4                   /*multiply  Q  by  four.    */
end  /*perform*/
/*Q  is now greater than  X.*/
z ◄── x                                /*set  Z  to the value of X.*/
r ◄── 0                                /*initialize  R  to zero.   */
perform  while q > 1          /*perform while  Q > unity. */
q ◄── q ÷ 4                   /*integer divide by  four.  */
t ◄── z - r - q               /*compute value of  T.      */
r ◄── r ÷ 2                   /*integer divide by  two.   */
if t >= 0  then do
z ◄── t       /*set  Z  to value of  T.   */
r ◄── r + q   /*compute new value of  R.  */
end
end  /*perform*/
/*R  is now the  Isqrt(X).  */
```

Another version for the (above)   1st   perform   is:

```                  perform  until q > X          /*perform until  Q > X.     */
q ◄── q * 4                   /*multiply  Q  by  four.    */
end  /*perform*/
```

Integer square roots of some values:

```Isqrt( 0)  is   0               Isqrt(60)  is  7                Isqrt( 99)  is   9
Isqrt( 1)  is   1               Isqrt(61)  is  7                Isqrt(100)  is  10
Isqrt( 2)  is   1               Isqrt(62)  is  7                Isqrt(102)  is  10
Isqrt( 3)  is   1               Isqrt(63)  is  7
Isqrt( 4)  is   2               Isqrt(64)  is  8                Isqet(120)  is  10
Isqrt( 5)  is   2               Isqrt(65)  is  8                Isqrt(121)  is  11
Isqrt( 6)  is   2               Isqrt(66)  is  8                Isqrt(122)  is  11
Isqrt( 7)  is   2               Isqrt(67)  is  8
Isqrt( 8)  is   2               Isqrt(68)  is  8                Isqrt(143)  is  11
Isqrt( 9)  is   3               Isqrt(69)  is  8                Isqrt(144)  is  12
Isqrt(10)  is   3               Isqrt(70)  is  8                Isqrt(145)  is  12
```

•   the `Isqrt` of the     integers     from     0 ───► 65    (inclusive), shown in a horizontal format.
•   the `Isqrt` of the   odd powers  from   71 ───► 773   (inclusive), shown in a   vertical   format.
•   use commas in the displaying of larger numbers.

You can show more numbers for the 2nd requirement if the displays fits on one screen on Rosetta Code.
If your computer programming language only supports smaller integers,   show what you can.

## ALGOL 68

Works with: ALGOL 68G version Any - tested with release 2.8.3.win32

Implements the task pseudo-code. <lang algol68>BEGIN # Integer square roots #

```   PR precision 200 PR
# returns the integer square root of x; x must be >= 0                   #
PROC isqrt = ( LONG LONG INT x )LONG LONG INT:
IF   x < 0 THEN print( ( "Negative number in isqrt", newline ) );stop
ELIF x < 2 THEN x
ELSE
# x is greater than 1                                            #
# find a power of 4 that's greater than x                        #
LONG LONG INT q := 1;
WHILE q <= x DO q *:= 4 OD;
# find the root                                                  #
LONG LONG INT z := x;
LONG LONG INT r := 0;
WHILE q > 1 DO
q OVERAB 4;
LONG LONG INT t = z - r - q;
r OVERAB 2;
IF t >= 0 THEN
z  := t;
r +:= q
FI
OD;
r
FI; # isqrt #
# returns a string representation of n with commas                       #
PROC commatise = ( LONG LONG INT n )STRING:
BEGIN
STRING result      := "";
STRING unformatted  = whole( n, 0 );
INT    ch count    := 0;
FOR c FROM UPB unformatted BY -1 TO LWB unformatted DO
IF   ch count <= 2 THEN ch count +:= 1
ELSE                    ch count  := 1; "," +=: result
FI;
unformatted[ c ] +=: result
OD;
result
END; # commatise #
# left-pads a string to at least n characters                            #
PROC pad left = ( STRING s, INT n )STRING:
BEGIN
STRING result := s;
WHILE ( UPB result - LWB result ) + 1 < n DO " " +=: result OD;
result
print( ( "Integer square roots of 0..65", newline ) );
FOR i FROM 0 TO 65 DO print( ( " ", whole( isqrt( i ), 0 ) ) ) OD;
print( ( newline ) );
# integer square roots of odd powers of 7                                #
print( ( "Integer square roots of 7^n", newline ) );
print( ( " n|", pad left( "7^n", 82 ), "|", pad left( "isqrt(7^n)", 42 ), newline ) );
LONG LONG INT p7 := 7;
FOR p BY 2 TO 73 DO
print( ( whole( p, -2 )
, "|"
, pad left( commatise(        p7   ), 82 )
, "|"
, pad left( commatise( isqrt( p7 ) ), 42 )
, newline
)
);
p7 *:= 49
OD
```

END</lang>

Output:
```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
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
```

## C++

Library: Boost

<lang cpp>#include <iomanip>

1. include <iostream>
2. include <sstream>
3. include <boost/multiprecision/cpp_int.hpp>

using big_int = boost::multiprecision::cpp_int;

template <typename integer> integer isqrt(integer x) {

```   integer q = 1;
while (q <= x)
q <<= 2;
integer r = 0;
while (q > 1) {
q >>= 2;
integer t = x - r - q;
r >>= 1;
if (t >= 0) {
x = t;
r += q;
}
}
return r;
```

}

std::string commatize(const big_int& n) {

```   std::ostringstream out;
out << n;
std::string str(out.str());
std::string result;
size_t digits = str.size();
result.reserve(4 * digits/3);
for (size_t i = 0; i < digits; ++i) {
if (i > 0 && i % 3 == digits % 3)
result += ',';
result += str[i];
}
return result;
```

}

int main() {

```   std::cout << "Integer square root for numbers 0 to 65:\n";
for (int n = 0; n <= 65; ++n)
std::cout << isqrt(n) << ' ';
std::cout << "\n\n";
```
```   std::cout << "Integer square roots of odd powers of 7 from 1 to 73:\n";
const int power_width = 83, isqrt_width = 42;
std::cout << " n |"
<< std::setw(power_width) << "7 ^ n" << " |"
<< std::setw(isqrt_width) << "isqrt(7 ^ n)"
<< '\n';
std::cout << std::string(6 + power_width + isqrt_width, '-') << '\n';
big_int p = 7;
for (int n = 1; n <= 73; n += 2, p *= 49) {
std::cout << std::setw(2) << n << " |"
<< std::setw(power_width) << commatize(p) << " |"
<< std::setw(isqrt_width) << commatize(isqrt(p))
<< '\n';
}
return 0;
```

}</lang>

Output:
```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 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
```

## C#

<lang csharp>using System; using static System.Console; using BI = System.Numerics.BigInteger;   class Program {

```   static BI isqrt(BI x) { BI q = 1, r = 0, t; while (q <= x) q <<= 2; while (q > 1) {
q >>= 2; t = x - r - q; r >>= 1; if (t >= 0) { x = t; r += q; } } return r; }
```

```   static void Main() { const int max = 73, smax = 65;
int power_width = ((BI.Pow(7, max).ToString().Length / 3) << 2) + 3,
isqrt_width = (power_width + 1) >> 1;
WriteLine("Integer square root for numbers 0 to {0}:", smax);
for (int n = 0; n <= smax; ++n) Write("{0} ",
(n / 10).ToString().Replace("0", " ")); WriteLine();
for (int n = 0; n <= smax; ++n) Write("{0} ", n % 10); WriteLine();
WriteLine(new String('-', (smax << 1) + 1));
for (int n = 0; n <= smax; ++n) Write("{0} ", isqrt(n));
WriteLine("\n\nInteger square roots of odd powers of 7 from 1 to {0}:", max);
string s = string.Format("[0,2] |[1,{0}:n0] |[2,{1}:n0]",
power_width, isqrt_width).Replace("[", "{").Replace("]", "}");
WriteLine(s, "n", "7 ^ n", "isqrt(7 ^ n)");
WriteLine(new String('-', power_width + isqrt_width + 6));
BI p = 7; for (int n = 1; n <= max; n += 2, p *= 49)
WriteLine (s, n, p, isqrt(p)); }
```

}</lang>

Output:
```Integer square root for numbers 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

Integer square roots of odd powers of 7 from 1 to 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
```

See #Pascal.

## F#

<lang fsharp> // 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

```                             (true,e) when e>=0I->fN e (g/2I+l) (l/4I)
|(true,_)           ->fN i (g/2I)   (l/4I)
|_                  ->g
fN n 0I (let rec fG g=if g>n then g/4I else fG (g*4I) in fG 1I)
```

[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))) </lang>

Output:
```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
```

## Factor

The `isqrt` word is a straightforward translation of the pseudocode from the task description using lexical variables.

Works with: Factor version 0.99 2020-07-03

<lang factor>USING: formatting io kernel locals math math.functions math.ranges prettyprint sequences tools.memory.private ;

isqrt ( x -- n )
```   1 :> q!
[ q x > ] [ q 4 * q! ] until
x 0 :> ( z! r! )
[ q 1 > ] [
q 4 /i q!
z r - q - :> t
r -1 shift r!
t 0 >= [
t z!
r q + r!
] when
] while
r ;
```

"Integer square root for numbers 0 to 65 (inclusive):" print 66 <iota> [ bl ] [ isqrt pprint ] interleave nl nl

align ( str str str -- ) "%2s%85s%44s\n" printf ;
show ( n -- ) dup 7 swap ^ dup isqrt [ commas ] tri@ align ;

"x" "7^x" "isqrt(7^x)" align "-" "---" "----------" align 1 73 2 <range> [ show ] each</lang>

Output:
```Integer square root for numbers 0 to 65 (inclusive):
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8

x                                                                                  7^x                                  isqrt(7^x)
-                                                                                  ---                                  ----------
1                                                                                    7                                           2
3                                                                                  343                                          18
5                                                                               16,807                                         129
7                                                                              823,543                                         907
9                                                                           40,353,607                                       6,352
11                                                                        1,977,326,743                                      44,467
13                                                                       96,889,010,407                                     311,269
15                                                                    4,747,561,509,943                                   2,178,889
17                                                                  232,630,513,987,207                                  15,252,229
19                                                               11,398,895,185,373,143                                 106,765,608
21                                                              558,545,864,083,284,007                                 747,359,260
23                                                           27,368,747,340,080,916,343                               5,231,514,822
25                                                        1,341,068,619,663,964,900,807                              36,620,603,758
27                                                       65,712,362,363,534,280,139,543                             256,344,226,312
29                                                    3,219,905,755,813,179,726,837,607                           1,794,409,584,184
31                                                  157,775,382,034,845,806,615,042,743                          12,560,867,089,291
33                                                7,730,993,719,707,444,524,137,094,407                          87,926,069,625,040
35                                              378,818,692,265,664,781,682,717,625,943                         615,482,487,375,282
37                                           18,562,115,921,017,574,302,453,163,671,207                       4,308,377,411,626,977
39                                          909,543,680,129,861,140,820,205,019,889,143                      30,158,641,881,388,842
41                                       44,567,640,326,363,195,900,190,045,974,568,007                     211,110,493,169,721,897
43                                    2,183,814,375,991,796,599,109,312,252,753,832,343                   1,477,773,452,188,053,281
45                                  107,006,904,423,598,033,356,356,300,384,937,784,807                  10,344,414,165,316,372,973
47                                5,243,338,316,756,303,634,461,458,718,861,951,455,543                  72,410,899,157,214,610,812
49                              256,923,577,521,058,878,088,611,477,224,235,621,321,607                 506,876,294,100,502,275,687
51                           12,589,255,298,531,885,026,341,962,383,987,545,444,758,743               3,548,134,058,703,515,929,815
53                          616,873,509,628,062,366,290,756,156,815,389,726,793,178,407              24,836,938,410,924,611,508,707
55                       30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943             173,858,568,876,472,280,560,953
57                    1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207           1,217,009,982,135,305,963,926,677
59                   72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143           8,519,069,874,947,141,747,486,745
61                3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007          59,633,489,124,629,992,232,407,216
63              174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343         417,434,423,872,409,945,626,850,517
65            8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807       2,922,040,967,106,869,619,387,953,625
67          418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543      20,454,286,769,748,087,335,715,675,381
69       20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607     143,180,007,388,236,611,350,009,727,669
71    1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743   1,002,260,051,717,656,279,450,068,093,686
73   49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407   7,015,820,362,023,593,956,150,476,655,802
```

## FreeBASIC

Odd powers up to 7^21 are shown; more would require an arbitrary precision library that would just add bloat without being illustrative. <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</lang>

Output:
```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```

## 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. <lang go>package main

import (

```   "fmt"
"log"
"math/big"
```

)

var zero = big.NewInt(0) var one = big.NewInt(1)

func isqrt(x *big.Int) *big.Int {

```   if x.Cmp(zero) < 0 {
log.Fatal("Argument cannot be negative.")
}
q := big.NewInt(1)
for q.Cmp(x) <= 0 {
q.Lsh(q, 2)
}
z := new(big.Int).Set(x)
r := big.NewInt(0)
for q.Cmp(one) > 0 {
q.Rsh(q, 2)
t := new(big.Int)
t.Sub(t, r)
t.Sub(t, q)
r.Rsh(r, 1)
if t.Cmp(zero) >= 0 {
z.Set(t)
}
}
return r
```

}

func commatize(s string) string {

```   le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
return s
```

}

func main() {

```   fmt.Println("The integer square roots of integers from 0 to 65 are:")
for i := int64(0); i <= 65; i++ {
fmt.Printf("%d ", isqrt(big.NewInt(i)))
}
fmt.Println()
fmt.Println("\nThe integer square roots of powers of 7 from 7^1 up to 7^73 are:\n")
fmt.Println("power                                    7 ^ power                                                 integer square root")
fmt.Println("----- --------------------------------------------------------------------------------- -----------------------------------------")
pow7 := big.NewInt(7)
bi49 := big.NewInt(49)
for i := 1; i <= 73; i += 2 {
fmt.Printf("%2d %84s %41s\n", i, commatize(pow7.String()), commatize(isqrt(pow7).String()))
pow7.Mul(pow7, bi49)
}
```

}</lang>

Output:
```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
```

## Julia

Translation of: Go

Julia also has a built in isqrt() function which works on integer types, but the function integer_sqrt is shown for the task. <lang julia>using Formatting

function integer_sqrt(x)

```   @assert(x >= 0)
q = one(x)
while q <= x
q <<= 2
end
z, r = x, zero(x)
while q > 1
q >>= 2
t = z - r - q
r >>= 1
if t >= 0
z = t
r += q
end
end
return r
```

end

println("The integer square roots of integers from 0 to 65 are:") println(integer_sqrt.(collect(0:65)))

println("\nThe integer square roots of odd powers of 7 from 7^1 up to 7^73 are:\n") println("power", " "^36, "7 ^ power", " "^60, "integer square root") println("----- ", "-"^80, " ------------------------------------------") pow7 = big"7" for i in 1:2:73

```   println(lpad(i, 2), lpad(format(pow7^i, commas=true), 84),
```

end

</lang>
Output:
```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
```

## Kotlin

Translation of: Go

<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
}
```

}</lang>

Output:
```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```

## Pascal

[1]
Translation of: C++

<lang Pascal> //************************************************// // // // Thanks for rvelthuis for BigIntegers library // // https://github.com/rvelthuis/DelphiBigNumbers // // // //************************************************//

{\$APPTYPE CONSOLE}

{\$R *.res}

uses

``` System.SysUtils,
Velthuis.BigIntegers;
```

function isqrt(x: BigInteger): BigInteger; var

``` q, r, t: BigInteger;
```

begin

``` q := 1;
r := 0;
while (q <= x) do
q := q shl 2;
```
``` while (q > 1) do
begin
q := q shr 2;
t := x - r - q;
r := r shr 1;
if (t >= 0) then
begin
x := t;
r := r + q;
end;
end;
Result := r;
```

end;

function commatize(const n: BigInteger; size: Integer): string; var

``` str: string;
digits: Integer;
i: Integer;
```

begin

``` Result := ;
str := n.ToString;
digits := str.Length;
```
``` for i := 1 to digits do
begin
if ((i > 1) and (((i - 1) mod 3) = (digits mod 3))) then
Result := Result + ',';
Result := Result + str[i];
end;
```
``` if Result.Length < size then
Result := string.Create(' ', size - Result.Length) + Result;
```

end;

const

``` POWER_WIDTH = 83;
ISQRT_WIDTH = 42;
```

var

``` n, i: Integer;
f: TextFile;
p: BigInteger;
```

begin

``` AssignFile(f, 'output.txt');
rewrite(f);
```
``` Writeln(f, 'Integer square root for numbers 0 to 65:');
for n := 0 to 65 do
Write(f, isqrt(n).ToString, ' ');
```
``` Writeln(f, #10#10'Integer square roots of odd powers of 7 from 1 to 73:');
```
``` Write(f, ' n |', string.Create(' ', 78), '7 ^ n |', string.Create(' ', 30),
'isqrt(7 ^ n)'#10);
```
``` Writeln(f, string.Create('-', 17 + POWER_WIDTH + ISQRT_WIDTH));
```
``` p := 7;
n := 1;
repeat
Writeln(f, Format('%2d', [n]), ' |', commatize(p, power_width), ' |',
commatize(isqrt(p), isqrt_width));
inc(n, 2);
p := p * 49;
until (n > 73);
```
``` CloseFile(f);
```

end. </lang>

## Perl

Translation of: Julia

<lang Perl># 20201029 added Perl programming solution

use strict; use warnings; use bigint;

use CLDR::Number 'decimal_formatter';

sub integer_sqrt {

```  ( my \$x = \$_[0] ) >= 0 or die;
my \$q = 1;
while (\$q <= \$x) {
\$q <<= 2
}
my (\$z, \$r) = (\$x, 0);
while (\$q > 1) {
\$q >>= 2;
my \$t = \$z - \$r - \$q;
\$r >>= 1;
if (\$t >= 0) {
\$z  = \$t;
\$r += \$q;
}
}
return \$r
```

}

print "The integer square roots of integers from 0 to 65 are:\n"; 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 = 1; \$i < 74; \$i += 2) {

```  printf("%2s ", \$i);
printf("%82s", \$decf->format( 7**\$i ) );
printf("%44s", \$decf->format( integer_sqrt(7**\$i) ) ) ;
print "\n";
```

}</lang>

Output:
```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
```

## 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). <lang Phix>include mpfr.e

function isqrt(mpz x)

```   if mpz_cmp_si(x,0)<0 then
crash("Argument cannot be negative.")
end if
mpz q = mpz_init(1),
r = mpz_init(0),
t = mpz_init(),
z = mpz_init_set(x)
while mpz_cmp(q,x)<= 0 do
mpz_mul_si(q,q,4)
end while
while mpz_cmp_si(q,1)>0 do
assert(mpz_fdiv_q_ui(q, q, 4)=0)
mpz_sub(t,z,r)
mpz_sub(t,t,q)
assert(mpz_fdiv_q_ui(r, r, 2)=0)
if mpz_cmp_si(t,0) >= 0 then
mpz_set(z,t)
end if
end while
```

-- return r

```   return shorten(mpz_get_str(r,10,true))
```

end function

printf(1,"The integer square roots of integers from 0 to 65 are:\n") for i=0 to 65 do

```   printf(1,"%s ", {isqrt(mpz_init(i))})
```

end for printf(1,"\n\npower 7 ^ power integer square root\n") printf(1,"----- --------------------------------------------------------- ----------------------------------------------------------\n") mpz pow7 = mpz_init(7) for i=1 to 9000 do

```   if (i<=73  and remainder(i,2)=1)
or (i<100  and remainder(i,10)=5)
or (i<1000 and remainder(i,100)=0)
or             remainder(i,1000)=0 then
printf(1,"%4d  %58s %60s\n", {i, shorten(mpz_get_str(pow7,10,true)),isqrt(pow7)})
end if
mpz_mul_si(pow7,pow7,7)
```

end for</lang>

Output:
```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
-----  ---------------------------------------------------------   ----------------------------------------------------------
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,8...,987,545,444,758,743 (44 digits)                                3,548,134,058,703,515,929,815
53     616,873,509,628,062,...,389,726,793,178,407 (45 digits)                               24,836,938,410,924,611,508,707
55     30,226,801,971,775,0...,096,612,865,741,943 (47 digits)                              173,858,568,876,472,280,560,953
57     1,481,113,296,616,97...,734,030,421,355,207 (49 digits)                            1,217,009,982,135,305,963,926,677
59     72,574,551,534,231,9...,967,490,646,405,143 (50 digits)                            8,519,069,874,947,141,747,486,745
61     3,556,153,025,177,36...,407,041,673,852,007 (52 digits)                           59,633,489,124,629,992,232,407,216
63     174,251,498,233,690,...,945,042,018,748,343 (54 digits)                          417,434,423,872,409,945,626,850,517
65     8,538,323,413,450,84...,307,058,918,668,807 (55 digits)                        2,922,040,967,106,869,619,387,953,625
67     418,377,847,259,091,...,045,887,014,771,543 (57 digits)                       20,454,286,769,748,087,335,715,675,381
69     20,500,514,515,695,4...,248,463,723,805,607 (59 digits)                      143,180,007,388,236,611,350,009,727,669
71     1,004,525,211,269,07...,174,722,466,474,743 (61 digits)                    1,002,260,051,717,656,279,450,068,093,686
73     49,221,735,352,184,8...,561,400,857,262,407 (62 digits)                    7,015,820,362,023,593,956,150,476,655,802
75     2,411,865,032,257,05...,508,642,005,857,943 (64 digits)                   49,110,742,534,165,157,693,053,336,590,618
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)
```

(Note that pre-0.8.2 the "(NNN digits)" count includes commas)

## Raku

Since there is already the task Integer roots that covers exactly this operation, with the caveat that it will calculate any nth root (including 2) not just square roots, we'll refer you to that.

See the Integer roots Raku entry.

## REXX

A fair amount of code was included so that the output aligns correctly. <lang rexx>/*REXX program computes and displays the Isqrt (integer square root) of some integers.*/ numeric digits 200 /*insure 'nuff decimal digs for results*/ parse arg range power base . /*obtain optional arguments from the CL*/ if range== | range=="," then range= 0..65 /*Not specified? Then use the default.*/ if power== | power=="," then power= 1..73 /* " " " " " " */ if base == | base =="," then base = 7 /* " " " " " " */ parse var range rLO '..' rHI; if rHI== then rHI= rLO /*handle a range? */ parse var power pLO '..' pHI; if pHI== then pHI= pLO /* " " " */ \$=

```           do j=rLO  to rHI  while rHI>0        /*compute Isqrt for a range of integers*/
\$= \$ commas( Isqrt(j) )              /*append the Isqrt to a list for output*/
end   /*j*/
```

\$= strip(\$) /*elide the leading blank in the list. */ say center(' Isqrt for numbers: ' rLO " ──► " rHI' ', length(\$), "─") say strip(\$) /*\$ has a leading blank for 1st number*/ say z= base ** pHI /*compute max. exponentiation product.*/ Lp= max(30, length( commas( z) ) ) /*length of " " " */ Lr= max(20, length( commas( Isqrt(z) ) ) ) /* " " " " " Isqrt of above.*/ say 'index' center(base"**index", Lp) center('Isqrt', Lr) /*show a title.*/ say '─────' copies("─", Lp) copies('─', Lr) /* " " header*/

```           do j=pLO  to pHI  by 2  while pHI>0;                              x= base ** j
say center(j, 5)  right( commas(x), Lp)      right( commas( Isqrt(x) ),  Lr)
end   /*j*/                          /* [↑]  show a bunch of powers & Isqrt.*/
```

exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _ /*──────────────────────────────────────────────────────────────────────────────────────*/ Isqrt: procedure; parse arg x /*obtain the only passed argument X. */

```      x= x % 1                                  /*convert possible real X to an integer*/     /* ◄■■■■■■■  optional. */
q= 1                                      /*initialize the  Q  variable to unity.*/
do until q>x      /*find a  Q  that is greater than  X.  */
q= q * 4          /*multiply   Q   by four.              */
end   /*until*/
r= 0                                      /*R:    will be the integer sqrt of X. */
do while q>1                    /*keep processing while  Q  is > than 1*/
q= q % 4                        /*divide  Q  by four  (no remainder).  */
t= x - r - q                    /*compute a temporary variable.        */
r= r % 2                        /*divide  R  by two   (no remainder).  */
if t >= 0  then do              /*if   T  is non─negative  ...         */
x= t            /*recompute the value of  X            */
r= r + q        /*    "      "    "    "  R            */
end
end   /*while*/
return r                                  /*return the integer square root of X. */</lang>
```
output   when using the default inputs:
```───────────────────────────────────────────────── Isqrt for numbers:  0  ──►  65 ──────────────────────────────────────────────────
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8

index                                      7**index                                                        Isqrt
───── ────────────────────────────────────────────────────────────────────────────────── ─────────────────────────────────────────
1                                                                                    7                                         2
3                                                                                  343                                        18
5                                                                               16,807                                       129
7                                                                              823,543                                       907
9                                                                           40,353,607                                     6,352
11                                                                        1,977,326,743                                    44,467
13                                                                       96,889,010,407                                   311,269
15                                                                    4,747,561,509,943                                 2,178,889
17                                                                  232,630,513,987,207                                15,252,229
19                                                               11,398,895,185,373,143                               106,765,608
21                                                              558,545,864,083,284,007                               747,359,260
23                                                           27,368,747,340,080,916,343                             5,231,514,822
25                                                        1,341,068,619,663,964,900,807                            36,620,603,758
27                                                       65,712,362,363,534,280,139,543                           256,344,226,312
29                                                    3,219,905,755,813,179,726,837,607                         1,794,409,584,184
31                                                  157,775,382,034,845,806,615,042,743                        12,560,867,089,291
33                                                7,730,993,719,707,444,524,137,094,407                        87,926,069,625,040
35                                              378,818,692,265,664,781,682,717,625,943                       615,482,487,375,282
37                                           18,562,115,921,017,574,302,453,163,671,207                     4,308,377,411,626,977
39                                          909,543,680,129,861,140,820,205,019,889,143                    30,158,641,881,388,842
41                                       44,567,640,326,363,195,900,190,045,974,568,007                   211,110,493,169,721,897
43                                    2,183,814,375,991,796,599,109,312,252,753,832,343                 1,477,773,452,188,053,281
45                                  107,006,904,423,598,033,356,356,300,384,937,784,807                10,344,414,165,316,372,973
47                                5,243,338,316,756,303,634,461,458,718,861,951,455,543                72,410,899,157,214,610,812
49                              256,923,577,521,058,878,088,611,477,224,235,621,321,607               506,876,294,100,502,275,687
51                           12,589,255,298,531,885,026,341,962,383,987,545,444,758,743             3,548,134,058,703,515,929,815
53                          616,873,509,628,062,366,290,756,156,815,389,726,793,178,407            24,836,938,410,924,611,508,707
55                       30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943           173,858,568,876,472,280,560,953
57                    1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207         1,217,009,982,135,305,963,926,677
59                   72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143         8,519,069,874,947,141,747,486,745
61                3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007        59,633,489,124,629,992,232,407,216
63              174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343       417,434,423,872,409,945,626,850,517
65            8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807     2,922,040,967,106,869,619,387,953,625
67          418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543    20,454,286,769,748,087,335,715,675,381
69       20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607   143,180,007,388,236,611,350,009,727,669
71    1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686
73   49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802
```

## Ruby

<lang ruby>class Integer

``` def commatize
self.to_s.gsub( /(\d)(?=\d{3}+(?:\.|\$))(\d{3}\..*)?/, "\\1,\\2")
end
```

end

puts (0..65).map{|n| Integer.sqrt(n) }.join(" ")

1.step(73, 2) do |n|

``` print "#{n}:\t"
puts Integer.sqrt(7**n).commatize
```

end </lang>

Output:
```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
73:	7,015,820,362,023,593,956,150,476,655,802
```

## Seed7

<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 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(sqrt(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
pow7 := pow7 * 49_;
end for;
end func;</lang>
```
Output:
```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
```

## Swift

Translation of: C++

Requires the attaswift BigInt package. <lang swift>import BigInt

func integerSquareRoot<T: BinaryInteger>(_ num: T) -> T {

```   var x: T = num
var q: T = 1
while q <= x {
q <<= 2
}
var r: T = 0
while q > 1 {
q >>= 2
let t: T = x - r - q
r >>= 1
if t >= 0 {
x = t
r += q
}
}
return r
```

}

func pad(string: String, width: Int) -> String {

```   if string.count >= width {
return string
}
return String(repeating: " ", count: width - string.count) + string
```

}

func commatize<T: BinaryInteger>(_ num: T) -> String {

```   let string = String(num)
var result = String()
result.reserveCapacity(4 * string.count / 3)
var i = 0
for ch in string {
if i > 0 && i % 3 == string.count % 3 {
result += ","
}
result.append(ch)
i += 1
}
return result
```

}

print("Integer square root for numbers 0 to 65:") for n in 0...65 {

```   print(integerSquareRoot(n), terminator: " ")
```

}

let powerWidth = 83 let isqrtWidth = 42 print("\n\nInteger square roots of odd powers of 7 from 1 to 73:") print(" n |\(pad(string: "7 ^ n", width: powerWidth)) |\(pad(string: "isqrt(7 ^ n)", width: isqrtWidth))") print(String(repeating: "-", count: powerWidth + isqrtWidth + 6)) var p: BigInt = 7 for n in stride(from: 1, through: 73, by: 2) {

```   let power = pad(string: commatize(p), width: powerWidth)
let isqrt = pad(string: commatize(integerSquareRoot(p)), width: isqrtWidth)
print("\(pad(string: String(n), width: 2)) |\(power) |\(isqrt)")
p *= 49
```

}</lang>

Output:
```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 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
```

## Tiny BASIC

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. <lang Tiny 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</lang>

## Visual Basic .NET

Translation of: C#

<lang vbnet>Imports System Imports System.Console Imports BI = System.Numerics.BigInteger

Module Module1

```   Function isqrt(ByVal x As BI) As BI
Dim t As BI, q As BI = 1, r As BI = 0
While q <= x : q <<= 2 : End While
While q > 1 : q >>= 2 : t = x - r - q : r >>= 1
If t >= 0 Then x = t : r += q
End While : Return r
End Function
```
```   Sub Main()
Const max As Integer = 73, smax As Integer = 65
Dim power_width As Integer = ((BI.Pow(7, max).ToString().Length \ 3) << 2) + 3,
isqrt_width As Integer = (power_width + 1) >> 1,
n as Integer
WriteLine("Integer square root for numbers 0 to {0}:", smax)
For n = 0 To smax : Write("{0} ", (n \ 10).ToString().Replace("0", " "))
Next : WriteLine()
For n = 0 To smax : Write("{0} ", n Mod 10) : Next : WriteLine()
WriteLine(New String("-"c, (smax << 1) + 1))
For n = 0 To smax : Write("{0} ", isqrt(n)) : Next
WriteLine(vbLf & vbLf & "Integer square roots of odd powers of 7 from 1 to {0}:", max)
Dim s As String = String.Format("[0,2] |[1,{0}:n0] |[2,{1}:n0]",
power_width, isqrt_width).Replace("[", "{").Replace("]", "}")
WriteLine(s, "n", "7 ^ n", "isqrt(7 ^ n)")
WriteLine(New String("-"c, power_width + isqrt_width + 6))
Dim p As BI = 7 : n = 1 : While n <= max
WriteLine(s, n, p, isqrt(p)) : n += 2 : p = p * 49
End While
End Sub
```

End Module</lang>

Output:
```Integer square root for numbers 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

Integer square roots of odd powers of 7 from 1 to 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
```

## Wren

Library: Wren-big
Library: Wren-fmt

<lang ecmascript>import "/big" for BigInt import "/fmt" for Fmt

var isqrt = Fn.new { |x|

```   if (!(x is BigInt && x >= BigInt.zero)) {
Fiber.abort("Argument must be a non-negative big integer.")
}
var q = BigInt.one
while (q <= x) q = q * 4
var z = x
var r = BigInt.zero
while (q > BigInt.one) {
q = q >> 2
var t = z - r - q
r = r >> 1
if (t >= 0) {
z = t
r = r + q
}
}
return r
```

}

System.print("The integer square roots of integers from 0 to 65 are:") for (i in 0..65) System.write("%(isqrt.call(BigInt.new(i))) ") System.print()

System.print("\nThe integer square roots of powers of 7 from 7^1 up to 7^73 are:\n") System.print("power 7 ^ power integer square root") System.print("----- --------------------------------------------------------------------------------- -----------------------------------------") var pow7 = BigInt.new(7) var bi49 = BigInt.new(49) var i = 1 while (i <= 73) {

```   Fmt.print("\$2d \$,84s \$,41s", i, pow7, isqrt.call(pow7))
pow7 = pow7 * bi49
i = i + 2
```

}</lang>

Output:
```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
```