Initial estimate for Integer#sqrt should be improved
r57705, by Nobu, in response to issue #13219, added Integer#sqrt. The initial estimator used is
1 << (b-1)/2 | n >> (b+1)/2. For this style of estimator,
1 << (b-1)/2 | n >> (b+3)/2 would be best. (Basically, there is a fencepost error in the current commit.)
However, much better initial estimates can be made. In particular, using the hardware floating point square root will almost certainly eliminate 3-4 rounds of approximation. Even for smaller numbers, this represents a substantial gain.
If for some reason, it is problematic to use fsqrt, a small table lookup can eliminate a couple of rounds.