37 lines
843 B
C#
37 lines
843 B
C#
using System;
|
|
using System.Numerics;
|
|
|
|
namespace BigInt
|
|
{
|
|
public static class NumericsExtensions
|
|
{
|
|
public static System.Numerics.BigInteger Sqrt(this System.Numerics.BigInteger n)
|
|
{
|
|
if (n == 0) return 0;
|
|
if (n > 0)
|
|
{
|
|
int bitLength = Convert.ToInt32(Math.Ceiling(System.Numerics.BigInteger.Log(n, 2)));
|
|
System.Numerics.BigInteger root = System.Numerics.BigInteger.One << (bitLength / 2);
|
|
|
|
while (!isSqrt(n, root))
|
|
{
|
|
root += n / root;
|
|
root /= 2;
|
|
}
|
|
|
|
return root;
|
|
}
|
|
|
|
throw new ArithmeticException("NaN");
|
|
}
|
|
|
|
private static Boolean isSqrt(System.Numerics.BigInteger n, System.Numerics.BigInteger root)
|
|
{
|
|
System.Numerics.BigInteger lowerBound = root * root;
|
|
System.Numerics.BigInteger upperBound = (root + 1) * (root + 1);
|
|
|
|
return (n >= lowerBound && n < upperBound);
|
|
}
|
|
}
|
|
}
|