Integer roots: Difference between revisions
Thundergnat (talk | contribs) m (→{{header|Ring}}: Remove vanity tags) |
m (Added Easylang) |
||
(63 intermediate revisions by 26 users not shown) | |||
Line 18: | Line 18: | ||
Example: With N=2 and X=2×100<sup>2,000</sup> you would calculate a large integer consisting of the first 2,001 digits (in order) of the square root of two. |
Example: With N=2 and X=2×100<sup>2,000</sup> you would calculate a large integer consisting of the first 2,001 digits (in order) of the square root of two. |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|D}} |
|||
<syntaxhighlight lang="11l">F iRoot(BigInt b, Int n) |
|||
I b < 2 {R b} |
|||
V n1 = n - 1 |
|||
V n2 = BigInt(n) |
|||
V n3 = BigInt(n1) |
|||
V c = BigInt(1) |
|||
V d = (n3 + b) I/ n2 |
|||
V e = (n3 * d + b I/ d ^ n1) I/ n2 |
|||
L c != d & c != e |
|||
c = d |
|||
d = e |
|||
e = (n3 * e + b I/ e ^ n1) I/ n2 |
|||
I d < e {R d} |
|||
R e |
|||
print(‘3rd root of 8 = ’iRoot(8, 3)) |
|||
print(‘3rd root of 9 = ’iRoot(9, 3)) |
|||
print(‘First 2001 digits of the square root of 2: ’iRoot(BigInt(100) ^ 2000 * 2, 2))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
3rd root of 8 = 2 |
|||
3rd root of 9 = 2 |
|||
First 2001 digits of the square root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008 |
|||
</pre> |
|||
=={{header|Ada}}== |
|||
<syntaxhighlight lang="ada"> |
|||
-- Find integer roots |
|||
-- J. Carter 2023 Jun |
|||
with Ada.Text_IO; |
|||
with System; |
|||
procedure Integer_Roots is |
|||
type Big is mod System.Max_Binary_Modulus; |
|||
function Root (N : in Positive; X : in Big) return Big With Pre => N > 1; |
|||
-- Returns the largest integer R such that R ** N <= X |
|||
-- Derived from Modula-2 |
|||
function Root (N : in Positive; X : in Big) return Big is |
|||
N1 : constant Positive := N - 1; |
|||
N2 : constant Big := Big (N); |
|||
N3 : constant Big := N2 - 1; |
|||
C : Big := 1; |
|||
D : Big := (N3 + X) / N2; |
|||
E : Big := (N3 * D + X / D ** N1) / N2; |
|||
begin -- Root |
|||
if X <= 1 then |
|||
return X; |
|||
end if; |
|||
Converge : loop |
|||
exit Converge when C = D or C = E; |
|||
C := D; |
|||
D := E; |
|||
E := (N3 * D + X / E ** N1) / N2; |
|||
end loop Converge; |
|||
return (if D < E then D else E); |
|||
end Root; |
|||
Large : constant Big := 2 * 10 ** 38; |
|||
-- On 64-bit platforms, recent versions of GNAT provide 128-bit integers |
|||
-- 10 ** 38 is the largest power of 10 < 2 ** 128 |
|||
begin -- Integer_Roots |
|||
Ada.Text_IO.Put_Line (Item => "Cube root of 8 =" & Root (3, 8)'Image); |
|||
Ada.Text_IO.Put_Line (Item => "Cube root of 9 =" & Root (3, 9)'Image); |
|||
Ada.Text_IO.Put_Line (Item => "Square root of" & Large'Image & " =" & Root (2, Large)'Image); |
|||
end Integer_Roots; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Cube root of 8 = 2 |
|||
Cube root of 9 = 2 |
|||
Square root of 200000000000000000000000000000000000000 = 14142135623730950488 |
|||
</pre> |
|||
=={{header|Arturo}}== |
|||
{{trans|D}} |
|||
<syntaxhighlight lang="rebol">iroot: function [b n][ |
|||
if b<2 -> return b |
|||
n1: n-1 |
|||
n2: n |
|||
n3: n1 |
|||
c: 1 |
|||
d: (n3+b)/n2 |
|||
e: ((n3*d) + b/d^n1)/n2 |
|||
while [and? c<>d c<>e][ |
|||
c: d |
|||
d: e |
|||
e: ((n3*e) + b/e^n1)/n2 |
|||
] |
|||
if d<e -> return d |
|||
return e |
|||
] |
|||
print ["3rd root of 8:" iroot 8 3] |
|||
print ["3rd root of 9:" iroot 9 3] |
|||
print ["First 2001 digits of the square root of 2:" iroot (100^2000)*2 2]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3rd root of 8: 2 |
|||
3rd root of 9: 2 |
|||
First 2001 digits of the square root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008</pre> |
|||
=={{header|BASIC256}}== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="basic256">function root(n, x) |
|||
for nr = floor(sqr(x)) to 1 step -1 |
|||
if (nr ^ n) <= x then return nr |
|||
next nr |
|||
end function |
|||
print root(3, 8) |
|||
print root(3, 9) |
|||
print root(4, 167) |
|||
print root(2, 2e18) |
|||
end</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Igual que la entrada de FreeBASIC. |
|||
</pre> |
|||
=={{header|C}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="c">#include <stdio.h> |
|||
#include <math.h> |
|||
typedef unsigned long long ulong; |
|||
ulong root(ulong base, ulong n) { |
|||
ulong n1, n2, n3, c, d, e; |
|||
if (base < 2) return base; |
|||
if (n == 0) return 1; |
|||
n1 = n - 1; |
|||
n2 = n; |
|||
n3 = n1; |
|||
c = 1; |
|||
d = (n3 + base) / n2; |
|||
e = (n3 * d + base / (ulong)powl(d, n1)) / n2; |
|||
while (c != d && c != e) { |
|||
c = d; |
|||
d = e; |
|||
e = (n3*e + base / (ulong)powl(e, n1)) / n2; |
|||
} |
|||
if (d < e) return d; |
|||
return e; |
|||
} |
|||
int main() { |
|||
ulong b = (ulong)2e18; |
|||
printf("3rd root of 8 = %lld\n", root(8, 3)); |
|||
printf("3rd root of 9 = %lld\n", root(9, 3)); |
|||
printf("2nd root of %lld = %lld\n", b, root(b, 2)); |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3rd root of 8 = 2 |
|||
3rd root of 9 = 2 |
|||
2nd root of 2000000000000000000 = 1414213562</pre> |
|||
=={{header|C sharp|C#}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="csharp">using System; |
|||
using System.Numerics; |
|||
namespace IntegerRoots { |
|||
class Program { |
|||
static BigInteger IRoot(BigInteger @base, int n) { |
|||
if (@base < 0 || n <= 0) { |
|||
throw new ArgumentException(); |
|||
} |
|||
int n1 = n - 1; |
|||
BigInteger n2 = n; |
|||
BigInteger n3 = n1; |
|||
BigInteger c = 1; |
|||
BigInteger d = (n3 + @base) / n2; |
|||
BigInteger e = ((n3 * d) + (@base / BigInteger.Pow(d, n1))) / n2; |
|||
while (c != d && c != e) { |
|||
c = d; |
|||
d = e; |
|||
e = (n3 * e + @base / BigInteger.Pow(e, n1)) / n2; |
|||
} |
|||
if (d < e) { |
|||
return d; |
|||
} |
|||
return e; |
|||
} |
|||
static void Main(string[] args) { |
|||
Console.WriteLine("3rd integer root of 8 = {0}", IRoot(8, 3)); |
|||
Console.WriteLine("3rd integer root of 9 = {0}", IRoot(9, 3)); |
|||
BigInteger b = BigInteger.Pow(100, 2000) * 2; |
|||
Console.WriteLine("First 2001 digits of the sqaure root of 2: {0}", IRoot(b, 2)); |
|||
} |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3rd integer root of 8 = 2 |
|||
3rd integer root of 9 = 2 |
|||
First 2001 digits of the sqaure root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008</pre> |
|||
=={{header|C++}}== |
|||
<syntaxhighlight lang="cpp">#include <iostream> |
|||
#include <math.h> |
|||
unsigned long long root(unsigned long long base, unsigned int n) { |
|||
if (base < 2) return base; |
|||
if (n == 0) return 1; |
|||
unsigned int n1 = n - 1; |
|||
unsigned long long n2 = n; |
|||
unsigned long long n3 = n1; |
|||
unsigned long long c = 1; |
|||
auto d = (n3 + base) / n2; |
|||
auto e = (n3 * d + base / pow(d, n1)) / n2; |
|||
while (c != d && c != e) { |
|||
c = d; |
|||
d = e; |
|||
e = (n3*e + base / pow(e, n1)) / n2; |
|||
} |
|||
if (d < e) return d; |
|||
return e; |
|||
} |
|||
int main() { |
|||
using namespace std; |
|||
cout << "3rd root of 8 = " << root(8, 3) << endl; |
|||
cout << "3rd root of 9 = " << root(9, 3) << endl; |
|||
unsigned long long b = 2e18; |
|||
cout << "2nd root of " << b << " = " << root(b, 2) << endl; |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3rd root of 8 = 2 |
|||
3rd root of 9 = 2 |
|||
2nd root of 2000000000000000000 = 1414213562</pre> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="d">import std.bigint; |
||
import std.stdio; |
import std.stdio; |
||
Line 50: | Line 314: | ||
b = BigInt(100)^^2000*2; |
b = BigInt(100)^^2000*2; |
||
writeln("First 2001 digits of the square root of 2: ", b.iRoot(2)); |
writeln("First 2001 digits of the square root of 2: ", b.iRoot(2)); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3rd root of 8 = 2 |
<pre>3rd root of 8 = 2 |
||
3rd root of 9 = 2 |
3rd root of 9 = 2 |
||
First 2001 digits of the square root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008</pre> |
First 2001 digits of the square root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008</pre> |
||
=={{header|Delphi}}== |
|||
{{works with|Delphi|6.0}} |
|||
{{libheader|SysUtils,StdCtrls}} |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="Delphi"> |
|||
function IntRoot(Base: int64; N: cardinal): int64; |
|||
var N1: cardinal; |
|||
var N2,N3,C: int64; |
|||
var D,E: int64; |
|||
begin |
|||
if Base < 2 then Result:=Base |
|||
else if N = 0 then Result:=1 |
|||
else |
|||
begin |
|||
N1:=N - 1; |
|||
N2:=N; |
|||
N3:=N1; |
|||
C:=1; |
|||
d:=round((N3 + Base) / N2); |
|||
e:=round((N3 * D + Base / Power(D, N1)) / N2); |
|||
while (C<>D) and (C<>E) do |
|||
begin |
|||
C:=D; |
|||
D:=E; |
|||
E:=Round((N3*E + Base / Power(E, N1)) / N2); |
|||
end; |
|||
if D < E then Result:=D |
|||
else Result:=E; |
|||
end; |
|||
end; |
|||
procedure ShowIntegerRoots(Memo: TMemo); |
|||
var Base: int64; |
|||
begin |
|||
Memo.Lines.Add('3rd integer root of 8 = '+IntToStr(IntRoot(8, 3))); |
|||
Memo.Lines.Add('3rd integer root of 9 = '+IntToStr(IntRoot(9, 3))); |
|||
Base:=2000000000000000000; |
|||
Memo.Lines.Add('sqaure root of 2 = '+IntToStr(IntRoot(Base, 2))); |
|||
end; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
3rd integer root of 8 = 2 |
|||
3rd integer root of 9 = 2 |
|||
sqaure root of 2 = 1414213562 |
|||
Elapsed Time: 2.747 ms. |
|||
</pre> |
|||
=={{header|EasyLang}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight> |
|||
func root base n . |
|||
if base < 2 |
|||
return base |
|||
. |
|||
if n = 0 |
|||
return 1 |
|||
. |
|||
n1 = n - 1 |
|||
n2 = n |
|||
n3 = n1 |
|||
c = 1 |
|||
d = (n3 + base) div n2 |
|||
e = (n3 * d + base div pow d n1) div n2 |
|||
while c <> d and c <> e |
|||
c = d |
|||
d = e |
|||
e = (n3 * e + base div pow e n1) div n2 |
|||
. |
|||
if (d < e) |
|||
return d |
|||
. |
|||
return e |
|||
. |
|||
print "3rd root of 8 = " & root 8 3 |
|||
print "3rd root of 9 = " & root 9 3 |
|||
b = 2e18 |
|||
print "2nd root of " & b & " = " & root b 2 |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
3rd root of 8 = 2 |
|||
3rd root of 9 = 2 |
|||
2nd root of 2e+18 = 1414213562 |
|||
</pre> |
|||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
< |
<syntaxhighlight lang="elixir">defmodule Integer_roots do |
||
def root(_, b) when b<2, do: b |
def root(_, b) when b<2, do: b |
||
def root(a, b) do |
def root(a, b) do |
||
Line 83: | Line 443: | ||
end |
end |
||
Integer_roots.task</ |
Integer_roots.task</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 92: | Line 452: | ||
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008 |
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008 |
||
</pre> |
</pre> |
||
=={{header|F_Sharp|F#}}== |
|||
{{trans|C#}} |
|||
<syntaxhighlight lang="fsharp">open System |
|||
let iroot (base_ : bigint) n = |
|||
if base_ < bigint.Zero || n <= 0 then |
|||
raise (ArgumentException "Bad parameter") |
|||
let n1 = n - 1 |
|||
let n2 = bigint n |
|||
let n3 = bigint n1 |
|||
let mutable c = bigint.One |
|||
let mutable d = (n3 + base_) / n2 |
|||
let mutable e = ((n3 * d) + (base_ / bigint.Pow(d, n1))) / n2 |
|||
while c <> d && c <> e do |
|||
c <- d |
|||
d <- e |
|||
e <- (n3 * e + base_ / bigint.Pow(e, n1)) / n2 |
|||
if d < e then |
|||
d |
|||
else |
|||
e |
|||
[<EntryPoint>] |
|||
let main _ = |
|||
Console.WriteLine("3rd integer root of 8 = {0}", (iroot (bigint 8) 3)) |
|||
Console.WriteLine("3rd integer root of 9 = {0}", (iroot (bigint 9) 3)) |
|||
let b = bigint.Pow(bigint 100, 2000) * (bigint 2) |
|||
Console.WriteLine("First 2001 digits of the sqaure root of 2: {0}", (iroot b 2)) |
|||
0 // return an integer exit code</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3rd integer root of 8 = 2 |
|||
3rd integer root of 9 = 2 |
|||
First 2001 digits of the sqaure root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008</pre> |
|||
=={{header|Factor}}== |
|||
{{trans|Sidef}} |
|||
<syntaxhighlight lang="factor">USING: io kernel locals math math.functions math.order |
|||
prettyprint sequences ; |
|||
:: (root) ( a b -- n ) |
|||
a 1 - 1 :> ( a1 c! ) |
|||
[| x | a1 x * b x a1 ^ /i + a /i ] :> f |
|||
c f call :> d! |
|||
d f call :> e! |
|||
[ c { d e } member? ] [ |
|||
d c! e d! e f call e! |
|||
] until |
|||
d e min ; |
|||
: root ( a b -- n ) dup 2 < [ nip ] [ (root) ] if ; |
|||
"First 2,001 digits of the square root of two:" print |
|||
2 100 2000 ^ 2 * root .</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 2,001 digits of the square root of two: |
|||
14142135623730950488016887242096980[...]32952546758516447107578486024636008 |
|||
</pre> |
|||
=={{header|FreeBASIC}}== |
|||
{{trans|Ring}} |
|||
<syntaxhighlight lang="freebasic">#define floor(x) ((x*2.0-0.5) Shr 1) |
|||
Function root(n As Uinteger, x As Uinteger) As Uinteger |
|||
For nr As Uinteger = floor(Sqr(x)) To 1 Step -1 |
|||
If (nr ^ n) <= x Then Return nr |
|||
Next nr |
|||
End Function |
|||
Print root(3, 8) |
|||
Print root(3, 9) |
|||
Print root(4, 167) |
|||
Print root(2, 2e18) |
|||
Sleep</syntaxhighlight> |
|||
{{out}} |
|||
<pre>2 |
|||
2 |
|||
3 |
|||
1414213562</pre> |
|||
=={{header|FutureBasic}}== |
|||
<syntaxhighlight lang="futurebasic"> |
|||
local fn root( n as UInt64, x as UInt64 ) as double |
|||
double nr, result = 0 |
|||
for nr = fn floor( sqr(x) ) to 1 step -1 |
|||
if ( nr ^ n ) <= x then result = nr : exit fn |
|||
next |
|||
end fn = result |
|||
print @"3rd root of 8 = "; fn root( 3, 8 ) |
|||
print @"3rd root of 9 = "; fn root( 3, 9 ) |
|||
print @"4th root of 167 = "; fn root( 4, 167 ) |
|||
print @"2nd root of 2e+018 = "; fn root( 2, 2e+018 ) |
|||
HandleEvents |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
3rd root of 8 = 2 |
|||
3rd root of 9 = 2 |
|||
4th root of 167 = 3 |
|||
2nd root of 2e+018 = 1414213562 |
|||
</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
===int=== |
===int=== |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 126: | Line 600: | ||
r += Δr |
r += Δr |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 134: | Line 608: | ||
</pre> |
</pre> |
||
===big.Int=== |
===big.Int=== |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 171: | Line 645: | ||
r.Add(r, &Δr) |
r.Add(r, &Δr) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 182: | Line 656: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="haskell">root :: Integer -> Integer -> Integer |
||
root a b = findAns |
root a b = findAns $ iterate (\x -> (a1 * x + b `div` (x ^ a1)) `div` a) 1 |
||
where |
|||
sequence = iterate (\x -> (a1 * x + b `div` (x ^ a1)) `div` a) 1 |
|||
a1 = a - 1 |
a1 = a - 1 |
||
findAns (x:xs@(y:z:_)) |
findAns (x:xs@(y:z:_)) |
||
| x == y || x == z = min y z |
|||
| otherwise = findAns xs |
|||
main :: IO () |
main :: IO () |
||
Line 193: | Line 668: | ||
print $ root 3 8 |
print $ root 3 8 |
||
print $ root 3 9 |
print $ root 3 9 |
||
print $ root 2 (2 * 100^2000) -- first 2001 digits of the square root of 2</ |
print $ root 2 (2 * 100 ^ 2000) -- first 2001 digits of the square root of 2</syntaxhighlight> |
||
Or equivalently, in terms of an applicative expression: |
|||
<syntaxhighlight lang="haskell">integerRoot :: Integer -> Integer -> Integer |
|||
integerRoot n x = |
|||
go $ iterate ((`div` n) . ((+) . (pn *) <*> (x `div`) . (^ pn))) 1 |
|||
where |
|||
pn = pred n |
|||
go (x:xs@(y:z:_)) |
|||
| x == y || x == z = min y z |
|||
| otherwise = go xs |
|||
main :: IO () |
|||
main = mapM_ (print . uncurry integerRoot) [(3, 8), (3, 9), (2, 2 * 100 ^ 2000)]</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre>2 |
||
2 |
2 |
||
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008</pre> |
|||
2 |
|||
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008 |
|||
</pre> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
Line 205: | Line 693: | ||
<code><.@%:</code> satisfies this task. Left argument is the task's N, right argument is the task's X: |
<code><.@%:</code> satisfies this task. Left argument is the task's N, right argument is the task's X: |
||
'''Note:''' If you are looking for a decimal expansion of an integer root, one must select the proper number of digits for N, that is, ''2000'', ''2001'', ''2002'', etc..., otherwise the result will be the digits of the nth root of 20, 2000, etc...<br/> |
|||
<lang J> 9!:37]0 4096 0 222 NB. set display truncation sufficiently high for our results |
|||
For example, If you use "3 <.@%: (2*10x^2*200'''0''')" instead of "3 <.@%: (2*10x^2*200'''1''')", you will get an output starting with "271441761659490657151808946...", which are the first digits of the cube root of 20, not 2. This constraint is independent of the task requirements, except in an illustrative sense, so will not be developed further, here. |
|||
<syntaxhighlight lang="j"> 9!:37]0 4096 0 222 NB. set display truncation sufficiently high for our results |
|||
2 <.@%: (2*10x^2*2000) |
2 <.@%: (2*10x^2*2000) |
||
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008 |
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008 |
||
3 <.@%: (2*10x^2* |
3 <.@%: (2*10x^2*2001) |
||
125992104989487316476721060727822835057025146470150798008197511215529967651395948372939656243625509415431025603561566525939902404061373722845911030426935524696064261662500097747452656548030686718540551868924587251676419937370969509838278316139915512931369536618394746344857657030311909589598474110598116290705359081647801147352132548477129788024220858205325797252666220266900566560819947156281764050606648267735726704194862076214429656942050793191724414809204482328401274703219642820812019057141889964599983175038018886895942020559220211547299738488026073636974178877921579846750995396300782609596242034832386601398573634339097371265279959919699683779131681681544288502796515292781076797140020406056748039385612517183570069079849963419762914740448345402697154762285131780206438780476493225790528984670858052862581300054293885607206097472230406313572349364584065759169169167270601244028967000010690810353138529027004150842323362398893864967821941498380270729571768128790014457462271477023483571519055067220848184850092872392092826466067171742477537097370300127429180940544256965920750363575703751896037074739934610144901451576359604711119738452991329657262589048609788561801386773836157730098659836608059757560127871214868562426845564116515581793532280158962912994450040120842541416015752584162988142309735821530604057724253836453253356 |
|||
27144176165949065715180894696794892048051077694890969572843654428033085563287658494871973768515010449601702702662017016622108188038292129512829222732037939681464769491319263029308919709511736401200395299672806902057959507281705818417585572775465293620106435558459837272246448049135012971629241921717289904494332635356114519208640365765906522454723182775121756558058020787429240528065700321862315922465987881667832001482693220149093231249941256750252873117504822276540899360702266289427386749058832442643990936924594623694605667125995688788028079451303313515777223983018552490248388121970980055977541748894293734175182220013380497630428176870053423294103392285168797917553010332228664978678396929617114885278335650885524410898341213271192520021355449870508579216359067962061031950345530646092202370608763454397416764433915183368398263533906772869972563479248093751375796381425079119097628053496428734814910307755317031117606073779997125797512066497555354285360734633889394275558674944424368960732987910929093583629174893939036518727793282632439102479840614327136348027409016670160346303867705846755103908964945780837562103026771901489757443287280572195601219016859180373403783498753667545621963282035797597576337893795984255961467481252116653755272803423453851317757500585155874395469445425245653837328715044666730082806623655698726925 |
|||
5 <.@%: (2*10x^2*2000) |
5 <.@%: (2*10x^2*2000) |
||
114869835499703500679862694677792758944385088909779750551371111849360320625351305681147311301150847391457571782825280872990018972855371267615994917020637676959403854539263226492033301322122190625130645468320078386350285806907949085127708283982797043969640382563667945344431106523789654147255972578315704103326302050272017414235255993151553782375173884359786924137881735354092890268530342009402133755822717151679559278360263800840317501093689917495888199116488588871447782240220513546797235647742625493141141704109917646404017146978939243424915943739448283626010758721504375406023613552985026793701507511351368254645700768390780390334017990233124030682358360249760098999315658413563173197024899154512108923313999675829872581317721346549115423634135836394159076400636688679216398175376716152621781331348 |
114869835499703500679862694677792758944385088909779750551371111849360320625351305681147311301150847391457571782825280872990018972855371267615994917020637676959403854539263226492033301322122190625130645468320078386350285806907949085127708283982797043969640382563667945344431106523789654147255972578315704103326302050272017414235255993151553782375173884359786924137881735354092890268530342009402133755822717151679559278360263800840317501093689917495888199116488588871447782240220513546797235647742625493141141704109917646404017146978939243424915943739448283626010758721504375406023613552985026793701507511351368254645700768390780390334017990233124030682358360249760098999315658413563173197024899154512108923313999675829872581317721346549115423634135836394159076400636688679216398175376716152621781331348 |
||
7 <.@%: (2*10x^2* |
7 <.@%: (2*10x^2*2002) |
||
1104089513673812337649505387623344721325326600780124165514532464142106322880380980716598289886302005146897159065579931253969214680430855796510648058388081961639198643922155838145512343974763395078906646859029211806139421440562835192195007740110439139292223389537903767320705032063903809884944457070845279252405827307254864679671836816589429995916822424590361601902611505690284386526869351720866524568004847701822070064334667580822044823960984514550922242408608825451442062850448298384317793721518676765230683406727811327252052334859250776811047221310365241746671294399050316</syntaxhighlight> |
|||
29619362959451736245702628695019269518064618216015009169507699742781423769947484925822512257735101524178182602734424986961003971858127002794053824818478879396020132662403256874761276690431037137165264232256601651438511207764019815767975124455844526943932927494896013055497926678521360177960529077012650088983239249505488961115547364229473827474458408002500739618874659540108997885564940730803150961523774615079827002013042942440654069714159530336055547627964891459096727426898214883744931710925020592035759639587602673656267343846153343265577563529779031634608306646526796</lang> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="java">import java.math.BigInteger; |
||
public class IntegerRoots { |
public class IntegerRoots { |
||
Line 256: | Line 747: | ||
System.out.println(iRoot(b, 2)); |
System.out.println(iRoot(b, 2)); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3rd integer root of 8 = 2 |
<pre>3rd integer root of 8 = 2 |
||
3rd integer root of 9 = 2 |
3rd integer root of 9 = 2 |
||
First 2001 digits of the square root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008</pre> |
First 2001 digits of the square root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008</pre> |
||
=={{header|jq}}== |
|||
'''Adapted from [[#Julia|Julia]]''' |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
<syntaxhighlight lang="jq"># To take advantage of gojq's arbitrary-precision integer arithmetic: |
|||
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in); |
|||
# If $j is 0, then an error condition is raised; |
|||
# otherwise, assuming infinite-precision integer arithmetic, |
|||
# if the input and $j are integers, then the result will be an integer. |
|||
def idivide($j): |
|||
(. - (. % $j)) / $j ; |
|||
def iroot(a; b): |
|||
if b < 2 then b |
|||
else (a-1) as $a1 |
|||
| {c: 1, |
|||
d: (($a1 + (b | idivide(1))) | idivide(a)) } |
|||
| .d as $d |
|||
| .e = ($a1 * $d + (b |idivide($d | power($a1))) | idivide(a)) |
|||
| until( .d == .c or .c == .e; |
|||
.c = .d |
|||
| .d = .e |
|||
| .e as $e |
|||
| .e = ($a1 * .e + (b | idivide(($e | power($a1)))) | idivide(a)) ) |
|||
| [.d, .e] | min |
|||
end ; |
|||
# The task: |
|||
"First 2,001 digits of the square root of two:", |
|||
iroot(2; 2 * (100 | power(2000)))</syntaxhighlight> |
|||
{{out}} |
|||
Exactly as for [[#Julia|Julia]]. |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{works with|Julia| |
{{works with|Julia|1.3}} |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="julia">function iroot(a, b) |
||
b < 2 && return b |
|||
a1, c = a - 1, 1 |
a1, c = a - 1, 1 |
||
d = (a1 * c + b ÷ |
d = (a1 * c + b ÷ c^a1) ÷ a |
||
e = (a1 * d + b ÷ |
e = (a1 * d + b ÷ d^a1) ÷ a |
||
while |
while d ≠ c ≠ e |
||
c, d, e = d, e, (a1 * e + b ÷ (e ^ a1)) ÷ a |
c, d, e = d, e, (a1 * e + b ÷ (e ^ a1)) ÷ a |
||
end |
end |
||
min(d, e) |
|||
end |
end |
||
println("First 2,001 digits of the square root of two:\n", iroot(2, 2 * big(100) ^ 2000))</ |
println("First 2,001 digits of the square root of two:\n", iroot(2, 2 * big(100) ^ 2000))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 286: | Line 812: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="scala">// version 1.1.2 |
||
import java.math.BigInteger |
import java.math.BigInteger |
||
Line 320: | Line 846: | ||
println("First 2001 digits of the square root of 2:") |
println("First 2001 digits of the square root of 2:") |
||
println(b.iRoot(2)) |
println(b.iRoot(2)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 332: | Line 858: | ||
</pre> |
</pre> |
||
=={{header| |
=={{header|Lua}}== |
||
{{trans| |
{{trans|C}} |
||
<syntaxhighlight lang="lua">function root(base, n) |
|||
<lang perl6>sub integer_root ( Int $p where * >= 2, Int $n --> Int ) { |
|||
if base < 2 then return base end |
|||
if n == 0 then return 1 end |
|||
local n1 = n - 1 |
|||
local n2 = n |
|||
local n3 = n1 |
|||
local c = 1 |
|||
local d = math.floor((n3 + base) / n2) |
|||
local e = math.floor((n3 * d + base / math.pow(d, n1)) / n2) |
|||
while c ~= d and c ~= e do |
|||
my $iterator = { ( $d * $^x + $n div ($^x ** $d) ) div $p }; |
|||
c = d |
|||
d = e |
|||
e = math.floor((n3 * e + base / math.pow(e, n1)) / n2) |
|||
end |
|||
if d < e then return d end |
|||
my $endpoint = { $^x ** $p <= $n |
|||
return e |
|||
and ($^x + 1) ** $p > $n }; |
|||
end |
|||
-- main |
|||
return [min] (+$guess, $iterator ... $endpoint)[*-1, *-2]; |
|||
local b = 2e18 |
|||
print("3rd root of 8 = " .. root(8, 3)) |
|||
print("3rd root of 9 = " .. root(9, 3)) |
|||
print("2nd root of " .. b .. " = " .. root(b, 2))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3rd root of 8 = 2 |
|||
3rd root of 9 = 2 |
|||
2nd root of 2e+018 = 1414213562</pre> |
|||
=={{header|Modula-2}}== |
|||
<syntaxhighlight lang="modula2">MODULE IntegerRoot; |
|||
FROM FormatString IMPORT FormatString; |
|||
FROM Terminal IMPORT WriteString,ReadChar; |
|||
PROCEDURE pow(b : LONGCARD; p : CARDINAL) : LONGCARD; |
|||
VAR |
|||
result : LONGCARD; |
|||
BEGIN |
|||
result := 1; |
|||
WHILE p > 0 DO |
|||
IF p MOD 2 = 1 THEN |
|||
DEC(p); |
|||
result := result * b; |
|||
END; |
|||
p := p / 2; |
|||
b := b * b |
|||
END; |
|||
RETURN result |
|||
END pow; |
|||
PROCEDURE root(base : LONGCARD; n : CARDINAL) : LONGCARD; |
|||
VAR |
|||
n1,n2,n3,c,d,e : LONGCARD; |
|||
BEGIN |
|||
IF base < 2 THEN RETURN base END; |
|||
IF n = 0 THEN RETURN 1 END; |
|||
n1 := n - 1; |
|||
n2 := n; |
|||
n3 := n1; |
|||
c := 1; |
|||
d := (n3 + base) / n2; |
|||
e := (n3 * d + base / pow(d, n1)) / n2; |
|||
WHILE (c # d) AND (c # e) DO |
|||
c := d; |
|||
d := e; |
|||
e := (n3 * e + base / pow(e, n1)) / n2 |
|||
END; |
|||
IF d < e THEN RETURN d END; |
|||
RETURN e |
|||
END root; |
|||
(* main *) |
|||
VAR |
|||
buf : ARRAY[0..63] OF CHAR; |
|||
b : LONGCARD; |
|||
BEGIN |
|||
FormatString("3rd root of 8 = %u\n", buf, root(8, 3)); |
|||
WriteString(buf); |
|||
FormatString("3rd root of 9 = %u\n", buf, root(9, 3)); |
|||
WriteString(buf); |
|||
b := 2000000000000000000; |
|||
FormatString("2nd root of %u = %u\n", buf, b, root(b, 2)); |
|||
WriteString(buf); |
|||
ReadChar |
|||
END IntegerRoot.</syntaxhighlight> |
|||
=={{header|Nim}}== |
|||
{{trans|Kotlin}} |
|||
{{libheader|bignum}} |
|||
<syntaxhighlight lang="nim">import bignum |
|||
proc root(x: Int; n: int): Int = |
|||
if x < 2: return x |
|||
let n1 = (n - 1).culong |
|||
var c = newInt(1) |
|||
var d = (n1 + x) div n |
|||
var e = (n1 * d + x div d.pow(n1)) div n |
|||
while c != d and c != e: |
|||
c = d |
|||
d = e |
|||
e = (n1 * e + x div e.pow(n1)) div n |
|||
result = if d < e: d else: e |
|||
var x: Int |
|||
x = newInt(8) |
|||
echo "3rd integer root of 8 = ", x.root(3) |
|||
x = newInt(9) |
|||
echo "3rd integer root of 9 = ", x.root(3) |
|||
x = newInt(100).pow(2000) * newInt(2) |
|||
echo "First 2001 digits of the square root of 2:" |
|||
let s = $x.root(2) |
|||
for i in countup(0, s.high, 87): echo s.substr(i, i + 86)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3rd integer root of 8 = 2 |
|||
3rd integer root of 9 = 2 |
|||
First 2001 digits of the square root of 2: |
|||
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038 |
|||
753432764157273501384623091229702492483605585073721264412149709993583141322266592750559 |
|||
275579995050115278206057147010955997160597027453459686201472851741864088919860955232923 |
|||
048430871432145083976260362799525140798968725339654633180882964062061525835239505474575 |
|||
028775996172983557522033753185701135437460340849884716038689997069900481503054402779031 |
|||
645424782306849293691862158057846311159666871301301561856898723723528850926486124949771 |
|||
542183342042856860601468247207714358548741556570696776537202264854470158588016207584749 |
|||
226572260020855844665214583988939443709265918003113882464681570826301005948587040031864 |
|||
803421948972782906410450726368813137398552561173220402450912277002269411275736272804957 |
|||
381089675040183698683684507257993647290607629969413804756548237289971803268024744206292 |
|||
691248590521810044598421505911202494413417285314781058036033710773091828693147101711116 |
|||
839165817268894197587165821521282295184884720896946338628915628827659526351405422676532 |
|||
396946175112916024087155101351504553812875600526314680171274026539694702403005174953188 |
|||
629256313851881634780015693691768818523786840522878376293892143006558695686859645951555 |
|||
016447245098368960368873231143894155766510408839142923381132060524336294853170499157717 |
|||
562285497414389991880217624309652065642118273167262575395947172559346372386322614827426 |
|||
222086711558395999265211762526989175409881593486400834570851814722318142040704265090565 |
|||
323333984364578657967965192672923998753666172159825788602633636178274959942194037777536 |
|||
814262177387991945513972312740668983299898953867288228563786977496625199665835257761989 |
|||
393228453447356947949629521688914854925389047558288345260965240965428893945386466257449 |
|||
275563819644103169798330618520193793849400571563337205480685405758679996701213722394758 |
|||
214263065851322174088323829472876173936474678374319600015921888073478576172522118674904 |
|||
249773669292073110963697216089337086611567345853348332952546758516447107578486024636008</pre> |
|||
=={{header|PARI/GP}}== |
|||
<syntaxhighlight lang="parigp">sqrtnint(8,3) |
|||
sqrtnint(9,3) |
|||
sqrtnint(2*100^2000,2)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>%1 = 2 |
|||
%2 = 2 |
|||
%3 = 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008</pre> |
|||
=={{header|Perl}}== |
|||
{{trans|Ruby}} |
|||
<syntaxhighlight lang="perl">use bigint; |
|||
sub integer_root { |
|||
our($a,$b) = @_; |
|||
our $a1 = $a - 1; |
|||
my $c = 1; |
|||
my $d = f($c); |
|||
my $e = f($d); |
|||
($c, $d, $e) = ($d, $e, f($e)) until $c==$d || $c==$e; |
|||
return $d < $e ? $d : $e; |
|||
sub f { ($a1*$_[0]+$b/$_[0]**$a1)/$a } |
|||
} |
} |
||
print integer_root( 3, 8), "\n"; |
|||
print integer_root( 3, 9), "\n"; |
|||
print integer_root( 2, 2 * 100 ** 2000), "\n";</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre>2 |
|||
<pre>141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008 |
|||
2 |
|||
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008</pre> |
|||
===Using a module=== |
|||
If using bigints, we can do this directly, which will be much faster than the method above: |
|||
<syntaxhighlight lang="perl">use bigint; |
|||
print 8->babs->broot(3),"\n"; |
|||
print 9->babs->broot(3),"\n"; |
|||
print +(2*100**2000)->babs->broot(2),"\n";</syntaxhighlight> |
|||
The <code>babs</code> calls are only necessary if the input might be non-negative. |
|||
Even faster, using a module: |
|||
<syntaxhighlight lang="perl">use bigint; |
|||
use ntheory "rootint"; |
|||
print rootint(8,3),"\n"; |
|||
print rootint(9,3),"\n"; |
|||
print rootint(2*100**2000,2),"\n";</syntaxhighlight> |
|||
Both generate the same output as above. |
|||
=={{header|Phix}}== |
|||
{{libheader|Phix/mpfr}} |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<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: #008080;">function</span> <span style="color: #000000;">integer_root</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000080;font-style:italic;">-- a must be integer or string |
|||
-- (were a an mpz you would have to invoke mpz_init_set(), not mpz_init(), |
|||
-- or better yet pass a as the second parameter of mpz_root() instead.)</span> |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">mpz_nthroot</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"3rd root of 8 = %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">integer_root</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"3rd root of 9 = %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">integer_root</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">integer_root</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"2"</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4000</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"First digits of the square root of 2: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">integer_root</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"2"</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6000</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"First digits of the cube root of 2: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
<pre> |
|||
3rd root of 8 = 2 |
|||
3rd root of 9 = 2 |
|||
First digits of the square root of 2: 14142135623730950488...47107578486024636008 (2,001 digits) |
|||
First digits of the cube root of 2: 12599210498948731647...22546828353183047061 (2,001 digits) |
|||
"0.4s" |
|||
</pre> |
</pre> |
||
While this finishes near-instantly on the desktop, it takes about 25s under pwa/p2js. |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">def root(a, b): |
||
if b<2: |
if b < 2: |
||
return b |
|||
a1 = a - 1 |
|||
c = 1 |
|||
d=(a1*c+b//(c**a1))//a |
|||
d = (a1 * c + b // (c ** a1)) // a |
|||
e = (a1 * d + b // (d ** a1)) // a |
|||
while c!=d and c!=e: |
|||
while c not in (d, e): |
|||
c, d, e = d, e, (a1 * e + b // (e ** a1)) // a |
|||
return min(d,e) |
|||
return min(d, e) |
|||
print("First 2,001 digits of the square root of two:\n{}".format(root(2,2*100**2000)))</lang> |
|||
print("First 2,001 digits of the square root of two:\n{}".format( |
|||
root(2, 2 * 100 ** 2000) |
|||
))</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre>First 2,001 digits of the square root of two: |
<pre>First 2,001 digits of the square root of two: |
||
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008</pre> |
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008</pre> |
||
=={{header|Quackery}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="quackery"> [ stack ] is a-1 ( --> s ) |
|||
[ stack ] is b ( --> s ) |
|||
[ a-1 share tuck 2dup * |
|||
unrot ** |
|||
b share swap / + |
|||
swap 1+ / ] is nextapprox ( n --> n ) |
|||
[ over 2 < iff drop done |
|||
1 - a-1 put |
|||
b put |
|||
1 |
|||
2 times [ dup nextapprox ] |
|||
[ dip [ 2dup = rot ] |
|||
tuck = rot or not while |
|||
dup nextapprox again ] |
|||
min |
|||
b release a-1 release ] is root ( n n --> n ) |
|||
say "3rd root of 8 = " 8 3 root echo cr |
|||
say "3rd root of 9 = " 9 3 root echo cr |
|||
say "First 2001 digits of the square root of 2: " |
|||
2 100 2000 ** * 2 root echo cr</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3rd root of 8 = 2 |
|||
3rd root of 9 = 2 |
|||
First 2001 digits of the square root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008 |
|||
</pre> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
See [[#Scheme]], there’s very little can be done to improve it. |
See [[#Scheme]], there’s very little can be done to improve it. |
||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="raku" line>sub integer_root ( Int $p where * >= 2, Int $n --> Int ) { |
|||
my Int $d = $p - 1; |
|||
( |
|||
10**($n.chars div $p), |
|||
{ ( $d * $^x + $n div ($x ** $d) ) div $p } ... |
|||
-> $a, $, $c { $a == $c } |
|||
).tail(2).min; |
|||
} |
|||
say integer_root( 2, 2 * 100 ** 2000 );</syntaxhighlight> |
|||
{{out}} |
|||
<pre>141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008 |
|||
</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Line 379: | Line 1,178: | ||
<br>multiply the guess ['''G'''] by unity, and no need to compute the guess to the 1<sup>st</sup> power, bypassing some trivial arithmetic). |
<br>multiply the guess ['''G'''] by unity, and no need to compute the guess to the 1<sup>st</sup> power, bypassing some trivial arithmetic). |
||
===integer result only=== |
===integer result only=== |
||
< |
<syntaxhighlight lang="rexx">/*REXX program calculates the Nth root of a number to a specified number of decimal digs*/ |
||
parse arg num root digs . /*obtain the optional arguments from CL*/ |
parse arg num root digs . /*obtain the optional arguments from CL*/ |
||
if num=='' | num=="," then num= 2 /*Not specified? Then use the default.*/ |
if num=='' | num=="," then num= 2 /*Not specified? Then use the default.*/ |
||
Line 401: | Line 1,200: | ||
if m==1 then do until old==g; old=g; g=(g + z % g ) % root; end |
if m==1 then do until old==g; old=g; g=(g + z % g ) % root; end |
||
else do until old==g; old=g; g=(g*m + z % (g**m) ) % root; end |
else do until old==g; old=g; g=(g*m + z % (g**m) ) % root; end |
||
return left(g,p) /*return the Nth root of Z to invoker.*/</ |
return left(g,p) /*return the Nth root of Z to invoker.*/</syntaxhighlight> |
||
'''output''' when the defaults are being used: |
'''output''' when the defaults are being used: |
||
<pre> |
<pre> |
||
Line 424: | Line 1,223: | ||
===true results=== |
===true results=== |
||
<br>Negative and complex roots are supported. The expressed root may have a decimal point. |
<br>Negative and complex roots are supported. The expressed root may have a decimal point. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program calculates the Nth root of a number to a specified number of decimal digs*/ |
||
parse arg num root digs . /*obtain the optional arguments from CL*/ |
parse arg num root digs . /*obtain the optional arguments from CL*/ |
||
if num=='' | num=="," then num= 2 /*Not specified? Then use the default.*/ |
if num=='' | num=="," then num= 2 /*Not specified? Then use the default.*/ |
||
Line 458: | Line 1,257: | ||
numeric digits od /*set numeric digits to the original.*/ |
numeric digits od /*set numeric digits to the original.*/ |
||
if oy<0 then return (1/_)i /*Is the root negative? Use reciprocal*/ |
if oy<0 then return (1/_)i /*Is the root negative? Use reciprocal*/ |
||
return (_/1)i /*return the Yth root of X to invoker.*/</ |
return (_/1)i /*return the Yth root of X to invoker.*/</syntaxhighlight> |
||
'''output''' when the defaults are being used: |
'''output''' when the defaults are being used: |
||
<pre> |
<pre> |
||
Line 498: | Line 1,297: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
# Project : Integer roots |
# Project : Integer roots |
||
Line 512: | Line 1,311: | ||
ok |
ok |
||
next |
next |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 519: | Line 1,318: | ||
3 |
3 |
||
</pre> |
</pre> |
||
=={{header|RPL}}== |
|||
{{trans|Python}} |
|||
« DUP 1 - |
|||
→ x n n1 |
|||
« '''IF''' x 2 < '''THEN''' x |
|||
'''ELSE''' |
|||
« n1 OVER * x 3 PICK n1 ^ / IP + n / IP » |
|||
→ func |
|||
« 1 func EVAL func EVAL |
|||
'''WHILE''' ROT DUP2 ≠ SWAP 4 PICK ≠ AND |
|||
'''REPEAT''' func EVAL '''END''' |
|||
MIN |
|||
» |
|||
'''END''' |
|||
» » '<span style="color:blue">IROOT</span>' STO <span style="color:grey"> @ ''( x n → root ) with root^n ≤ x</span>'' |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
{{trans|Python, zkl}} |
{{trans|Python, zkl}} |
||
< |
<syntaxhighlight lang="ruby">def root(a,b) |
||
return b if b<2 |
return b if b<2 |
||
a1, c = a-1, 1 |
a1, c = a-1, 1 |
||
Line 534: | Line 1,349: | ||
puts "First 2,001 digits of the square root of two:" |
puts "First 2,001 digits of the square root of two:" |
||
puts root(2, 2*100**2000) |
puts root(2, 2*100**2000) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}}<pre>First 2,001 digits of the square root of two: |
{{out}}<pre>First 2,001 digits of the square root of two: |
||
14142135623730950488016887242096(...)46758516447107578486024636008</pre> |
14142135623730950488016887242096(...)46758516447107578486024636008</pre> |
||
=={{header|Rust}}== |
|||
The rug crate provides the functionality required for this task. |
|||
<syntaxhighlight lang="rust">// [dependencies] |
|||
// rug = "1.9" |
|||
fn shorten(s: &str, digits: usize) -> String { |
|||
if s.len() <= digits + 3 { |
|||
return String::from(s); |
|||
} |
|||
format!("{}...{}", &s[0..digits/2], &s[s.len()-digits/2..]) |
|||
} |
|||
fn main() { |
|||
use rug::{ops::Pow, Integer}; |
|||
let x = Integer::from(8); |
|||
let r = Integer::from(x.root_ref(3)); |
|||
println!("Integer cube root of {}: {}", x, r); |
|||
let x = Integer::from(9); |
|||
let r = Integer::from(x.root_ref(3)); |
|||
println!("Integer cube root of {}: {}", x, r); |
|||
let mut x = Integer::from(100).pow(2000); |
|||
x *= 2; |
|||
let s = Integer::from(x.root(2)).to_string(); |
|||
println!("First {} digits of the square root of 2:\n{}", s.len(), shorten(&s, 70)); |
|||
let mut x = Integer::from(100).pow(3000); |
|||
x *= 2; |
|||
let s = Integer::from(x.root(3)).to_string(); |
|||
println!("First {} digits of the cube root of 2:\n{}", s.len(), shorten(&s, 70)); |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Integer cube root of 8: 2 |
|||
Integer cube root of 9: 2 |
|||
First 2001 digits of the square root of 2: |
|||
14142135623730950488016887242096980...32952546758516447107578486024636008 |
|||
First 2001 digits of the cube root of 2: |
|||
12599210498948731647672106072782283...28546452083111122546828353183047061 |
|||
</pre> |
|||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
===Functional solution, tail recursive, no immutables=== |
===Functional solution, tail recursive, no immutables=== |
||
< |
<syntaxhighlight lang="scala">import scala.annotation.tailrec |
||
object IntegerRoots extends App { |
object IntegerRoots extends App { |
||
Line 567: | Line 1,426: | ||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{Out}}See it running in your browser by [https://scalafiddle.io/sf/bVwlHfa/0 ScalaFiddle (JavaScript, non JVM)] or by [https://scastie.scala-lang.org/0T93IhLVRGiYfuKpW7DTUg Scastie (JVM)]. |
{{Out}}See it running in your browser by [https://scalafiddle.io/sf/bVwlHfa/0 ScalaFiddle (JavaScript, non JVM)] or by [https://scastie.scala-lang.org/0T93IhLVRGiYfuKpW7DTUg Scastie (JVM)]. |
||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="scheme">(define (root a b) |
||
(define // quotient) |
(define // quotient) |
||
(define (y a a1 b c d e) |
(define (y a a1 b c d e) |
||
Line 587: | Line 1,446: | ||
(display "First 2,001 digits of the cube root of two:\n") |
(display "First 2,001 digits of the cube root of two:\n") |
||
(display (root 3 (* 2 (expt 1000 2000))))</ |
(display (root 3 (* 2 (expt 1000 2000))))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 595: | Line 1,454: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
< |
<syntaxhighlight lang="ruby">func root(a, b) { |
||
b < 2 && return(b) |
b < 2 && return(b) |
||
var (a1, c) = (a-1, 1) |
var (a1, c) = (a-1, 1) |
||
Line 608: | Line 1,467: | ||
say "First 2,001 digits of the square root of two:" |
say "First 2,001 digits of the square root of two:" |
||
say root(2, 2 * 100**2000)</ |
say root(2, 2 * 100**2000)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 614: | Line 1,473: | ||
14142135623730950488016887242096980[...]32952546758516447107578486024636008 |
14142135623730950488016887242096980[...]32952546758516447107578486024636008 |
||
</pre> |
</pre> |
||
=={{header|Tcl}}== |
|||
Tcl is not made for number crunching. The execution is quite slow compared to compiled languages. |
|||
On the other hand, everything is very straightforward, no libraries necessary. |
|||
<syntaxhighlight lang="tcl"> |
|||
proc root {this n} { |
|||
if {$this < 2} {return $this} |
|||
set n1 [expr $n - 1] |
|||
set n2 $n |
|||
set n3 $n1 |
|||
set c 1 |
|||
set d [expr ($n3 + $this) / $n2] |
|||
set e [expr ($n3 * $d + $this / ($d ** $n1)) / $n2] |
|||
while {$c != $d && $c != $e} { |
|||
set c $d |
|||
set d $e |
|||
set e [expr ($n3 * $e + $this / ($e ** $n1)) / $n2] |
|||
} |
|||
return [expr min($d, $e)] |
|||
} |
|||
puts [root 8 3] |
|||
puts [root 9 3] |
|||
puts [root [expr 2* (100**2000)] 2] |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
2 |
|||
2 |
|||
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008 |
|||
</pre> |
|||
=={{header|Visual Basic .NET}}== |
|||
{{libheader|System.Numerics}} |
|||
From the method described on [https://en.wikipedia.org/wiki/Nth_root_algorithm the Wikipedia page]. Included is an Integer Square Root function to compare results to the Integer Nth Square root function. One must choose the exponents carefully, otherwise one will obtain the digits of the nth root of 20, 200, 2000, etc..., instead of 2. For example, 4008 was chosen because it works for both ''n = 2'' and ''n = 3'', whereas 4004 was chosen for ''n = 7''<syntaxhighlight lang="vbnet">Imports System |
|||
Imports System.Numerics |
|||
Imports Microsoft.VisualBasic.Strings |
|||
Public Module Module1 |
|||
Public Function IntSqRoot(v As BigInteger) As BigInteger |
|||
Dim digs As Integer = Math.Max(0, v.ToString().Length / 2 - 1) |
|||
IntSqRoot = BigInteger.Parse("3" & StrDup(digs, "0")) |
|||
Dim term As BigInteger |
|||
Do |
|||
term = v / IntSqRoot |
|||
If Math.Abs(CDbl(term - IntSqRoot)) < 2 Then Exit Do |
|||
IntSqRoot = (IntSqRoot + term) / 2 |
|||
Loop Until False |
|||
End Function |
|||
Public Function IntNthRoot(n As Integer, v As BigInteger) As BigInteger |
|||
Dim digs As Integer = Math.Max(0, v.ToString().Length / n - 1) |
|||
IntNthRoot = BigInteger.Parse(If(digs > 1, 3, 2).ToString() & StrDup(digs, "0")) |
|||
Dim va As BigInteger, dr As BigInteger |
|||
Do |
|||
va = v : For i As Integer = 2 To n : va /= IntNthRoot : Next |
|||
va -= IntNthRoot |
|||
dr = va / n : If dr = 0 Then Exit Do |
|||
IntNthRoot += dr |
|||
Loop Until False |
|||
End Function |
|||
Public Sub Main() |
|||
Dim b As BigInteger = BigInteger.Parse("2" & StrDup(4008, "0")) |
|||
Console.WriteLine("Integer Cube Root of 8:") |
|||
Console.WriteLine(IntNthRoot(3, 8).ToString()) ' given example |
|||
Console.WriteLine("Integer Cube Root of 9:") |
|||
Console.WriteLine(IntNthRoot(3, 9).ToString()) ' given example |
|||
Console.WriteLine("Integer Square Root of 2, (actually 2 * 10 ^ 4008, square root method):") |
|||
Console.WriteLine(IntSqRoot(b).ToString()) ' reality check |
|||
Console.WriteLine("Integer Square Root of 2, (actually 2 * 10 ^ 4008, nth root method):") |
|||
Console.WriteLine(IntNthRoot(2, b).ToString()) ' given example |
|||
Console.WriteLine("Integer Cube Root of 2, (actually 2 * 10 ^ 4008):") |
|||
Console.WriteLine(IntNthRoot(3, b).ToString()) ' bonus example |
|||
b /= 10000 |
|||
Console.WriteLine("Integer 7th Root of 2, (actually 2 * 10 ^ 4004):") |
|||
Console.WriteLine(IntNthRoot(7, b).ToString()) ' bonus example |
|||
If Diagnostics.Debugger.IsAttached Then Console.Read() |
|||
End Sub |
|||
End Module |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre style="height:64ex;overflow:scroll"> |
|||
Integer Cube Root of 8: |
|||
2 |
|||
Integer Cube Root of 9: |
|||
2 |
|||
Integer Square Root of 2, (actually 2 * 10 ^ 4008, square root method): |
|||
1414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641572735013846230912297024924836055850737212644121497099935831413222665927505592755799950501152782060571470109559971605970274534596862014728517418640889198609552329230484308714321450839762603627995251407989687253396546331808829640620615258352395054745750287759961729835575220337531857011354374603408498847160386899970699004815030544027790316454247823068492936918621580578463111596668713013015618568987237235288509264861249497715421833420428568606014682472077143585487415565706967765372022648544701585880162075847492265722600208558446652145839889394437092659180031138824646815708263010059485870400318648034219489727829064104507263688131373985525611732204024509122770022694112757362728049573810896750401836986836845072579936472906076299694138047565482372899718032680247442062926912485905218100445984215059112024944134172853147810580360337107730918286931471017111168391658172688941975871658215212822951848847208969463386289156288276595263514054226765323969461751129160240871551013515045538128756005263146801712740265396947024030051749531886292563138518816347800156936917688185237868405228783762938921430065586956868596459515550164472450983689603688732311438941557665104088391429233811320605243362948531704991577175622854974143899918802176243096520656421182731672625753959471725593463723863226148274262220867115583959992652117625269891754098815934864008345708518147223181420407042650905653233339843645786579679651926729239987536661721598257886026336361782749599421940377775368142621773879919455139723127406689832998989538672882285637869774966251996658352577619893932284534473569479496295216889148549253890475582883452609652409654288939453864662574492755638196441031697983306185201937938494005715633372054806854057586799967012137223947582142630658513221740883238294728761739364746783743196000159218880734785761725221186749042497736692920731109636972160893370866115673458533483329525467585164471075784860246360083444 |
|||
Integer Square Root of 2, (actually 2 * 10 ^ 4008, nth root method): |
|||
1414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641572735013846230912297024924836055850737212644121497099935831413222665927505592755799950501152782060571470109559971605970274534596862014728517418640889198609552329230484308714321450839762603627995251407989687253396546331808829640620615258352395054745750287759961729835575220337531857011354374603408498847160386899970699004815030544027790316454247823068492936918621580578463111596668713013015618568987237235288509264861249497715421833420428568606014682472077143585487415565706967765372022648544701585880162075847492265722600208558446652145839889394437092659180031138824646815708263010059485870400318648034219489727829064104507263688131373985525611732204024509122770022694112757362728049573810896750401836986836845072579936472906076299694138047565482372899718032680247442062926912485905218100445984215059112024944134172853147810580360337107730918286931471017111168391658172688941975871658215212822951848847208969463386289156288276595263514054226765323969461751129160240871551013515045538128756005263146801712740265396947024030051749531886292563138518816347800156936917688185237868405228783762938921430065586956868596459515550164472450983689603688732311438941557665104088391429233811320605243362948531704991577175622854974143899918802176243096520656421182731672625753959471725593463723863226148274262220867115583959992652117625269891754098815934864008345708518147223181420407042650905653233339843645786579679651926729239987536661721598257886026336361782749599421940377775368142621773879919455139723127406689832998989538672882285637869774966251996658352577619893932284534473569479496295216889148549253890475582883452609652409654288939453864662574492755638196441031697983306185201937938494005715633372054806854057586799967012137223947582142630658513221740883238294728761739364746783743196000159218880734785761725221186749042497736692920731109636972160893370866115673458533483329525467585164471075784860246360083445 |
|||
Integer Cube Root of 2, (actually 2 * 10 ^ 4008): |
|||
12599210498948731647672106072782283505702514647015079800819751121552996765139594837293965624362550941543102560356156652593990240406137372284591103042693552469606426166250009774745265654803068671854055186892458725167641993737096950983827831613991551293136953661839474634485765703031190958959847411059811629070535908164780114735213254847712978802422085820532579725266622026690056656081994715628176405060664826773572670419486207621442965694205079319172441480920448232840127470321964282081201905714188996459998317503801888689594202055922021154729973848802607363697417887792157984675099539630078260959624203483238660139857363433909737126527995991969968377913168168154428850279651529278107679714002040605674803938561251718357006907984996341976291474044834540269715476228513178020643878047649322579052898467085805286258130005429388560720609747223040631357234936458406575916916916727060124402896700001069081035313852902700415084232336239889386496782194149838027072957176812879001445746227147702348357151905506722084818485009287239209282646606717174247753709737030012742918094054425696592075036357570375189603707473993461014490145157635960471111973845299132965726258904860978856180138677383615773009865983660805975756012787121486856242684556411651558179353228015896291299445004012084254141601575258416298814230973582153060405772425383645325335660 |
|||
Integer 7th Root of 2, (actually 2 * 10 ^ 4004): |
|||
110408951367381233764950538762334472132532660078012416551453246414210632288038098071659828988630200514689715906557993125396921468043085579651064805838808196163919864392215583814551234397476339507890664685902921180613942144056283519219500774011043913929222338953790376732070503206390380988494445707084527925240582730725486467967183681658942999591682242459036160190261150569028438652686935172086652456800484770182207006433466758082204482396098451455092224240860882545144206285044829838431779372151867676523068340672781132725205233485925077681104722131036524174667129439905032</pre> |
|||
=={{header|Wren}}== |
|||
<syntaxhighlight lang="wren">import "./big" for BigInt |
|||
// only use for integers less than 2^53 |
|||
var intRoot = Fn.new { |x, n| |
|||
if (!(x is Num && x.isInteger && x >= 0)) { |
|||
Fiber.abort("First argument must be a non-negative integer.") |
|||
} |
|||
if (!(n is Num && x.isInteger && x >= 1)) { |
|||
Fiber.abort("Second argument must be a positive integer.") |
|||
} |
|||
return x.pow(1/n).floor |
|||
} |
|||
var a = [ [8, 3], [9, 3], [2e18, 2] ] |
|||
for (e in a) { |
|||
var x = e[0] |
|||
var n = e[1] |
|||
System.print("%(x) ^ (1/%(n)) = %(intRoot.call(x, n))") |
|||
} |
|||
System.print("\nFirst 2001 digits of the square root of 2:") |
|||
System.print((BigInt.two * BigInt.new(100).pow(2000)).isqrt)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
8 ^ (1/3) = 2 |
|||
9 ^ (1/3) = 2 |
|||
2e+18 ^ (1/2) = 1414213562 |
|||
First 2001 digits of the square root of 2: |
|||
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008 |
|||
</pre> |
|||
=={{header|XPL0}}== |
|||
<syntaxhighlight lang "XPL0">func real IRoot(X, N); |
|||
real X, N; |
|||
return Floor(Pow(X, 1./N)); |
|||
[Format(1, 0); |
|||
RlOut(0, IRoot(8., 3.)); CrLf(0); |
|||
RlOut(0, IRoot(9., 3.)); CrLf(0); |
|||
RlOut(0, IRoot(2e18, 2.)); CrLf(0); |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
2 |
|||
2 |
|||
1414213562 |
|||
</pre> |
|||
=={{header|Yabasic}}== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="yabasic">sub root(n, x) |
|||
for nr = floor(sqr(x)) to 1 step -1 |
|||
if (nr ^ n) <= x then return nr : fi |
|||
next nr |
|||
end sub |
|||
print root(3, 8) |
|||
print root(3, 9) |
|||
print root(4, 167) |
|||
end</syntaxhighlight> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
Uses GNU GMP library |
Uses GNU GMP library |
||
< |
<syntaxhighlight lang="zkl">var [const] BN=Import("zklBigNum"); |
||
fcn root(n,r){ |
fcn root(n,r){ |
||
f:='wrap(z){ (n/z.pow(r-1) + z*(r-1))/r or 1 }; //--> v or 1 |
f:='wrap(z){ (n/z.pow(r-1) + z*(r-1))/r or 1 }; //--> v or 1 |
||
Line 624: | Line 1,646: | ||
while(c!=d and c!=e){ c,d,e=d,e,f(e) } |
while(c!=d and c!=e){ c,d,e=d,e,f(e) } |
||
if(d<e) d else e |
if(d<e) d else e |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">a:=BN(100).pow(2000)*2; |
||
println("Does GMP agree: ",root(a,3)==a.root(3));</ |
println("Does GMP agree: ",root(a,3)==a.root(3));</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Latest revision as of 19:18, 20 April 2024
- Task
Create a program that computes an approximation of the principal Nth root of X as the largest integer less than or equal to R for which RN=X.
──where:
N is a positive integer. X is a non-negative integer. R (the root) is a non-negative real number.
No arbitrary limits should be placed on the magnitudes of the numbers involved.
Example: With N=3 and X=8 you would calculate the number 2 because
Example: With N=3 and X=9 you would again calculate the number 2 because 2 is the largest integer less than or equal to the root R.
Example: With N=2 and X=2×1002,000 you would calculate a large integer consisting of the first 2,001 digits (in order) of the square root of two.
11l
F iRoot(BigInt b, Int n)
I b < 2 {R b}
V n1 = n - 1
V n2 = BigInt(n)
V n3 = BigInt(n1)
V c = BigInt(1)
V d = (n3 + b) I/ n2
V e = (n3 * d + b I/ d ^ n1) I/ n2
L c != d & c != e
c = d
d = e
e = (n3 * e + b I/ e ^ n1) I/ n2
I d < e {R d}
R e
print(‘3rd root of 8 = ’iRoot(8, 3))
print(‘3rd root of 9 = ’iRoot(9, 3))
print(‘First 2001 digits of the square root of 2: ’iRoot(BigInt(100) ^ 2000 * 2, 2))
- Output:
3rd root of 8 = 2 3rd root of 9 = 2 First 2001 digits of the square root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
Ada
-- Find integer roots
-- J. Carter 2023 Jun
with Ada.Text_IO;
with System;
procedure Integer_Roots is
type Big is mod System.Max_Binary_Modulus;
function Root (N : in Positive; X : in Big) return Big With Pre => N > 1;
-- Returns the largest integer R such that R ** N <= X
-- Derived from Modula-2
function Root (N : in Positive; X : in Big) return Big is
N1 : constant Positive := N - 1;
N2 : constant Big := Big (N);
N3 : constant Big := N2 - 1;
C : Big := 1;
D : Big := (N3 + X) / N2;
E : Big := (N3 * D + X / D ** N1) / N2;
begin -- Root
if X <= 1 then
return X;
end if;
Converge : loop
exit Converge when C = D or C = E;
C := D;
D := E;
E := (N3 * D + X / E ** N1) / N2;
end loop Converge;
return (if D < E then D else E);
end Root;
Large : constant Big := 2 * 10 ** 38;
-- On 64-bit platforms, recent versions of GNAT provide 128-bit integers
-- 10 ** 38 is the largest power of 10 < 2 ** 128
begin -- Integer_Roots
Ada.Text_IO.Put_Line (Item => "Cube root of 8 =" & Root (3, 8)'Image);
Ada.Text_IO.Put_Line (Item => "Cube root of 9 =" & Root (3, 9)'Image);
Ada.Text_IO.Put_Line (Item => "Square root of" & Large'Image & " =" & Root (2, Large)'Image);
end Integer_Roots;
- Output:
Cube root of 8 = 2 Cube root of 9 = 2 Square root of 200000000000000000000000000000000000000 = 14142135623730950488
Arturo
iroot: function [b n][
if b<2 -> return b
n1: n-1
n2: n
n3: n1
c: 1
d: (n3+b)/n2
e: ((n3*d) + b/d^n1)/n2
while [and? c<>d c<>e][
c: d
d: e
e: ((n3*e) + b/e^n1)/n2
]
if d<e -> return d
return e
]
print ["3rd root of 8:" iroot 8 3]
print ["3rd root of 9:" iroot 9 3]
print ["First 2001 digits of the square root of 2:" iroot (100^2000)*2 2]
- Output:
3rd root of 8: 2 3rd root of 9: 2 First 2001 digits of the square root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
BASIC256
function root(n, x)
for nr = floor(sqr(x)) to 1 step -1
if (nr ^ n) <= x then return nr
next nr
end function
print root(3, 8)
print root(3, 9)
print root(4, 167)
print root(2, 2e18)
end
- Output:
Igual que la entrada de FreeBASIC.
C
#include <stdio.h>
#include <math.h>
typedef unsigned long long ulong;
ulong root(ulong base, ulong n) {
ulong n1, n2, n3, c, d, e;
if (base < 2) return base;
if (n == 0) return 1;
n1 = n - 1;
n2 = n;
n3 = n1;
c = 1;
d = (n3 + base) / n2;
e = (n3 * d + base / (ulong)powl(d, n1)) / n2;
while (c != d && c != e) {
c = d;
d = e;
e = (n3*e + base / (ulong)powl(e, n1)) / n2;
}
if (d < e) return d;
return e;
}
int main() {
ulong b = (ulong)2e18;
printf("3rd root of 8 = %lld\n", root(8, 3));
printf("3rd root of 9 = %lld\n", root(9, 3));
printf("2nd root of %lld = %lld\n", b, root(b, 2));
return 0;
}
- Output:
3rd root of 8 = 2 3rd root of 9 = 2 2nd root of 2000000000000000000 = 1414213562
C#
using System;
using System.Numerics;
namespace IntegerRoots {
class Program {
static BigInteger IRoot(BigInteger @base, int n) {
if (@base < 0 || n <= 0) {
throw new ArgumentException();
}
int n1 = n - 1;
BigInteger n2 = n;
BigInteger n3 = n1;
BigInteger c = 1;
BigInteger d = (n3 + @base) / n2;
BigInteger e = ((n3 * d) + (@base / BigInteger.Pow(d, n1))) / n2;
while (c != d && c != e) {
c = d;
d = e;
e = (n3 * e + @base / BigInteger.Pow(e, n1)) / n2;
}
if (d < e) {
return d;
}
return e;
}
static void Main(string[] args) {
Console.WriteLine("3rd integer root of 8 = {0}", IRoot(8, 3));
Console.WriteLine("3rd integer root of 9 = {0}", IRoot(9, 3));
BigInteger b = BigInteger.Pow(100, 2000) * 2;
Console.WriteLine("First 2001 digits of the sqaure root of 2: {0}", IRoot(b, 2));
}
}
}
- Output:
3rd integer root of 8 = 2 3rd integer root of 9 = 2 First 2001 digits of the sqaure root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
C++
#include <iostream>
#include <math.h>
unsigned long long root(unsigned long long base, unsigned int n) {
if (base < 2) return base;
if (n == 0) return 1;
unsigned int n1 = n - 1;
unsigned long long n2 = n;
unsigned long long n3 = n1;
unsigned long long c = 1;
auto d = (n3 + base) / n2;
auto e = (n3 * d + base / pow(d, n1)) / n2;
while (c != d && c != e) {
c = d;
d = e;
e = (n3*e + base / pow(e, n1)) / n2;
}
if (d < e) return d;
return e;
}
int main() {
using namespace std;
cout << "3rd root of 8 = " << root(8, 3) << endl;
cout << "3rd root of 9 = " << root(9, 3) << endl;
unsigned long long b = 2e18;
cout << "2nd root of " << b << " = " << root(b, 2) << endl;
return 0;
}
- Output:
3rd root of 8 = 2 3rd root of 9 = 2 2nd root of 2000000000000000000 = 1414213562
D
import std.bigint;
import std.stdio;
auto iRoot(BigInt b, int n) in {
assert(b >=0 && n > 0);
} body {
if (b < 2) return b;
auto n1 = n - 1;
auto n2 = BigInt(n);
auto n3 = BigInt(n1);
auto c = BigInt(1);
auto d = (n3 + b) / n2;
auto e = (n3 * d + b / d^^n1) / n2;
while (c != d && c != e) {
c = d;
d = e;
e = (n3 * e + b / e^^n1) / n2;
}
if (d < e) return d;
return e;
}
void main() {
auto b = BigInt(8);
writeln("3rd root of 8 = ", b.iRoot(3));
b = BigInt(9);
writeln("3rd root of 9 = ", b.iRoot(3));
b = BigInt(100)^^2000*2;
writeln("First 2001 digits of the square root of 2: ", b.iRoot(2));
}
- Output:
3rd root of 8 = 2 3rd root of 9 = 2 First 2001 digits of the square root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
Delphi
function IntRoot(Base: int64; N: cardinal): int64;
var N1: cardinal;
var N2,N3,C: int64;
var D,E: int64;
begin
if Base < 2 then Result:=Base
else if N = 0 then Result:=1
else
begin
N1:=N - 1;
N2:=N;
N3:=N1;
C:=1;
d:=round((N3 + Base) / N2);
e:=round((N3 * D + Base / Power(D, N1)) / N2);
while (C<>D) and (C<>E) do
begin
C:=D;
D:=E;
E:=Round((N3*E + Base / Power(E, N1)) / N2);
end;
if D < E then Result:=D
else Result:=E;
end;
end;
procedure ShowIntegerRoots(Memo: TMemo);
var Base: int64;
begin
Memo.Lines.Add('3rd integer root of 8 = '+IntToStr(IntRoot(8, 3)));
Memo.Lines.Add('3rd integer root of 9 = '+IntToStr(IntRoot(9, 3)));
Base:=2000000000000000000;
Memo.Lines.Add('sqaure root of 2 = '+IntToStr(IntRoot(Base, 2)));
end;
- Output:
3rd integer root of 8 = 2 3rd integer root of 9 = 2 sqaure root of 2 = 1414213562 Elapsed Time: 2.747 ms.
EasyLang
func root base n .
if base < 2
return base
.
if n = 0
return 1
.
n1 = n - 1
n2 = n
n3 = n1
c = 1
d = (n3 + base) div n2
e = (n3 * d + base div pow d n1) div n2
while c <> d and c <> e
c = d
d = e
e = (n3 * e + base div pow e n1) div n2
.
if (d < e)
return d
.
return e
.
print "3rd root of 8 = " & root 8 3
print "3rd root of 9 = " & root 9 3
b = 2e18
print "2nd root of " & b & " = " & root b 2
- Output:
3rd root of 8 = 2 3rd root of 9 = 2 2nd root of 2e+18 = 1414213562
Elixir
defmodule Integer_roots do
def root(_, b) when b<2, do: b
def root(a, b) do
a1 = a - 1
f = fn x -> (a1 * x + div(b, power(x, a1))) |> div(a) end
c = 1
d = f.(c)
e = f.(d)
until(c, d, e, f)
end
defp until(c, d, e, _) when c in [d, e], do: min(d, e)
defp until(_, d, e, f), do: until(d, e, f.(e), f)
defp power(_, 0), do: 1
defp power(n, m), do: Enum.reduce(1..m, 1, fn _,acc -> acc*n end)
def task do
IO.puts root(3,8)
IO.puts root(3,9)
IO.puts "First 2,001 digits of the square root of two:"
IO.puts root(2, 2 * power(100, 2000))
end
end
Integer_roots.task
- Output:
2 2 First 2,001 digits of the square root of two: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
F#
open System
let iroot (base_ : bigint) n =
if base_ < bigint.Zero || n <= 0 then
raise (ArgumentException "Bad parameter")
let n1 = n - 1
let n2 = bigint n
let n3 = bigint n1
let mutable c = bigint.One
let mutable d = (n3 + base_) / n2
let mutable e = ((n3 * d) + (base_ / bigint.Pow(d, n1))) / n2
while c <> d && c <> e do
c <- d
d <- e
e <- (n3 * e + base_ / bigint.Pow(e, n1)) / n2
if d < e then
d
else
e
[<EntryPoint>]
let main _ =
Console.WriteLine("3rd integer root of 8 = {0}", (iroot (bigint 8) 3))
Console.WriteLine("3rd integer root of 9 = {0}", (iroot (bigint 9) 3))
let b = bigint.Pow(bigint 100, 2000) * (bigint 2)
Console.WriteLine("First 2001 digits of the sqaure root of 2: {0}", (iroot b 2))
0 // return an integer exit code
- Output:
3rd integer root of 8 = 2 3rd integer root of 9 = 2 First 2001 digits of the sqaure root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
Factor
USING: io kernel locals math math.functions math.order
prettyprint sequences ;
:: (root) ( a b -- n )
a 1 - 1 :> ( a1 c! )
[| x | a1 x * b x a1 ^ /i + a /i ] :> f
c f call :> d!
d f call :> e!
[ c { d e } member? ] [
d c! e d! e f call e!
] until
d e min ;
: root ( a b -- n ) dup 2 < [ nip ] [ (root) ] if ;
"First 2,001 digits of the square root of two:" print
2 100 2000 ^ 2 * root .
- Output:
First 2,001 digits of the square root of two: 14142135623730950488016887242096980[...]32952546758516447107578486024636008
FreeBASIC
#define floor(x) ((x*2.0-0.5) Shr 1)
Function root(n As Uinteger, x As Uinteger) As Uinteger
For nr As Uinteger = floor(Sqr(x)) To 1 Step -1
If (nr ^ n) <= x Then Return nr
Next nr
End Function
Print root(3, 8)
Print root(3, 9)
Print root(4, 167)
Print root(2, 2e18)
Sleep
- Output:
2 2 3 1414213562
FutureBasic
local fn root( n as UInt64, x as UInt64 ) as double
double nr, result = 0
for nr = fn floor( sqr(x) ) to 1 step -1
if ( nr ^ n ) <= x then result = nr : exit fn
next
end fn = result
print @"3rd root of 8 = "; fn root( 3, 8 )
print @"3rd root of 9 = "; fn root( 3, 9 )
print @"4th root of 167 = "; fn root( 4, 167 )
print @"2nd root of 2e+018 = "; fn root( 2, 2e+018 )
HandleEvents
- Output:
3rd root of 8 = 2 3rd root of 9 = 2 4th root of 167 = 3 2nd root of 2e+018 = 1414213562
Go
int
package main
import "fmt"
func main() {
fmt.Println(root(3, 8))
fmt.Println(root(3, 9))
fmt.Println(root(2, 2e18))
}
func root(N, X int) int {
// adapted from https://en.wikipedia.org/wiki/Nth_root_algorithm
for r := 1; ; {
x := X
for i := 1; i < N; i++ {
x /= r
}
x -= r
// A small complication here is that Go performs truncated integer
// division but for negative values of x, Δr in the line below needs
// to be computed as the floor of x / N. The following % test and
// correction completes the floor division operation (for positive N.)
Δr := x / N
if x%N < 0 {
Δr--
}
if Δr == 0 {
return r
}
r += Δr
}
}
- Output:
2 2 1414213562
big.Int
package main
import (
"fmt"
"math/big"
)
func main() {
fmt.Println(root(3, "8"))
fmt.Println(root(3, "9"))
fmt.Println(root(2, "2000000000000000000"))
fmt.Println(root(2, "200000000000000000000000000000000000000000000000000"))
}
var one = big.NewInt(1)
func root(N int, X string) *big.Int {
var xx, x, Δr big.Int
xx.SetString(X, 10)
nn := big.NewInt(int64(N))
for r := big.NewInt(1); ; {
x.Set(&xx)
for i := 1; i < N; i++ {
x.Quo(&x, r)
}
// big.Quo performs Go-like truncated division and would allow direct
// translation of the int-based solution, but package big also provides
// Div which performs Euclidean rather than truncated division.
// This gives the desired result for negative x so the int-based
// correction is no longer needed and the code here can more directly
// follow the Wikipedia article.
Δr.Div(x.Sub(&x, r), nn)
if len(Δr.Bits()) == 0 {
return r
}
r.Add(r, &Δr)
}
}
- Output:
2 2 1414213562 14142135623730950488016887
Haskell
root :: Integer -> Integer -> Integer
root a b = findAns $ iterate (\x -> (a1 * x + b `div` (x ^ a1)) `div` a) 1
where
a1 = a - 1
findAns (x:xs@(y:z:_))
| x == y || x == z = min y z
| otherwise = findAns xs
main :: IO ()
main = do
print $ root 3 8
print $ root 3 9
print $ root 2 (2 * 100 ^ 2000) -- first 2001 digits of the square root of 2
Or equivalently, in terms of an applicative expression:
integerRoot :: Integer -> Integer -> Integer
integerRoot n x =
go $ iterate ((`div` n) . ((+) . (pn *) <*> (x `div`) . (^ pn))) 1
where
pn = pred n
go (x:xs@(y:z:_))
| x == y || x == z = min y z
| otherwise = go xs
main :: IO ()
main = mapM_ (print . uncurry integerRoot) [(3, 8), (3, 9), (2, 2 * 100 ^ 2000)]
- Output:
2 2 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
J
<.@%:
satisfies this task. Left argument is the task's N, right argument is the task's X:
Note: If you are looking for a decimal expansion of an integer root, one must select the proper number of digits for N, that is, 2000, 2001, 2002, etc..., otherwise the result will be the digits of the nth root of 20, 2000, etc...
For example, If you use "3 <.@%: (2*10x^2*2000)" instead of "3 <.@%: (2*10x^2*2001)", you will get an output starting with "271441761659490657151808946...", which are the first digits of the cube root of 20, not 2. This constraint is independent of the task requirements, except in an illustrative sense, so will not be developed further, here.
9!:37]0 4096 0 222 NB. set display truncation sufficiently high for our results
2 <.@%: (2*10x^2*2000)
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
3 <.@%: (2*10x^2*2001)
125992104989487316476721060727822835057025146470150798008197511215529967651395948372939656243625509415431025603561566525939902404061373722845911030426935524696064261662500097747452656548030686718540551868924587251676419937370969509838278316139915512931369536618394746344857657030311909589598474110598116290705359081647801147352132548477129788024220858205325797252666220266900566560819947156281764050606648267735726704194862076214429656942050793191724414809204482328401274703219642820812019057141889964599983175038018886895942020559220211547299738488026073636974178877921579846750995396300782609596242034832386601398573634339097371265279959919699683779131681681544288502796515292781076797140020406056748039385612517183570069079849963419762914740448345402697154762285131780206438780476493225790528984670858052862581300054293885607206097472230406313572349364584065759169169167270601244028967000010690810353138529027004150842323362398893864967821941498380270729571768128790014457462271477023483571519055067220848184850092872392092826466067171742477537097370300127429180940544256965920750363575703751896037074739934610144901451576359604711119738452991329657262589048609788561801386773836157730098659836608059757560127871214868562426845564116515581793532280158962912994450040120842541416015752584162988142309735821530604057724253836453253356
5 <.@%: (2*10x^2*2000)
114869835499703500679862694677792758944385088909779750551371111849360320625351305681147311301150847391457571782825280872990018972855371267615994917020637676959403854539263226492033301322122190625130645468320078386350285806907949085127708283982797043969640382563667945344431106523789654147255972578315704103326302050272017414235255993151553782375173884359786924137881735354092890268530342009402133755822717151679559278360263800840317501093689917495888199116488588871447782240220513546797235647742625493141141704109917646404017146978939243424915943739448283626010758721504375406023613552985026793701507511351368254645700768390780390334017990233124030682358360249760098999315658413563173197024899154512108923313999675829872581317721346549115423634135836394159076400636688679216398175376716152621781331348
7 <.@%: (2*10x^2*2002)
1104089513673812337649505387623344721325326600780124165514532464142106322880380980716598289886302005146897159065579931253969214680430855796510648058388081961639198643922155838145512343974763395078906646859029211806139421440562835192195007740110439139292223389537903767320705032063903809884944457070845279252405827307254864679671836816589429995916822424590361601902611505690284386526869351720866524568004847701822070064334667580822044823960984514550922242408608825451442062850448298384317793721518676765230683406727811327252052334859250776811047221310365241746671294399050316
Java
import java.math.BigInteger;
public class IntegerRoots {
private static BigInteger iRoot(BigInteger base, int n) {
if (base.compareTo(BigInteger.ZERO) < 0 || n <= 0) {
throw new IllegalArgumentException();
}
int n1 = n - 1;
BigInteger n2 = BigInteger.valueOf(n);
BigInteger n3 = BigInteger.valueOf(n1);
BigInteger c = BigInteger.ONE;
BigInteger d = n3.add(base).divide(n2);
BigInteger e = n3.multiply(d).add(base.divide(d.pow(n1))).divide(n2);
while (!c.equals(d) && !c.equals(e)) {
c = d;
d = e;
e = n3.multiply(e).add(base.divide(e.pow(n1))).divide(n2);
}
if (d.compareTo(e) < 0) {
return d;
}
return e;
}
public static void main(String[] args) {
BigInteger b = BigInteger.valueOf(8);
System.out.print("3rd integer root of 8 = ");
System.out.println(iRoot(b, 3));
b = BigInteger.valueOf(9);
System.out.print("3rd integer root of 9 = ");
System.out.println(iRoot(b, 3));
b = BigInteger.valueOf(100).pow(2000).multiply(BigInteger.valueOf(2));
System.out.print("First 2001 digits of the square root of 2: ");
System.out.println(iRoot(b, 2));
}
}
- Output:
3rd integer root of 8 = 2 3rd integer root of 9 = 2 First 2001 digits of the square root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
jq
Adapted from Julia
Works with gojq, the Go implementation of jq
# To take advantage of gojq's arbitrary-precision integer arithmetic:
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
# If $j is 0, then an error condition is raised;
# otherwise, assuming infinite-precision integer arithmetic,
# if the input and $j are integers, then the result will be an integer.
def idivide($j):
(. - (. % $j)) / $j ;
def iroot(a; b):
if b < 2 then b
else (a-1) as $a1
| {c: 1,
d: (($a1 + (b | idivide(1))) | idivide(a)) }
| .d as $d
| .e = ($a1 * $d + (b |idivide($d | power($a1))) | idivide(a))
| until( .d == .c or .c == .e;
.c = .d
| .d = .e
| .e as $e
| .e = ($a1 * .e + (b | idivide(($e | power($a1)))) | idivide(a)) )
| [.d, .e] | min
end ;
# The task:
"First 2,001 digits of the square root of two:",
iroot(2; 2 * (100 | power(2000)))
- Output:
Exactly as for Julia.
Julia
function iroot(a, b)
b < 2 && return b
a1, c = a - 1, 1
d = (a1 * c + b ÷ c^a1) ÷ a
e = (a1 * d + b ÷ d^a1) ÷ a
while d ≠ c ≠ e
c, d, e = d, e, (a1 * e + b ÷ (e ^ a1)) ÷ a
end
min(d, e)
end
println("First 2,001 digits of the square root of two:\n", iroot(2, 2 * big(100) ^ 2000))
- Output:
First 2,001 digits of the square root of two: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
Kotlin
// version 1.1.2
import java.math.BigInteger
val bigZero = BigInteger.ZERO
val bigOne = BigInteger.ONE
val bigTwo = BigInteger.valueOf(2L)
fun BigInteger.iRoot(n: Int): BigInteger {
require(this >= bigZero && n > 0)
if (this < bigTwo) return this
val n1 = n - 1
val n2 = BigInteger.valueOf(n.toLong())
val n3 = BigInteger.valueOf(n1.toLong())
var c = bigOne
var d = (n3 + this) / n2
var e = (n3 * d + this / d.pow(n1)) / n2
while (c != d && c != e) {
c = d
d = e
e = (n3 * e + this / e.pow(n1)) / n2
}
return if (d < e) d else e
}
fun main(args: Array<String>) {
var b: BigInteger
b = BigInteger.valueOf(8L)
println("3rd integer root of 8 = ${b.iRoot(3)}\n")
b = BigInteger.valueOf(9L)
println("3rd integer root of 9 = ${b.iRoot(3)}\n")
b = BigInteger.valueOf(100L).pow(2000) * bigTwo
println("First 2001 digits of the square root of 2:")
println(b.iRoot(2))
}
- Output:
3rd integer root of 8 = 2 3rd integer root of 9 = 2 First 2001 digits of the square root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
Lua
function root(base, n)
if base < 2 then return base end
if n == 0 then return 1 end
local n1 = n - 1
local n2 = n
local n3 = n1
local c = 1
local d = math.floor((n3 + base) / n2)
local e = math.floor((n3 * d + base / math.pow(d, n1)) / n2)
while c ~= d and c ~= e do
c = d
d = e
e = math.floor((n3 * e + base / math.pow(e, n1)) / n2)
end
if d < e then return d end
return e
end
-- main
local b = 2e18
print("3rd root of 8 = " .. root(8, 3))
print("3rd root of 9 = " .. root(9, 3))
print("2nd root of " .. b .. " = " .. root(b, 2))
- Output:
3rd root of 8 = 2 3rd root of 9 = 2 2nd root of 2e+018 = 1414213562
Modula-2
MODULE IntegerRoot;
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,ReadChar;
PROCEDURE pow(b : LONGCARD; p : CARDINAL) : LONGCARD;
VAR
result : LONGCARD;
BEGIN
result := 1;
WHILE p > 0 DO
IF p MOD 2 = 1 THEN
DEC(p);
result := result * b;
END;
p := p / 2;
b := b * b
END;
RETURN result
END pow;
PROCEDURE root(base : LONGCARD; n : CARDINAL) : LONGCARD;
VAR
n1,n2,n3,c,d,e : LONGCARD;
BEGIN
IF base < 2 THEN RETURN base END;
IF n = 0 THEN RETURN 1 END;
n1 := n - 1;
n2 := n;
n3 := n1;
c := 1;
d := (n3 + base) / n2;
e := (n3 * d + base / pow(d, n1)) / n2;
WHILE (c # d) AND (c # e) DO
c := d;
d := e;
e := (n3 * e + base / pow(e, n1)) / n2
END;
IF d < e THEN RETURN d END;
RETURN e
END root;
(* main *)
VAR
buf : ARRAY[0..63] OF CHAR;
b : LONGCARD;
BEGIN
FormatString("3rd root of 8 = %u\n", buf, root(8, 3));
WriteString(buf);
FormatString("3rd root of 9 = %u\n", buf, root(9, 3));
WriteString(buf);
b := 2000000000000000000;
FormatString("2nd root of %u = %u\n", buf, b, root(b, 2));
WriteString(buf);
ReadChar
END IntegerRoot.
Nim
import bignum
proc root(x: Int; n: int): Int =
if x < 2: return x
let n1 = (n - 1).culong
var c = newInt(1)
var d = (n1 + x) div n
var e = (n1 * d + x div d.pow(n1)) div n
while c != d and c != e:
c = d
d = e
e = (n1 * e + x div e.pow(n1)) div n
result = if d < e: d else: e
var x: Int
x = newInt(8)
echo "3rd integer root of 8 = ", x.root(3)
x = newInt(9)
echo "3rd integer root of 9 = ", x.root(3)
x = newInt(100).pow(2000) * newInt(2)
echo "First 2001 digits of the square root of 2:"
let s = $x.root(2)
for i in countup(0, s.high, 87): echo s.substr(i, i + 86)
- Output:
3rd integer root of 8 = 2 3rd integer root of 9 = 2 First 2001 digits of the square root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038 753432764157273501384623091229702492483605585073721264412149709993583141322266592750559 275579995050115278206057147010955997160597027453459686201472851741864088919860955232923 048430871432145083976260362799525140798968725339654633180882964062061525835239505474575 028775996172983557522033753185701135437460340849884716038689997069900481503054402779031 645424782306849293691862158057846311159666871301301561856898723723528850926486124949771 542183342042856860601468247207714358548741556570696776537202264854470158588016207584749 226572260020855844665214583988939443709265918003113882464681570826301005948587040031864 803421948972782906410450726368813137398552561173220402450912277002269411275736272804957 381089675040183698683684507257993647290607629969413804756548237289971803268024744206292 691248590521810044598421505911202494413417285314781058036033710773091828693147101711116 839165817268894197587165821521282295184884720896946338628915628827659526351405422676532 396946175112916024087155101351504553812875600526314680171274026539694702403005174953188 629256313851881634780015693691768818523786840522878376293892143006558695686859645951555 016447245098368960368873231143894155766510408839142923381132060524336294853170499157717 562285497414389991880217624309652065642118273167262575395947172559346372386322614827426 222086711558395999265211762526989175409881593486400834570851814722318142040704265090565 323333984364578657967965192672923998753666172159825788602633636178274959942194037777536 814262177387991945513972312740668983299898953867288228563786977496625199665835257761989 393228453447356947949629521688914854925389047558288345260965240965428893945386466257449 275563819644103169798330618520193793849400571563337205480685405758679996701213722394758 214263065851322174088323829472876173936474678374319600015921888073478576172522118674904 249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
PARI/GP
sqrtnint(8,3)
sqrtnint(9,3)
sqrtnint(2*100^2000,2)
- Output:
%1 = 2 %2 = 2 %3 = 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
Perl
use bigint;
sub integer_root {
our($a,$b) = @_;
our $a1 = $a - 1;
my $c = 1;
my $d = f($c);
my $e = f($d);
($c, $d, $e) = ($d, $e, f($e)) until $c==$d || $c==$e;
return $d < $e ? $d : $e;
sub f { ($a1*$_[0]+$b/$_[0]**$a1)/$a }
}
print integer_root( 3, 8), "\n";
print integer_root( 3, 9), "\n";
print integer_root( 2, 2 * 100 ** 2000), "\n";
- Output:
2 2 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
Using a module
If using bigints, we can do this directly, which will be much faster than the method above:
use bigint;
print 8->babs->broot(3),"\n";
print 9->babs->broot(3),"\n";
print +(2*100**2000)->babs->broot(2),"\n";
The babs
calls are only necessary if the input might be non-negative.
Even faster, using a module:
use bigint;
use ntheory "rootint";
print rootint(8,3),"\n";
print rootint(9,3),"\n";
print rootint(2*100**2000,2),"\n";
Both generate the same output as above.
Phix
with javascript_semantics include mpfr.e function integer_root(integer n, object a) -- a must be integer or string -- (were a an mpz you would have to invoke mpz_init_set(), not mpz_init(), -- or better yet pass a as the second parameter of mpz_root() instead.) mpz res = mpz_init(a) mpz_nthroot(res,res,n) return mpz_get_str(res) end function atom t0 = time() printf(1,"3rd root of 8 = %s\n", {integer_root(3,8)}) printf(1,"3rd root of 9 = %s\n", {integer_root(3,9)}) string s = integer_root(2,"2"&repeat('0',4000)) printf(1,"First digits of the square root of 2: %s\n", {shorten(s)}) s = integer_root(3,"2"&repeat('0',6000)) printf(1,"First digits of the cube root of 2: %s\n", {shorten(s)}) ?elapsed(time()-t0)
- Output:
3rd root of 8 = 2 3rd root of 9 = 2 First digits of the square root of 2: 14142135623730950488...47107578486024636008 (2,001 digits) First digits of the cube root of 2: 12599210498948731647...22546828353183047061 (2,001 digits) "0.4s"
While this finishes near-instantly on the desktop, it takes about 25s under pwa/p2js.
Python
def root(a, b):
if b < 2:
return b
a1 = a - 1
c = 1
d = (a1 * c + b // (c ** a1)) // a
e = (a1 * d + b // (d ** a1)) // a
while c not in (d, e):
c, d, e = d, e, (a1 * e + b // (e ** a1)) // a
return min(d, e)
print("First 2,001 digits of the square root of two:\n{}".format(
root(2, 2 * 100 ** 2000)
))
- Output:
First 2,001 digits of the square root of two: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
Quackery
[ stack ] is a-1 ( --> s )
[ stack ] is b ( --> s )
[ a-1 share tuck 2dup *
unrot **
b share swap / +
swap 1+ / ] is nextapprox ( n --> n )
[ over 2 < iff drop done
1 - a-1 put
b put
1
2 times [ dup nextapprox ]
[ dip [ 2dup = rot ]
tuck = rot or not while
dup nextapprox again ]
min
b release a-1 release ] is root ( n n --> n )
say "3rd root of 8 = " 8 3 root echo cr
say "3rd root of 9 = " 9 3 root echo cr
say "First 2001 digits of the square root of 2: "
2 100 2000 ** * 2 root echo cr
- Output:
3rd root of 8 = 2 3rd root of 9 = 2 First 2001 digits of the square root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
Racket
See #Scheme, there’s very little can be done to improve it.
Raku
(formerly Perl 6)
sub integer_root ( Int $p where * >= 2, Int $n --> Int ) {
my Int $d = $p - 1;
(
10**($n.chars div $p),
{ ( $d * $^x + $n div ($x ** $d) ) div $p } ...
-> $a, $, $c { $a == $c }
).tail(2).min;
}
say integer_root( 2, 2 * 100 ** 2000 );
- Output:
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
REXX
No error checking is performed to ensure the root is a non-zero integer.
This version incorporates some optimization when computing square roots (because M is
unity, there is no need to
multiply the guess [G] by unity, and no need to compute the guess to the 1st power, bypassing some trivial arithmetic).
integer result only
/*REXX program calculates the Nth root of a number to a specified number of decimal digs*/
parse arg num root digs . /*obtain the optional arguments from CL*/
if num=='' | num=="," then num= 2 /*Not specified? Then use the default.*/
if root=='' | root=="," then root= 2 /* " " " " " " */
if digs=='' | digs=="," then digs=2001 /* " " " " " " */
numeric digits digs /*utilize this number of decimal digits*/
say 'number=' num /*display the number that will be used.*/
say ' root=' root /* " " root " " " " */
say 'digits=' digs /* " dec. digits " " " " */
say /* " a blank line. */
say 'result:'; say rootI(num, root, digs) /* " what it is; display the root.*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
rootI: procedure; parse arg x,root,p /*obtain the numbers, Y is the root #.*/
numeric digits p*root+length(x) /*double the number of digits + guard.*/
if x<2 then return x /*B is one or zero? Return that value.*/
z=x*(10**root)**p /*calculate the number with appended 0s*/
m=root - 1 /*utilize a diminished (by one) power. */
g=(1 + z) % root /*take a stab at the first root guess. */
old=. /* [↓] When M=1, a fast path for sqrt.*/
if m==1 then do until old==g; old=g; g=(g + z % g ) % root; end
else do until old==g; old=g; g=(g*m + z % (g**m) ) % root; end
return left(g,p) /*return the Nth root of Z to invoker.*/
output when the defaults are being used:
number= 2 root= 2 digits= 2001 result: 14142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927557999505011527820605714 70109559971605970274534596862014728517418640889198609552329230484308714321450839762603627995251407989687253396546331808829640620615258352395054745750287759961729835575220337531857011354374603408498847 16038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016 20758474922657226002085584466521458398893944370926591800311388246468157082630100594858704003186480342194897278290641045072636881313739855256117322040245091227700226941127573627280495738108967504018369 86836845072579936472906076299694138047565482372899718032680247442062926912485905218100445984215059112024944134172853147810580360337107730918286931471017111168391658172688941975871658215212822951848847 20896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558 69568685964595155501644724509836896036887323114389415576651040883914292338113206052433629485317049915771756228549741438999188021762430965206564211827316726257539594717255934637238632261482742622208671 15583959992652117625269891754098815934864008345708518147223181420407042650905653233339843645786579679651926729239987536661721598257886026336361782749599421940377775368142621773879919455139723127406689 83299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685 40575867999670121372239475821426306585132217408832382947287617393647467837431960001592188807347857617252211867490424977366929207311096369721608933708661156734585334833295254675851644710757848602463600 8
true results
Negative and complex roots are supported. The expressed root may have a decimal point.
/*REXX program calculates the Nth root of a number to a specified number of decimal digs*/
parse arg num root digs . /*obtain the optional arguments from CL*/
if num=='' | num=="," then num= 2 /*Not specified? Then use the default.*/
if root=='' | root=="," then root= 2 /* " " " " " " */
if digs=='' | digs=="," then digs=2001 /* " " " " " " */
numeric digits digs /*utilize this number of decimal digits*/
say 'number=' num /*display the number that will be used.*/
say ' root=' root /* " " root " " " " */
say 'digits=' digs /* " dec. digits " " " " */
say /* " a blank line. */
say 'result:'; say iRoot(num, root) /* " what it is; display the root.*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
iRoot: procedure; parse arg x 1 ox, y 1 oy /*obtain the numbers, Y is the root #.*/
i=; x=abs(x); y=abs(y) /*use the absolute values of X and Y. */
if ox<0 & oy//2==0 then do; i='i'; ox=x; end /*if the results will be imaginary ··· */
od=digits() /*the current number of decimal digits.*/
a=od+9 /*bump the decimal digits by nine. */
numeric form /*number will be in exponential form.*/
parse value format(x,2,1,,0) 'E0' with ? 'E' _ . /*obtain exponent so we can do division*/
g=(?/y'E'_ % y) + (x>1) /*this is a best first guess of a root.*/
m=y-1 /*define a (fast) variable for later. */
d=5 /*start with only five decimal digits. */
do until d==a /*keep computing 'til we're at max digs*/
d=min(d+d,a); dm=d-2 /*bump number of (growing) decimal digs*/
numeric digits d /*increase the number of decimal digits*/
o=0 /*set the old value to zero (1st time).*/
do until o=g; o=g /*keep computing as long as G changes.*/
g=format((m*g**y+x)/y/g**m,,dm) /*compute the Yth root of X. */
end /*until o=g*/
end /*until d==a*/
_=g*sign(ox) /*change the sign of the result, maybe.*/
numeric digits od /*set numeric digits to the original.*/
if oy<0 then return (1/_)i /*Is the root negative? Use reciprocal*/
return (_/1)i /*return the Yth root of X to invoker.*/
output when the defaults are being used:
number= 2 root= 2 digits= 2001 result: 1.414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641572735013846230912297024924836055850737212644121497099935831413222665927505592755799950501152782060571 47010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884 71603868999706990048150305440277903164542478230684929369186215805784631115966687130130156185689872372352885092648612494977154218334204285686060146824720771435854874155657069677653720226485447015858801 62075847492265722600208558446652145839889394437092659180031138824646815708263010059485870400318648034219489727829064104507263688131373985525611732204024509122770022694112757362728049573810896750401836 98683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884 72089694633862891562882765952635140542267653239694617511291602408715510135150455381287560052631468017127402653969470240300517495318862925631385188163478001569369176881852378684052287837629389214300655 86956868596459515550164472450983689603688732311438941557665104088391429233811320605243362948531704991577175622854974143899918802176243096520656421182731672625753959471725593463723863226148274262220867 11558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668 98329989895386728822856378697749662519966583525776198939322845344735694794962952168891485492538904755828834526096524096542889394538646625744927556381964410316979833061852019379384940057156333720548068 54057586799967012137223947582142630658513221740883238294728761739364746783743196000159218880734785761725221186749042497736692920731109636972160893370866115673458533483329525467585164471075784860246360 08
output when using the input of: -81
number= -81 root= 2 digits= 2001 result: 9i
output when using the input of: 4 -2
number= 4 root= -2 digits= 2001 result: 0.5
Ring
# Project : Integer roots
see root(3, 8)
see root(3, 9)
see root(4, 167)
func root(n, x)
for nr = floor(sqrt(x)) to 1 step -1
if pow(nr, n) <= x
see nr + nl
exit
ok
next
Output:
2 2 3
RPL
« DUP 1 - → x n n1 « IF x 2 < THEN x ELSE « n1 OVER * x 3 PICK n1 ^ / IP + n / IP » → func « 1 func EVAL func EVAL WHILE ROT DUP2 ≠ SWAP 4 PICK ≠ AND REPEAT func EVAL END MIN » END » » 'IROOT' STO @ ( x n → root ) with root^n ≤ x
Ruby
def root(a,b)
return b if b<2
a1, c = a-1, 1
f = -> x {(a1*x+b/(x**a1))/a} # a lambda with argument x
d = f[c]
e = f[d]
c, d, e = d, e, f[e] until [d,e].include?(c)
[d,e].min
end
puts "First 2,001 digits of the square root of two:"
puts root(2, 2*100**2000)
- Output:
First 2,001 digits of the square root of two: 14142135623730950488016887242096(...)46758516447107578486024636008
Rust
The rug crate provides the functionality required for this task.
// [dependencies]
// rug = "1.9"
fn shorten(s: &str, digits: usize) -> String {
if s.len() <= digits + 3 {
return String::from(s);
}
format!("{}...{}", &s[0..digits/2], &s[s.len()-digits/2..])
}
fn main() {
use rug::{ops::Pow, Integer};
let x = Integer::from(8);
let r = Integer::from(x.root_ref(3));
println!("Integer cube root of {}: {}", x, r);
let x = Integer::from(9);
let r = Integer::from(x.root_ref(3));
println!("Integer cube root of {}: {}", x, r);
let mut x = Integer::from(100).pow(2000);
x *= 2;
let s = Integer::from(x.root(2)).to_string();
println!("First {} digits of the square root of 2:\n{}", s.len(), shorten(&s, 70));
let mut x = Integer::from(100).pow(3000);
x *= 2;
let s = Integer::from(x.root(3)).to_string();
println!("First {} digits of the cube root of 2:\n{}", s.len(), shorten(&s, 70));
}
- Output:
Integer cube root of 8: 2 Integer cube root of 9: 2 First 2001 digits of the square root of 2: 14142135623730950488016887242096980...32952546758516447107578486024636008 First 2001 digits of the cube root of 2: 12599210498948731647672106072782283...28546452083111122546828353183047061
Scala
Functional solution, tail recursive, no immutables
import scala.annotation.tailrec
object IntegerRoots extends App {
println("3rd integer root of 8 = " + iRoot(8, 3))
println("3rd integer root of 9 = " + iRoot(9, 3))
val result = iRoot(BigInt(100).pow(2000) * BigInt(2), 2)
println(s"All ${result.toString.length} digits of the square root of 2: \n$result")
private def iRoot(base: BigInt, degree: Int): BigInt = {
require(base >= 0 && degree > 0,
"Base has to be non-negative while the degree must be positive.")
val (n1, n2) = (degree - 1, BigInt(degree))
val d = (n1 + base) / n2
@tailrec
def loop(c: BigInt, d: BigInt, e: BigInt): BigInt = {
if (c == d || c == e) if (d < e) d else e
else loop(d, e, (n1 * e + (base / e.pow(n1))) / n2)
}
loop(1, (n1 + base) / n2, (n1 * d + (base / d.pow(n1))) / n2)
}
}
- Output:
See it running in your browser by ScalaFiddle (JavaScript, non JVM) or by Scastie (JVM).
Scheme
(define (root a b)
(define // quotient)
(define (y a a1 b c d e)
(if (or (= c d) (= c e))
(min d e)
(y a a1 b d e (// (+ (* a1 e) (// b (expt e a1))) a))))
(if (< b 2)
b
(let* ((a1 (- a 1))
(c 1)
(d (// (+ (* a1 c) (// b (expt c a1))) a))
(e (// (+ (* a1 d) (// b (expt d a1))) a)))
(y a a1 b c d e))))
(display "First 2,001 digits of the cube root of two:\n")
(display (root 3 (* 2 (expt 1000 2000))))
- Output:
First 2,001 digits of the cube root of two: 125992104989487316476721060727822835057025146470150798008197511215529967651395948372939656243625509415431025603561566525939902404061373722845911030426935524696064261662500097747452656548030686718540551868924587251676419937370969509838278316139915512931369536618394746344857657030311909589598474110598116290705359081647801147352132548477129788024220858205325797252666220266900566560819947156281764050606648267735726704194862076214429656942050793191724414809204482328401274703219642820812019057141889964599983175038018886895942020559220211547299738488026073636974178877921579846750995396300782609596242034832386601398573634339097371265279959919699683779131681681544288502796515292781076797140020406056748039385612517183570069079849963419762914740448345402697154762285131780206438780476493225790528984670858052862581300054293885607206097472230406313572349364584065759169169167270601244028967000010690810353138529027004150842323362398893864967821941498380270729571768128790014457462271477023483571519055067220848184850092872392092826466067171742477537097370300127429180940544256965920750363575703751896037074739934610144901451576359604711119738452991329657262589048609788561801386773836157730098659836608059757560127871214868562426845564116515581793532280158962912994450040120842541416015752584162988142309735821530604057724253836453253356595511725228557956227724036656284687590154306675351908548451181817520429124123378096317252135754114181146612736604578303605744026513096070968164006888185657231009008428452608641405950336900307918699355691335183428569382625543135589735445023330285314932245513412195545782119650083395771426685063328419619686512109255789558850899686190154670043896878665545309854505763765036008943306510356935777537249548436821370317162162183495809356208726009626785183418345652239744540004476021778894208183802786665306532663261864116007400747475473558527701689502063754132232329694243701742343491617690600723853902227681129777413872079823430391031628546452083111122546828353183047061
Sidef
func root(a, b) {
b < 2 && return(b)
var (a1, c) = (a-1, 1)
var f = {|x| (a1*x + b//(x**a1)) // a }
var d = f(c)
var e = f(d)
while (c !~ [d, e]) {
(c, d, e) = (d, e, f(e))
}
[d, e].min
}
say "First 2,001 digits of the square root of two:"
say root(2, 2 * 100**2000)
- Output:
First 2,001 digits of the square root of two: 14142135623730950488016887242096980[...]32952546758516447107578486024636008
Tcl
Tcl is not made for number crunching. The execution is quite slow compared to compiled languages.
On the other hand, everything is very straightforward, no libraries necessary.
proc root {this n} {
if {$this < 2} {return $this}
set n1 [expr $n - 1]
set n2 $n
set n3 $n1
set c 1
set d [expr ($n3 + $this) / $n2]
set e [expr ($n3 * $d + $this / ($d ** $n1)) / $n2]
while {$c != $d && $c != $e} {
set c $d
set d $e
set e [expr ($n3 * $e + $this / ($e ** $n1)) / $n2]
}
return [expr min($d, $e)]
}
puts [root 8 3]
puts [root 9 3]
puts [root [expr 2* (100**2000)] 2]
- Output:
2 2 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
Visual Basic .NET
From the method described on the Wikipedia page. Included is an Integer Square Root function to compare results to the Integer Nth Square root function. One must choose the exponents carefully, otherwise one will obtain the digits of the nth root of 20, 200, 2000, etc..., instead of 2. For example, 4008 was chosen because it works for both n = 2 and n = 3, whereas 4004 was chosen for n = 7
Imports System
Imports System.Numerics
Imports Microsoft.VisualBasic.Strings
Public Module Module1
Public Function IntSqRoot(v As BigInteger) As BigInteger
Dim digs As Integer = Math.Max(0, v.ToString().Length / 2 - 1)
IntSqRoot = BigInteger.Parse("3" & StrDup(digs, "0"))
Dim term As BigInteger
Do
term = v / IntSqRoot
If Math.Abs(CDbl(term - IntSqRoot)) < 2 Then Exit Do
IntSqRoot = (IntSqRoot + term) / 2
Loop Until False
End Function
Public Function IntNthRoot(n As Integer, v As BigInteger) As BigInteger
Dim digs As Integer = Math.Max(0, v.ToString().Length / n - 1)
IntNthRoot = BigInteger.Parse(If(digs > 1, 3, 2).ToString() & StrDup(digs, "0"))
Dim va As BigInteger, dr As BigInteger
Do
va = v : For i As Integer = 2 To n : va /= IntNthRoot : Next
va -= IntNthRoot
dr = va / n : If dr = 0 Then Exit Do
IntNthRoot += dr
Loop Until False
End Function
Public Sub Main()
Dim b As BigInteger = BigInteger.Parse("2" & StrDup(4008, "0"))
Console.WriteLine("Integer Cube Root of 8:")
Console.WriteLine(IntNthRoot(3, 8).ToString()) ' given example
Console.WriteLine("Integer Cube Root of 9:")
Console.WriteLine(IntNthRoot(3, 9).ToString()) ' given example
Console.WriteLine("Integer Square Root of 2, (actually 2 * 10 ^ 4008, square root method):")
Console.WriteLine(IntSqRoot(b).ToString()) ' reality check
Console.WriteLine("Integer Square Root of 2, (actually 2 * 10 ^ 4008, nth root method):")
Console.WriteLine(IntNthRoot(2, b).ToString()) ' given example
Console.WriteLine("Integer Cube Root of 2, (actually 2 * 10 ^ 4008):")
Console.WriteLine(IntNthRoot(3, b).ToString()) ' bonus example
b /= 10000
Console.WriteLine("Integer 7th Root of 2, (actually 2 * 10 ^ 4004):")
Console.WriteLine(IntNthRoot(7, b).ToString()) ' bonus example
If Diagnostics.Debugger.IsAttached Then Console.Read()
End Sub
End Module
- Output:
Integer Cube Root of 8: 2 Integer Cube Root of 9: 2 Integer Square Root of 2, (actually 2 * 10 ^ 4008, square root method): 1414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641572735013846230912297024924836055850737212644121497099935831413222665927505592755799950501152782060571470109559971605970274534596862014728517418640889198609552329230484308714321450839762603627995251407989687253396546331808829640620615258352395054745750287759961729835575220337531857011354374603408498847160386899970699004815030544027790316454247823068492936918621580578463111596668713013015618568987237235288509264861249497715421833420428568606014682472077143585487415565706967765372022648544701585880162075847492265722600208558446652145839889394437092659180031138824646815708263010059485870400318648034219489727829064104507263688131373985525611732204024509122770022694112757362728049573810896750401836986836845072579936472906076299694138047565482372899718032680247442062926912485905218100445984215059112024944134172853147810580360337107730918286931471017111168391658172688941975871658215212822951848847208969463386289156288276595263514054226765323969461751129160240871551013515045538128756005263146801712740265396947024030051749531886292563138518816347800156936917688185237868405228783762938921430065586956868596459515550164472450983689603688732311438941557665104088391429233811320605243362948531704991577175622854974143899918802176243096520656421182731672625753959471725593463723863226148274262220867115583959992652117625269891754098815934864008345708518147223181420407042650905653233339843645786579679651926729239987536661721598257886026336361782749599421940377775368142621773879919455139723127406689832998989538672882285637869774966251996658352577619893932284534473569479496295216889148549253890475582883452609652409654288939453864662574492755638196441031697983306185201937938494005715633372054806854057586799967012137223947582142630658513221740883238294728761739364746783743196000159218880734785761725221186749042497736692920731109636972160893370866115673458533483329525467585164471075784860246360083444 Integer Square Root of 2, (actually 2 * 10 ^ 4008, nth root method): 1414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641572735013846230912297024924836055850737212644121497099935831413222665927505592755799950501152782060571470109559971605970274534596862014728517418640889198609552329230484308714321450839762603627995251407989687253396546331808829640620615258352395054745750287759961729835575220337531857011354374603408498847160386899970699004815030544027790316454247823068492936918621580578463111596668713013015618568987237235288509264861249497715421833420428568606014682472077143585487415565706967765372022648544701585880162075847492265722600208558446652145839889394437092659180031138824646815708263010059485870400318648034219489727829064104507263688131373985525611732204024509122770022694112757362728049573810896750401836986836845072579936472906076299694138047565482372899718032680247442062926912485905218100445984215059112024944134172853147810580360337107730918286931471017111168391658172688941975871658215212822951848847208969463386289156288276595263514054226765323969461751129160240871551013515045538128756005263146801712740265396947024030051749531886292563138518816347800156936917688185237868405228783762938921430065586956868596459515550164472450983689603688732311438941557665104088391429233811320605243362948531704991577175622854974143899918802176243096520656421182731672625753959471725593463723863226148274262220867115583959992652117625269891754098815934864008345708518147223181420407042650905653233339843645786579679651926729239987536661721598257886026336361782749599421940377775368142621773879919455139723127406689832998989538672882285637869774966251996658352577619893932284534473569479496295216889148549253890475582883452609652409654288939453864662574492755638196441031697983306185201937938494005715633372054806854057586799967012137223947582142630658513221740883238294728761739364746783743196000159218880734785761725221186749042497736692920731109636972160893370866115673458533483329525467585164471075784860246360083445 Integer Cube Root of 2, (actually 2 * 10 ^ 4008): 12599210498948731647672106072782283505702514647015079800819751121552996765139594837293965624362550941543102560356156652593990240406137372284591103042693552469606426166250009774745265654803068671854055186892458725167641993737096950983827831613991551293136953661839474634485765703031190958959847411059811629070535908164780114735213254847712978802422085820532579725266622026690056656081994715628176405060664826773572670419486207621442965694205079319172441480920448232840127470321964282081201905714188996459998317503801888689594202055922021154729973848802607363697417887792157984675099539630078260959624203483238660139857363433909737126527995991969968377913168168154428850279651529278107679714002040605674803938561251718357006907984996341976291474044834540269715476228513178020643878047649322579052898467085805286258130005429388560720609747223040631357234936458406575916916916727060124402896700001069081035313852902700415084232336239889386496782194149838027072957176812879001445746227147702348357151905506722084818485009287239209282646606717174247753709737030012742918094054425696592075036357570375189603707473993461014490145157635960471111973845299132965726258904860978856180138677383615773009865983660805975756012787121486856242684556411651558179353228015896291299445004012084254141601575258416298814230973582153060405772425383645325335660 Integer 7th Root of 2, (actually 2 * 10 ^ 4004): 110408951367381233764950538762334472132532660078012416551453246414210632288038098071659828988630200514689715906557993125396921468043085579651064805838808196163919864392215583814551234397476339507890664685902921180613942144056283519219500774011043913929222338953790376732070503206390380988494445707084527925240582730725486467967183681658942999591682242459036160190261150569028438652686935172086652456800484770182207006433466758082204482396098451455092224240860882545144206285044829838431779372151867676523068340672781132725205233485925077681104722131036524174667129439905032
Wren
import "./big" for BigInt
// only use for integers less than 2^53
var intRoot = Fn.new { |x, n|
if (!(x is Num && x.isInteger && x >= 0)) {
Fiber.abort("First argument must be a non-negative integer.")
}
if (!(n is Num && x.isInteger && x >= 1)) {
Fiber.abort("Second argument must be a positive integer.")
}
return x.pow(1/n).floor
}
var a = [ [8, 3], [9, 3], [2e18, 2] ]
for (e in a) {
var x = e[0]
var n = e[1]
System.print("%(x) ^ (1/%(n)) = %(intRoot.call(x, n))")
}
System.print("\nFirst 2001 digits of the square root of 2:")
System.print((BigInt.two * BigInt.new(100).pow(2000)).isqrt)
- Output:
8 ^ (1/3) = 2 9 ^ (1/3) = 2 2e+18 ^ (1/2) = 1414213562 First 2001 digits of the square root of 2: 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008
XPL0
func real IRoot(X, N);
real X, N;
return Floor(Pow(X, 1./N));
[Format(1, 0);
RlOut(0, IRoot(8., 3.)); CrLf(0);
RlOut(0, IRoot(9., 3.)); CrLf(0);
RlOut(0, IRoot(2e18, 2.)); CrLf(0);
]
- Output:
2 2 1414213562
Yabasic
sub root(n, x)
for nr = floor(sqr(x)) to 1 step -1
if (nr ^ n) <= x then return nr : fi
next nr
end sub
print root(3, 8)
print root(3, 9)
print root(4, 167)
end
zkl
Uses GNU GMP library
var [const] BN=Import("zklBigNum");
fcn root(n,r){
f:='wrap(z){ (n/z.pow(r-1) + z*(r-1))/r or 1 }; //--> v or 1
c,d,e:=1,f(c),f(d);
while(c!=d and c!=e){ c,d,e=d,e,f(e) }
if(d<e) d else e
}
a:=BN(100).pow(2000)*2;
println("Does GMP agree: ",root(a,3)==a.root(3));
- Output:
Does GMP agree: True
- Draft Programming Tasks
- Arithmetic operations
- 11l
- Ada
- Arturo
- BASIC256
- C
- C sharp
- C++
- D
- Delphi
- SysUtils,StdCtrls
- EasyLang
- Elixir
- F Sharp
- Factor
- FreeBASIC
- FutureBasic
- Go
- Haskell
- J
- Java
- Jq
- Julia
- Kotlin
- Lua
- Modula-2
- Nim
- Bignum
- PARI/GP
- Perl
- Phix
- Phix/mpfr
- Python
- Quackery
- Racket
- Raku
- REXX
- Ring
- RPL
- Ruby
- Rust
- Scala
- Scheme
- Sidef
- Tcl
- Visual Basic .NET
- System.Numerics
- Wren
- XPL0
- Yabasic
- Zkl