Integer roots

Integer roots is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Integer roots

The task is to write a program that computes the Nth root of X as the largest integer less than or equal to R for which R^N=X. N and X are both integers. R is a real number.

As a test, you can calculate the first 2,001 digits in the decimal expansion of the square root of two. The method involves multiplying 2 by 100^2000 before taking the square root. You will then have the 2,001 most significant digits of the square root of two. Just remember where the decimal point goes and you are all set!

Python

<lang 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!=d and c!=e:
       c,d,e=d,e,(a1*e+b//(e**a1))//a
   return min(d,e)

print(root(2,2*100**2000))</lang>

Output:

141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723528850926486124949771542183342042856860601468247207714358548741556570696776537202264854470158588016207584749226572260020855844665214583988939443709265918003113882464681570826301005948587040031864803421948972782906410450726368813137398552561173220402450912277002269411275736272804957381089675040183698683684507257993647290607629969413804756548237289971803268024744206292691248590521810044598421505911202494413417285314781058036033710773091828693147101711116839165817268894197587165821521282295184884720896946338628915628827659526351405422676532396946175112916024087155101351504553812875600526314680171274026539694702403005174953188629256313851881634780015693691768818523786840522878376293892143006558695686859645951555016447245098368960368873231143894155766510408839142923381132060524336294853170499157717562285497414389991880217624309652065642118273167262575395947172559346372386322614827426222086711558395999265211762526989175409881593486400834570851814722318142040704265090565323333984364578657967965192672923998753666172159825788602633636178274959942194037777536814262177387991945513972312740668983299898953867288228563786977496625199665835257761989393228453447356947949629521688914854925389047558288345260965240965428893945386466257449275563819644103169798330618520193793849400571563337205480685405758679996701213722394758214263065851322174088323829472876173936474678374319600015921888073478576172522118674904249773669292073110963697216089337086611567345853348332952546758516447107578486024636008

zkl

Translation of: Python

Uses GNU GMP library <lang zkl>var [const] BN=Import("zklBigNum"); fcn root(n,r){ rm1:=r-1;

   c:=1;
   (d:=(n/c.pow(rm1) + c*rm1)/r) : if(_==0) d=1;;
   (e:=(n/d.pow(rm1) + d*rm1)/r) : if(_==0) e=1;;
   while(c!=d and c!=e){ c,d,e=d,e,(n/e.pow(rm1) + e*rm1)/r }
   if(d<e) d else e

}</lang> <lang zkl>a:=BN(100).pow(2000)*2; println("Does GMP agree: ",root(a,3)==a.root(3));</lang>

Output:

Does GMP agree: True