What’s a good algorithm to determine if an input is a perfect square? [duplicate]

by 
bool IsPerfectSquare(long input)
{
    long closestRoot = (long) Math.Sqrt(input);
    return input == closestRoot * closestRoot;
}

This may get away from some of the problems of just checking “is the square root an integer” but possibly not all. You potentially need to get a little bit funkier:

bool IsPerfectSquare(long input)
{
    double root = Math.Sqrt(input);

    long rootBits = BitConverter.DoubleToInt64Bits(root);
    long lowerBound = (long) BitConverter.Int64BitsToDouble(rootBits-1);
    long upperBound = (long) BitConverter.Int64BitsToDouble(rootBits+1);

    for (long candidate = lowerBound; candidate <= upperBound; candidate++)
    {
         if (candidate * candidate == input)
         {
             return true;
         }
    }
    return false;
}

Icky, and unnecessary for anything other than really large values, but I think it should work…

More Related Contents:

  1. Custom Weighted Scale [closed]
  2. How to find nth prime with complexity o(1)
  3. Calculate distance between two latitude-longitude points? (Haversine formula)
  4. How to determine if a point is in a 2D triangle? [closed]
  5. Algorithm to find Largest prime factor of a number
  6. Is log(n!) = Θ(n·log(n))?
  7. How to calculate an angle from three points? [closed]
  8. Select k random elements from a list whose elements have weights
  9. How to make rounded percentages add up to 100%
  10. Writing your own square root function
  11. Finding out nth fibonacci number for very large ‘n’
  12. What is the fastest integer factorization algorithm?
  13. Computing set intersection in linear time?
  14. Floating Point Divider Hardware Implementation Details
  15. Unsupervised clustering with unknown number of clusters
  16. Circle-circle intersection points
  17. How to find the smallest number with just 0 and 1 which is divided by a given number?
  18. How to calculate the index (lexicographical order) when the combination is given
  19. How do I find a factorial? [closed]
  20. Calculating the position of points in a circle
  21. Strategies for simplifying math expressions
  22. How to express tetration function, for complex numbers
  23. What is the method for converting radians to degrees?
  24. Given Prime Number N, Compute the Next Prime?
  25. How to check if an integer is a power of 3?
  26. Find out which combinations of numbers in a set add up to a given total
  27. How to generate a power set of a given set?
  28. determine if a point sits inside an arbitrary shape?
  29. How can I perform Collision Detection on rotated rectangles? [closed]
  30. Location of highest density on a sphere

Leave a Comment