Reputation: 597
The integer square root of a positive integer n is the largest integer whose square is less than or equal to n. (E.g. the integer square root of 7 is 2, and that of 9 is 3).
Here is my attempt:
intSquareRoot :: Int -> Int
intSquareRoot n
| n*n > n = intSquareRoot (n - 1)
| n*n <= n = n
I'm guessing its not working because n decreases along with the recursion as required, but due to this being Haskell you can't use variables to keep the original n.
Upvotes: 5
Views: 19167
Reputation: 111
I tried to find the integer square root and its remainder with the following:
squareRoot :: Integer -> Integer
squareRoot n
| n < 0 = error "negative input"
| otherwise = square n 10
where
square n m
| n > m*m = square n (m*m)
| otherwise = root (m*m) (2*m) 1
where
root a b c
| a+b+c > n = root (a-b+c) (b-2*c) c
| otherwise = b `div` 2 + c
squareRootRemainder :: Integer -> Integer
squareRootRemainder n = n-(squareRoot n)^2
From top to bottom: I check whether or not the number is negative and its magnitude one hundred at a time so that I can use the binomial coefficients 100, 20 and 1 to decompose the number. If their sum is greater than the latter, then I subtract the first coefficient with the second and add the third, otherwise I show the result by halving the second coefficient and adding the third.
The idea works according to this:
81-18+1 = 64, the square of 8, 18 double the product of 9 and 1, so 9+1 is the root of 100.
64-16+1 = 49, the square of 7, 16 double the product of 8 and 1, so 8+1 is the root of 81.
49-14+1 = 36, the square of 6, 14 double the product of 7 and 1, so 7+1 is the root of 64.
...
And it carries on. I don't know whether it's the most efficient or not. I thought that it was a good exercise in trying to make it reasonable and capable of being generalized since the cube root uses coefficients 1000, 300, 30 and 1, with the number having to be checked for its magnitude one thousand at a time.
Upvotes: 0
Reputation: 511
The proposed solution doesn't work because overlaps the n
parameter in each recursion call.
The following solution uses binary search and finds the integer square root in O(log(n))
:
intSquareRoot :: Int -> Int
intSquareRoot n = bbin 0 (n+1)
where bbin a b | a + 1 == b = a
| otherwise = if m*m > n
then bbin a m
else bbin m b
where m = (a + b) `div` 2
dividing the range [a,b)
by two on each recursion call ([a,m)
or [m,b)
) depending where the square root is located.
Upvotes: 1
Reputation: 1739
... but due to this being Haskell you cant use variables to keep the original n.
I don't know what makes you say that. Here's how you could implement it:
intSquareRoot :: Int -> Int
intSquareRoot n = aux n
where
aux x
| x*x > n = aux (x - 1)
| otherwise = x
This is good enough to play around, but it's not a very efficient implementation. A better one can be found on Haskell's wiki:
(^!) :: Num a => a -> Int -> a
(^!) x n = x^n
squareRoot :: Integer -> Integer
squareRoot 0 = 0
squareRoot 1 = 1
squareRoot n =
let twopows = iterate (^!2) 2
(lowerRoot, lowerN) =
last $ takeWhile ((n>=) . snd) $ zip (1:twopows) twopows
newtonStep x = div (x + div n x) 2
iters = iterate newtonStep (squareRoot (div n lowerN) * lowerRoot)
isRoot r = r^!2 <= n && n < (r+1)^!2
in head $ dropWhile (not . isRoot) iters
Upvotes: 8
Reputation: 502
Your initial attempt, as well as the good correction of user2989737, tries every number from n down to the solution. It is very slow for large numbers, complexity is O(n). It will be better to start from 0 up to the solution, which improves complexity to O(sqrt n):
intSquareRoot :: Int -> Int
intSquareRoot n = try 0 where
try i | i*i <= n = try (i + 1)
| True = i - 1
But here is a much more efficient code using Babylonian method (Newton's method applied to square roots):
squareRoot :: Integral t => t -> t
squareRoot n
| n > 0 = babylon n
| n == 0 = 0
| n < 0 = error "Negative input"
where
babylon a | a > b = babylon b
| True = a
where b = quot (a + quot n a) 2
It is not as fast as Pedro Rodrigues solution (GNU's multiprecision library algorithm), but it is much simpler and easier to understand. It also needs to use an internal recursion in order to keep the original n.
To make it complete, I generalized it to any Integral type, checked for negative input, and checked for n == 0 to avoid division by 0.
Upvotes: 4
Reputation:
You might not have editable variables, but you can pass arguments recursively....
intSquareRoot :: Int -> Int
intSquareRoot n = try n where
try i | i*i > n = try (i - 1)
| i*i <= n = i
giving
ghci> intSquareRoot 16
4
ghci> intSquareRoot 17
4
Upvotes: 6