square root 2

#!/usr/bin/env python

def sqrt(x):
    
    begin = 0
    end   = x

    while begin <= end:

        mid = begin + (end - begin) // 2

        if mid*mid == x:
            return mid
        elif mid*mid < x:
            begin = mid + 1
        else:
            end = mid - 1

    return end




def main():
    import math
    x = 18014398509481983
    si = int(math.sqrt(x))
    sk = sqrt(x)

    ## all these assert fail
    assert(si**2 == x) # this one fails because sqrt uses floating-point
    assert(sk == si)   # this one fails because my implementation gives the lowest sqrt
    assert(sk**2 == x) # this one fails because x does not have a perfect square root
    

if __name__ == '__main__':
    main()