using System;

using System.Collections.Generic;

//** BigInteger implementation for .net35 from https://github.com/keiwando/biginteger

/** Based on BigInteger.cs by ScottGarland from http://biginteger.codeplex.com/ */

namespace SharpDPAPI

{

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 - 1, 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 string GetDataAsString()

{

string result = "";

foreach (DType data in m_data) {

result += data + " ";

}

return result;

}

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;

}

}

m_dataUsed = System.Math.Min(m_data.Length, m_dataUsed);

}

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)

{

if (shiftCount == 0) return m_data.Length;

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)

{

DType lastNum = (DType)carry;

if (IsNegative)

{

int byteCount = (int)Math.Floor(Math.Log(carry, 2));

lastNum = (0xffffffff << byteCount) | (DType)carry;

}

temporary.Add(lastNum);

}

}

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