module IntArithmetic (squareRoot, isRoot) where
 
-- squareRoot only works on positive elements!
squareRoot :: (Integral t) => t -> t
squareRoot 0 = 0
squareRoot 1 = 1
squareRoot n = newton n (squareRoot (n `div` upper) * lower)
	where (lower, upper) = giantStep n 1 2

-- giantStep finds the pair of subsequent squares that is greater (upper) and less (lower) than n
giantStep n lower upper = if square >= n then (lower, upper) else giantStep n upper square
	where square = upper ^ 2

-- newton approaches the root faster if guess is further away and slower when it gets closer
newton n guess = if isRoot n guess then guess else newton n newGuess
	where newGuess = (guess + (n `div` guess)) `div` 2

isRoot :: (Num a, Ord a) => a -> a -> Bool
isRoot n r =  (r^2 <= n) && ((r+1)^2 > n)