How to find integer nth roots?

by

One solution first brackets the answer between lo and hi by repeatedly multiplying hi by 2 until n is between lo and hi, then uses binary search to compute the exact answer:

def iroot(k, n):
    hi = 1
    while pow(hi, k) < n:
        hi *= 2
    lo = hi // 2
    while hi - lo > 1:
        mid = (lo + hi) // 2
        midToK = pow(mid, k)
        if midToK < n:
            lo = mid
        elif n < midToK:
            hi = mid
        else:
            return mid
    if pow(hi, k) == n:
        return hi
    else:
        return lo

A different solution uses Newton’s method, which works perfectly well on integers:

def iroot(k, n):
    u, s = n, n+1
    while u < s:
        s = u
        t = (k-1) * s + n // pow(s, k-1)
        u = t // k
    return s

More Related Contents:

  1. Evenly distributing n points on a sphere
  2. What is the best way to get all the divisors of a number?
  3. How did Python implement the built-in function pow()?
  4. Algorithm to find which number in a list sum up to a certain number
  5. How to compute the nth root of a very big integer
  6. Getting the subsets of a set in Python
  7. counting combinations and permutations efficiently
  8. Fastest way to list all primes below N
  9. Sieve of Eratosthenes – Finding Primes Python
  10. Check if a number is a perfect square
  11. Quicksort with Python
  12. Python and Powers Math
  13. Math operations from string [duplicate]
  14. Difference between the built-in pow() and math.pow() for floats, in Python?
  15. Python: sort function breaks in the presence of nan
  16. Rotate image and crop out black borders
  17. How can I quickly estimate the distance between two (latitude, longitude) points?
  18. How to invert a permutation array in numpy
  19. Adjacency List and Adjacency Matrix in Python
  20. Linear regression of arrays containing NANs in Python/Numpy
  21. Binary search algorithm in python
  22. What algorithm does Python’s built-in sort() method use?
  23. Equivalent of `polyfit` for a 2D polynomial in Python
  24. Get all numbers that add up to a number
  25. Python: maximum recursion depth exceeded while calling a Python object
  26. How do I fix wrongly nested / unclosed HTML tags?
  27. Python pi calculation?
  28. Calculating the angle between two vectors in Python
  29. Sieve of Eratosthenes – Primes between X and N
  30. How to perform bilinear interpolation in Python

Leave a Comment