using System;
using System.Collections.Generic;

namespace ScottGarland
{
	using DType = System.UInt32; // This could be UInt32, UInt16 or Byte; not UInt64.

    #region DigitsArray
    internal class DigitsArray
    {
        internal DigitsArray(int size)
        {
            Allocate(size, 0);
        }

        internal DigitsArray(int size, int used)
        {
            Allocate(size, used);
        }

        internal DigitsArray(DType[] copyFrom)
        {
            Allocate(copyFrom.Length);
            CopyFrom(copyFrom, 0, 0, copyFrom.Length);
            ResetDataUsed();
        }

        internal DigitsArray(DigitsArray copyFrom)
        {
            Allocate(copyFrom.Count, copyFrom.DataUsed);
            Array.Copy(copyFrom.m_data, 0, m_data, 0, copyFrom.Count);
        }

        private DType[] m_data;

        internal static readonly DType AllBits;		// = ~((DType)0);
        internal static readonly DType HiBitSet;	// = 0x80000000;
        internal static int DataSizeOf
        {
            get { return sizeof(DType); }
        }

        internal static int DataSizeBits
        {
            get { return sizeof(DType) * 8; }
        }

        static DigitsArray()
        {
            unchecked
            {
                AllBits = (DType)~((DType)0);
                HiBitSet = (DType)(((DType)1) << (DataSizeBits) - 1);
            }
        }

        public void Allocate(int size)
        {
            Allocate(size, 0);
        }

        public void Allocate(int size, int used)
        {
            m_data = new DType[size + 1];
            m_dataUsed = used;
        }

        internal void CopyFrom(DType[] source, int sourceOffset, int offset, int length)
        {
            Array.Copy(source, sourceOffset, m_data, 0, length);
        }

        internal void CopyTo(DType[] array, int offset, int length)
        {
            Array.Copy(m_data, 0, array, offset, length);
        }

        internal DType this[int index]
        {
            get
            {
                if (index < m_dataUsed) return m_data[index];
                return (IsNegative ? (DType)AllBits : (DType)0);
            }
            set { m_data[index] = value; }
        }

        private int m_dataUsed;
        internal int DataUsed
        {
            get { return m_dataUsed; }
            set { m_dataUsed = value; }
        }

        internal int Count
        {
            get { return m_data.Length; }
        }

        internal bool IsZero
        {
            get { return m_dataUsed == 0 || (m_dataUsed == 1 && m_data[0] == 0); }
        }

        internal bool IsNegative
        {
            get { return (m_data[m_data.Length - 1] & HiBitSet) == HiBitSet; }
        }

        internal void ResetDataUsed()
        {
            m_dataUsed = m_data.Length;
            if (IsNegative)
            {
                while (m_dataUsed > 1 && m_data[m_dataUsed - 1] == AllBits)
                {
                    --m_dataUsed;
                }
                m_dataUsed++;
            }
            else
            {
                while (m_dataUsed > 1 && m_data[m_dataUsed - 1] == 0)
                {
                    --m_dataUsed;
                }
                if (m_dataUsed == 0)
                {
                    m_dataUsed = 1;
                }
            }
        }

        internal int ShiftRight(int shiftCount)
        {
            return ShiftRight(m_data, shiftCount);
        }

        internal static int ShiftRight(DType[] buffer, int shiftCount)
        {
            int shiftAmount = DigitsArray.DataSizeBits;
            int invShift = 0;
            int bufLen = buffer.Length;

            while (bufLen > 1 && buffer[bufLen - 1] == 0)
            {
                bufLen--;
            }

            for (int count = shiftCount; count > 0; count -= shiftAmount)
            {
                if (count < shiftAmount)
                {
                    shiftAmount = count;
                    invShift = DigitsArray.DataSizeBits - shiftAmount;
                }

                ulong carry = 0;
                for (int i = bufLen - 1; i >= 0; i--)
                {
                    ulong val = ((ulong)buffer[i]) >> shiftAmount;
                    val |= carry;

                    carry = ((ulong)buffer[i]) << invShift;
                    buffer[i] = (DType)(val);
                }
            }

            while (bufLen > 1 && buffer[bufLen - 1] == 0)
            {
                bufLen--;
            }

            return bufLen;
        }

        internal int ShiftLeft(int shiftCount)
        {
            return ShiftLeft(m_data, shiftCount);
        }

        internal static int ShiftLeft(DType[] buffer, int shiftCount)
        {
            int shiftAmount = DigitsArray.DataSizeBits;
            int bufLen = buffer.Length;

            while (bufLen > 1 && buffer[bufLen - 1] == 0)
            {
                bufLen--;
            }

            for (int count = shiftCount; count > 0; count -= shiftAmount)
            {
                if (count < shiftAmount)
                {
                    shiftAmount = count;
                }

                ulong carry = 0;
                for (int i = 0; i < bufLen; i++)
                {
                    ulong val = ((ulong)buffer[i]) << shiftAmount;
                    val |= carry;

                    buffer[i] = (DType)(val & DigitsArray.AllBits);
                    carry = (val >> DigitsArray.DataSizeBits);
                }

                if (carry != 0)
                {
                    if (bufLen + 1 <= buffer.Length)
                    {
                        buffer[bufLen] = (DType)carry;
                        bufLen++;
                        carry = 0;
                    }
                    else
                    {
                        throw new OverflowException();
                    }
                }
            }
            return bufLen;
        }

        internal int ShiftLeftWithoutOverflow(int shiftCount)
        {
            List<DType> temporary = new List<DType>(m_data);
            int shiftAmount = DigitsArray.DataSizeBits;

            for (int count = shiftCount; count > 0; count -= shiftAmount)
            {
                if (count < shiftAmount)
                {
                    shiftAmount = count;
                }

                ulong carry = 0;
                for (int i = 0; i < temporary.Count; i++)
                {
                    ulong val = ((ulong)temporary[i]) << shiftAmount;
                    val |= carry;

                    temporary[i] = (DType)(val & DigitsArray.AllBits);
                    carry = (val >> DigitsArray.DataSizeBits);
                }

                if (carry != 0)
                {
                    temporary.Add(0);
                    temporary[temporary.Count - 1] = (DType)carry;
                }
            }
            m_data = new DType[temporary.Count];
            temporary.CopyTo(m_data);
            return m_data.Length;
        }
    }
    #endregion

