Geeks With Blogs

If you google carefully, it appears there are some resources to help with a common problem.

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

Comments on this post: Fast Square Root calculation for the BigInteger class in .NET

# re: Fast Square Root calculation for the BigInteger class in .NET Are you kidding? I tried this code, it never finished rooting A LOT of numbers (try 10), and is greatly slower than methods using multiplication, already commonly referred as super slow.
Left by roBsonn on Feb 13, 2018 3:32 PM

# re: Fast Square Root calculation for the BigInteger class in .NET My spouse and i continue to have blended sentiments about the apple ipad. I’d really enjoy to relax and play close to utilizing one to get a compelling realization. click for more info
Left by Robinjack on Mar 18, 2018 7:03 AM