計算大整數根

儘管 Python 本身支援大整數，但是在 Python 中使用非常大數字的第 n 個根可能會失敗。

x = 2 ** 100
cube = x ** 3
root = cube ** (1.0 / 3)

OverflowError：long int 太大而無法轉換為 float

處理這樣大的整數時，你需要使用自定義函式來計算數字的第 n 個根。

def nth_root(x, n):
    # Start with some reasonable bounds around the nth root.
    upper_bound = 1
    while upper_bound ** n <= x:
        upper_bound *= 2
    lower_bound = upper_bound // 2
    # Keep searching for a better result as long as the bounds make sense.
    while lower_bound < upper_bound:
        mid = (lower_bound + upper_bound) // 2
        mid_nth = mid ** n
        if lower_bound < mid and mid_nth < x:
            lower_bound = mid
        elif upper_bound > mid and mid_nth > x:
            upper_bound = mid
        else:
            # Found perfect nth root.
            return mid
    return mid + 1

x = 2 ** 100
cube = x ** 3
root = nth_root(cube, 3)
x == root
# True