How to compute the nth root of a very big integer

by

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

More Related Contents:

  1. How to find integer nth roots?
  2. Does Python IDE have a module which imports math functions such as cos or sin? [closed]
  3. What is the difference between ‘/’ and ‘//’ when used for division?
  4. Why does the division get rounded to an integer?
  5. How can I check for NaN values?
  6. Integer square root in python
  7. Convert a number range to another range, maintaining ratio
  8. How do you print superscript in Python?
  9. How do I do exponentiation in python? [duplicate]
  10. How can I convert radians to degrees with Python?
  11. How did Python implement the built-in function pow()?
  12. Algorithm to find which number in a list sum up to a certain number
  13. Why do “Not a Number” values equal True when cast as boolean in Python/Numpy?
  14. How can I randomly choose a maths operator and ask recurring maths questions with it?
  15. Integer division by negative number [duplicate]
  16. numpy arbitrary precision linear algebra
  17. What do these operators mean (** , ^ , %, //)? [closed]
  18. Can someone explain this: 0.2 + 0.1 = 0.30000000000000004? [duplicate]
  19. Python Math – TypeError: ‘NoneType’ object is not subscriptable
  20. Generating unique, ordered Pythagorean triplets
  21. How do order of operations go on Python?
  22. Math Expression Evaluation
  23. negative pow in python
  24. Inaccurate Logarithm in Python
  25. Function to determine if two numbers are nearly equal when rounded to n significant decimal digits
  26. What’s the simplest way to extend a numpy array in 2 dimensions?
  27. Rounding floats so that they sum to precisely 1
  28. Where can I inspect Python’s math functions?
  29. How do you get the next value in the floating-point sequence? [duplicate]
  30. Getting the subsets of a set in Python

Leave a Comment