Cube root of a very large number using only math library

Question

I want to compute the cube root of an extremely huge number in Python3.

I've tried the function below, as well the Python syntax x ** (1 / n), but they both yield an error:

OverflowError: (34, 'Numerical result out of range')

I really need to compute the cube-root to solve a problem in cryptography. I can't use any modules other than math.

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

An example number that causes the error is:

num = 68057481137876648248241485864416419482650225630788641878663638907856305801266787545152598107424503316701887749720220603415974959561242770647206405075854693761748645436474693912889174270087450524201874301881144063774246565393171209785613106940896565658550145896382997905000280819929717554126192912435958881333015570058980589421883357999956417864406416064784421639624577881872069579492555550080496871742644626220376297153908107132546228975057498201139955163867578898758090850986317974370013630474749530052454762925065538161450906977368449669946613816

Result should be this (which is what gmpy2 finds and its correct - I've validated):

408280486712458018941011423246208684000839238529670746836313590220206147266723174123590947072617862777039701335841276608156219318663582175921048087813907313165314488199897222817084206

Answer 1

Your issue is that you're not sticking strictly to integers. Python's integers are dynamically sized, so they can fit any size of value you want, without losing any precision. But floating point numbers have an inherently limited precision.

When you do low = high/2, you're getting a floating point calculation, even if you don't intend it. Since low is a float, mid ends up being one too, and when you test the cube of mid, the float ends up overflowing and you get an exception.

If you change the first computation of low to use // instead of /, you'll stick with integers throughout the computation, and you won't get an overflow exception. With just that single change, I was able to run your code and get the result you are expecting:

>>> find_invpow(num, 3)
408280486712458018941011423246208684000839238529670746836313590220206147266723174123590947072617862777039701335841276608156219318663582175921048087813907313165314488199897222817084206