	/// <summary>
	/// Represents a integer of abitrary length.
	/// </summary>
	/// <remarks>
	/// <para>
	/// A BigInteger object is immutable like System.String. The object can not be modifed, and new BigInteger objects are
	/// created by using the operations of existing BigInteger objects.
	/// </para>
	/// <para>
	/// Internally a BigInteger object is an array of ? that is represents the digits of the n-place integer. Negative BigIntegers
	/// are stored internally as 1's complements, thus every BigInteger object contains 1 or more padding elements to hold the sign.
	/// </para>
	/// </remarks>
	/// <example>
	/// <code>
	/// public class MainProgram
	/// {
	///		[STAThread]
	///		public static void Main(string[] args)
	///		{
	///			BigInteger a = new BigInteger(25);
	///			a = a + 100;
	///			
	///			BigInteger b = new BigInteger("139435810094598308945890230913");
	///			
	///			BigInteger c = b / a;
	///			BigInteger d = b % a;
	///			
	///			BigInteger e = (c * a) + d;
	///			if (e != b)
	///			{
	///				Console.WriteLine("Can never be true.");
	///			}
	///		}
	///	</code>
	/// </example>
	public class BigInteger
	{
		private DigitsArray m_digits;

		#region Constructors
		/// <summary>
		/// Create a BigInteger with an integer value of 0.
		/// </summary>
		public BigInteger()
		{
			m_digits = new DigitsArray(1, 1);
		}

		/// <summary>
		/// Creates a BigInteger with the value of the operand.
		/// </summary>
		/// <param name="number">A long.</param>
		public BigInteger(long number)
		{
			m_digits = new DigitsArray((8 / DigitsArray.DataSizeOf) + 1, 0);
			while (number != 0 && m_digits.DataUsed < m_digits.Count)
			{
				m_digits[m_digits.DataUsed] = (DType)(number & DigitsArray.AllBits);
				number >>= DigitsArray.DataSizeBits;
				m_digits.DataUsed++;
			}
			m_digits.ResetDataUsed();
		}

		/// <summary>
		/// Creates a BigInteger with the value of the operand. Can never be negative.
		/// </summary>
		/// <param name="number">A unsigned long.</param>
		public BigInteger(ulong number)
		{
			m_digits = new DigitsArray((8 / DigitsArray.DataSizeOf) + 1, 0);
			while (number != 0 && m_digits.DataUsed < m_digits.Count)
			{
				m_digits[m_digits.DataUsed] = (DType)(number & DigitsArray.AllBits);
				number >>= DigitsArray.DataSizeBits;
				m_digits.DataUsed++;
			}
			m_digits.ResetDataUsed();
		}

		/// <summary>
		/// Creates a BigInteger initialized from the byte array.
		/// </summary>
		/// <param name="array"></param>
		public BigInteger(byte[] array)
		{
			ConstructFrom(array, 0, array.Length);
		}

		/// <summary>
		/// Creates a BigInteger initialized from the byte array ending at <paramref name="length" />.
		/// </summary>
		/// <param name="array">A byte array.</param>
		/// <param name="length">Int number of bytes to use.</param>
		public BigInteger(byte[] array, int length)
		{
			ConstructFrom(array, 0, length);
		}

		/// <summary>
		/// Creates a BigInteger initialized from <paramref name="length" /> bytes starting at <paramref name="offset" />.
		/// </summary>
		/// <param name="array">A byte array.</param>
		/// <param name="offset">Int offset into the <paramref name="array" />.</param>
		/// <param name="length">Int number of bytes.</param>
		public BigInteger(byte[] array, int offset, int length)
		{
			ConstructFrom(array, offset, length);
		}

		private void ConstructFrom(byte[] array, int offset, int length)
		{
			if (array == null)
			{
				throw new ArgumentNullException("array");
			}
			if (offset > array.Length || length > array.Length)
			{
				throw new ArgumentOutOfRangeException("offset");
			}
			if (length > array.Length || (offset + length) > array.Length)
			{
				throw new ArgumentOutOfRangeException("length");
			}

			int estSize = length / 4;
			int leftOver = length & 3;
			if (leftOver != 0)
			{
				++estSize;
			}

			m_digits = new DigitsArray(estSize + 1, 0); // alloc one extra since we can't init -'s from here.

			for (int i = offset + length - 1, j = 0; (i - offset) >= 3; i -= 4, j++)
			{
				m_digits[j] = (DType)((array[i - 3] << 24) + (array[i - 2] << 16) + (array[i - 1] <<  8) + array[i]);
				m_digits.DataUsed++;
			}
			
            DType accumulator = 0;
            for (int i = leftOver; i > 0; i--)
            {
                DType digit = array[offset + leftOver - i];
                digit = (digit << ((i - 1) * 8));
                accumulator |= digit;
            }
            m_digits[m_digits.DataUsed] = accumulator;

            m_digits.ResetDataUsed();
		}

		/// <summary>
		/// Creates a BigInteger in base-10 from the parameter.
		/// </summary>
		/// <remarks>
		///  The new BigInteger is negative if the <paramref name="digits" /> has a leading - (minus).
		/// </remarks>
		/// <param name="digits">A string</param>
		public BigInteger(string digits)
		{
			Construct(digits, 10);
		}

		/// <summary>
		/// Creates a BigInteger in base and value from the parameters.
		/// </summary>
		/// <remarks>
		///  The new BigInteger is negative if the <paramref name="digits" /> has a leading - (minus).
		/// </remarks>
		/// <param name="digits">A string</param>
		/// <param name="radix">A int between 2 and 36.</param>
		public BigInteger(string digits, int radix)
		{
			Construct(digits, radix);
		}

