Probably checking if the square root of the number has any decimal part, or if it is a whole number. Implementationwise, I would consider something like this: double result = Math.Sqrt(numberToCheck); bool isSquare = result%1 == 0; isSquare should now be true for all squares, and false for all others.
Most modern non-embedded CPUs (x86 and the larger ARM cores, for example) have hardware instructions to compute square roots directly. The hardware implementation backing these instructions varies, but typically is a variant on the schoolbook digit-by-digit algorithm (though not always in base two; base four or sixteen can also be used). These are typically among … Read more
Integer Square Roots by Jack W. Crenshaw could be useful as another reference. The C Snippets Archive also has an integer square root implementation. This one goes beyond just the integer result, and calculates extra fractional (fixed-point) bits of the answer. (Update: unfortunately, the C snippets archive is now defunct. The link points to the … Read more
Just for fun: public static BigInteger sqrt(BigInteger x) { BigInteger div = BigInteger.ZERO.setBit(x.bitLength()/2); BigInteger div2 = div; // Loop until we hit the same value twice in a row, or wind // up alternating. for(;;) { BigInteger y = div.add(x.divide(div)).shiftRight(1); if (y.equals(div) || y.equals(div2)) return y; div2 = div; div = y; } }
I’ve used this and it works quite well. Here’s an example of how the algorithm works at a high level. Edit: I was curious to see just how accurate this was as defined below. Here is the sqrt(2) from an official source: (first 200 digits) 1.41421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147 and here it is using the approach I outline … Read more
nth root of x is x^(1/n), so you can do 9**(1/2) to find the 2nd root of 9, for example. In general, you can compute the nth root of x as: x**(1/n) Note: In Python 2, you had to do 1/float(n) or 1.0/n so that the result would be a float rather than an int. … Read more
The following computes floor(sqrt(N)) for N > 0: x = 2^ceil(numbits(N)/2) loop: y = floor((x + floor(N/x))/2) if y >= x return x x = y This is a version of Newton’s method given in Crandall & Pomerance, “Prime Numbers: A Computational Perspective”. The reason you should use this version is that people who know … Read more
Simple implementation using Binary Search with C++ double root(double n){ // Max and min are used to take into account numbers less than 1 double lo = min(1, n), hi = max(1, n), mid; // Update the bounds to be off the target by a factor of 10 while(100 * lo * lo < n) … Read more
FYI. Carmack didn’t write it. Terje Mathisen and Gary Tarolli both take partial (and very modest) credit for it, as well as crediting some other sources. How the mythical constant was derived is something of a mystery. To quote Gary Tarolli: Which actually is doing a floating point computation in integer – it took a … Read more