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?

Funk

possible duplicate of Fastest way to determine if an integer's square root is an integer – Severally

Answer 1

Oh, today I needed to determine if a number is perfect cube, and similar solution was VERY slow.

So, I came up with a pretty clever alternative

cubes = map (\x -> x*x*x) [1..]
is_cube n = n == (head $ dropWhile (<n) cubes)

Very simple. I think, I need to use a tree for faster lookups, but now I'll try this solution, maybe it will be fast enough for my task. If not, I'll edit the answer with proper datastructure

Funk

I do not know if this will be faster than original. It requires a lot more instructions to be executed. It might be faster depending on how Haskell does head/dropWhile and how big your numbers are. – Drexler

Using a different datastructure (Seq, Vector) and a binary search will likely be an order of magintude faster – Fonz

Answer 2

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.

Acord

I like this solution very much. I keep being amazed by just how useful binary search is for different things. However, O(log n) is misleading. You will preform O(log n) iterations, however in each iteration you have a hidden mid*mid. Squaring a number takes roughly O(mlogm). m is closing in on sqrt(n), so lets assume m = sqrt(n). The final efficiency of this is actually O(log n) * O(m log m) for m = sqrt(n). Still, +1 for binary search :P – Mecke

The question specifies Int which in Haskell is fixed-precision (typically 32-bit) so I would prefer the floating-point method as used in the question. If N was an Integer (arbitrary-precision) I would use your method. – Severally

Answer 3

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.

Fonz

I'm writing kind of my own number theory library for fun. My point is to understand how the functions I have in it work. The worst-case scenario for the function from that library is: – Consonant

Note this function has moved out of arithmoi to the integer-roots package. – Tauto

Answer 4

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.

Drexler

I just thought there is a simple and beautiful solution without two type conversions :) Ok, thank you! – Funk

profiling my app shows what 57% of the time is spent in is_square function :( – Funk

You might have to do some caching (do not compute the same integer twice), or pre-compute all integers initially. Using non Haskell speak: bool[] isSquare = new bool[100000]; for(int i = 1; i < isSquare.lenght; i++) { isSquare[i*i] = true; } This eliminates the sqrt and double multiplication. – Drexler

memorizing is_square, I never imagined that! but I'm using haskell and it's not so simple here. btw I can't understand why memorizing pure functions is not a part of haskell – Funk

Automatically memoizing things is a huge space leak. That's why you have to intentionally do it yourself. – Elka

You can use a Monad to add memoization, however don't forget that you typically only cache the n last results of the calls, otherwise your cache would grow endlessly... – Salary

You could also swap in another cast for the multiplication: is_square n = floor rt == ceil rt where rt = sqrt $ (fromIntegral n::Double) – Tenatenable

Answer 5

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:

Eugeniusz

Answer 6

Wikipedia's article on Integer Square Roots has algorithms can be adapted to suit your needs. Newton's method is nice because it converges quadratically, i.e., you get twice as many correct digits each step.

I would advise you to stay away from Double if the input might be bigger than 2^53, after which not all integers can be exactly represented as Double.

Dispermous

I don't need very complex algorythm, I just thought there is a simple and beautiful solution without two type conversions :) – Funk

@valya: Writing an isqrt function would eliminate the type conversions. – Dispermous

Answer 7

Sometimes you shouldn't divide problems into too small parts (like checks is_square):

intersectSorted [] _ = []
intersectSorted _ [] = []
intersectSorted xs (y:ys) | head xs > y = intersectSorted xs ys
intersectSorted (x:xs) ys | head ys > x = intersectSorted xs ys
intersectSorted (x:xs) (y:ys) | x == y = x : intersectSorted xs ys

squares = [x*x | x <- [ 1..]]
weird = [2*x+1 | x <- [ 1..]]

perfectSquareWeird = intersectSorted squares weird

Collator

oh, very interesting! I'll think about how to make this more suitable for me – Funk

Answer 8

There's a very simple way to test for a perfect square - quite literally, you check if the square root of the number has anything other than zero in the fractional part of it.
I'm assuming a square root function that returns a floating point, in which case you can do (Psuedocode):

func IsSquare(N)  
   sq = sqrt(N)
   return (sq modulus 1.0) equals 0.0

Mecke

isSquare b n = (mod' (logBase b n) 1.0) == 0.0 -- mod' from Data.Fixed – Exaggeration

Answer 9

It's not particularly pretty or fast, but here's a cast-free, FPA-free version based on Newton's method that works (slowly) for arbitrarily large integers:

import Control.Applicative ((<*>))
import Control.Monad (join)
import Data.Ratio ((%))

isSquare = (==) =<< (^2) . floor . (join g <*> join f) . (%1)
  where
    f n x = (x + n / x) / 2
    g n x y | abs (x - y) > 1 = g n y $ f n y
            | otherwise       = y

It could probably be sped up with some additional number theory trickery.

Knight

Thank you! but it's opposite to my task – Funk