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

REXX

<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 argumenst 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 #.*/ 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/_ /*Is the root negative? Use reciprocal*/

             return _/1                         /*return the  Yth root of X to invoker.*/</rexx>

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

=={{header|zkl}}==
{{trans|Python}}
Uses GNU GMP library
<lang zkl>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
}</lang>
<lang zkl>a:=BN(100).pow(2000)*2;
println("Does GMP agree: ",root(a,3)==a.root(3));</lang>
{{out}}
<pre>
Does GMP agree: True