What's the way to determine if an Int is a perfect square in Haskell?

Question

I need a simple function

is_square :: Int -> Bool

which determines if an Int N a perfect square (is there an integer x such that x*x = N).

Of course I can just write something like

is_square n = sq * sq == n
    where sq = floor $ sqrt $ (fromIntegral n::Double)

but it looks terrible! Maybe there is a common simple way to implement such a predicate?

Answer 1

Think of it this way, if you have a positive int n, then you're basically doing a binary search on the range of numbers from 1 .. n to find the first number n' where n' * n' = n.

I don't know Haskell, but this F# should be easy to convert:

let is_perfect_square n =
    let rec binary_search low high =
        let mid = (high + low) / 2
        let midSquare = mid * mid

        if low > high then false
        elif n = midSquare then true
        else if n < midSquare then binary_search low (mid - 1)
        else binary_search (mid + 1) high

    binary_search 1 n

Guaranteed to be O(log n). Easy to modify perfect cubes and higher powers.

Answer 2

There is a wonderful library for most number theory related problems in Haskell included in the arithmoi package.

Use the Math.NumberTheory.Powers.Squares library.

Specifically the isSquare' function.

is_square :: Int -> Bool
is_square = isSquare' . fromIntegral

The library is optimized and well vetted by people much more dedicated to efficiency then you or I. While it currently doesn't have this kind of shenanigans going on under the hood, it could in the future as the library evolves and gets more optimized. View the source code to understand how it works!

Don't reinvent the wheel, always use a library when available.

Answer 3

I think the code you provided is the fastest that you are going to get:

is_square n = sq * sq == n
    where sq = floor $ sqrt $ (fromIntegral n::Double)

The complexity of this code is: one sqrt, one double multiplication, one cast (dbl->int), and one comparison. You could try to use other computation methods to replace the sqrt and the multiplication with just integer arithmetic and shifts, but chances are it is not going to be faster than one sqrt and one multiplication.

The only place where it might be worth using another method is if the CPU on which you are running does not support floating point arithmetic. In this case the compiler will probably have to generate sqrt and double multiplication in software, and you could get advantage in optimizing for your specific application.

As pointed out by other answer, there is still a limitation of big integers, but unless you are going to run into those numbers, it is probably better to take advantage of the floating point hardware support than writing your own algorithm.

Answer 4

In a comment on another answer to this question, you discussed memoization. Keep in mind that this technique helps when your probe patterns exhibit good density. In this case, that would mean testing the same integers over and over. How likely is your code to repeat the same work and thus benefit from caching answers?

You didn't give us an idea of the distribution of your inputs, so consider a quick benchmark that uses the excellent criterion package:

module Main
where

import Criterion.Main
import Random

is_square n = sq * sq == n
    where sq = floor $ sqrt $ (fromIntegral n::Double)

is_square_mem =
  let check n = sq * sq == n
        where sq = floor $ sqrt $ (fromIntegral n :: Double)
  in (map check [0..] !!)

main = do
  g <- newStdGen
  let rs = take 10000 $ randomRs (0,1000::Int) g
      direct = map is_square
      memo   = map is_square_mem
  defaultMain [ bench "direct" $ whnf direct rs
              , bench "memo"   $ whnf memo   rs
              ]

This workload may or may not be a fair representative of what you're doing, but as written, the cache miss rate appears too high: