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