title: fast integer square root approximation
body: <p>I am currently searching for a very fast integer square root approximation, where <code>floor(sqrt(x)) &lt;= veryFastIntegerSquareRoot(x) &lt;= x</code></p>
  
  <p>The square root routine is used for calculating prime numbers, which get considerably faster if only values below or equals <code>sqrt(x)</code> are checked for being a divisor of <code>x</code>.</p>
  
  <p>What I am currently having is <a href="https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Example_2" rel="noreferrer">this function from Wikipedia</a>, adjusted a small bit to work with 64-bit integers.</p>
  
  <p>Because I have no other function to compare against (or more precise, the function is too precise for my purposes, and it probably takes more time, than being higher than the actual result.)</p>