#program to find the square root of a number
#The result is known to be an integer.
#The algorithm uses a divide and conquer approach


number = 1522756
low=1
high=number
guess = int((low+high)/2)
nsquared = guess**2
n=1
while nsquared != number: 
    if nsquared > number:
        high = int((high+low)/2)
        
    else:
        low = guess
    n=n+1
    guess = int((low+high)/2)
    nsquared = guess**2
    print (low, high,nsquared)
    

print("square root is ",guess)
print ("This took ", n, "guesses")