sqrt(n) rounded down

// logn
sqrt(n):
    if n < 1:
        throw
    lo = 0, hi = n
    if n == 1:
        return 1
    while true:
        mid = lo + (hi-lo)/2 //avoid overflow
        x = mid*mid
        if x < n:
            lo = mid
        else if x > n:
            hi = mid
        else: // mid*mid == n
            return mid
        if lo +1 == hi: //lo == mid
            return lo