Integer square root of integer
CJam, 17 (or 10) bytes

{_1.5#\/i}


Try it online by verifying the test cases:

[0 1 2 3 4 8 9 15 16 65535 65536 18446744073709551615]{_1.5#\/i}%N*


It won't pass the last test case because of rounding issues, but since 18446744073709551615 isn't an Integer in CJam (it's a Big Integer), we're still good, right?

If not, the following (and slightly longer) code will correct those errors:

{__1.5#\/i_2#@&gt;-}


Not the shortest solution anymore, but faaast.

How it works

__    " Duplicate the integer twice. ";
1.5#  " Raise to power 1.5. Note that, since 1.5 &gt; 1, this doesn't break the rules. ";
\     " Swap the result with the original integer. ";
/     " Divide. ";
i     " Cast to integer. ";
_2#   " Push square of a copy. ";
@     " Rotate the orginal integer on top of the stack. ";
&gt;-    " If the square root has been rounded up, subtract 1. ";