		private void Construct(string digits, int radix)
		{
			if (digits == null)
			{
				throw new ArgumentNullException("digits");
			}

			BigInteger multiplier = new BigInteger(1);
			BigInteger result = new BigInteger();
			digits = digits.ToUpper(System.Globalization.CultureInfo.CurrentCulture).Trim();
			
			int nDigits = (digits[0] == '-' ? 1 : 0);

			for (int idx = digits.Length - 1; idx >= nDigits ; idx--)
			{
				int d = (int)digits[idx];
				if (d >= '0' && d <= '9')
				{
					d -= '0';
				}
				else if (d >= 'A' && d <= 'Z')
				{
					d = (d - 'A') + 10;
				}
				else
				{
					throw new ArgumentOutOfRangeException("digits");
				}

				if (d >= radix)
				{
					throw new ArgumentOutOfRangeException("digits");
				}
				result += (multiplier * d);
				multiplier *= radix;
			}

			if (digits[0] == '-')
			{
				result = -result;
			}

			this.m_digits = result.m_digits;
		}

		/// <summary>
		/// Copy constructor, doesn't copy the digits parameter, assumes <code>this</code> owns the DigitsArray.
		/// </summary>
		/// <remarks>The <paramef name="digits" /> parameter is saved and reset.</remarks>
		/// <param name="digits"></param>
		private BigInteger(DigitsArray digits)
		{
			digits.ResetDataUsed();
			this.m_digits = digits;
		}
		#endregion

		#region Public Properties
		/// <summary>
		/// A bool value that is true when the BigInteger is negative (less than zero).
		/// </summary>
		/// <value>
		/// A bool value that is true when the BigInteger is negative (less than zero).
		/// </value>
		public bool IsNegative { get { return m_digits.IsNegative; } }

		/// <summary>
		/// A bool value that is true when the BigInteger is exactly zero.
		/// </summary>
		/// <value>
		/// A bool value that is true when the BigInteger is exactly zero.
		/// </value>
		public bool IsZero { get { return m_digits.IsZero; } }
		#endregion

		#region Implicit Type Operators Overloads

		/// <summary>
		/// Creates a BigInteger from a long.
		/// </summary>
		/// <param name="value">A long.</param>
		/// <returns>A BigInteger initialzed by <paramref name="value" />.</returns>
		public static implicit operator BigInteger(long value)
		{
			return (new BigInteger(value));
		}

		/// <summary>
		/// Creates a BigInteger from a ulong.
		/// </summary>
		/// <param name="value">A ulong.</param>
		/// <returns>A BigInteger initialzed by <paramref name="value" />.</returns>
		public static implicit operator BigInteger(ulong value)
		{
			return (new BigInteger(value));
		}

		/// <summary>
		/// Creates a BigInteger from a int.
		/// </summary>
		/// <param name="value">A int.</param>
		/// <returns>A BigInteger initialzed by <paramref name="value" />.</returns>
		public static implicit operator BigInteger(int value)
		{
			return (new BigInteger((long)value));
		}

		/// <summary>
		/// Creates a BigInteger from a uint.
		/// </summary>
		/// <param name="value">A uint.</param>
		/// <returns>A BigInteger initialzed by <paramref name="value" />.</returns>
		public static implicit operator BigInteger(uint value)
		{
			return (new BigInteger((ulong)value));
		}
		#endregion

		#region Addition and Subtraction Operator Overloads
		/// <summary>
		/// Adds two BigIntegers and returns a new BigInteger that represents the sum.
		/// </summary>
		/// <param name="leftSide">A BigInteger</param>
		/// <param name="rightSide">A BigInteger</param>
		/// <returns>The BigInteger result of adding <paramref name="leftSide" /> and <paramref name="rightSide" />.</returns>
		public static BigInteger operator + (BigInteger leftSide, BigInteger rightSide)
		{
			int size = System.Math.Max(leftSide.m_digits.DataUsed, rightSide.m_digits.DataUsed);
			DigitsArray da = new DigitsArray(size + 1);

			long carry = 0;
			for (int i = 0; i < da.Count; i++)
			{
				long sum = (long)leftSide.m_digits[i] + (long)rightSide.m_digits[i] + carry;
				carry  = (long)(sum >> DigitsArray.DataSizeBits);
				da[i] = (DType)(sum & DigitsArray.AllBits);
			}

			return new BigInteger(da);
		}

		/// <summary>
		/// Adds two BigIntegers and returns a new BigInteger that represents the sum.
		/// </summary>
		/// <param name="leftSide">A BigInteger</param>
		/// <param name="rightSide">A BigInteger</param>
		/// <returns>The BigInteger result of adding <paramref name="leftSide" /> and <paramref name="rightSide" />.</returns>
		public static BigInteger Add(BigInteger leftSide, BigInteger rightSide)
		{
			return leftSide - rightSide;
		}

		/// <summary>
		/// Increments the BigInteger operand by 1.
		/// </summary>
		/// <param name="leftSide">The BigInteger operand.</param>
		/// <returns>The value of <paramref name="leftSide" /> incremented by 1.</returns>
		public static BigInteger operator ++ (BigInteger leftSide)
		{
			return (leftSide + 1);
		}

		/// <summary>
		/// Increments the BigInteger operand by 1.
		/// </summary>
		/// <param name="leftSide">The BigInteger operand.</param>
		/// <returns>The value of <paramref name="leftSide" /> incremented by 1.</returns>
		public static BigInteger Increment(BigInteger leftSide)
		{
			return (leftSide + 1);
		}

		/// <summary>
		/// Substracts two BigIntegers and returns a new BigInteger that represents the sum.
		/// </summary>
		/// <param name="leftSide">A BigInteger</param>
		/// <param name="rightSide">A BigInteger</param>
		/// <returns>The BigInteger result of substracting <paramref name="leftSide" /> and <paramref name="rightSide" />.</returns>
		public static BigInteger operator - (BigInteger leftSide, BigInteger rightSide)
		{
			int size = System.Math.Max(leftSide.m_digits.DataUsed, rightSide.m_digits.DataUsed) + 1;
			DigitsArray da = new DigitsArray(size);
			
			long carry = 0;
			for (int i = 0; i < da.Count; i++)
			{
				long diff = (long)leftSide.m_digits[i] - (long)rightSide.m_digits[i] - carry;
				da[i] = (DType)(diff & DigitsArray.AllBits);
				da.DataUsed++;
				carry = ((diff < 0) ? 1 : 0);
			}
			return new BigInteger(da);
		}

