Calculate square root of a BigInteger (System.Numerics.BigInteger)

Question

.NET 4.0 provides System.Numerics.BigInteger, I need to compute the square root(a reasonable aproximation atleast) of a BigInteger, as to not reimplement the wheel, does anyone have a nice extension methods for this ?

Answer 1

The simplest feasible way to compute a square root to an arbitrary precision is probably Newton's method.

Answer 2

Google(java biginteger sqrt) gives many hits which help. For instance http://www.merriampark.com/bigsqrt.htm

Answer 3

I am not sure if Newton's Method is the best way to compute bignum square roots, because it involves divisions which are slow for bignums. You can use a CORDIC method, which uses only addition and shifts (shown here for unsigned ints)

static uint isqrt(uint x)
{
    int b=15; // this is the next bit we try 
    uint r=0; // r will contain the result
    uint r2=0; // here we maintain r squared
    while(b>=0) 
    {
        uint sr2=r2;
        uint sr=r;
                    // compute (r+(1<<b))**2, we have r**2 already.
        r2+=(uint)((r<<(1+b))+(1<<(b+b)));      
        r+=(uint)(1<<b);
        if (r2>x) 
        {
            r=sr;
            r2=sr2;
        }
        b--;
    }
    return r;
}

There's a similar method which uses only addition and shifts, called 'Dijkstras Square Root', explained for example here:

• http://lib.tkk.fi/Diss/2005/isbn9512275279/article3.pdf