Skip to content

Instantly share code, notes, and snippets.

@Olathe
Last active August 29, 2015 13:56
Show Gist options
  • Save Olathe/9083004 to your computer and use it in GitHub Desktop.
Save Olathe/9083004 to your computer and use it in GitHub Desktop.
Simple near-hardware-speed floored square root for 64-bit integers
/* Sometimes, taking the floored square root of a 64-bit integer is needed.
In order to gain the speed of hardware square root, 64-bit integers must be converted
to 53-bit mantissa doubles.
This can cause incorrect results due to loss of precision.
However, the floor of the square root produced will be either the correct
floored square root or the next higher integer.
For reasoning, see http://apps.topcoder.com/forums/?module=Thread&threadID=695233
So, we can simply:
1) Convert to double.
2) Use hardware square root.
3) Convert to long.
4) If the square of the result is higher than the input value, subtract one from the result.
5) Return the result.
*/
public static final long fastFlooredSqrt(final long value) {
long result = (long) Math.sqrt((double) value);
if (result*result > value) result--;
return result;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment