views:

450

answers:

8

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 predicate?

+1  A: 

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.

Dietrich Epp
I don't need very complex algorythm, I just thought there is a simple and beautiful solution without two type conversions :)
valya
@valya: Writing an `isqrt` function would eliminate the type conversions.
Dietrich Epp
+2  A: 

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.

earlNameless
I just thought there is a simple and beautiful solution without two type conversions :) Ok, thank you!
valya
profiling my app shows what 57% of the time is spent in is_square function :(
valya
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.
earlNameless
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
valya
Automatically memoizing things is a huge space leak. That's why you have to intentionally do it yourself.
Chuck
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...
Matthieu M.
A: 

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.

Travis Brown
Thank you! but it's opposite to my task
valya
+1  A: 

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

valya
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.
earlNameless
It's faster in practice.
valya
+1  A: 

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
ony
oh, very interesting! I'll think about how to make this more suitable for me
valya
A: 

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
Rubys
A: 

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:

timing probability-density

Greg Bacon
+3  A: 

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.

Juliet
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
Rubys
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.
finnw