Isqrt (integer square root) of X: Difference between revisions
Isqrt (integer square root) of X (view source)
Revision as of 12:06, 11 December 2023
, 5 months ago→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
(42 intermediate revisions by 18 users not shown) | |||
Line 101:
{{trans|D}}
<
V s = reversed(String(number))
String r = s[0]
Line 141:
L(i) (1..73).step(2)
print(‘#2 #84 #41’.format(i, commatize(pow7), commatize(isqrt(pow7))))
pow7 *= bi49</
{{out}}
Line 191:
=={{header|Ada}}==
{{works with|Ada 2022}}
<
with Ada.Numerics.Big_Numbers.Big_Integers;
with Ada.Strings.Fixed;
Line 277:
end;
end Integer_Square_Root;</
{{out}}
<pre>
Line 331:
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Implements the task pseudo-code.
<
PR precision 200 PR
# returns the integer square root of x; x must be >= 0 #
Line 396:
p7 *:= 49
OD
END</
{{out}}
<pre>
Line 440:
71| 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743| 1,002,260,051,717,656,279,450,068,093,686
73|49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407| 7,015,820,362,023,593,956,150,476,655,802
</pre>
=={{header|ALGOL W}}==
Algol W integers are restricted to signed 32-bit, so only the roots of the powers of 7 up to 7^9 are shown (7^11 will fit in 32-bits but the smallest power of 4 higher than 7^11 will overflow).
<syntaxhighlight lang="algolw">
begin % Integer square roots by quadratic residue %
% returns the integer square root of x - x must be >= 0 %
integer procedure iSqrt ( integer value x ) ;
if x < 0 then begin assert x >= 0; 0 end
else if x < 2 then x
else begin
% x is greater than 1 %
integer q, r, t, z;
% find a power of 4 that's greater than x %
q := 1;
while q <= x do q := q * 4;
% find the root %
z := x;
r := 0;
while q > 1 do begin
q := q div 4;
t := z - r - q;
r := r div 2;
if t >= 0 then begin
z := t;
r := r + q
end if_t_ge_0
end while_q_gt_1 ;
r
end isqrt;
% writes n in 14 character positions with separator commas %
procedure writeonWithCommas ( integer value n ) ;
begin
string(10) decDigits;
string(14) r;
integer v, cPos, dCount;
decDigits := "0123456789";
v := abs n;
r := " ";
r( 13 // 1 ) := decDigits( v rem 10 // 1 );
v := v div 10;
cPos := 12;
dCount := 1;
while cPos > 0 and v > 0 do begin
r( cPos // 1 ) := decDigits( v rem 10 // 1 );
v := v div 10;
cPos := cPos - 1;
dCount := dCount + 1;
if v not = 0 and dCount = 3 then begin
r( cPos // 1 ) := ",";
cPos := cPos - 1;
dCount := 0
end if_v_ne_0_and_dCount_eq_3
end for_cPos;
r( cPos // 1 ) := if n < 0 then "-" else " ";
writeon( s_w := 0, r )
end writeonWithCommas ;
begin % task test cases %
integer prevI, prevR, root, p7;
write( "Integer square roots of 0..65 (values the same as the previous one not shown):" );
write();
prevR := prevI := -1;
for i := 0 until 65 do begin
root := iSqrt( i );
if root not = prevR then begin
prevR := root;
prevI := i;
writeon( i_w := 1, s_w := 0, " ", i, ":", root )
end
else if prevI = i - 1 then writeon( "..." );
end for_i ;
write();
% integer square roots of odd powers of 7 %
write( "Integer square roots of 7^n, odd n" );
write( " n| 7^n| isqrt(7^n)" );
write( " -+--------------+--------------" );
p7 := 7;
for p := 1 step 2 until 9 do begin
write( i_w := 2, s_w := 0, p );
writeon( s_w := 0, "|" ); writeonWithCommas( p7 );
writeon( s_w := 0, "|" ); writeonWithCommas( iSqrt( p7 ) );
p7 := p7 * 49
end for_p
end task_test_cases
end.
</syntaxhighlight>
{{out}}
<pre>
Integer square roots of 0..65 (values the same as the previous one not shown):
0:0 1:1... 4:2... 9:3... 16:4... 25:5... 36:6... 49:7... 64:8...
Integer square roots of 7^n, odd n
n| 7^n| isqrt(7^n)
-+--------------+--------------
1| 7| 2
3| 343| 18
5| 16,807| 129
7| 823,543| 907
9| 40,353,607| 6,352
</pre>
=={{header|ALGOL-M}}==
The
<
BEGIN
COMMENT
RETURN INTEGER SQUARE ROOT OF N USING QUADRATIC RESIDUE
ALGORITHM. WARNING: THE FUNCTION WILL FAIL FOR X GREATER
THAN 4095;
INTEGER FUNCTION ISQRT(X);
INTEGER X;
BEGIN
INTEGER
Q := Q * 4; % WARNING! OVERFLOW YIELDS 0 %
Z := X;
R := 0;
WHILE Q > 1 DO
BEGIN
R := R / 2;
IF T >= 0 THEN
BEGIN
Z := T;
R := R + Q;
END;
END;
ISQRT :=
END;
Line 492 ⟶ 603:
END
</syntaxhighlight>
An alternative to the quadratic residue approach will allow calculation of the integer square root for the full range of signed integer values supported by ALGOL-M. (The output is identical.)
<
% RETURN INTEGER SQUARE ROOT OF N %
INTEGER FUNCTION ISQRT(N);
INTEGER N;
BEGIN
INTEGER
WHILE R1 > R2 DO
BEGIN
END;
ISQRT :=
END;
</syntaxhighlight>
{{out}}
<pre>
Line 543 ⟶ 642:
The odd-powers-of-7 part of the task is limited by the precision of AppleScript reals.
<
set q to 1
repeat until (q > x)
Line 597 ⟶ 696:
end doTask
doTask()</
{{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
Isqrts of odd powers of 7 from 1 to 17:
Line 611 ⟶ 710:
7^13 (96,889,010,407): 311,269
7^15 (4,747,561,509,943): 2,178,889
7^17 (232,630,513,987,207): 15,252,229"</
=={{header|APL}}==
Works in [[Dyalog APL]]
<
q←(×∘4)⍣{⍺>x}⊢1
⊃{ r z q←⍵
Line 627 ⟶ 726:
q≤1
}⊢0 x q
}</
{{output}}
<pre>
Line 652 ⟶ 751:
=={{header|Arturo}}==
<
reverse join.with:"," map split.every: 3 split reverse to :string x => join
]
Line 677 ⟶ 776:
loop range 1 .step: 2 72 'n ->
print [n "\t" commatize isqrt 7^n]</
{{out}}
Line 726 ⟶ 825:
<
Compile with "myatscc isqrt.dats", thus obtaining an executable called
Line 945 ⟶ 1,044:
print! ("-----------------------------------------------------------------------------------------------------------------------------------\n");
do_the_roots_of_odd_powers_of_7 ();
end</
{{out}}
Line 996 ⟶ 1,095:
71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686
73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802</pre>
=={{header|BASIC256}}==
<syntaxhighlight lang="basic256">print "Integer square root of first 65 numbers:"
for n = 1 to 65
print ljust(isqrt(n),3);
next n
print : print
print "Integer square root of odd powers of 7"
print " n 7^n isqrt"
print "-"*36
for n = 1 to 21 step 2
pow7 = int(7 ^ n)
print rjust(n,3);rjust(pow7,20);rjust(isqrt(pow7),12)
next n
end
function isqrt(x)
q = 1
while q <= x
q *= 4
end while
r = 0
while q > 1
q /= 4
t = x - r - q
r /= 2
if t >= 0 then
x = t
r += q
end if
end while
return int(r)
end function</syntaxhighlight>
=={{header|C}}==
{{trans|C++}}
Up to 64-bit limits with no big int library.
<
#include <stdio.h>
Line 1,037 ⟶ 1,169:
printf("%2d | %18lld | %12lld\n", n, p, isqrt(p));
}
}</
{{out}}
<pre>Integer square root for numbers 0 to 65:
Line 1,058 ⟶ 1,190:
=={{header|C++}}==
{{libheader|Boost}}
<
#include <iostream>
#include <sstream>
Line 1,119 ⟶ 1,251:
}
return 0;
}</
{{out}}
<pre style="font-size: 11px">
Integer square root for numbers 0 to 65:
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
Line 1,170 ⟶ 1,302:
=={{header|C#|CSharp}}==
{{libheader|System.Numerics}}
<
using static System.Console;
using BI = System.Numerics.BigInteger;
Line 1,195 ⟶ 1,327:
BI p = 7; for (int n = 1; n <= max; n += 2, p *= 49)
WriteLine (s, n, p, isqrt(p)); }
}</
{{Out}}
<pre>Integer square root for numbers 0 to 65:
Line 1,245 ⟶ 1,377:
</pre>
=={{header|CLU}}==
<
% Integer square root of a bigint
Line 1,312 ⟶ 1,444:
stream$putl(po, "")
end
end start_up</
{{out}}
<pre>isqrt of 0..65:
Line 1,358 ⟶ 1,490:
=={{header|
The COBOL compiler used here is limited to 18-digit math, meaning 7^19 is the largest odd power of 7 that can be calculated.
<syntaxhighlight lang="cobol"> IDENTIFICATION DIVISION.
PROGRAM-ID. I-SQRT.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 QUAD-RET-VARS.
03 X PIC 9(18).
03 Q PIC 9(18).
03 Z PIC 9(18).
03 T PIC S9(18).
03 R PIC 9(18).
01 TO-65-VARS.
03 ISQRT-N PIC 99.
03 DISP-LN PIC X(22) VALUE SPACES.
03 DISP-FMT PIC Z9.
03 PTR PIC 99 VALUE 1.
01 BIG-SQRT-VARS.
03 POW-7 PIC 9(18) VALUE 7.
03 POW-N PIC 99 VALUE 1.
03 POW-N-OUT PIC Z9.
03 POW-7-OUT PIC Z(10).
PROCEDURE DIVISION.
BEGIN.
PERFORM SQRTS-TO-65.
PERFORM BIG-SQRTS.
STOP RUN.
SQRTS-TO-65.
PERFORM DISP-SMALL-SQRT
VARYING ISQRT-N FROM 0 BY 1
UNTIL ISQRT-N IS GREATER THAN 65.
DISP-SMALL-SQRT.
MOVE ISQRT-N TO X.
PERFORM ISQRT.
MOVE R TO DISP-FMT.
STRING DISP-FMT DELIMITED BY SIZE INTO DISP-LN
WITH POINTER PTR.
IF PTR IS GREATER THAN 22,
DISPLAY DISP-LN,
MOVE 1 TO PTR.
BIG-SQRTS.
PERFORM BIG-SQRT 10 TIMES.
BIG-SQRT.
MOVE POW-7 TO X.
PERFORM ISQRT.
MOVE POW-N TO POW-N-OUT.
MOVE R TO POW-7-OUT.
DISPLAY "ISQRT(7^" POW-N-OUT ") = " POW-7-OUT.
ADD 2 TO POW-N.
MULTIPLY 49 BY POW-7.
ISQRT.
MOVE 1 TO Q.
PERFORM MUL-Q-BY-4 UNTIL Q IS GREATER THAN X.
MOVE X TO Z.
MOVE ZERO TO R.
PERFORM ISQRT-STEP UNTIL Q IS NOT GREATER THAN 1.
MUL-Q-BY-4.
MULTIPLY 4 BY Q.
ISQRT-STEP.
DIVIDE 4 INTO Q.
COMPUTE T = Z - R - Q.
DIVIDE 2 INTO R.
IF T IS NOT LESS THAN ZERO,
MOVE T TO Z,
ADD Q TO R.</syntaxhighlight>
{{out}}
<pre> 0 1 1 1 2 2 2 2 2 3 3
3 3 3 3 3 4 4 4 4 4 4
4 4 4 5 5 5 5 5 5 5 5
5 5 5 6 6 6 6 6 6 6 6
6 6 6 6 6 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 8 8
ISQRT(7^ 1) = 2
ISQRT(7^ 3) = 18
ISQRT(7^ 5) = 129
ISQRT(7^ 7) = 907
ISQRT(7^ 9) = 6352
ISQRT(7^11) = 44467
ISQRT(7^13) = 311269
ISQRT(7^15) = 2178889
ISQRT(7^17) = 15252229
ISQRT(7^19) = 106765608</pre>
=={{header|Common Lisp}}==
{{trans|Scheme}}
Line 1,375 ⟶ 1,604:
<
#|-*- mode:lisp -*-|#
#|
Line 1,440 ⟶ 1,669:
do (format t "~2D ~84:D ~43:D~%" i 7**i root)))
;;; vim: set ft=lisp lisp:</
{{out}}
Line 1,490 ⟶ 1,719:
71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686
73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802</pre>
=={{header|Cowgol}}==
<
# Integer square root
Line 1,546 ⟶ 1,773:
print_nl();
x := x + 1;
end loop;</
{{out}}
Line 1,568 ⟶ 1,795:
isqrt(7^10) = 16807
isqrt(7^11) = 44467</pre>
=={{header|Craft Basic}}==
<syntaxhighlight lang="basic">alert "integer square root of first 65 numbers:"
for n = 1 to 65
let x = n
gosub isqrt
print r
next n
alert "integer square root of odd powers of 7"
cls
cursor 1, 1
for n = 1 to 21 step 2
let x = 7 ^ n
gosub isqrt
print "isqrt of 7 ^ ", n, " = ", r
next n
end
sub isqrt
let q = 1
do
if q <= x then
let q = q * 4
endif
wait
loop q <= x
let r = 0
do
if q > 1 then
let q = q / 4
let t = x - r - q
let r = r / 2
if t >= 0 then
let x = t
let r = r + q
endif
endif
loop q > 1
let r = int(r)
return</syntaxhighlight>
{{out| Output}}<pre>integer square root of first 65 numbers:
1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
integer square root of odd powers of 7:
isqrt of 7 ^ 1 = 2
isqrt of 7 ^ 3 = 18
isqrt of 7 ^ 5 = 129
isqrt of 7 ^ 7 = 907
isqrt of 7 ^ 9 = 6352</pre>
=={{header|D}}==
{{trans|Kotlin}}
<
import std.conv;
import std.exception;
Line 1,650 ⟶ 1,952:
pow7 *= bi49;
}
}</
{{out}}
<pre>The integer square root of integers from 0 to 65 are:
Line 1,701 ⟶ 2,003:
Because all the intermediate values have to fit in a signed 32-bit integer, the largest power of 7
for which the square root can be calculated is 7^10.
<
proc nonrec isqrt(ulong x) ulong:
ulong q, z, r;
Line 1,740 ⟶ 2,042:
pow7 := pow7 * 7
od
corp</
{{out}}
<pre> 0 1 1 1 2 2 2 2 2 3 3
Line 1,759 ⟶ 2,061:
isqrt(7^ 9) = 6352
isqrt(7^10) = 16807</pre>
=={{header|EasyLang}}==
{{trans|Lua}}
<syntaxhighlight lang=easylang>
func isqrt x .
q = 1
while q <= x
q *= 4
.
while q > 1
q = q div 4
t = x - r - q
r = r div 2
if t >= 0
x = t
r = r + q
.
.
return r
.
print "Integer square roots from 0 to 65:"
for n = 0 to 65
write isqrt n & " "
.
print ""
print ""
print "Integer square roots of 7^n"
p = 7
n = 1
while n <= 21
print n & " " & isqrt p
n = n + 2
p = p * 49
.
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
<
// Find Integer Floor sqrt of a Large Integer. Nigel Galloway: July 17th., 2020
let Isqrt n=let rec fN i g l=match(l>0I,i-g-l) with
Line 1,770 ⟶ 2,108:
[0I..65I]|>Seq.iter(Isqrt>>string>>printf "%s "); printfn "\n"
let fN n=7I**n in [1..2..73]|>Seq.iter(fN>>Isqrt>>printfn "%a" (fun n g -> n.Write("{0:#,#}", g)))
</syntaxhighlight>
{{out}}
<pre>
Line 1,817 ⟶ 2,155:
The <code>isqrt</code> word is a straightforward translation of the pseudocode from the task description using lexical variables.
{{works with|Factor|0.99 2020-07-03}}
<
math.ranges prettyprint sequences tools.memory.private ;
Line 1,843 ⟶ 2,181:
"x" "7^x" "isqrt(7^x)" align
"-" "---" "----------" align
1 73 2 <range> [ show ] each</
{{out}}
<pre>
Line 1,894 ⟶ 2,232:
Código sacado de https://esolangs.org/wiki/Fish
<
]~$\!?={:,2+/n</
=={{header|Forth}}==
Only handles odd powers of 7 up to 7^21.
<syntaxhighlight lang="forth">
: d., ( n -- ) \ write double precision int, commatized.
tuck dabs
Line 1,941 ⟶ 2,279:
task1 cr task2 bye
</syntaxhighlight>
This version of the core word does not require locals.
<syntaxhighlight lang="text">: sqrt-rem ( n -- sqrt rem)
>r 0 1 begin dup r@ > 0= while 4 * repeat
begin \ find a power of 4 greater than TORS
Line 1,953 ⟶ 2,291:
;
: isqrt-mod sqrt-rem swap ;</
{{Out}}
<pre>
Line 1,974 ⟶ 2,312:
=={{header|Fortran}}==
<
IMPLICIT NONE
Line 2,009 ⟶ 2,347:
T = 0
DO WHILE (Q .
Q = Q * 4
END DO
Line 2,070 ⟶ 2,408:
END PROGRAM ISQRT_DEMO</
<pre>
Integer square root for numbers 0 to 65
Line 2,101 ⟶ 2,439:
43 | 2,183,814,375,991,796,599,109,312,252,753,832,343 | 1,477,773,452,188,053,281
</pre>
=={{header|FreeBASIC}}==
Odd powers up to 7^21 are shown; more would require an arbitrary precision library that would just add bloat without being illustrative.
<
function isqrt( byval x as ulongint ) as ulongint
dim as ulongint q = 1, r
Line 2,143 ⟶ 2,482:
ns = str(isqrt(7^i))
print i, commatize(ns)
next i</
{{out}}
<pre>0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
Line 2,157 ⟶ 2,496:
19 106,765,608
21 747,359,260</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
include "NSLog.incl"
local fn IntSqrt( x as SInt64 ) as SInt64
SInt64 q = 1, z = x, r = 0, t
do
q = q * 4
until ( q > x )
while( q > 1 )
q = q / 4 : t = z - r - q : r = r / 2
if ( t > -1 ) then z = t : r = r + q
wend
end fn = r
SInt64 p
NSInteger n
CFNumberRef tempNum
CFStringRef tempStr
NSLog( @"Integer square root for numbers 0 to 65:" )
for n = 0 to 65
NSLog( @"%lld \b", fn IntSqrt( n ) )
next
NSLog( @"\n" )
NSLog( @"Integer square roots of odd powers of 7 from 1 to 21:" )
NSLog( @" n | 7 ^ n | fn IntSqrt(7 ^ n)" )
p = 7
for n = 1 to 21 step 2
tempNum = fn NumberWithLongLong( fn IntSqrt(p) )
tempStr = fn NumberDescriptionWithLocale( tempNum, fn LocaleCurrent )
NSLog( @"%2d | %18lld | %12s", n, p, fn StringUTF8String( tempStr ) )
p = p * 49
next
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
Integer square root for numbers 0 to 65:
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
Integer square roots of odd powers of 7 from 1 to 21:
n | 7 ^ n | fn IntSqrt(7 ^ n)
1 | 7 | 2
3 | 343 | 18
5 | 16807 | 129
7 | 823543 | 907
9 | 40353607 | 6,352
11 | 1977326743 | 44,467
13 | 96889010407 | 311,269
15 | 4747561509943 | 2,178,889
17 | 232630513987207 | 15,252,229
19 | 11398895185373143 | 106,765,608
21 | 558545864083284007 | 747,359,260
</pre>
=={{header|Go}}==
Go's big.Int type already has a built-in integer square root function but, as the point of this task appears to be to compute it using a particular algorithm, we re-code it from the pseudo-code given in the task description.
<
import (
Line 2,219 ⟶ 2,619:
pow7.Mul(pow7, bi49)
}
}</
{{out}}
Line 2,271 ⟶ 2,671:
=={{header|Haskell}}==
<
isqrt :: Integer -> Integer
Line 2,285 ⟶ 2,685:
main = do
print $ isqrt <$> [1..65]
mapM_ print $ zip [1,3..73] (isqrt <$> iterate (49 *) 7)</
<pre>*Main> main
Line 2,329 ⟶ 2,729:
=={{header|Icon}}==
<
link printf
Line 2,386 ⟶ 2,786:
while q <= x do q := ishift(q, 2)
return q
end</
{{out}}
Line 2,440 ⟶ 2,840:
=={{header|J}}==
Three implementations given. The floating point method is best for small square roots, Newton's method is fastest for extended integers. isqrt adapted from the page preamble. Note that the "floating point method" is exact when arbitrary precision integers or rational numbers are used.
<syntaxhighlight lang="j">
isqrt_float=: <.@:%:
isqrt_newton=: 9&$: :(x:@:<.@:-:@:(] + x:@:<.@:%)^:_&>~&:x:)
Line 2,470 ⟶ 2,870:
NB. r , z
)
</syntaxhighlight>
The first line here shows that the simplest approach (the "floating point square root") is treated specially by J.
<pre> <.@%: 1000000000000000000000000000000000000000000000000x
1000000000000000000000000
(,. isqrt_float) 7x ^ 20 21x
79792266297612001 282475249
Line 2,591 ⟶ 2,995:
1,002,260,051,717,656,279,450,068,093,686
49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407
7,015,820,362,023,593,956,150,476,655,802
NB. isqrt_float is exact for large integers
align comma (,.isqrt_float),7^73x
49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407
7,015,820,362,023,593,956,150,476,655,802
Line 2,605 ⟶ 3,014:
timespacex 'isqrt 7 ^&x: 1 2 p. i. 37'
0.367744 319712
NB. but not as fast as isqrt_float, nor as space efficient
timespacex 'isqrt_float 7 ^&x: 1 2 p. i. 37'
0.0005145 152192</pre>
Note that isqrt_float (<code><.@%:</code>) is, mechanically, a different operation from floating point square root followed by floor. This difference is probably best thought of as a type issue. For example, <code><.%:7^73x</code> (without the <code>@</code>) produces a result which has the comma delimited integer representation of <tt>7,015,820,362,023,59<i>4,877,495,225,090</i></tt> rather than the <tt>7,015,820,362,023,59<b>3,956,150,476,655,802</b></tt> which we would get from integer square root.
=={{header|Java}}==
{{trans|Kotlin}}
<
public class Isqrt {
Line 2,653 ⟶ 3,067:
}
}
}</
{{out}}
<pre>The integer square root of integers from 0 to 65 are:
Line 2,701 ⟶ 3,115:
{{trans|Julia}}
The following program takes advantage of the support for unbounded-precision
integer arithmetic provided by gojq, the Go implementation of jq, but it can also be run, with different numerical results, using the C implementation.<
def idivide($j):
. as $i
Line 2,737 ⟶ 3,151:
(range( 1;74;2) as $i
| (7 | power($i)) as $p
| "\($i|lpad(2)) \($p|lpad(84)) \($p | isqrt | lpad(43))" )</
{{out}}
Invocation: gojq -ncr -f isqrt.jq
Line 2,787 ⟶ 3,201:
{{trans|Go}}
Julia also has a built in isqrt() function which works on integer types, but the function integer_sqrt is shown for the task.
<
function integer_sqrt(x)
Line 2,819 ⟶ 3,233:
lpad(format(integer_sqrt(pow7^i), commas=true), 43))
end
</
<pre>
The integer square roots of integers from 0 to 65 are:
Line 2,869 ⟶ 3,283:
=={{header|Kotlin}}==
{{trans|Go}}
<
fun isqrt(x: BigInteger): BigInteger {
Line 2,911 ⟶ 3,325:
pow7 *= bi49
}
}</
{{out}}
<pre>The integer square root of integers from 0 to 65 are:
Line 2,958 ⟶ 3,372:
=={{header|Lua}}==
{{trans|C}}
<
local q = 1
local r = 0
Line 2,992 ⟶ 3,406:
n = n + 2
p = p * 49
end</
{{out}}
<pre>Integer square root for numbers 0 to 65:
Line 3,010 ⟶ 3,424:
19 | 11398895185373143 | 106765608
21 | 558545864083284007 | 747359260</pre>
=={{header|M2000 Interpreter}}==
Using various types up to 7^35
<syntaxhighlight lang="m2000 interpreter">
module integer_square_root (f=-2) {
function IntSqrt(x as long long) {
long long q=1, z=x, t, r
do q*=4&& : until (q>x)
while q>1&&
q|div 4&&:t=z-r-q:r|div 2&&
if t>-1&& then z=t:r+= q
end while
=r
}
long i
print #f, "The integer square root of integers from 0 to 65 are:"
for i=0 to 65
print #f, IntSqrt(i)+" ";
next
print #f
print #f, "Using Long Long Type"
print #f, "The integer square roots of powers of 7 from 7^1 up to 7^21 are:"
for i=1 to 21 step 2 {
print #f, "IntSqrt(7^"+i+")="+(IntSqrt(7&&^i))+" of 7^"+i+" ("+(7&&^I)+")"
}
print #f
function IntSqrt(x as decimal) {
decimal q=1, z=x, t, r
do q*=4 : until (q>x)
while q>1
q/=4:t=z-r-q:r/=2
if t>-1 then z=t:r+= q
end while
=r
}
print #f, "Using Decimal Type"
print #f, "The integer square roots of powers of 7 from 7^23 up to 7^33 are:"
decimal j,p
for i=23 to 33 step 2 {
p=1:for j=1 to i:p*=7@:next
print #f, "IntSqrt(7^"+i+")="+(IntSqrt(p))+" of 7^"+i+" ("+p+")"
}
print #f
function IntSqrt(x as double) {
double q=1, z=x, t, r
do q*=4 : until (q>x)
while q>1
q/=4:t=z-r-q:r/=2
if t>-1 then z=t:r+= q
end while
=r
}
print #f, "Using Double Type"
print #f, "The integer square roots of powers of 7 from 7^19 up to 7^35 are:"
for i=19 to 35 step 2 {
print #f, "IntSqrt(7^"+i+")="+(IntSqrt(7^i))+" of 7^"+i+" ("+(7^i)+")"
}
print #f
}
open "" for output as #f // f = -2 now, direct output to screen
integer_square_root
close #f
open "out.txt" for output as #f
integer_square_root f
close #f
win "notepad", dir$+"out.txt"
</syntaxhighlight>
{{out}}
<pre>
The integer square root of integers from 0 to 65 are:
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
Using Long Long Type
The integer square roots of powers of 7 from 7^1 up to 7^21 are:
IntSqrt(7^1)=2 of 7^1 (7)
IntSqrt(7^3)=18 of 7^3 (343)
IntSqrt(7^5)=129 of 7^5 (16807)
IntSqrt(7^7)=907 of 7^7 (823543)
IntSqrt(7^9)=6352 of 7^9 (40353607)
IntSqrt(7^11)=44467 of 7^11 (1977326743)
IntSqrt(7^13)=311269 of 7^13 (96889010407)
IntSqrt(7^15)=2178889 of 7^15 (4747561509943)
IntSqrt(7^17)=15252229 of 7^17 (232630513987207)
IntSqrt(7^19)=106765608 of 7^19 (11398895185373143)
IntSqrt(7^21)=747359260 of 7^21 (558545864083284007)
Using Decimal Type
The integer square roots of powers of 7 from 7^23 up to 7^33 are:
IntSqrt(7^23)=5231514822 of 7^23 (27368747340080916343)
IntSqrt(7^25)=36620603758 of 7^25 (1341068619663964900807)
IntSqrt(7^27)=256344226312 of 7^27 (65712362363534280139543)
IntSqrt(7^29)=1794409584184 of 7^29 (3219905755813179726837607)
IntSqrt(7^31)=12560867089291 of 7^31 (157775382034845806615042743)
IntSqrt(7^33)=87926069625040 of 7^33 (7730993719707444524137094407)
Using Double Type
The integer square roots of powers of 7 from 7^19 up to 7^35 are:
IntSqrt(7^19)=106765608 of 7^19 (1.13988951853731E+16)
IntSqrt(7^21)=747359260 of 7^21 (5.58545864083284E+17)
IntSqrt(7^23)=5231514822 of 7^23 (2.73687473400809E+19)
IntSqrt(7^25)=36620603758 of 7^25 (1.34106861966396E+21)
IntSqrt(7^27)=256344226312 of 7^27 (6.57123623635343E+22)
IntSqrt(7^29)=1794409584184 of 7^29 (3.21990575581318E+24)
IntSqrt(7^31)=12560867089291 of 7^31 (1.57775382034846E+26)
IntSqrt(7^33)=87926069625040 of 7^33 (7.73099371970744E+27)
IntSqrt(7^35)=615482487375282 of 7^35 (3.78818692265665E+29)
</pre>
=={{header|MAD}}==
<
R INTEGER SQUARE ROOT OF X
Line 3,055 ⟶ 3,580:
VECTOR VALUES SQ7 = $9HISQRT.(7^,I2,4H) = ,I6*$
END OF PROGRAM </
{{out}}
Line 3,080 ⟶ 3,605:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
ISqrt[x_Integer?NonNegative] := Module[{q = 1, z, r, t},
While[q <= x,
Line 3,099 ⟶ 3,624:
]
ISqrt /@ Range[65]
Column[ISqrt /@ (7^Range[1, 73])]</
{{out}}
<pre>{1,1,1,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8}
Line 3,175 ⟶ 3,700:
2651730845859653471779023381601
7015820362023593956150476655802</pre>
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">/* -*- Maxima -*- */
/*
The Rosetta Code integer square root task, in Maxima.
I have not tried to make the output conform quite to the task
description, because Maxima is not a general purpose programming
language. Perhaps someone else will care to do it.
I *do* check that the Rosetta Code routine gives the same results as
the built-in function.
*/
/* pow4gtx -- find a power of 4 greater than x. */
pow4gtx (x) := block (
[q],
q : 1, while q <= x do q : bit_lsh (q, 2),
q
) $
/* rosetta_code_isqrt -- find the integer square root. */
rosetta_code_isqrt (x) := block (
[q, z, r, t],
q : pow4gtx (x),
z : x,
r : 0,
while 1 < q do (
q : bit_rsh (q, 2),
t : z - r - q,
r : bit_rsh (r, 1),
if 0 <= t then (
z : t,
r : r + q
)
),
r
) $
for i : 0 thru 65 do (
display (rosetta_code_isqrt (i),
is (equal (rosetta_code_isqrt (i), isqrt (i))))
) $
for i : 1 thru 73 step 2 do (
display (7**i, rosetta_code_isqrt (7**i),
is (equal (rosetta_code_isqrt (7**i), isqrt (7**i))))
) $</syntaxhighlight>
{{out}}
<pre style="height:30em;overflow:auto">$ maxima -q -b isqrt.mac
(%i1) batch("isqrt.mac")
read and interpret /home/trashman/src/chemoelectric/rosettacode-contributions/isqrt.mac
(%i2) pow4gtx(x):=block([q],q:1,while q <= x do q:bit_lsh(q,2),q)
(%i3) rosetta_code_isqrt(x):=block([q,z,r,t],q:pow4gtx(x),z:x,r:0,
while 1 < q do
(q:bit_rsh(q,2),t:z-r-q,r:bit_rsh(r,1),
if 0 <= t then (z:t,r:r+q)),r)
(%i4) for i from 0 thru 65 do
display(rosetta_code_isqrt(i),
is(equal(rosetta_code_isqrt(i),isqrt(i))))
rosetta_code_isqrt(0) = 0
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(1) = 1
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(2) = 1
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(3) = 1
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(4) = 2
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(5) = 2
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(6) = 2
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(7) = 2
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(8) = 2
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(9) = 3
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(10) = 3
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(11) = 3
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(12) = 3
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(13) = 3
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(14) = 3
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(15) = 3
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(16) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(17) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(18) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(19) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(20) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(21) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(22) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(23) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(24) = 4
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(25) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(26) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(27) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(28) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(29) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(30) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(31) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(32) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(33) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(34) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(35) = 5
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(36) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(37) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(38) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(39) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(40) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(41) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(42) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(43) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(44) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(45) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(46) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(47) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(48) = 6
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(49) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(50) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(51) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(52) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(53) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(54) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(55) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(56) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(57) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(58) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(59) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(60) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(61) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(62) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(63) = 7
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(64) = 8
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
rosetta_code_isqrt(65) = 8
is(equal(rosetta_code_isqrt(i), isqrt(i))) = true
(%i5) for i step 2 thru 73 do
display(7^i,rosetta_code_isqrt(7^i),
is(equal(rosetta_code_isqrt(7^i),isqrt(7^i))))
1
7 = 7
rosetta_code_isqrt(7) = 2
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
3
7 = 343
rosetta_code_isqrt(343) = 18
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
5
7 = 16807
rosetta_code_isqrt(16807) = 129
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
7
7 = 823543
rosetta_code_isqrt(823543) = 907
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
9
7 = 40353607
rosetta_code_isqrt(40353607) = 6352
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
11
7 = 1977326743
rosetta_code_isqrt(1977326743) = 44467
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
13
7 = 96889010407
rosetta_code_isqrt(96889010407) = 311269
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
15
7 = 4747561509943
rosetta_code_isqrt(4747561509943) = 2178889
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
17
7 = 232630513987207
rosetta_code_isqrt(232630513987207) = 15252229
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
19
7 = 11398895185373143
rosetta_code_isqrt(11398895185373143) = 106765608
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
21
7 = 558545864083284007
rosetta_code_isqrt(558545864083284007) = 747359260
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
23
7 = 27368747340080916343
rosetta_code_isqrt(27368747340080916343) = 5231514822
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
25
7 = 1341068619663964900807
rosetta_code_isqrt(1341068619663964900807) = 36620603758
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
27
7 = 65712362363534280139543
rosetta_code_isqrt(65712362363534280139543) = 256344226312
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
29
7 = 3219905755813179726837607
rosetta_code_isqrt(3219905755813179726837607) = 1794409584184
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
31
7 = 157775382034845806615042743
rosetta_code_isqrt(157775382034845806615042743) = 12560867089291
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
33
7 = 7730993719707444524137094407
rosetta_code_isqrt(7730993719707444524137094407) = 87926069625040
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
35
7 = 378818692265664781682717625943
rosetta_code_isqrt(378818692265664781682717625943) = 615482487375282
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
37
7 = 18562115921017574302453163671207
rosetta_code_isqrt(18562115921017574302453163671207) = 4308377411626977
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
39
7 = 909543680129861140820205019889143
rosetta_code_isqrt(909543680129861140820205019889143) = 30158641881388842
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
41
7 = 44567640326363195900190045974568007
rosetta_code_isqrt(44567640326363195900190045974568007) = 211110493169721897
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
43
7 = 2183814375991796599109312252753832343
rosetta_code_isqrt(2183814375991796599109312252753832343) = 1477773452188053281
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
45
7 = 107006904423598033356356300384937784807
rosetta_code_isqrt(107006904423598033356356300384937784807) =
10344414165316372973
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
47
7 = 5243338316756303634461458718861951455543
rosetta_code_isqrt(5243338316756303634461458718861951455543) =
72410899157214610812
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
49
7 = 256923577521058878088611477224235621321607
rosetta_code_isqrt(256923577521058878088611477224235621321607) =
506876294100502275687
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
51
7 = 12589255298531885026341962383987545444758743
rosetta_code_isqrt(12589255298531885026341962383987545444758743) =
3548134058703515929815
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
53
7 = 616873509628062366290756156815389726793178407
rosetta_code_isqrt(616873509628062366290756156815389726793178407) =
24836938410924611508707
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
55
7 = 30226801971775055948247051683954096612865741943
rosetta_code_isqrt(30226801971775055948247051683954096612865741943) =
173858568876472280560953
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
57
7 = 1481113296616977741464105532513750734030421355207
rosetta_code_isqrt(1481113296616977741464105532513750734030421355207) =
1217009982135305963926677
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
59
7 = 72574551534231909331741171093173785967490646405143
rosetta_code_isqrt(72574551534231909331741171093173785967490646405143) =
8519069874947141747486745
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
61
7 = 3556153025177363557255317383565515512407041673852007
rosetta_code_isqrt(3556153025177363557255317383565515512407041673852007) =
59633489124629992232407216
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
63
7 = 174251498233690814305510551794710260107945042018748343
rosetta_code_isqrt(174251498233690814305510551794710260107945042018748343) =
417434423872409945626850517
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
65
7 = 8538323413450849900970017037940802745289307058918668807
rosetta_code_isqrt(8538323413450849900970017037940802745289307058918668807) =
2922040967106869619387953625
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
67
7 = 418377847259091645147530834859099334519176045887014771543
rosetta_code_isqrt(418377847259091645147530834859099334519176045887014771543
) = 20454286769748087335715675381
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
69
7 = 20500514515695490612229010908095867391439626248463723805607
rosetta_code_isqrt(20500514515695490612229010908095867391439626248463723805607
) = 143180007388236611350009727669
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
71
7 = 1004525211269079039999221534496697502180541686174722466474743
rosetta_code_isqrt(10045252112690790399992215344966975021805416861747224664747\
43) = 1002260051717656279450068093686
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
73
7 = 49221735352184872959961855190338177606846542622561400857262407
rosetta_code_isqrt(49221735352184872959961855190338177606846542622561400857262\
407) = 7015820362023593956150476655802
i i
is(equal(rosetta_code_isqrt(7 ), isqrt(7 ))) = true
(%o6) /home/trashman/src/chemoelectric/rosettacode-contributions/isqrt.mac</pre>
=={{header|Mercury}}==
Line 3,181 ⟶ 4,350:
<
:- interface.
Line 3,299 ⟶ 4,468:
%%% prolog-indent-width: 2
%%% end:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%</
{{out}}
Line 3,349 ⟶ 4,518:
71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686
73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802</pre>
=={{header|Modula-2}}==
Line 3,359 ⟶ 4,526:
TopSpeed Modula-2 supports no integers larger than unsigned 32-bit, which means that the second part of the task stops at 7^11. There seems to be no option to insert commas into long numbers as requested.
<
MODULE IntSqrt;
Line 3,423 ⟶ 4,590:
END;
END IntSqrt.
</syntaxhighlight>
{{out}}
<pre>
Line 3,445 ⟶ 4,612:
{{libheader|bignum}}
This Nim implementation provides an <code>isqrt</code> function for signed integers and for big integers.
<
import bignum
Line 3,487 ⟶ 4,654:
for n in countup(1, 73, 2):
echo &"{n:>2} {insertSep($x, ','):>82} {insertSep($isqrt(x), ','):>41}"
x *= 49</
{{out}}
Line 3,541 ⟶ 4,708:
<
import io
Line 3,601 ⟶ 4,768:
while q <= x do q := ishift(q, 2)
return q
end</
{{out}}
Line 3,613 ⟶ 4,780:
i 7**i sqrt(7**i)
-----------------------------------------------------------------------------------------------------------------------------------
1 7 2
3 343 18
5 16,807 129
7 823,543 907
9 40,353,607 6,352
11 1,977,326,743 44,467
13 96,889,010,407 311,269
15 4,747,561,509,943 2,178,889
17 232,630,513,987,207 15,252,229
19 11,398,895,185,373,143 106,765,608
21 558,545,864,083,284,007 747,359,260
23 27,368,747,340,080,916,343 5,231,514,822
25 1,341,068,619,663,964,900,807 36,620,603,758
27 65,712,362,363,534,280,139,543 256,344,226,312
29 3,219,905,755,813,179,726,837,607 1,794,409,584,184
31 157,775,382,034,845,806,615,042,743 12,560,867,089,291
33 7,730,993,719,707,444,524,137,094,407 87,926,069,625,040
35 378,818,692,265,664,781,682,717,625,943 615,482,487,375,282
37 18,562,115,921,017,574,302,453,163,671,207 4,308,377,411,626,977
39 909,543,680,129,861,140,820,205,019,889,143 30,158,641,881,388,842
41 44,567,640,326,363,195,900,190,045,974,568,007 211,110,493,169,721,897
43 2,183,814,375,991,796,599,109,312,252,753,832,343 1,477,773,452,188,053,281
45 107,006,904,423,598,033,356,356,300,384,937,784,807 10,344,414,165,316,372,973
47 5,243,338,316,756,303,634,461,458,718,861,951,455,543 72,410,899,157,214,610,812
49 256,923,577,521,058,878,088,611,477,224,235,621,321,607 506,876,294,100,502,275,687
51 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 3,548,134,058,703,515,929,815
53 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 24,836,938,410,924,611,508,707
55 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 173,858,568,876,472,280,560,953
57 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 1,217,009,982,135,305,963,926,677
59 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 8,519,069,874,947,141,747,486,745
61 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 59,633,489,124,629,992,232,407,216
63 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 417,434,423,872,409,945,626,850,517
65 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 2,922,040,967,106,869,619,387,953,625
67 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 20,454,286,769,748,087,335,715,675,381
69 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 143,180,007,388,236,611,350,009,727,669
71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686
73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802</pre>
=={{header|OCaml}}==
{{trans|Scheme}}
{{libheader|Zarith}}
<syntaxhighlight lang="ocaml">(* The Rosetta Code integer square root task, in OCaml, using Zarith
for large integers.
Compile with, for example:
ocamlfind ocamlc -package zarith -linkpkg -o isqrt isqrt.ml
Translated from the Scheme. *)
let find_a_power_of_4_greater_than_x x =
let open Z in
let rec loop q =
if x < q then q else loop (q lsl 2)
in
loop one
let isqrt x =
let open Z in
let rec loop q z r =
if q = one then
r
else
let q = q asr 2 in
let t = z - r - q in
let r = r asr 1 in
if t < zero then
loop q z r
else
loop q t (r + q)
in
let q0 = find_a_power_of_4_greater_than_x x in
let z0 = x in
let r0 = zero in
loop q0 z0 r0
let insert_separators s sep =
let rec loop revchars i newchars =
match revchars with
| [] -> newchars
| revchars when i = 3 -> loop revchars 0 (sep :: newchars)
| c :: tail -> loop tail (i + 1) (c :: newchars)
in
let revchars = List.rev (List.of_seq (String.to_seq s)) in
String.of_seq (List.to_seq (loop revchars 0 []))
let commas s = insert_separators s ','
let main () =
Printf.printf "isqrt(i) for 0 <= i <= 65:\n\n";
for i = 0 to 64 do
Printf.printf "%s " Z.(to_string (isqrt (of_int i)))
done;
Printf.printf "%s\n" Z.(to_string (isqrt (of_int 65)));
Printf.printf "\n\n";
Printf.printf "isqrt(7**i) for 1 <= i <= 73, i odd:\n\n";
Printf.printf "%2s %84s %43s\n" "i" "7**i" "isqrt(7**i)";
for i = 1 to 131 do Printf.printf "-" done;
Printf.printf "\n";
for j = 0 to 36 do
let i = j + j + 1 in
let power = Z.(of_int 7 ** i) in
let root = isqrt power in
Printf.printf "%2d %84s %43s\n"
i (commas (Z.to_string power)) (commas (Z.to_string root))
done
;;
main ()</syntaxhighlight>
{{out}}
<pre>$ ocamlfind ocamlc -package zarith -linkpkg -o isqrt isqrt.ml && ./isqrt
isqrt(i) for 0 <= i <= 65:
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
isqrt(7**i) for 1 <= i <= 73, i odd:
i 7**i isqrt(7**i)
-----------------------------------------------------------------------------------------------------------------------------------
1 7 2
Line 3,655 ⟶ 4,947:
=={{header|Ol}}==
<
(print "Integer square roots of 0..65")
(for-each (lambda (x)
Line 3,670 ⟶ 4,962:
(iota 73 1)))
(print)
</syntaxhighlight>
{{Out}}
<pre>
Line 3,754 ⟶ 5,046:
{{libheader|Velthuis.BigIntegers}}[https://github.com/rvelthuis/DelphiBigNumbers]
{{trans|C++}}
<syntaxhighlight lang="pascal">
//************************************************//
// //
Line 3,851 ⟶ 5,143:
CloseFile(f);
end.
</syntaxhighlight>
=={{header|Perl}}==
{{trans|Julia}}
<
use strict;
Line 3,897 ⟶ 5,189:
printf("%44s", $decf->format( integer_sqrt(7**$i) ) ) ;
print "\n";
}</
{{out}}
<pre>
Line 3,946 ⟶ 5,238:
=={{header|Phix}}==
See also [[Integer_roots#Phix]] for a simpler and shorter example using the mpz_root() routine, or better yet just use mpz_root() directly (that is, rather than the isqrt() below).
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
Line 3,991 ⟶ 5,283:
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pow7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pow7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
Perfect squares are denoted with an asterisk.
<pre style="font-size: 11px">
The integer square roots of integers from 0 to 65 are:
0* 1* 1 1 2* 2 2 2 2 3* 3 3 3 3 3 3 4* 4 4 4 4 4 4 4 4 5* 5 5 5 5 5 5 5 5 5 5 6* 6 6 6 6 6 6 6 6 6 6 6 6 7* 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8* 8
Line 4,065 ⟶ 5,357:
<
%%%
%%% The Rosetta Code integer square root task, for SWI Prolog.
Line 4,125 ⟶ 5,417:
%%% prolog-indent-width: 2
%%% end:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%</
{{out}}
Line 4,178 ⟶ 5,470:
=={{header|Python}}==
{{works with|Python|2.7}}
<
q = 1
while q <= x :
Line 4,191 ⟶ 5,483:
print ' '.join( '%d'%isqrt( n ) for n in xrange( 66 ))
print '\n'.join( '{0:114,} = isqrt( 7^{1:3} )'.format( isqrt( 7**n ),n ) for n in range( 1,204,2 ))</
{{out}}
<pre>
Line 4,301 ⟶ 5,593:
=={{header|Quackery}}==
<
[ char , swap
i 1+ -3 * stuff ]
Line 4,326 ⟶ 5,618:
rot over + ]
again ]
nip swap ] is sqrt
( sqrt+ returns the integer square root and remainder )
( i.e. isqrt+ of 28 is 5 remainder 3 as (5^2)+3 = 28 )
( To make it task compliant change the last line to )
( "nip nip ] is sqrt
66 times [ i^ sqrt+ drop echo sp ] cr cr
73 times
[ 7 i^ 1+ ** sqrt+ drop
number$ +commas 41 justify
echo$ cr
2 step ]</
'''Output:'''
Line 4,385 ⟶ 5,677:
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
Line 4,429 ⟶ 5,721:
(* num 49))
</syntaxhighlight>
{{out}}
<pre>
Line 4,482 ⟶ 5,774:
Quadratic residue algorithm follows:
<syntaxhighlight lang="raku"
sub isqrt ( \x ) { my ( $X, $q, $r, $t ) = x, 1, 0 ;
Line 4,495 ⟶ 5,787:
say (^66)».&{ isqrt $_ }.Str ;
(1, 3…73)».&{ "7**$_: " ~ comma(isqrt 7**$_) }».say</
{{out}}
<pre>0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
Line 4,538 ⟶ 5,830:
=={{header|REXX}}==
A fair amount of code was included so that the output aligns correctly.
<
numeric digits 200 /*insure 'nuff decimal digs for results*/
parse arg range power base . /*obtain optional arguments from the CL*/
Line 4,583 ⟶ 5,875:
end
end /*while*/
return r /*return the integer square root of X. */</
{{out|output|text= when using the default inputs:}}
<pre>
Line 4,629 ⟶ 5,921:
73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802
</pre>
=={{header|RPL}}==
Because RPL can only handle unsigned integers, a light change has been made in the proposed algorithm,
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
#1
'''WHILE''' DUP2 ≥ '''REPEAT'''
SL SL '''END'''
#0
'''WHILE''' OVER #1 > '''REPEAT'''
SWAP SR SR SWAP
DUP2 +
SWAP SR SWAP
'''IF''' 4 PICK SWAP DUP2 ≥ '''THEN'''
- 4 ROLL DROP ROT ROT
OVER +
'''ELSE''' DROP2 '''END'''
'''END''' ROT ROT DROP2
≫
´'''ISQRT'''’ STO
|
'''ISQRT''' ''( #n -- #sqrt(n) )''
q ◄── 1
perform while q <= x
q ◄── q * 4
z ◄── x
r ◄── 0
perform while q > 1
q ◄── q ÷ 4
u ◄── r + q
r ◄── r ÷ 2
if z >= u then do
z ◄── z - u
r ◄── r + q
else remove u and copy of z from stack
end perform, clean stack
|}
{{in}}
<pre>
≪ { } 0 65 FOR n n R→B ISQRT B→R + NEXT ≫ EVAL
≪ {} #7 1 11 START DUP ISQRT ROT SWAP + SWAP 49 * NEXT DROP ≫ EVAL
</pre>
{{out}}
<pre>
2: { 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 }
1: { # 2d # 18d # 129d # 907d # 6352d # 44467d # 311269d # 2178889d # 15252229d # 106765608d # 747359260d }
</pre>
=={{header|Ruby}}==
Ruby already has [https://ruby-doc.org/core-2.7.0/Integer.html#method-c-sqrt Integer.sqrt], which results in the integer square root of a positive integer. It can be re-implemented as follows:
<
refine Integer do
def commatize
Line 4,656 ⟶ 6,003:
puts isqrt(7**n).commatize
end
</syntaxhighlight>
{{out}}
<pre>0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
Line 4,699 ⟶ 6,046:
=={{header|Rust}}==
<
use num::BigUint;
use num::CheckedSub;
Line 4,751 ⟶ 6,098:
});
}
</syntaxhighlight>
{{out}}
<pre>
Line 4,799 ⟶ 6,146:
=={{header|S-BASIC}}==
This follows the algorithm given in the task description. The q = q * 4 computation, however, will result in overflow (and an endless loop!) for large values of x.
<
comment
return integer square root of n using quadratic
Line 4,841 ⟶ 6,188:
end
</syntaxhighlight>
An alternate version of isqrt() that can handle the full range of S-BASIC integer values (well, almost: it will fail for 32,767) looks like this.
<
function isqrt(x = integer) = integer
var x0, x1 = integer
Line 4,854 ⟶ 6,201:
until x1 >= x0
end = x0
</syntaxhighlight>
{{out}}
The output for 7^5 will be shown only if the alternate version of the function is used.
<pre>
Integer square root of first 65 numbers
Line 4,868 ⟶ 6,216:
1 7 2
3 343 18
5 16807 129
</pre>
Line 4,879 ⟶ 6,228:
<
(import (scheme write))
(import (format)) ;; Common Lisp formatting for CHICKEN Scheme.
Line 4,918 ⟶ 6,267:
((= i 75))
(let ((7**i (expt 7 i)))
(format #t "~2D ~84:D ~43:D~%" i 7**i (isqrt 7**i))))</
{{out}}
Line 4,969 ⟶ 6,318:
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|
<syntaxhighlight lang="setl">program isqrt;
loop for i in [1..65] do
putchar(lpad(str isqrt(i), 5));
if i mod 13=0 then print(); end if;
end loop;
print();
loop for p in [1, 3..73] do
sqrtp := isqrt(7 ** p);
print("sqrt(7^" + lpad(str p,2) + ") = " + lpad(str sqrtp, 32));
end loop;
proc isqrt(x);
q := 1;
loop while q<=x do
q *:= 4;
end loop;
z := x;
r := 0;
loop while q>1 do
q div:= 4;
t := z-r-q;
r div:= 2;
if t>=0 then
z := t;
r +:= q;
end if;
end loop;
return r;
end proc;
end program;</syntaxhighlight>
{{out}}
<pre> 1 1 1 2 2 2 2 2 3 3 3 3 3
3 3 4 4 4 4 4 4 4 4 4 5 5
5 5 5 5 5 5 5 5 5 6 6 6 6
6 6 6 6 6 6 6 6 6 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 8 8
sqrt(7^ 1) = 2
sqrt(7^ 3) = 18
sqrt(7^ 5) = 129
sqrt(7^ 7) = 907
sqrt(7^ 9) = 6352
sqrt(7^11) = 44467
sqrt(7^13) = 311269
sqrt(7^15) = 2178889
sqrt(7^17) = 15252229
sqrt(7^19) = 106765608
sqrt(7^21) = 747359260
sqrt(7^23) = 5231514822
sqrt(7^25) = 36620603758
sqrt(7^27) = 256344226312
sqrt(7^29) = 1794409584184
sqrt(7^31) = 12560867089291
sqrt(7^33) = 87926069625040
sqrt(7^35) = 615482487375282
sqrt(7^37) = 4308377411626977
sqrt(7^39) = 30158641881388842
sqrt(7^41) = 211110493169721897
sqrt(7^43) = 1477773452188053281
sqrt(7^45) = 10344414165316372973
sqrt(7^47) = 72410899157214610812
sqrt(7^49) = 506876294100502275687
sqrt(7^51) = 3548134058703515929815
sqrt(7^53) = 24836938410924611508707
sqrt(7^55) = 173858568876472280560953
sqrt(7^57) = 1217009982135305963926677
sqrt(7^59) = 8519069874947141747486745
sqrt(7^61) = 59633489124629992232407216
sqrt(7^63) = 417434423872409945626850517
sqrt(7^65) = 2922040967106869619387953625
sqrt(7^67) = 20454286769748087335715675381
sqrt(7^69) = 143180007388236611350009727669
sqrt(7^71) = 1002260051717656279450068093686
sqrt(7^73) = 7015820362023593956150476655802</pre>
=={{header|Seed7}}==
Seed7 has integer [https://seed7.sourceforge.net/libraries/integer.htm#sqrt(in_integer) sqrt()] and bigInteger [https://seed7.sourceforge.net/libraries/bigint.htm#sqrt(in_var_bigInteger) sqrt()] functions.
These functions could be used if an integer square root is needed.
But this task does not allow using the language's built-in sqrt() function.
Instead the ''quadratic residue'' algorithm for finding the integer square root must be used.
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i";
include "bigint.s7i";
Line 4,985 ⟶ 6,413:
stri := stri[.. index] & "," & stri[succ(index) ..];
end for;
end func;
const func bigInteger: isqrt (in bigInteger: x) is func
result
var bigInteger: r is 0_;
local
var bigInteger: q is 1_;
var bigInteger: z is 0_;
var bigInteger: t is 0_;
begin
while q <= x do
q *:= 4_;
end while;
z := x;
while q > 1_ do
q := q mdiv 4_;
t := z - r - q;
r := r mdiv 2_;
if t >= 0_ then
z := t;
r +:= q;
end if;
end while;
end func;
Line 4,994 ⟶ 6,445:
writeln("The integer square roots of integers from 0 to 65 are:");
for number range 0 to 65 do
write(
end for;
writeln("\n\nThe integer square roots of powers of 7 from 7**1 up to 7**73 are:");
Line 5,000 ⟶ 6,451:
writeln("----- --------------------------------------------------------------------------------- -----------------------------------------");
for number range 1 to 73 step 2 do
writeln(number lpad 2 <& commatize(pow7) lpad 85 <& commatize(
pow7 *:=
end for;
end func;</
{{out}}
<pre>
Line 5,054 ⟶ 6,505:
Built-in:
<
say n.isqrt
say n.iroot(2)</
Explicit implementation for the integer k-th root of n:
<
return 0 if (n == 0)
var (s, v) = (n, k - 1)
Line 5,069 ⟶ 6,520:
}
s
}</
Implementation of integer square root of n (using the quadratic residue algorithm):
<
while (q > 1) { q >>= 2; var t = x-r+q; r >>= 1
if (t >= 0) { (x, r) = (t, r+q) } } r }
Line 5,079 ⟶ 6,530:
for n in (1..73 `by` 2) {
printf("isqrt(7^%-2d): %42s\n", n, isqrt(7**n).commify) }</
{{out}}
<pre>0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
Line 5,121 ⟶ 6,572:
isqrt(7^73): 7,015,820,362,023,593,956,150,476,655,802
</pre>
=={{header|Standard ML}}==
{{trans|Scheme}}
{{trans|OCaml}}
{{works with|MLton}}
<syntaxhighlight lang="sml">(*
The Rosetta Code integer square root task, in Standard ML.
Compile with, for example:
mlton isqrt.sml
*)
val zero = IntInf.fromInt (0)
val one = IntInf.fromInt (1)
val seven = IntInf.fromInt (7)
val word1 = Word.fromInt (1)
val word2 = Word.fromInt (2)
fun
find_a_power_of_4_greater_than_x (x) =
let
fun
loop (q) =
if x < q then
q
else
loop (IntInf.<< (q, word2))
in
loop (one)
end;
fun
isqrt (x) =
let
fun
loop (q, z, r) =
if q = one then
r
else
let
val q = IntInf.~>> (q, word2)
val t = z - r - q
val r = IntInf.~>> (r, word1)
in
if t < zero then
loop (q, z, r)
else
loop (q, t, r + q)
end
in
loop (find_a_power_of_4_greater_than_x (x), x, zero)
end;
fun
insert_separators (s, sep) =
(* Insert separator characters (such as #",", #".", #" ") in a numeral
that is already in string form. *)
let
fun
loop (revchars, i, newchars) =
case (revchars, i) of
([], _) => newchars
| (revchars, 3) => loop (revchars, 0, sep :: newchars)
| (c :: tail, i) => loop (tail, i + 1, c :: newchars)
in
implode (loop (rev (explode s), 0, []))
end;
fun
commas (s) =
(* Insert commas in a numeral that is already in string form. *)
insert_separators (s, #",");
val pad_with_spaces = StringCvt.padLeft #" "
fun
main () =
let
val i = ref 0
in
print ("isqrt(i) for 0 <= i <= 65:\n\n");
i := 0;
while !i < 65 do (
print (IntInf.toString (isqrt (IntInf.fromInt (!i))));
print (" ");
i := !i + 1
);
print (IntInf.toString (isqrt (IntInf.fromInt (65))));
print ("\n\n\n");
print ("isqrt(7**i) for 1 <= i <= 73, i odd:\n\n");
print (pad_with_spaces 2 "i");
print (pad_with_spaces 85 "7**i");
print (pad_with_spaces 44 "sqrt(7**i)");
print ("\n");
i := 1;
while !i <= 131 do (
print ("-");
i := !i + 1
);
print ("\n");
i := 1;
while !i <= 73 do (
let
val pow7 = IntInf.pow (seven, !i)
val root = isqrt (pow7)
in
print (pad_with_spaces 2 (Int.toString (!i)));
print (pad_with_spaces 85 (commas (IntInf.toString pow7)));
print (pad_with_spaces 44 (commas (IntInf.toString root)));
print ("\n");
i := !i + 2
end
)
end;
main ();
(* local variables: *)
(* mode: sml *)
(* sml-indent-level: 2 *)
(* sml-indent-args: 2 *)
(* end: *)</syntaxhighlight>
{{out}}
<pre>$ mlton isqrt.sml && ./isqrt
isqrt(i) for 0 <= i <= 65:
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
isqrt(7**i) for 1 <= i <= 73, i odd:
i 7**i sqrt(7**i)
-----------------------------------------------------------------------------------------------------------------------------------
1 7 2
3 343 18
5 16,807 129
7 823,543 907
9 40,353,607 6,352
11 1,977,326,743 44,467
13 96,889,010,407 311,269
15 4,747,561,509,943 2,178,889
17 232,630,513,987,207 15,252,229
19 11,398,895,185,373,143 106,765,608
21 558,545,864,083,284,007 747,359,260
23 27,368,747,340,080,916,343 5,231,514,822
25 1,341,068,619,663,964,900,807 36,620,603,758
27 65,712,362,363,534,280,139,543 256,344,226,312
29 3,219,905,755,813,179,726,837,607 1,794,409,584,184
31 157,775,382,034,845,806,615,042,743 12,560,867,089,291
33 7,730,993,719,707,444,524,137,094,407 87,926,069,625,040
35 378,818,692,265,664,781,682,717,625,943 615,482,487,375,282
37 18,562,115,921,017,574,302,453,163,671,207 4,308,377,411,626,977
39 909,543,680,129,861,140,820,205,019,889,143 30,158,641,881,388,842
41 44,567,640,326,363,195,900,190,045,974,568,007 211,110,493,169,721,897
43 2,183,814,375,991,796,599,109,312,252,753,832,343 1,477,773,452,188,053,281
45 107,006,904,423,598,033,356,356,300,384,937,784,807 10,344,414,165,316,372,973
47 5,243,338,316,756,303,634,461,458,718,861,951,455,543 72,410,899,157,214,610,812
49 256,923,577,521,058,878,088,611,477,224,235,621,321,607 506,876,294,100,502,275,687
51 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 3,548,134,058,703,515,929,815
53 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 24,836,938,410,924,611,508,707
55 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 173,858,568,876,472,280,560,953
57 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 1,217,009,982,135,305,963,926,677
59 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 8,519,069,874,947,141,747,486,745
61 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 59,633,489,124,629,992,232,407,216
63 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 417,434,423,872,409,945,626,850,517
65 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 2,922,040,967,106,869,619,387,953,625
67 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 20,454,286,769,748,087,335,715,675,381
69 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 143,180,007,388,236,611,350,009,727,669
71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686
73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802</pre>
=={{header|Swift}}==
{{trans|C++}}
Requires the attaswift BigInt package.
<
func integerSquareRoot<T: BinaryInteger>(_ num: T) -> T {
Line 5,184 ⟶ 6,816:
print("\(pad(string: String(n), width: 2)) |\(power) |\(isqrt)")
p *= 49
}</
{{out}}
<pre style="font-size: 11px">
Integer square root for numbers 0 to 65:
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
Line 5,232 ⟶ 6,864:
73 | 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 | 7,015,820,362,023,593,956,150,476,655,802
</pre>
=={{Header|Tiny BASIC}}==
{{works with|TinyBasic}}
Tiny BASIC does not support string formatting or concatenation, and is limited to integer arithmetic on numbers no greater than 32,767. The isqrt of 0-65 and the first two odd powers of 7 are shown in column format. The algorithm itself (the interesting part) begins on line 100.
<syntaxhighlight lang
20 GOSUB 100
30 PRINT R
Line 5,261 ⟶ 6,895:
220 LET Z = T
230 LET R = R + Q
240 GOTO 170</
=={{header|UNIX Shell}}==
Line 5,267 ⟶ 6,901:
{{works with|Korn Shell}}
{{Works with|Zsh}}
<
typeset -i x
for x; do
Line 5,324 ⟶ 6,958:
break
fi
done</
{{Out}}
Line 5,352 ⟶ 6,986:
=={{header|Visual Basic .NET}}==
{{libheader|System.Numerics}}{{trans|C#}}
<
Imports System.Console
Imports BI = System.Numerics.BigInteger
Line 5,385 ⟶ 7,019:
End While
End Sub
End Module</
{{Out}}
<pre>Integer square root for numbers 0 to 65:
Line 5,433 ⟶ 7,067:
71 | 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 | 1,002,260,051,717,656,279,450,068,093,686
73 | 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 | 7,015,820,362,023,593,956,150,476,655,802
</pre>
=={{header|VTL-2}}==
The ISQRT routine starts at line 2000. As VTL-2 only has unsigned 16-bit arithmetic, only the roots of 7^1, 7^3 and 7^5 are shown as 7^7 is too large.
<syntaxhighlight lang="vtl2">
1000 X=0
1010 #=2000
1020 $=32
1030 ?=R
1040 X=X+1
1050 #=X=33=0*1070
1060 ?=""
1070 #=X<66*1010
1080 P=1
1090 X=7
1100 #=2000
1110 ?=""
1120 ?="Root 7^";
1130 ?=P
1140 ?="(";
1150 ?=X
1160 ?=") = ";
1170 ?=R
1180 X=X*49
1190 P=P+2
1200 #=P<6*1100
1210 #=9999
2000 A=!
2010 Q=1
2020 #=X>Q=0*2050
2030 Q=Q*4
2040 #=2020
2050 Z=X
2060 R=0
2070 #=Q<2*A
2080 Q=Q/4
2090 T=Z-R-Q
2100 I=Z<(R+Q)
2110 R=R/2
2120 #=I*2070
2130 Z=T
2140 R=R+Q
2150 #=2070
</syntaxhighlight>
{{out}}
<pre>
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5
5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
Root 7^1(7) = 2
Root 7^3(343) = 18
Root 7^5(16807) = 129
</pre>
Line 5,438 ⟶ 7,123:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
var isqrt = Fn.new { |x|
Line 5,475 ⟶ 7,160:
pow7 = pow7 * bi49
i = i + 2
}</
{{out}}
Line 5,524 ⟶ 7,209:
73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802
</pre>
=={{header|Yabasic}}==
<syntaxhighlight lang="freebasic">// Rosetta Code problem: https://rosettacode.org/wiki/Isqrt_(integer_square_root)_of_X
// by Jjuanhdez, 06/2022
print "Integer square root of first 65 numbers:"
for n = 1 to 65
print isqrt(n) using("##");
next n
print : print
print "Integer square root of odd powers of 7"
print " n | 7^n | isqrt "
print "----|--------------------|-----------"
for n = 1 to 21 step 2
pow7 = 7 ^ n
print n using("###"), " | ", left$(str$(pow7,"%20.1f"),18), " | ", left$(str$(isqrt(pow7),"%11.1f"),9)
next n
end
sub isqrt(x)
q = 1
while q <= x
q = q * 4
wend
r = 0
while q > 1
q = q / 4
t = x - r - q
r = r / 2
if t >= 0 then
x = t
r = r + q
end if
wend
return int(r)
end sub</syntaxhighlight>
|