		/// <summary>
		/// Substracts two BigIntegers and returns a new BigInteger that represents the sum.
		/// </summary>
		/// <param name="leftSide">A BigInteger</param>
		/// <param name="rightSide">A BigInteger</param>
		/// <returns>The BigInteger result of substracting <paramref name="leftSide" /> and <paramref name="rightSide" />.</returns>
		public static BigInteger Subtract(BigInteger leftSide, BigInteger rightSide)
		{
			return leftSide - rightSide;
		}

		/// <summary>
		/// Decrements the BigInteger operand by 1.
		/// </summary>
		/// <param name="leftSide">The BigInteger operand.</param>
		/// <returns>The value of the <paramref name="leftSide" /> decremented by 1.</returns>
		public static BigInteger operator -- (BigInteger leftSide)
		{
			return (leftSide - 1);
		}

		/// <summary>
		/// Decrements the BigInteger operand by 1.
		/// </summary>
		/// <param name="leftSide">The BigInteger operand.</param>
		/// <returns>The value of the <paramref name="leftSide" /> decremented by 1.</returns>
		public static BigInteger Decrement(BigInteger leftSide)
		{
			return (leftSide - 1);
		}
		#endregion

		#region Negate Operator Overload
		/// <summary>
		/// Negates the BigInteger, that is, if the BigInteger is negative return a positive BigInteger, and if the
		/// BigInteger is negative return the postive.
		/// </summary>
		/// <param name="leftSide">A BigInteger operand.</param>
		/// <returns>The value of the <paramref name="this" /> negated.</returns>
		public static BigInteger operator - (BigInteger leftSide)
		{
			if (object.ReferenceEquals(leftSide, null))
			{
				throw new ArgumentNullException("leftSide");
			}

			if (leftSide.IsZero)
			{
				return new BigInteger(0);
			}

			DigitsArray da = new DigitsArray(leftSide.m_digits.DataUsed + 1, leftSide.m_digits.DataUsed + 1);

			for (int i = 0; i < da.Count; i++)
			{
				da[i] = (DType)(~(leftSide.m_digits[i]));
			}

			// add one to result (1's complement + 1)
			bool carry = true;
			int index = 0;
			while (carry && index < da.Count)
			{
				long val = (long)da[index] + 1;
				da[index] = (DType)(val & DigitsArray.AllBits);
				carry = ((val >> DigitsArray.DataSizeBits) > 0);
				index++;
			}

			return new BigInteger(da);
		}

		/// <summary>
		/// Negates the BigInteger, that is, if the BigInteger is negative return a positive BigInteger, and if the
		/// BigInteger is negative return the postive.
		/// </summary>
		/// <returns>The value of the <paramref name="this" /> negated.</returns>
		public BigInteger Negate()
		{
			return -this;
		}

		/// <summary>
		/// Creates a BigInteger absolute value of the operand.
		/// </summary>
		/// <param name="leftSide">A BigInteger.</param>
		/// <returns>A BigInteger that represents the absolute value of <paramref name="leftSide" />.</returns>
		public static BigInteger Abs(BigInteger leftSide)
		{
			if (object.ReferenceEquals(leftSide, null))
			{
				throw new ArgumentNullException("leftSide");
			}
			if (leftSide.IsNegative)
			{
				return -leftSide;
			}
			return leftSide;
		}
		#endregion

		#region Multiplication, Division and Modulus Operators
		/// <summary>
		/// Multiply two BigIntegers returning the result.
		/// </summary>
		/// <remarks>
		/// See Knuth.
		/// </remarks>
		/// <param name="leftSide">A BigInteger.</param>
		/// <param name="rightSide">A BigInteger</param>
		/// <returns></returns>
		public static BigInteger operator * (BigInteger leftSide, BigInteger rightSide)
		{
			if (object.ReferenceEquals(leftSide, null))
			{
				throw new ArgumentNullException("leftSide");
			}
			if (object.ReferenceEquals(rightSide, null))
			{
				throw new ArgumentNullException("rightSide");
			}

			bool leftSideNeg = leftSide.IsNegative;
			bool rightSideNeg = rightSide.IsNegative;

			leftSide = Abs(leftSide);
			rightSide = Abs(rightSide);

			DigitsArray da = new DigitsArray(leftSide.m_digits.DataUsed + rightSide.m_digits.DataUsed);
			da.DataUsed = da.Count;

			for (int i = 0; i < leftSide.m_digits.DataUsed; i++)
			{
				ulong carry = 0;
				for (int j = 0, k = i; j < rightSide.m_digits.DataUsed; j++, k++)
				{
					ulong val = ((ulong)leftSide.m_digits[i] * (ulong)rightSide.m_digits[j]) + (ulong)da[k] + carry;

					da[k] = (DType)(val & DigitsArray.AllBits);
					carry = (val >> DigitsArray.DataSizeBits);
				}

				if (carry != 0)
				{
					da[i + rightSide.m_digits.DataUsed] = (DType)carry;
				}
			}

			//da.ResetDataUsed();
			BigInteger result = new BigInteger(da);
			return (leftSideNeg != rightSideNeg ? -result : result);
		}

		/// <summary>
		/// Multiply two BigIntegers returning the result.
		/// </summary>
		/// <param name="leftSide">A BigInteger.</param>
		/// <param name="rightSide">A BigInteger</param>
		/// <returns></returns>
		public static BigInteger Multiply(BigInteger leftSide, BigInteger rightSide)
		{
			return leftSide * rightSide;
		}

		/// <summary>
		/// Divide a BigInteger by another BigInteger and returning the result.
		/// </summary>
		/// <param name="leftSide">A BigInteger divisor.</param>
		/// <param name="rightSide">A BigInteger dividend.</param>
		/// <returns>The BigInteger result.</returns>
		public static BigInteger operator / (BigInteger leftSide, BigInteger rightSide)
		{
			if (leftSide == null)
			{
				throw new ArgumentNullException("leftSide");
			}
			if (rightSide == null)
			{
				throw new ArgumentNullException("rightSide");
			}

			if (rightSide.IsZero)
			{
				throw new DivideByZeroException();
			}

			bool divisorNeg = rightSide.IsNegative;
			bool dividendNeg = leftSide.IsNegative;

			leftSide = Abs(leftSide);
			rightSide = Abs(rightSide);

			if (leftSide < rightSide)
			{
				return new BigInteger(0);
			}

			BigInteger quotient;
			BigInteger remainder;
			Divide(leftSide, rightSide, out quotient, out remainder);

			return (dividendNeg != divisorNeg ? -quotient : quotient);
		}

		/// <summary>
		/// Divide a BigInteger by another BigInteger and returning the result.
		/// </summary>
		/// <param name="leftSide">A BigInteger divisor.</param>
		/// <param name="rightSide">A BigInteger dividend.</param>
		/// <returns>The BigInteger result.</returns>
		public static BigInteger Divide(BigInteger leftSide, BigInteger rightSide)
		{
			return leftSide / rightSide;
		}

		private static void Divide(BigInteger leftSide, BigInteger rightSide, out BigInteger quotient, out BigInteger remainder)
		{
			if (leftSide.IsZero)
			{
				quotient = new BigInteger();
				remainder = new BigInteger();
				return;
			}

			if (rightSide.m_digits.DataUsed == 1)
			{
				SingleDivide(leftSide, rightSide, out quotient, out remainder);
			}
			else
			{
				MultiDivide(leftSide, rightSide, out quotient, out remainder);
			}
		}

		private static void MultiDivide(BigInteger leftSide, BigInteger rightSide, out BigInteger quotient, out BigInteger remainder)
		{
			if (rightSide.IsZero)
			{
				throw new DivideByZeroException();
			}

			DType val = rightSide.m_digits[rightSide.m_digits.DataUsed - 1];
			int d = 0;
			for (uint mask = DigitsArray.HiBitSet; mask != 0 && (val & mask) == 0; mask >>= 1)
			{
				d++;
			}

			int remainderLen = leftSide.m_digits.DataUsed + 1;
			DType[] remainderDat = new DType[remainderLen];
			leftSide.m_digits.CopyTo(remainderDat, 0, leftSide.m_digits.DataUsed);

			DigitsArray.ShiftLeft(remainderDat, d);
			rightSide = rightSide << d;

			ulong firstDivisor = rightSide.m_digits[rightSide.m_digits.DataUsed - 1];
			ulong secondDivisor = (rightSide.m_digits.DataUsed < 2 ? (DType)0 : rightSide.m_digits[rightSide.m_digits.DataUsed - 2]);

			int divisorLen = rightSide.m_digits.DataUsed + 1;
			DigitsArray dividendPart = new DigitsArray(divisorLen, divisorLen);
			DType[] result = new DType[leftSide.m_digits.Count + 1];
			int resultPos = 0;

			ulong carryBit = (ulong)0x1 << DigitsArray.DataSizeBits; // 0x100000000
			for (int j = remainderLen - rightSide.m_digits.DataUsed, pos = remainderLen - 1; j > 0; j--, pos--)
			{
				ulong dividend = ((ulong)remainderDat[pos] << DigitsArray.DataSizeBits) + (ulong)remainderDat[pos - 1];
				ulong qHat = (dividend / firstDivisor);
				ulong rHat = (dividend % firstDivisor);

				while (pos >= 2)
				{
					if (qHat == carryBit || (qHat * secondDivisor) > ((rHat << DigitsArray.DataSizeBits) + remainderDat[pos - 2]))
					{
						qHat--;
						rHat += firstDivisor;
						if (rHat < carryBit)
						{
							continue;
						}
					}
					break;
				}

				for (int h = 0; h < divisorLen; h++)
				{
					dividendPart[divisorLen - h - 1] = remainderDat[pos - h];
				}

				BigInteger dTemp = new BigInteger(dividendPart);
				BigInteger rTemp = rightSide * (long)qHat;
				while (rTemp > dTemp)
				{
					qHat--;
					rTemp -= rightSide;
				}

				rTemp = dTemp - rTemp;
				for (int h = 0; h < divisorLen; h++)
				{
					remainderDat[pos - h] = rTemp.m_digits[rightSide.m_digits.DataUsed - h];
				}

				result[resultPos++] = (DType)qHat;
			}

			Array.Reverse(result, 0, resultPos);
			quotient = new BigInteger(new DigitsArray(result));

			int n = DigitsArray.ShiftRight(remainderDat, d);
			DigitsArray rDA = new DigitsArray(n, n);
			rDA.CopyFrom(remainderDat, 0, 0, rDA.DataUsed);
			remainder = new BigInteger(rDA);
		}

		private static void SingleDivide(BigInteger leftSide, BigInteger rightSide, out BigInteger quotient, out BigInteger remainder)
		{
			if (rightSide.IsZero)
			{
				throw new DivideByZeroException();
			}

			DigitsArray remainderDigits = new DigitsArray(leftSide.m_digits);
			remainderDigits.ResetDataUsed();

			int pos = remainderDigits.DataUsed - 1;
			ulong divisor = (ulong)rightSide.m_digits[0];
			ulong dividend = (ulong)remainderDigits[pos];

			DType[] result = new DType[leftSide.m_digits.Count];
			leftSide.m_digits.CopyTo(result, 0, result.Length);
			int resultPos = 0;

			if (dividend >= divisor)
			{
				result[resultPos++] = (DType)(dividend / divisor);
				remainderDigits[pos] = (DType)(dividend % divisor);
			}
			pos--;

			while (pos >= 0)
			{
				dividend = ((ulong)(remainderDigits[pos + 1]) << DigitsArray.DataSizeBits) + (ulong)remainderDigits[pos];
				result[resultPos++] = (DType)(dividend / divisor);
				remainderDigits[pos + 1] = 0;
				remainderDigits[pos--] = (DType)(dividend % divisor);
			}
			remainder = new BigInteger(remainderDigits);

			DigitsArray quotientDigits = new DigitsArray(resultPos + 1, resultPos);
			int j = 0;
			for (int i = quotientDigits.DataUsed - 1; i >= 0; i--, j++)
			{
				quotientDigits[j] = result[i];
			}
			quotient = new BigInteger(quotientDigits);
		}

		/// <summary>
		/// Perform the modulus of a BigInteger with another BigInteger and return the result.
		/// </summary>
		/// <param name="leftSide">A BigInteger divisor.</param>
		/// <param name="rightSide">A BigInteger dividend.</param>
		/// <returns>The BigInteger result.</returns>
		public static BigInteger operator % (BigInteger leftSide, BigInteger rightSide)
		{
			if (leftSide == null)
			{
				throw new ArgumentNullException("leftSide");
			}

			if (rightSide == null)
			{
				throw new ArgumentNullException("rightSide");
			}

			if (rightSide.IsZero)
			{
				throw new DivideByZeroException();
			}

			BigInteger quotient;
			BigInteger remainder;

			bool dividendNeg = leftSide.IsNegative;
			leftSide = Abs(leftSide);
			rightSide = Abs(rightSide);

			if (leftSide < rightSide)
			{
				return leftSide;
			}

			Divide(leftSide, rightSide, out quotient, out remainder);

			return (dividendNeg ? -remainder : remainder);
		}

		/// <summary>
		/// Perform the modulus of a BigInteger with another BigInteger and return the result.
		/// </summary>
		/// <param name="leftSide">A BigInteger divisor.</param>
		/// <param name="rightSide">A BigInteger dividend.</param>
		/// <returns>The BigInteger result.</returns>
		public static BigInteger Modulus(BigInteger leftSide, BigInteger rightSide)
		{
			return leftSide % rightSide;
		}
		#endregion

		#region Bitwise Operator Overloads

		public static BigInteger operator & (BigInteger leftSide, BigInteger rightSide)
		{
			int len = System.Math.Max(leftSide.m_digits.DataUsed, rightSide.m_digits.DataUsed);
			DigitsArray da = new DigitsArray(len, len);
			for (int idx = 0; idx < len; idx++)
			{
				da[idx] = (DType)(leftSide.m_digits[idx] & rightSide.m_digits[idx]);
			}
			return new BigInteger(da);
		}

		public static BigInteger BitwiseAnd(BigInteger leftSide, BigInteger rightSide)
		{
			return leftSide & rightSide;
		}

		public static BigInteger operator | (BigInteger leftSide, BigInteger rightSide)
		{
			int len = System.Math.Max(leftSide.m_digits.DataUsed, rightSide.m_digits.DataUsed);
			DigitsArray da = new DigitsArray(len, len);
			for (int idx = 0; idx < len; idx++)
			{
				da[idx] = (DType)(leftSide.m_digits[idx] | rightSide.m_digits[idx]);
			}
			return new BigInteger(da);
		}

		public static BigInteger BitwiseOr(BigInteger leftSide, BigInteger rightSide)
		{
			return leftSide | rightSide;
		}

		public static BigInteger operator ^ (BigInteger leftSide, BigInteger rightSide)
		{
			int len = System.Math.Max(leftSide.m_digits.DataUsed, rightSide.m_digits.DataUsed);
			DigitsArray da = new DigitsArray(len, len);
			for (int idx = 0; idx < len; idx++)
			{
				da[idx] = (DType)(leftSide.m_digits[idx] ^ rightSide.m_digits[idx]);
			}
			return new BigInteger(da);
		}

		public static BigInteger Xor(BigInteger leftSide, BigInteger rightSide)
		{
			return leftSide ^ rightSide;
		}
		
		public static BigInteger operator ~ (BigInteger leftSide)
		{
			DigitsArray da = new DigitsArray(leftSide.m_digits.Count);
			for(int idx = 0; idx < da.Count; idx++)
			{
				da[idx] = (DType)(~(leftSide.m_digits[idx]));
			}

			return new BigInteger(da);
		}

		public static BigInteger OnesComplement(BigInteger leftSide)
		{
			return ~leftSide;
		}

		#endregion

		#region Left and Right Shift Operator Overloads
		public static BigInteger operator << (BigInteger leftSide, int shiftCount)
		{
			if (leftSide == null)
			{
				throw new ArgumentNullException("leftSide");
			}
			
			DigitsArray da = new DigitsArray(leftSide.m_digits);
			da.DataUsed = da.ShiftLeftWithoutOverflow(shiftCount);

			return new BigInteger(da);
		}

		public static BigInteger LeftShift(BigInteger leftSide, int shiftCount)
		{
			return leftSide << shiftCount;
		}

		public static BigInteger operator >> (BigInteger leftSide, int shiftCount)
		{
			if (leftSide == null)
			{
				throw new ArgumentNullException("leftSide");
			}

			DigitsArray da = new DigitsArray(leftSide.m_digits);
			da.DataUsed = da.ShiftRight(shiftCount);

			if (leftSide.IsNegative)
			{
				for (int i = da.Count - 1; i >= da.DataUsed; i--)
				{
					da[i] = DigitsArray.AllBits;
				}

				DType mask = DigitsArray.HiBitSet;
				for (int i = 0; i < DigitsArray.DataSizeBits; i++)
				{
					if ((da[da.DataUsed - 1] & mask) == DigitsArray.HiBitSet)
					{
						break;
					}
					da[da.DataUsed - 1] |= mask;
					mask >>= 1;
				}
				da.DataUsed = da.Count;
			}

			return new BigInteger(da);
		}

		public static BigInteger RightShift(BigInteger leftSide, int shiftCount)
		{
			if (leftSide == null)
			{
				throw new ArgumentNullException("leftSide");
			}

			return leftSide >> shiftCount;
		}
		#endregion

		#region Relational Operator Overloads

