Isqrt (integer square root) of X: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|Factor}}: variable t doesn't need to be mutable)
(Added C++ solution)
Line 90: Line 90:
:*   [https://rosettacode.org/wiki/Sequence_of_non-squares sequence of non─squares sequence].
:*   [https://rosettacode.org/wiki/Sequence_of_non-squares sequence of non─squares sequence].
<br><br>__TOC__
<br><br>__TOC__

=={{header|C++}}==
{{libheader|Boost}}
<lang cpp>#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;
}</lang>

{{out}}
<pre>
Integer square root for numbers 0 to 65:
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8

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


=={{header|Factor}}==
=={{header|Factor}}==

Revision as of 13:51, 16 July 2020

Isqrt (integer square root) of X is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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



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

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

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

}</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 odd integer square roots of 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

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


Phix

See also Integer_roots#Phix for a simpler and shorter example using the mpz_root() routine. <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(0),
       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
       if mpz_fdiv_q_ui(q, q, 4)!=0 then ?9/0 end if
       mpz_sub(t,z,r)
       mpz_sub(t,t,q)
       if mpz_fdiv_q_ui(r, r, 2)!=0 then ?9/0 end if
       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<10
   or (i<100 and remainder(i,10)=0)
   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
   2                                                          49                                                            7
   3                                                         343                                                           18
   4                                                       2,401                                                           49
   5                                                      16,807                                                          129
   6                                                     117,649                                                          343
   7                                                     823,543                                                          907
   8                                                   5,764,801                                                        2,401
   9                                                  40,353,607                                                        6,352
  10                                                 282,475,249                                                       16,807
  20                                      79,792,266,297,612,001                                                  282,475,249
  30                          22,539,340,290,692,258,087,863,249                                            4,747,561,509,943
  40               6,366,805,760,909,027,985,741,435,139,224,001                                       79,792,266,297,612,001
  50     1,798,465,042,647,41...,569,649,349,251,249 (43 digits)                                1,341,068,619,663,964,900,807
  60     508,021,860,739,623,...,772,434,524,836,001 (51 digits)                           22,539,340,290,692,258,087,863,249
  70     143,503,601,609,868,...,739,246,066,639,249 (60 digits)                      378,818,692,265,664,781,682,717,625,943
  80     40,536,215,597,144,3...,746,192,454,448,001 (68 digits)                6,366,805,760,909,027,985,741,435,139,224,001
  90     11,450,477,594,321,0...,372,120,240,027,249 (77 digits)          107,006,904,423,598,033,356,356,300,384,937,784,807
 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

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
Retrieved from "https://rosettacode.org/wiki/Isqrt_(integer_square_root)_of_X?oldid=301056"