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.
... 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 
intSqrt = floor . sqrt . fromInteger?
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 
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.
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.
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.
r*randn, what value would you try for r? And how would you let Haskell know about it?