		/// <summary>
		/// Compare this instance to a specified object and returns indication of their relative value.
		/// </summary>
		/// <param name="value">An object to compare, or a null reference (<b>Nothing</b> in Visual Basic).</param>
		/// <returns>A signed number indicating the relative value of this instance and <i>value</i>.
		/// <list type="table">
		///		<listheader>
		///			<term>Return Value</term>
		///			<description>Description</description>
		///		</listheader>
		///		<item>
		///			<term>Less than zero</term>
		///			<description>This instance is less than <i>value</i>.</description>
		///		</item>
		///		<item>
		///			<term>Zero</term>
		///			<description>This instance is equal to <i>value</i>.</description>
		///		</item>
		///		<item>
		///			<term>Greater than zero</term>
		///			<description>
		///				This instance is greater than <i>value</i>. 
		///				<para>-or-</para>
		///				<i>value</i> is a null reference (<b>Nothing</b> in Visual Basic).
		///			</description>
		///		</item>
		/// </list>
		/// </returns>
		public int CompareTo(BigInteger value)
		{
			return Compare(this, value);
		}

		/// <summary>
		/// Compare two objects and return an indication of their relative value.
		/// </summary>
		/// <param name="leftSide">An object to compare, or a null reference (<b>Nothing</b> in Visual Basic).</param>
		/// <param name="rightSide">An object to compare, or a null reference (<b>Nothing</b> in Visual Basic).</param>
		/// <returns>A signed number indicating the relative value of this instance and <i>value</i>.
		/// <list type="table">
		///		<listheader>
		///			<term>Return Value</term>
		///			<description>Description</description>
		///		</listheader>
		///		<item>
		///			<term>Less than zero</term>
		///			<description>This instance is less than <i>value</i>.</description>
		///		</item>
		///		<item>
		///			<term>Zero</term>
		///			<description>This instance is equal to <i>value</i>.</description>
		///		</item>
		///		<item>
		///			<term>Greater than zero</term>
		///			<description>
		///				This instance is greater than <i>value</i>. 
		///				<para>-or-</para>
		///				<i>value</i> is a null reference (<b>Nothing</b> in Visual Basic).
		///			</description>
		///		</item>
		/// </list>
		/// </returns>
		public static int Compare(BigInteger leftSide, BigInteger rightSide)
		{
			if (object.ReferenceEquals(leftSide, rightSide))
			{
				return 0;
			}

			if (object.ReferenceEquals(leftSide, null))
			{
				throw new ArgumentNullException("leftSide");
			}

			if (object.ReferenceEquals(rightSide, null))
			{
				throw new ArgumentNullException("rightSide");
			}

			if (leftSide > rightSide) return 1;
			if (leftSide == rightSide) return 0;
			return -1;
		}

		public static bool operator == (BigInteger leftSide, BigInteger rightSide)
		{
			if (object.ReferenceEquals(leftSide, rightSide))
			{
				return true;
			}
			
			if (object.ReferenceEquals(leftSide, null ) || object.ReferenceEquals(rightSide, null ))
			{
				return false;
			}

			if (leftSide.IsNegative != rightSide.IsNegative)
			{
				return false;
			}
        
			return leftSide.Equals(rightSide);
		}

		public static bool operator != (BigInteger leftSide, BigInteger rightSide)
		{
			return !(leftSide == rightSide);
		}

		public static bool operator > (BigInteger leftSide, BigInteger rightSide)
		{
			if (object.ReferenceEquals(leftSide, null))
			{
				throw new ArgumentNullException("leftSide");
			}

			if (object.ReferenceEquals(rightSide, null))
			{
				throw new ArgumentNullException("rightSide");
			}

			if (leftSide.IsNegative != rightSide.IsNegative)
			{
				return rightSide.IsNegative;
			}

			if (leftSide.m_digits.DataUsed != rightSide.m_digits.DataUsed)
			{
				return leftSide.m_digits.DataUsed > rightSide.m_digits.DataUsed;
			}

			for (int idx = leftSide.m_digits.DataUsed - 1; idx >= 0; idx--)
			{
				if (leftSide.m_digits[idx] != rightSide.m_digits[idx])
				{
					return (leftSide.m_digits[idx] > rightSide.m_digits[idx]);
				}
			}
			return false;
		}

		public static bool operator < (BigInteger leftSide, BigInteger rightSide)
		{
			if (object.ReferenceEquals(leftSide, null))
			{
				throw new ArgumentNullException("leftSide");
			}

			if (object.ReferenceEquals(rightSide, null))
			{
				throw new ArgumentNullException("rightSide");
			}

			if (leftSide.IsNegative != rightSide.IsNegative)
			{
				return leftSide.IsNegative;
			}

			if (leftSide.m_digits.DataUsed != rightSide.m_digits.DataUsed)
			{
				return leftSide.m_digits.DataUsed < rightSide.m_digits.DataUsed;
			}
			
			for (int idx = leftSide.m_digits.DataUsed - 1; idx >= 0; idx--)
			{
				if (leftSide.m_digits[idx] != rightSide.m_digits[idx])
				{
					return (leftSide.m_digits[idx] < rightSide.m_digits[idx]);
				}
			}
			return false;
		}

		public static bool operator >= (BigInteger leftSide, BigInteger rightSide)
		{
			return Compare(leftSide, rightSide) >= 0;
		}

		public static bool operator <= (BigInteger leftSide, BigInteger rightSide)
		{
			return Compare(leftSide, rightSide) <= 0;
		}
		#endregion

		#region Object Overrides
		/// <summary>
		/// Determines whether two Object instances are equal.
		/// </summary>
		/// <param name="obj">An <see cref="System.Object">Object</see> to compare with this instance.</param>
		/// <returns></returns>
		/// <seealso cref="System.Object">System.Object</seealso> 
		public override bool Equals(object obj)
		{
			if (object.ReferenceEquals(obj, null))
			{
				return false;
			}

			if (object.ReferenceEquals(this, obj))
			{
				return true;
			}

			BigInteger c = (BigInteger)obj;
			if (this.m_digits.DataUsed != c.m_digits.DataUsed)
			{
				return false;
			}

			for (int idx = 0; idx < this.m_digits.DataUsed; idx++)
			{
				if (this.m_digits[idx] != c.m_digits[idx])
				{
					return false;
				}
			}
			return true;
		}

