How to compute the nth root of a very big integer

Question

I need a way to compute the nth root of a long integer in Python.

I tried pow(m, 1.0/n), but it doesn't work:

OverflowError: long int too large to convert to float

Any ideas?

By long integer I mean REALLY long integers like:

11968003966030964356885611480383408833172346450467339251 196093144141045683463085291115677488411620264826942334897996389 485046262847265769280883237649461122479734279424416861834396522 819159219215308460065265520143082728303864638821979329804885526 557893649662037092457130509980883789368448042961108430809620626 059287437887495827369474189818588006905358793385574832590121472 680866521970802708379837148646191567765584039175249171110593159 305029014037881475265618958103073425958633163441030267478942720 703134493880117805010891574606323700178176718412858948243785754 898788359757528163558061136758276299059029113119763557411729353 915848889261125855717014320045292143759177464380434854573300054 940683350937992500211758727939459249163046465047204851616590276 724564411037216844005877918224201569391107769029955591465502737 961776799311859881060956465198859727495735498887960494256488224 613682478900505821893815926193600121890632

Answer 1

If it's a REALLY big number. You could use a binary search.

def find_invpow(x,n):     """Finds the integer component of the n'th root of x,     an integer such that y ** n <= x < (y + 1) ** n.     """     high = 1     while high ** n <= x:         high *= 2     low = high/2     while low < high:         mid = (low + high) // 2         if low < mid and mid**n < x:             low = mid         elif high > mid and mid**n > x:             high = mid         else:             return mid     return mid + 1 

For example:

>>> x = 237734537465873465 >>> n = 5 >>> y = find_invpow(x,n) >>> y 2986 >>> y**n <= x <= (y+1)**n True >>> >>> x = 119680039660309643568856114803834088331723464504673392511960931441> >>> n = 45 >>> y = find_invpow(x,n) >>> y 227661383982863143360L >>> y**n <= x < (y+1)**n True >>> find_invpow(y**n,n) == y True >>> 

Answer 2

Gmpy is a C-coded Python extension module that wraps the GMP library to provide to Python code fast multiprecision arithmetic (integer, rational, and float), random number generation, advanced number-theoretical functions, and more.

Includes a root function:

x.root(n): returns a 2-element tuple (y,m), such that y is the (possibly truncated) n-th root of x; m, an ordinary Python int, is 1 if the root is exact (x==y**n), else 0. n must be an ordinary Python int, >=0.

For example, 20th root:

>>> import gmpy >>> i0=11968003966030964356885611480383408833172346450467339251  >>> m0=gmpy.mpz(i0) >>> m0 mpz(11968003966030964356885611480383408833172346450467339251L) >>> m0.root(20) (mpz(567), 0)