Root of number - January 8 2018 - excellent performance

RootOfNumber_January8_2018.py

"""
1. binary search.
2. input are nonnegative. x is nonegative float and n is positive int.
3. if x in [0, 1], then search space is [0, 1]
   elif x in (1, inf), then search space is (1, x)
4. if abs(mid * n - x) <= 0.001:
       return mid
   elif mid * n - x > 0.001:
       hi = mid
   else:
       lo = mid
5. time complexity is O(logx)
0 - Max(1, x), 0.001, how many in total 1000 * max(1, x), log1000 Max(1, x)
not related to n, n power of number
10 * logMax(1, x)

   space complexity is O(1)
if x < 1, then range should be > x

0.1 ^ 2 = 0.01

X > 1, x = 8, n = 3
root^3 = 8 => root < x

examples:
input:  x = 7, n = 3
output: 1.913

input:  x = 9, n = 2
output: 3

4. 
"""

import math

def root(x, n):
    if x == 1:
        return 1
    elif x < 1:
        lo, hi = 0.0, 1.0
    else:
        lo, hi = 1.0, x * 1.0

    while lo < hi:
        mid = (lo + hi) / 2
        diff = mid ** n - x
        
        if abs(diff) <= 0.001:
            return round(mid, 3)
        elif diff > 0.001:
            hi = mid
        else:
            lo = mid
            
print root(4, 2)