I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Isqrt (integer square root) of X

From Rosetta Code
Task
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.


Pseudo─code using quadratic residue

For this task, the integer square root of a non─negative number will be computed using a version of   quadratic residue,   which has the advantage that no   floating point   calculations are used,   only integer arithmetic.   Furthermore, the 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


Task

Compute and show all output here   (on this page)   for:

  •   the Isqrt of the     integers     from     0 ───► 65    (inclusive), shown in a horizontal format.
  •   the Isqrt of the   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.


Related tasks



ALGOL 68[edit]

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

Implements the task pseudo-code.

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
END; # pad left #
# task test cases #
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
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++[edit]

Library: Boost
#include <iomanip>
#include <iostream>
#include <sstream>
#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;
}
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#[edit]

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)); }
}
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

Delphi[edit]

See #Pascal.

F#[edit]

 
// 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)))
 
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[edit]

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
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 ] [email protected] align ;
 
"x" "7^x" "isqrt(7^x)" align
"-" "---" "----------" align
1 73 2 <range> [ show ] each
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

Go[edit]

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.

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.Add(t, z)
t.Sub(t, r)
t.Sub(t, q)
r.Rsh(r, 1)
if t.Cmp(zero) >= 0 {
z.Set(t)
r.Add(r, q)
}
}
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)
}
}
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[edit]

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.

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),
lpad(format(integer_sqrt(pow7^i), commas=true), 43))
end
 
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

Pascal[edit]

[1]
Translation of: C++
 
//************************************************//
// //
// Thanks for rvelthuis for BigIntegers library //
// https://github.com/rvelthuis/DelphiBigNumbers //
// //
//************************************************//
 
program IsqrtTask;
 
{$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.
 

Phix[edit]

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).

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)
mpz_add(r,r,q)
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
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[edit]

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[edit]

A fair amount of code was included so that the output aligns correctly.

/*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. */
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[edit]

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

Swift[edit]

Translation of: C++

Requires the attaswift BigInt package.

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
}
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[edit]

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.

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

Visual Basic .NET[edit]

Translation of: C#
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
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[edit]

Library: Wren-big
Library: Wren-fmt
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
}
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