A perfect square kata

I was doing some katas on CodeWars recently, and some of them were involving perfect square numbers. In short, perfect square number is an integer which square root is also an integer, like 9, 16, 25, and 36.

Anyway, solutions which got most votes in both categories, best practice and clever use:

1
2
3
bool IsPerfectSquare(long number) {
    return Math.Sqrt(number) % 1 == 0;
}

This is kind of clever, as .NET (surprisingly) does not provide double Math.Frac(double), which would need to be implemented as:

1
2
3
double Frac(double number) {
    return number - Math.Floor(number);
}

But is it correct (best practice) at all?

Every time you see equals (==) used with floating point types the red light should go off in your head. Equality and floating point numbers do not work well together. Floating point numbers are usually greater (or equal) than (> or >=), less (or equal) than (< or <=), or within particular range (Math.Abs(x - y) <= Epsilon), but they are rarely equal (==). At least you should not rely on that.

Just try that:

1
2
3
4
var sum = 0.0;
Debug.Assert(sum == 0.0);
for (int i = 0; i < 100; i++) sum += 0.1;
Debug.Assert(sum == 100*0.1); // FAIL! 9.99999999999998 != 10

So I know that clever implementation of IsPerfectSquare is potentially flawed, but as a true wannabe skeptic, I also know that experiment beats theory. I decided to find what is the smallest not so perfect square number which will deceive this method and force it to provide false positive.
The best bet is a number which is true perfect square plus 1, so:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static bool IsPerfectSquare(long number) {
    return Math.Sqrt(number) % 1 == 0;
}

static void Main()
{
    for (long i = 1; i < int.MaxValue; i++) {
        var fake = i*i + 1; // fake perfect square
        if (IsPerfectSquare(fake)) {
            Console.WriteLine("{0} is the smallest fake perfect square", fake);
            break;
        }
    }
}

…and we have an answer in below 3s:

1
4503599627370497 is the smallest fake perfect square

which is 67108864^2 + 1.

How can we implement IsPerfectSquare properly then?

For square roots in integer domain we should probably use dedicated algorithm but because this is outside of the scope here (and outside the scope of this kata, I suppose) we need to think how to make Math.Sqrt(...) work for us.

We need to bring the equality test back to integer domain. So, even if we use floating point numbers to calculate square root, we will perform the test itself using integers.

Let’s get the integer (rounded) “square root candidate” first:

1
var root = (long)Math.Sqrt(number);

…and then test if it is really is a square root of given number:

1
return root*root == number;

That’s it. Not much more code. There was really no reason to sacrifice correctness for “cleverness”.

1
2
3
4
bool IsPerfectSquare(long number) {
    var root = (long)Math.Sqrt(number);
    return root*root == number;
}

As a bonus we can also check if rounding might be a problem leading to false negatives:

1
2
var max = (long)int.MaxValue;
Debug.Assert((long)Math.Sqrt(max*max) == max); // SUCCESS!

…and it (most likely) won’t.
Of course, this approach will stop working at some point:

1
2
3
4
var number = new BigInteger(long.MaxValue);
var square = number*number;
var root = new BigInteger(Math.Sqrt((double)square));
Debug.Assert(root == number); // FAIL!

…but that’s different story.