Integer roots
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