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:
This is kind of clever, as .NET (surprisingly) does not provide
double Math.Frac(double), which would need to be implemented as:
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 (
>=), less (or equal) than (
<=), 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:
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:
…and we have an answer in below 3s:
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:
…and then test if it is really is a square root of given number:
That’s it. Not much more code. There was really no reason to sacrifice correctness for “cleverness”.
As a bonus we can also check if rounding might be a problem leading to false negatives:
…and it (most likely) won’t.
Of course, this approach will stop working at some point:
…but that’s different story.