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

@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

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).

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.)

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