benharris
benharris

Reputation: 597

Integer square root function in Haskell

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

Answers (5)

Marco_O
Marco_O

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

pachopepe
pachopepe

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

Pedro Rodrigues
Pedro Rodrigues

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

enrique
enrique

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

user2989737
user2989737

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

Related Questions