CODEWITHSUNDEEP
haskellrecursion
newbie
newbie

Reputation: 1217

How to tell if a number is a square number with recursion?

I solved the following exercise, but I'm not a fan of the solution:

Write the function isPerfectSquare using recursion, to tell if an Int is a perfectSquare isPerfectSquare 1 -> Should return True
isPerfectSquare 3 -> Should return False

the num+1 part is for the case for isPerfectSquare 0 and isPerfectSquare 1, one of the parts I don't like one bit, this is my solutiuon:

perfectSquare 0 1 = [0] ++ perfectSquare 1 3
perfectSquare current diff = [current] ++ perfectSquare (current + diff) (diff + 2)

isPerfectSquare num = any (==num) (take (num+1) (perfectSquare 0 1))

What is a more elegant solution to this problem? of course we can't use sqrt, nor floating point operations.

Upvotes: 3

Views: 1179

Answers (4)

fp_mora
fp_mora

Reputation: 714

If the function is recursive then it is primitive recursive as are 90% of all recursive functions. For these folds are fast and effective. Considering the programmers time, while keeping things simple and correct is important.

Now, that said, it might be fruitful to cinsider text patterns of functions like sqrt. sqrt return a floating point number. If a number is a perfect square then two characters are ".0" at the end. The pattern might occur, however, at the start of any mantissa. If a string goes in, in reverse, then "0." is at the top of the list.

This function takes a Number and returns a Bool

fps n = (take 2.reverse.show $ (n / (sqrt n))) == "0."

fps 10000.00001

False

fps 10000

True

Upvotes: 0

Daniel Wagner
Daniel Wagner

Reputation: 152837

Wikipedia suggests using Newton's method. Here's how that would look. We'll start with some boilerplate. ensure is a little combinator I've used fairly frequently. It's written to be very general, but I've included a short comment that should be pretty explanatory for how we'll plan to use it.

import Control.Applicative
import Control.Monad

ensure :: Alternative f => (a -> Bool) -> a -> f a
ensure p x = x <$ guard (p x)
-- ensure p x | p x = Just x
--            | otherwise = Nothing

Here's the implementation of the formula given by Wikipedia for taking one step in Newton's method. x is our current guess about the square root, and n is the number we're taking the square root of.

stepApprox :: Integer -> Integer -> Integer
stepApprox x n = (x + n `div` x) `div` 2

Now we can recursively call this stepping function until we get the floor of the square root. Since we're using integer division, the right termination condition is to watch for the next step of the approximation to be equal or one greater to the current step. This is the only recursive function.

iterateStepApprox :: Integer -> Integer -> Integer
iterateStepApprox x n = case x' - x of
    0 -> x
    1 -> x
    _ -> iterateStepApprox x' n
    where x' = stepApprox x n

To wrap the whole development up in a nice API, to check if a number is a square we can just check that the floor of its square root squares to it. We also need to pick a starting approximation, but we don't have to be super smart -- Newton's method converges very quickly for square roots. We'll pick half the number (rounded up) as our approximation. To avoid division by zero and other nonsense, we'll make zero and negative numbers special cases.

isqrt :: Integer -> Maybe Integer
isqrt n | n < 0 = Nothing
isqrt 0 = Just 0
isqrt n = ensure (\x -> x*x == n) (iterateStepApprox ((n+1)`div`2) n)

Now we're done! It's pretty fast even for large numbers:

> :set +s
> isqrt (10^10000) == Just (10^5000)
True
(0.58 secs, 182,610,408 bytes)

Yours would spend rather a longer time than the universe has got left computing that. It is also marginally faster than the binary search algorithm in my tests. (Of course, not hand-rolling it yourself is several orders of magnitude faster still, probably in part because it uses a better, but more complicated, algorithm based on Karatsuba multiplication.)

Upvotes: 1

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476669

You can perform some sort of "binary search" on some implicit list of squares. There is however a problem of course, and that is that we first need an upper bound. We can use as upper bound the number itself, since for all integral squares, the square is larger than the value we square.

So it could look like:

isPerfectSquare n = search 0 n
    where search i k | i > k = False
                     | j2 > n = search i (j-1)
                     | j2 < n = search (j+1) k
                     | otherwise = True
              where j = div (i+k) 2
                    j2 = j * j

To verify that a number n is a perfect square, we thus have an algorithm that runs in O(log n) in case the integer operations are done in constant time (for example if the number of bits is fixed).

Upvotes: 3

newbie
newbie

Reputation: 1217

@luqui you mean like this?

pow n = n*n
perfectSquare pRoot pSquare | pow(pRoot) == pSquare = True
                            | pow(pRoot)>pSquare = perfectSquare (pRoot-1) pSquare
                            | otherwise = False
--
isPerfectSquare number = perfectSquare number number

I can't believe I didn't see it xD thanks a lot! I must be really tired

Upvotes: 5

Related Questions