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

:*   [[Square_Root_by_Hand|square root by hand]]

<br><br>

 

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}

Implements the task pseudo-code.

PR precision 200 PR

# returns the integer square root of x; x must be >= 0 #

p7 *:= 49

OD

{{out}}

<pre>

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>

 

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)

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

7^13 (96,889,010,407): 311,269

7^15 (4,747,561,509,943): 2,178,889

 

=={{header|APL}}==

Works in [[Dyalog APL]]

{{output}}

<pre>

=={{header|Arturo}}==

 

reverse join.with:"," map split.every: 3 split reverse to :string x => join

]

loop range 1 .step: 2 72 'n ->

 

{{out}}

69 143,180,007,388,236,611,350,009,727,669

71 1,002,260,051,717,656,279,450,068,093,686</pre>

 

=={{header|C}}==

{{trans|C++}}

Up to 64-bit limits with no big int library.

#include <stdio.h>

 

printf("%2d | %18lld | %12lld\n", n, p, isqrt(p));

}

{{out}}

<pre>Integer square root for numbers 0 to 65:

=={{header|C++}}==

{{libheader|Boost}}

#include <iostream>

#include <sstream>

}

return 0;

 

{{out}}

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

=={{header|C#|CSharp}}==

{{libheader|System.Numerics}}

using static System.Console;

using BI = System.Numerics.BigInteger;

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:

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

print_nl();

x := x + 1;

 

{{out}}

isqrt(7^10) = 16807

isqrt(7^11) = 44467</pre>

 

=={{header|D}}==

{{trans|Kotlin}}

import std.conv;

import std.exception;

pow7 *= bi49;

}

{{out}}

<pre>The integer square root of integers from 0 to 65 are:

=={{header|Delphi}}==

See [[#Pascal]].

 

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

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

{{out}}

<pre>

7,015,820,362,023,593,956,150,476,655,802

</pre>

=={{header|Factor}}==

The <code>isqrt</code> word is a straightforward translation of the pseudocode from the task description using lexical variables.

{{works with|Factor|0.99 2020-07-03}}

math.ranges prettyprint sequences tools.memory.private ;

 

"x" "7^x" "isqrt(7^x)" align

"-" "---" "----------" align

{{out}}

<pre>

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|Forth}}==

Only handles odd powers of 7 up to 7^21.

: d., ( n -- ) \ write double precision int, commatized.

tuck dabs

 

task1 cr task2 bye

{{Out}}

<pre>

21 747,359,260

</pre>

=={{header|Fortran}}==

IMPLICIT NONE

 

T = 0

Q = Q * 4

END DO

 

<pre>

Integer square root for numbers 0 to 65

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

ns = str(isqrt(7^i))

print i, commatize(ns)

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

19 106,765,608

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

pow7.Mul(pow7, bi49)

}

 

{{out}}

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|Java}}==

{{trans|Kotlin}}

 

public class Isqrt {

}

}

{{out}}

<pre>The integer square root of integers from 0 to 65 are:

{{trans|Julia}}

The following program takes advantage of the support for unbounded-precision

def idivide($j):

. as $i

(range( 1;74;2) as $i

| (7 | power($i)) as $p

{{out}}

Invocation: gojq -ncr -f isqrt.jq

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

lpad(format(integer_sqrt(pow7^i), commas=true), 43))

end

<pre>

The integer square roots of integers from 0 to 65 are:

=={{header|Kotlin}}==

{{trans|Go}}

 

fun isqrt(x: BigInteger): BigInteger {

pow7 *= bi49

}

{{out}}

<pre>The integer square root of integers from 0 to 65 are:

=={{header|Lua}}==

{{trans|C}}

local q = 1

local r = 0

n = n + 2

p = p * 49

{{out}}

<pre>Integer square root for numbers 0 to 65:

21 | 558545864083284007 | 747359260</pre>

 

 

 

R INTEGER SQUARE ROOT OF X

INTERNAL FUNCTION(X)

ENTRY TO ISQRT.

END OF FUNCTION

VECTOR VALUES SQ7 = $9HISQRT.(7^,I2,4H) = ,I6*$

 

 

{{out}}

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

ISqrt[x_Integer?NonNegative] := Module[{q = 1, z, r, t},

While[q <= x,

]

ISqrt /@ Range[65]

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

2651730845859653471779023381601

7015820362023593956150476655802</pre>

 

=={{header|Nim}}==

{{libheader|bignum}}

This Nim implementation provides an <code>isqrt</code> function for signed integers and for big integers.

import bignum

 

for n in countup(1, 73, 2):

echo &"{n:>2} {insertSep($x, ','):>82} {insertSep($isqrt(x), ','):>41}"

 

{{out}}

71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686

73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802</pre>

 

=={{header|Ol}}==

(print "Integer square roots of 0..65")

(for-each (lambda (x)

(iota 73 1)))

(print)

{{Out}}

<pre>

{{libheader|Velthuis.BigIntegers}}[https://github.com/rvelthuis/DelphiBigNumbers]

{{trans|C++}}

//************************************************//

// //

CloseFile(f);

end.

 

=={{header|Perl}}==

{{trans|Julia}}

 

use strict;

printf("%44s", $decf->format( integer_sqrt(7**$i) ) ) ;

print "\n";

{{out}}

<pre>

=={{header|Phix}}==

See also [[Integer_roots#Phix]] for a simpler and shorter example using the mpz_root() routine, or better yet just use mpz_root() directly (that is, rather than the isqrt() below).

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>

<span style="color: #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.

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

</pre>

<small>(Note that pre-0.8.2 the "(NNN digits)" count includes commas)</small>

 

=={{header|Python}}==

{{works with|Python|2.7}}

q = 1

while q <= x :

 

print ' '.join( '%d'%isqrt( n ) for n in xrange( 66 ))

{{out}}

<pre>

=={{header|Quackery}}==

 

[ char , swap

i 1+ -3 * stuff ]

rot over + ]

again ]

 

 

73 times

number$ +commas 41 justify

echo$ cr

 

'''Output:'''

7,015,820,362,023,593,956,150,476,655,802

</pre>

 

=={{header|Raku}}==

 

Quadratic residue algorithm follows:

$q +<= 2 while $q ≤ $X ;

while $q > 1 {

say (^66)».&{ isqrt $_ }.Str ;

 

{{out}}

7**1: 2

7**3: 18

7**5: 129

7**7: 907

 

=={{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*/

end

end /*while*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

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

end

end

 

def isqrt(x)

q, r = 1, 0

puts isqrt(7**n).commatize

end

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

 

=={{header|Rust}}==

use num::BigUint;

use num::CheckedSub;

});

}

{{out}}

<pre>

</pre>

 

 

include "bigint.s7i";

 

stri := stri[.. index] & "," & stri[succ(index) ..];

end for;