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++;

}

}