Geeks With Blogs
Alex Hildyard

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++;
    }
}
Posted on Monday, February 22, 2016 7:15 PM | Back to top


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
Requesting Gravatar...
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
Requesting Gravatar...
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

Your comment:
 (will show your gravatar)


Copyright © Alex Hildyard | Powered by: GeeksWithBlogs.net