		/// <summary>
		/// Returns the hash code for this instance.
		/// </summary>
		/// <returns>A 32-bit signed integer has code.</returns>
		/// <seealso cref="System.Object">System.Object</seealso> 
		public override int GetHashCode()
		{
			return this.m_digits.GetHashCode();
		}

		/// <summary>
		/// Converts the numeric value of this instance to its equivalent base 10 string representation.
		/// </summary>
		/// <returns>A <see cref="System.String">String</see> in base 10.</returns>
		/// <seealso cref="System.Object">System.Object</seealso> 
		public override string ToString()
		{
			return ToString(10);
		}
		#endregion

		#region Type Conversion Methods
		/// <summary>
		/// Converts the numeric value of this instance to its equivalent string representation in specified base.
		/// </summary>
		/// <param name="radix">Int radix between 2 and 36</param>
		/// <returns>A string.</returns>
		public string ToString(int radix)
		{
			if (radix < 2 || radix > 36)
			{
				throw new ArgumentOutOfRangeException("radix");
			}

			if (IsZero)
			{
				return "0";
			}

			BigInteger a = this;
			bool negative = a.IsNegative;
			a = Abs(this);

			BigInteger quotient;
			BigInteger remainder;
			BigInteger biRadix = new BigInteger(radix);

			const string charSet = "0123456789abcdefghijklmnopqrstuvwxyz";
			System.Collections.ArrayList al = new System.Collections.ArrayList();
			while (a.m_digits.DataUsed > 1 || (a.m_digits.DataUsed == 1 && a.m_digits[0] != 0))
			{
				Divide(a, biRadix, out quotient, out remainder);
				al.Insert(0, charSet[(int)remainder.m_digits[0]]);
				a = quotient;
			}

			string result = new String((char[])al.ToArray(typeof(char)));
			if (radix == 10 && negative)
			{
				return "-" + result;
			}

			return result;
		}

		/// <summary>
		/// Returns string in hexidecimal of the internal digit representation.
		/// </summary>
		/// <remarks>
		/// This is not the same as ToString(16). This method does not return the sign, but instead
		/// dumps the digits array into a string representation in base 16.
		/// </remarks>
		/// <returns>A string in base 16.</returns>
		public string ToHexString()
		{
			System.Text.StringBuilder sb = new System.Text.StringBuilder();
			sb.AppendFormat("{0:X}", m_digits[m_digits.DataUsed - 1]);
			
            string f = "{0:X" + (2 * DigitsArray.DataSizeOf) + "}";
			for (int i = m_digits.DataUsed - 2; i >= 0; i--)
			{
				sb.AppendFormat(f, m_digits[i]);
			}

			return sb.ToString();
		}

		/// <summary>
		/// Returns BigInteger as System.Int16 if possible.
		/// </summary>
		/// <param name="value"></param>
		/// <returns>Int value of BigInteger</returns>
		/// <exception cref="System.Exception">When BigInteger is too large to fit into System.Int16</exception>
		public static int ToInt16(BigInteger value)
		{
			if (object.ReferenceEquals(value, null))
			{
				throw new ArgumentNullException("value");
			}
			return System.Int16.Parse(value.ToString(), System.Globalization.NumberStyles.Integer, System.Globalization.CultureInfo.CurrentCulture);
		}

		/// <summary>
		/// Returns BigInteger as System.UInt16 if possible.
		/// </summary>
		/// <param name="value"></param>
		/// <returns></returns>
		/// <exception cref="System.Exception">When BigInteger is too large to fit into System.UInt16</exception>
		public static uint ToUInt16(BigInteger value)
		{
			if (object.ReferenceEquals(value, null))
			{
				throw new ArgumentNullException("value");
			}
			return System.UInt16.Parse(value.ToString(), System.Globalization.NumberStyles.Integer, System.Globalization.CultureInfo.CurrentCulture);
		}

		/// <summary>
		/// Returns BigInteger as System.Int32 if possible.
		/// </summary>
		/// <param name="value"></param>
		/// <returns></returns>
		/// <exception cref="System.Exception">When BigInteger is too large to fit into System.Int32</exception>
		public static int ToInt32(BigInteger value)
		{
			if (object.ReferenceEquals(value, null))
			{
				throw new ArgumentNullException("value");
			}
			return System.Int32.Parse(value.ToString(), System.Globalization.NumberStyles.Integer, System.Globalization.CultureInfo.CurrentCulture);
		}

		/// <summary>
		/// Returns BigInteger as System.UInt32 if possible.
		/// </summary>
		/// <param name="value"></param>
		/// <returns></returns>
		/// <exception cref="System.Exception">When BigInteger is too large to fit into System.UInt32</exception>
		public static uint ToUInt32(BigInteger value)
		{
			if (object.ReferenceEquals(value, null))
			{
				throw new ArgumentNullException("value");
			}
			return System.UInt32.Parse(value.ToString(), System.Globalization.NumberStyles.Integer, System.Globalization.CultureInfo.CurrentCulture);
		}

		/// <summary>
		/// Returns BigInteger as System.Int64 if possible.
		/// </summary>
		/// <param name="value"></param>
		/// <returns></returns>
		/// <exception cref="System.Exception">When BigInteger is too large to fit into System.Int64</exception>
		public static long ToInt64(BigInteger value)
		{
			if (object.ReferenceEquals(value, null))
			{
				throw new ArgumentNullException("value");
			}
			return System.Int64.Parse(value.ToString(), System.Globalization.NumberStyles.Integer, System.Globalization.CultureInfo.CurrentCulture);
		}

		/// <summary>
		/// Returns BigInteger as System.UInt64 if possible.
		/// </summary>
		/// <param name="value"></param>
		/// <returns></returns>
		/// <exception cref="System.Exception">When BigInteger is too large to fit into System.UInt64</exception>
		public static ulong ToUInt64(BigInteger value)
		{
			if (object.ReferenceEquals(value, null))
			{
				throw new ArgumentNullException("value");
			}
			return System.UInt64.Parse(value.ToString(), System.Globalization.NumberStyles.Integer, System.Globalization.CultureInfo.CurrentCulture);
		}

        internal object ToString(string v)
        {
            throw new NotImplementedException();
        }
        #endregion
    }
}