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

Question

.NET 4.0 provides the System.Numerics.BigInteger type for arbitrarily-large integers. I need to compute the square root (or a reasonable approximation -- e.g., integer square root) of a BigInteger. So that I don't have to reimplement the wheel, does anyone have a nice extension method for this?

Answer 1

Check if BigInteger is not a perfect square has code to compute the integer square root of a Java BigInteger. Here it is translated into C#, as an extension method.

    public static BigInteger Sqrt(this BigInteger n)     {         if (n == 0) return 0;         if (n > 0)         {             int bitLength = Convert.ToInt32(Math.Ceiling(BigInteger.Log(n, 2)));             BigInteger root = BigInteger.One << (bitLength / 2);              while (!isSqrt(n, root))             {                 root += n / root;                 root /= 2;             }              return root;         }          throw new ArithmeticException("NaN");     }      private static Boolean isSqrt(BigInteger n, BigInteger root)     {         BigInteger lowerBound = root*root;         BigInteger upperBound = (root + 1)*(root + 1);          return (n >= lowerBound && n < upperBound);     } 

Informal testing indicates that this is about 75X slower than Math.Sqrt, for small integers. The VS profiler points to the multiplications in isSqrt as the hotspots.