But just for good measure, here's my own implementation, which utilises the fact sq(n) = (n-1)(n+1)+1, and the difference between two terms "t" apart in the resultant series is 2t + 3. Theoretically this should give you the square root in a single iteration, once the nearest power of two has been calculated, an initial step
which I'm sure can be optimised. But because all operations are integer-based, in practice more than one iteration is required. The code will still root a 300 digit integer in around 10 iterations, which is probably sufficient for general purposes.
static BigInteger SQRT(BigInteger N)
{
BigInteger q = N;
int two_pows = 1;
int iters = 0;
// Handle 1
if (q == 1)
{
return q;
}
// Get powers of 2 for N
while (q > 1)
{
two_pows++;
q /= 2;
}
// Divide by 2 to get the root
two_pows /= 2;
// First approximation
BigInteger t = N / BigInteger.Pow(2, two_pows);
iters = 0;
while (true)
{
BigInteger p = t * (t + 2) + 1;
if (p == N)
{
return t+1;
}
BigInteger e = N - p;
BigInteger correction = (2 * (t + 1)) + 1;
t += e / correction;
if (t * t == N)
{
return t;
}
iters++;
}
}