text:
using System;
using System.Text.RegularExpressions;
using System.Collections;
using System.Text;
using System.Collections.Generic;

namespace System
{
	/// <summary>
	/// Numeric class which represents arbitrary-precision integers.
	/// (c) Andriy Kozachuk a.k.a. Oyster [dev.oyster@gmail.com] 2005-2010
	/// </summary>
	public sealed class IntX :
		IEquatable<IntX>, IEquatable<int>, IEquatable<uint>, IEquatable<long>, IEquatable<ulong>,
		IComparable, IComparable<IntX>, IComparable<int>, IComparable<uint>, IComparable<long>, IComparable<ulong>,
        IDisposable, ICloneable
    {

        #region Internal Classes

        #region IntXDivider
        internal static class IntXDivider
        {
            /// <summary>
            /// Returns true if it's better to use classic algorithm for given big integers.
            /// </summary>
            /// <param name="length1">First big integer length.</param>
            /// <param name="length2">Second big integer length.</param>
            /// <returns>True if classic algorithm is better.</returns>
            private static bool IsClassicAlgorithmNeeded(uint length1, uint length2)
            {
                return
                    length1 < Constants.AutoNewtonLengthLowerBound || length2 < Constants.AutoNewtonLengthLowerBound ||
                    length1 > Constants.AutoNewtonLengthUpperBound || length2 > Constants.AutoNewtonLengthUpperBound;
            }

            /// <summary>
            /// Divides two big integers.
            /// Also modifies <paramref name="digits1" /> and <paramref name="length1"/> (it will contain remainder).
            /// </summary>
            /// <param name="digits1">First big integer digits.</param>
            /// <param name="digitsBuffer1">Buffer for first big integer digits. May also contain remainder. Can be null - in this case it's created if necessary.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="digits2">Second big integer digits.</param>
            /// <param name="digitsBuffer2">Buffer for second big integer digits. Only temporarily used. Can be null - in this case it's created if necessary.</param>
            /// <param name="length2">Second big integer length.</param>
            /// <param name="digitsRes">Resulting big integer digits.</param>
            /// <param name="resultFlags">Which operation results to return.</param>
            /// <param name="cmpResult">Big integers comparsion result (pass -2 if omitted).</param>
            /// <returns>Resulting big integer length.</returns>
            public static unsafe uint DivMod(uint[] digits1, uint[] digitsBuffer1, ref uint length1, uint[] digits2, uint[] digitsBuffer2, uint length2, uint[] digitsRes, DivModResultFlags resultFlags, int cmpResult)
            {
                // Maybe immediately use classic algorithm here
                if (IsClassicAlgorithmNeeded(length1, length2))
                {
                    return ClassicDivMod(digits1, digitsBuffer1, ref length1, digits2, digitsBuffer2, length2, digitsRes, resultFlags, cmpResult);
                }

                // Create some buffers if necessary
                if (digitsBuffer1 == null)
                {
                    digitsBuffer1 = new uint[length1 + 1];
                }

                fixed (uint* digitsPtr1 = digits1, digitsBufferPtr1 = digitsBuffer1, digitsPtr2 = digits2, digitsBufferPtr2 = digitsBuffer2 != null ? digitsBuffer2 : digits1, digitsResPtr = digitsRes != null ? digitsRes : digits1)
                {
                    return DivMod(
                        digitsPtr1,
                        digitsBufferPtr1,
                        ref length1,
                        digitsPtr2,
                        digitsBufferPtr2 == digitsPtr1 ? null : digitsBufferPtr2,
                        length2,
                        digitsResPtr == digitsPtr1 ? null : digitsResPtr,
                        resultFlags,
                        cmpResult);
                }
            }

            /// <summary>
            /// Divides two big integers.
            /// Also modifies <paramref name="digitsPtr1" /> and <paramref name="length1"/> (it will contain remainder).
            /// </summary>
            /// <param name="digitsPtr1">First big integer digits.</param>
            /// <param name="digitsBufferPtr1">Buffer for first big integer digits. May also contain remainder.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="digitsPtr2">Second big integer digits.</param>
            /// <param name="digitsBufferPtr2">Buffer for second big integer digits. Only temporarily used.</param>
            /// <param name="length2">Second big integer length.</param>
            /// <param name="digitsResPtr">Resulting big integer digits.</param>
            /// <param name="resultFlags">Which operation results to return.</param>
            /// <param name="cmpResult">Big integers comparsion result (pass -2 if omitted).</param>
            /// <returns>Resulting big integer length.</returns>
            public static unsafe uint DivMod(uint* digitsPtr1, uint* digitsBufferPtr1, ref uint length1, uint* digitsPtr2, uint* digitsBufferPtr2, uint length2, uint* digitsResPtr, DivModResultFlags resultFlags, int cmpResult)
            {
                // Maybe immediately use classic algorithm here
                if (IsClassicAlgorithmNeeded(length1, length2))
                {
                    return ClassicDivMod(digitsPtr1, digitsBufferPtr1, ref length1, digitsPtr2, digitsBufferPtr2, length2, digitsResPtr, resultFlags, cmpResult);
                }

                // Call base (for special cases)
                uint resultLength = BaseDivMod(digitsPtr1, digitsBufferPtr1, ref length1, digitsPtr2, digitsBufferPtr2, length2, digitsResPtr, resultFlags, cmpResult);
                if (resultLength != uint.MaxValue)
                    return resultLength;

                // First retrieve opposite for the divider
                uint int2OppositeLength;
                ulong int2OppositeRightShift;
                uint[] int2OppositeDigits = NewtonHelper.GetIntegerOpposite(digitsPtr2, length2, length1, digitsBufferPtr1, out int2OppositeLength, out int2OppositeRightShift);

                // We will need to muptiply it by divident now to receive quotient.
                // Prepare digits for multiply result
                uint quotLength;
                uint[] quotDigits = new uint[length1 + int2OppositeLength];

                // Fix some arrays
                fixed (uint* oppositePtr = int2OppositeDigits, quotPtr = quotDigits)
                {
                    // Multiply
                    quotLength = IntXMultiplier.Multiply(oppositePtr, int2OppositeLength, digitsPtr1, length1, quotPtr);

                    // Calculate shift
                    uint shiftOffset = (uint)(int2OppositeRightShift / Constants.DigitBitCount);
                    int shiftCount = (int)(int2OppositeRightShift % Constants.DigitBitCount);

                    // Get the very first bit of the shifted part
                    uint highestLostBit;
                    if (shiftCount == 0)
                    {
                        highestLostBit = quotPtr[shiftOffset - 1] >> 31;
                    }
                    else
                    {
                        highestLostBit = quotPtr[shiftOffset] >> (shiftCount - 1) & 1U;
                    }

                    // After this result must be shifted to the right - this is required
                    quotLength = DigitOpHelper.Shr(quotPtr + shiftOffset, quotLength - shiftOffset, quotPtr, shiftCount, false);

                    // Maybe quotient must be corrected
                    if (highestLostBit == 1U)
                    {
                        quotLength = DigitOpHelper.Add(quotPtr, quotLength, &highestLostBit, 1U, quotPtr);
                    }

                    // Check quotient - finally it might be too big.
                    // For this we must multiply quotient by divider
                    uint quotDivLength;
                    uint[] quotDivDigits = new uint[quotLength + length2];
                    fixed (uint* quotDivPtr = quotDivDigits)
                    {
                        quotDivLength = IntXMultiplier.Multiply(quotPtr, quotLength, digitsPtr2, length2, quotDivPtr);

                        int cmpRes = DigitOpHelper.Cmp(quotDivPtr, quotDivLength, digitsPtr1, length1);
                        if (cmpRes > 0)
                        {
                            highestLostBit = 1;
                            quotLength = DigitOpHelper.Sub(quotPtr, quotLength, &highestLostBit, 1U, quotPtr);
                            quotDivLength = DigitOpHelper.Sub(quotDivPtr, quotDivLength, digitsPtr2, length2, quotDivPtr);
                        }

                        // Now everything is ready and prepared to return results

                        // First maybe fill remainder
                        if ((resultFlags & DivModResultFlags.Mod) != 0)
                        {
                            length1 = DigitOpHelper.Sub(digitsPtr1, length1, quotDivPtr, quotDivLength, digitsBufferPtr1);
                        }

                        // And finally fill quotient
                        if ((resultFlags & DivModResultFlags.Div) != 0)
                        {
                            DigitHelper.DigitsBlockCopy(quotPtr, digitsResPtr, quotLength);
                        }
                        else
                        {
                            quotLength = 0;
                        }

                        // Return some arrays to pool
                        ArrayPool<uint>.Instance.AddArray(int2OppositeDigits);

                        return quotLength;
                    }
                }
            }

            /// <summary>
            /// Divides one <see cref="IntX" /> by another.
            /// </summary>
            /// <param name="int1">First big integer.</param>
            /// <param name="int2">Second big integer.</param>
            /// <param name="modRes">Remainder big integer.</param>
            /// <param name="resultFlags">Which operation results to return.</param>
            /// <returns>Divident big integer.</returns>
            /// <exception cref="ArgumentNullException"><paramref name="int1" /> or <paramref name="int2" /> is a null reference.</exception>
            /// <exception cref="DivideByZeroException"><paramref name="int2" /> equals zero.</exception>
            public static IntX DivMod(IntX int1, IntX int2, out IntX modRes, DivModResultFlags resultFlags)
            {
                // Null reference exceptions
                if (ReferenceEquals(int1, null))
                {
                    throw new ArgumentNullException("int1", "Operands can't be null.");
                }
                else if (ReferenceEquals(int2, null))
                {
                    throw new ArgumentNullException("int2", "Operands can't be null.");
                }

                // Check if int2 equals zero
                if (int2._length == 0)
                {
                    throw new DivideByZeroException();
                }

                // Get flags
                bool divNeeded = (resultFlags & DivModResultFlags.Div) != 0;
                bool modNeeded = (resultFlags & DivModResultFlags.Mod) != 0;

                // Special situation: check if int1 equals zero; in this case zero is always returned
                if (int1._length == 0)
                {
                    modRes = modNeeded ? new IntX() : null;
                    return divNeeded ? new IntX() : null;
                }

                // Special situation: check if int2 equals one - nothing to divide in this case
                if (int2._length == 1 && int2._digits[0] == 1)
                {
                    modRes = modNeeded ? new IntX() : null;
                    return divNeeded ? int2._negative ? -int1 : +int1 : null;
                }

                // Get resulting sign
                bool resultNegative = int1._negative ^ int2._negative;

                // Check if int1 > int2
                int compareResult = DigitOpHelper.Cmp(int1._digits, int1._length, int2._digits, int2._length);
                if (compareResult < 0)
                {
                    modRes = modNeeded ? new IntX(int1) : null;
                    return divNeeded ? new IntX() : null;
                }
                else if (compareResult == 0)
                {
                    modRes = modNeeded ? new IntX() : null;
                    return divNeeded ? new IntX(resultNegative ? -1 : 1) : null;
                }

                //
                // Actually divide here (by Knuth algorithm)
                //

                // Prepare divident (if needed)
                IntX divRes = null;
                if (divNeeded)
                {
                    divRes = new IntX(int1._length - int2._length + 1U, resultNegative);
                }

                // Prepare mod (if needed)
                if (modNeeded)
                {
                    modRes = new IntX(int1._length + 1U, int1._negative);
                }
                else
                {
                    modRes = null;
                }

                // Call procedure itself
                uint modLength = int1._length;
                uint divLength = DivMod(
                    int1._digits,
                    modNeeded ? modRes._digits : null,
                    ref modLength,
                    int2._digits,
                    null,
                    int2._length,
                    divNeeded ? divRes._digits : null,
                    resultFlags,
                    compareResult);

                // Maybe set new lengths and perform normalization
                if (divNeeded)
                {
                    divRes._length = divLength;
                    divRes.TryNormalize();
                }
                if (modNeeded)
                {
                    modRes._length = modLength;
                    modRes.TryNormalize();
                }

                // Return div
                return divRes;
            }

            /// <summary>
            /// Divides two big integers.
            /// Also modifies <paramref name="digits1" /> and <paramref name="length1"/> (it will contain remainder).
            /// </summary>
            /// <param name="digits1">First big integer digits.</param>
            /// <param name="digitsBuffer1">Buffer for first big integer digits. May also contain remainder. Can be null - in this case it's created if necessary.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="digits2">Second big integer digits.</param>
            /// <param name="digitsBuffer2">Buffer for second big integer digits. Only temporarily used. Can be null - in this case it's created if necessary.</param>
            /// <param name="length2">Second big integer length.</param>
            /// <param name="digitsRes">Resulting big integer digits.</param>
            /// <param name="resultFlags">Which operation results to return.</param>
            /// <param name="cmpResult">Big integers comparsion result (pass -2 if omitted).</param>
            /// <returns>Resulting big integer length.</returns>
            public static unsafe uint ClassicDivMod(uint[] digits1, uint[] digitsBuffer1, ref uint length1, uint[] digits2, uint[] digitsBuffer2, uint length2, uint[] digitsRes, DivModResultFlags resultFlags, int cmpResult)
            {
                // Create some buffers if necessary
                if (digitsBuffer1 == null)
                {
                    digitsBuffer1 = new uint[length1 + 1];
                }
                if (digitsBuffer2 == null)
                {
                    digitsBuffer2 = new uint[length2];
                }

                fixed (uint* digitsPtr1 = digits1, digitsBufferPtr1 = digitsBuffer1, digitsPtr2 = digits2, digitsBufferPtr2 = digitsBuffer2, digitsResPtr = digitsRes != null ? digitsRes : digits1)
                {
                    return DivMod(
                        digitsPtr1,
                        digitsBufferPtr1,
                        ref length1,
                        digitsPtr2,
                        digitsBufferPtr2,
                        length2,
                        digitsResPtr == digitsPtr1 ? null : digitsResPtr,
                        resultFlags,
                        cmpResult);
                }
            }

            /// <summary>
            /// Divides two big integers.
            /// Also modifies <paramref name="digitsPtr1" /> and <paramref name="length1"/> (it will contain remainder).
            /// </summary>
            /// <param name="digitsPtr1">First big integer digits.</param>
            /// <param name="digitsBufferPtr1">Buffer for first big integer digits. May also contain remainder.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="digitsPtr2">Second big integer digits.</param>
            /// <param name="digitsBufferPtr2">Buffer for second big integer digits. Only temporarily used.</param>
            /// <param name="length2">Second big integer length.</param>
            /// <param name="digitsResPtr">Resulting big integer digits.</param>
            /// <param name="resultFlags">Which operation results to return.</param>
            /// <param name="cmpResult">Big integers comparsion result (pass -2 if omitted).</param>
            /// <returns>Resulting big integer length.</returns>
            public static unsafe uint ClassicDivMod(uint* digitsPtr1, uint* digitsBufferPtr1, ref uint length1, uint* digitsPtr2, uint* digitsBufferPtr2, uint length2, uint* digitsResPtr, DivModResultFlags resultFlags, int cmpResult)
            {
                // Call base (for special cases)
                uint resultLength = BaseDivMod(digitsPtr1, digitsBufferPtr1, ref length1, digitsPtr2, digitsBufferPtr2, length2, digitsResPtr, resultFlags, cmpResult);
                if (resultLength != uint.MaxValue)
                    return resultLength;

                bool divNeeded = (resultFlags & DivModResultFlags.Div) != 0;
                bool modNeeded = (resultFlags & DivModResultFlags.Mod) != 0;

                //
                // Prepare digitsBufferPtr1 and digitsBufferPtr2
                //

                int shift1 = 31 - Bits.Msb(digitsPtr2[length2 - 1]);
                if (shift1 == 0)
                {
                    // We don't need to shift - just copy
                    DigitHelper.DigitsBlockCopy(digitsPtr1, digitsBufferPtr1, length1);

                    // We also don't need to shift second digits
                    digitsBufferPtr2 = digitsPtr2;
                }
                else
                {
                    int rightShift1 = Constants.DigitBitCount - shift1;

                    // We do need to shift here - so copy with shift - suppose we have enough storage for this operation
                    length1 = DigitOpHelper.Shr(digitsPtr1, length1, digitsBufferPtr1 + 1, rightShift1, true) + 1U;

                    // Second digits also must be shifted
                    DigitOpHelper.Shr(digitsPtr2, length2, digitsBufferPtr2 + 1, rightShift1, true);
                }

                //
                // Division main algorithm implementation
                //

                ulong longDigit;
                ulong divEst;
                ulong modEst;

                ulong mulRes;
                uint divRes;
                long k, t;

                // Some digits2 cached digits
                uint lastDigit2 = digitsBufferPtr2[length2 - 1];
                uint preLastDigit2 = digitsBufferPtr2[length2 - 2];

                // Main divide loop
                bool isMaxLength;
                uint maxLength = length1 - length2;
                for (uint i = maxLength, iLen2 = length1, j, ji; i <= maxLength; --i, --iLen2)
                {
                    isMaxLength = iLen2 == length1;

                    // Calculate estimates
                    if (isMaxLength)
                    {
                        longDigit = digitsBufferPtr1[iLen2 - 1];
                    }
                    else
                    {
                        longDigit = (ulong)digitsBufferPtr1[iLen2] << Constants.DigitBitCount | digitsBufferPtr1[iLen2 - 1];
                    }

                    divEst = longDigit / lastDigit2;
                    modEst = longDigit - divEst * lastDigit2;

                    // Check estimate (maybe correct it)
                    for (; ; )
                    {
                        if (divEst == Constants.BitCountStepOf2 || divEst * preLastDigit2 > (modEst << Constants.DigitBitCount) + digitsBufferPtr1[iLen2 - 2])
                        {
                            --divEst;
                            modEst += lastDigit2;
                            if (modEst < Constants.BitCountStepOf2) continue;
                        }
                        break;
                    }
                    divRes = (uint)divEst;

                    // Multiply and subtract
                    k = 0;
                    for (j = 0, ji = i; j < length2; ++j, ++ji)
                    {
                        mulRes = (ulong)divRes * digitsBufferPtr2[j];
                        t = digitsBufferPtr1[ji] - k - (long)(mulRes & 0xFFFFFFFF);
                        digitsBufferPtr1[ji] = (uint)t;
                        k = (long)(mulRes >> Constants.DigitBitCount) - (t >> Constants.DigitBitCount);
                    }

                    if (!isMaxLength)
                    {
                        t = digitsBufferPtr1[iLen2] - k;
                        digitsBufferPtr1[iLen2] = (uint)t;
                    }
                    else
                    {
                        t = -k;
                    }

                    // Correct result if subtracted too much
                    if (t < 0)
                    {
                        --divRes;

                        k = 0;
                        for (j = 0, ji = i; j < length2; ++j, ++ji)
                        {
                            t = (long)digitsBufferPtr1[ji] + digitsBufferPtr2[j] + k;
                            digitsBufferPtr1[ji] = (uint)t;
                            k = t >> Constants.DigitBitCount;
                        }

                        if (!isMaxLength)
                        {
                            digitsBufferPtr1[iLen2] = (uint)(k + digitsBufferPtr1[iLen2]);
                        }
                    }

                    // Maybe save div result
                    if (divNeeded)
                    {
                        digitsResPtr[i] = divRes;
                    }
                }

                if (modNeeded)
                {
                    // First set correct mod length
                    length1 = DigitHelper.GetRealDigitsLength(digitsBufferPtr1, length2);

                    // Next maybe shift result back to the right
                    if (shift1 != 0 && length1 != 0)
                    {
                        length1 = DigitOpHelper.Shr(digitsBufferPtr1, length1, digitsBufferPtr1, shift1, false);
                    }
                }

                // Finally return length
                return !divNeeded ? 0 : (digitsResPtr[maxLength] == 0 ? maxLength : ++maxLength);
            }

            /// <summary>
            /// Divides two big integers.
            /// Also modifies <paramref name="digitsPtr1" /> and <paramref name="length1"/> (it will contain remainder).
            /// </summary>
            /// <param name="digitsPtr1">First big integer digits.</param>
            /// <param name="digitsBufferPtr1">Buffer for first big integer digits. May also contain remainder.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="digitsPtr2">Second big integer digits.</param>
            /// <param name="digitsBufferPtr2">Buffer for second big integer digits. Only temporarily used.</param>
            /// <param name="length2">Second big integer length.</param>
            /// <param name="digitsResPtr">Resulting big integer digits.</param>
            /// <param name="resultFlags">Which operation results to return.</param>
            /// <param name="cmpResult">Big integers comparsion result (pass -2 if omitted).</param>
            /// <returns>Resulting big integer length.</returns>
            public static unsafe uint BaseDivMod(uint* digitsPtr1, uint* digitsBufferPtr1, ref uint length1, uint* digitsPtr2, uint* digitsBufferPtr2, uint length2, uint* digitsResPtr, DivModResultFlags resultFlags, int cmpResult)
            {
                // Base implementation covers some special cases

                bool divNeeded = (resultFlags & DivModResultFlags.Div) != 0;
                bool modNeeded = (resultFlags & DivModResultFlags.Mod) != 0;

                //
                // Special cases
                //

                // Case when length1 == 0
                if (length1 == 0) return 0;

                // Case when both lengths are 1
                if (length1 == 1 && length2 == 1)
                {
                    if (divNeeded)
                    {
                        *digitsResPtr = *digitsPtr1 / *digitsPtr2;
                        if (*digitsResPtr == 0)
                        {
                            length2 = 0;
                        }
                    }
                    if (modNeeded)
                    {
                        *digitsBufferPtr1 = *digitsPtr1 % *digitsPtr2;
                        if (*digitsBufferPtr1 == 0)
                        {
                            length1 = 0;
                        }
                    }

                    return length2;
                }

                // Compare digits first (if was not previously compared)
                if (cmpResult == -2)
                {
                    cmpResult = DigitOpHelper.Cmp(digitsPtr1, length1, digitsPtr2, length2);
                }

                // Case when first value is smaller then the second one - we will have remainder only
                if (cmpResult < 0)
                {
                    // Maybe we should copy first digits into remainder (if remainder is needed at all)
                    if (modNeeded)
                    {
                        DigitHelper.DigitsBlockCopy(digitsPtr1, digitsBufferPtr1, length1);
                    }

                    // Zero as division result
                    return 0;
                }

                // Case when values are equal
                if (cmpResult == 0)
                {
                    // Maybe remainder must be marked as empty
                    if (modNeeded)
                    {
                        length1 = 0;
                    }

                    // One as division result
                    if (divNeeded)
                    {
                        *digitsResPtr = 1;
                    }

                    return 1;
                }

                // Case when second length equals to 1
                if (length2 == 1)
                {
                    // Call method basing on fact if div is needed
                    uint modRes;
                    if (divNeeded)
                    {
                        length2 = DigitOpHelper.DivMod(digitsPtr1, length1, *digitsPtr2, digitsResPtr, out modRes);
                    }
                    else
                    {
                        modRes = DigitOpHelper.Mod(digitsPtr1, length1, *digitsPtr2);
                    }

                    // Maybe save mod result
                    if (modNeeded)
                    {
                        if (modRes != 0)
                        {
                            length1 = 1;
                            *digitsBufferPtr1 = modRes;
                        }
                        else
                        {
                            length1 = 0;
                        }
                    }

                    return length2;
                }

                // This is regular case, not special
                return uint.MaxValue;
            }

        }
        #endregion

        #region IntXMultiplier
        internal static class IntXMultiplier
        {
            /// <summary>
            /// Multiplies two big integers.
            /// </summary>
            /// <param name="int1">First big integer.</param>
            /// <param name="int2">Second big integer.</param>
            /// <returns>Resulting big integer.</returns>
            /// <exception cref="ArgumentNullException"><paramref name="int1" /> or <paramref name="int2" /> is a null reference.</exception>
            /// <exception cref="ArgumentException"><paramref name="int1" /> or <paramref name="int2" /> is too big for multiply operation.</exception>
            public static IntX Multiply(IntX int1, IntX int2)
            {
                // Exceptions
                if (ReferenceEquals(int1, null))
                {
                    throw new ArgumentNullException("int1", "Operands can't be null.");
                }
                else if (ReferenceEquals(int2, null))
                {
                    throw new ArgumentNullException("int2", "Operands can't be null.");
                }

                // Special behavior for zero cases
                if (int1._length == 0 || int2._length == 0) return new IntX();

                // Get new big integer length and check it
                ulong newLength = (ulong)int1._length + int2._length;
                if (newLength >> 32 != 0)
                {
                    throw new ArgumentException("One of the operated big integers is too big.");
                }

                // Create resulting big int
                IntX newInt = new IntX((uint)newLength, int1._negative ^ int2._negative);

                // Perform actual digits multiplication
                newInt._length = Multiply(int1._digits, int1._length, int2._digits, int2._length, newInt._digits);

                // Normalization may be needed
                newInt.TryNormalize();

                return newInt;
            }

            /// <summary>
            /// Multiplies two big integers represented by their digits.
            /// </summary>
            /// <param name="digits1">First big integer digits.</param>
            /// <param name="length1">First big integer real length.</param>
            /// <param name="digits2">Second big integer digits.</param>
            /// <param name="length2">Second big integer real length.</param>
            /// <param name="digitsRes">Where to put resulting big integer.</param>
            /// <returns>Resulting big integer real length.</returns>
            private static unsafe uint Multiply(uint[] digits1, uint length1, uint[] digits2, uint length2, uint[] digitsRes)
            {
                fixed (uint* digitsPtr1 = digits1, digitsPtr2 = digits2, digitsResPtr = digitsRes)
                {
                    return Multiply(digitsPtr1, length1, digitsPtr2, length2, digitsResPtr);
                }
            }
            /// <summary>
            /// Multiplies two big integers using pointers.
            /// </summary>
            /// <param name="digitsPtr1">First big integer digits.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="digitsPtr2">Second big integer digits.</param>
            /// <param name="length2">Second big integer length.</param>
            /// <param name="digitsResPtr">Resulting big integer digits.</param>
            /// <returns>Resulting big integer real length.</returns>
            internal static unsafe uint Multiply(uint* digitsPtr1, uint length1, uint* digitsPtr2, uint length2, uint* digitsResPtr)
            {
                // Check length - maybe use classic multiplier instead
                if (length1 < Constants.AutoFhtLengthLowerBound || length2 < Constants.AutoFhtLengthLowerBound ||
                    length1 > Constants.AutoFhtLengthUpperBound || length2 > Constants.AutoFhtLengthUpperBound)
                {
                    return ClassicMultiply(digitsPtr1, length1, digitsPtr2, length2, digitsResPtr);
                }

                uint newLength = length1 + length2;

                // Do FHT for first big integer
                double[] data1 = FhtHelper.ConvertDigitsToDouble(digitsPtr1, length1, newLength);
                FhtHelper.Fht(data1, (uint)data1.LongLength);

                // Compare digits
                double[] data2;
                if (digitsPtr1 == digitsPtr2 || DigitOpHelper.Cmp(digitsPtr1, length1, digitsPtr2, length2) == 0)
                {
                    // Use the same FHT for equal big integers
                    data2 = data1;
                }
                else
                {
                    // Do FHT over second digits
                    data2 = FhtHelper.ConvertDigitsToDouble(digitsPtr2, length2, newLength);
                    FhtHelper.Fht(data2, (uint)data2.LongLength);
                }

                // Perform multiplication and reverse FHT
                FhtHelper.MultiplyFhtResults(data1, data2, (uint)data1.LongLength);
                FhtHelper.ReverseFht(data1, (uint)data1.LongLength);

                // Convert to digits
                fixed (double* slice1 = data1)
                {
                    FhtHelper.ConvertDoubleToDigits(slice1, (uint)data1.LongLength, newLength, digitsResPtr);
                }

                // Return double arrays back to pool
                ArrayPool<double>.Instance.AddArray(data1);
                if (data2 != data1)
                {
                    ArrayPool<double>.Instance.AddArray(data2);
                }

                //// Maybe check for validity using classic multiplication
                //if (System.IntX.GlobalSettings.ApplyFhtValidityCheck)
                //{
                //    uint lowerDigitCount = System.Math.Min(length2, System.Math.Min(length1, Constants.FhtValidityCheckDigitCount));

                //    // Validate result by multiplying lowerDigitCount digits using classic algorithm and comparing
                //    uint[] validationResult = new uint[lowerDigitCount * 2];
                //    fixed (uint* validationResultPtr = validationResult)
                //    {
                //        ClassicMultiply(digitsPtr1, lowerDigitCount, digitsPtr2, lowerDigitCount, validationResultPtr);
                //        if (DigitOpHelper.Cmp(validationResultPtr, lowerDigitCount, digitsResPtr, lowerDigitCount) != 0)
                //        {
                //            throw new FhtMultiplicationException(string.Format("FHT multiplication returned invalid result for IntX objects with lengths {0} and {1}.", length1, length2));
                //        }
                //    }
                //}

                return digitsResPtr[newLength - 1] == 0 ? --newLength : newLength;
            }

            /// <summary>
            /// Multiplies two big integers using pointers.
            /// </summary>
            /// <param name="digitsPtr1">First big integer digits.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="digitsPtr2">Second big integer digits.</param>
            /// <param name="length2">Second big integer length.</param>
            /// <param name="digitsResPtr">Resulting big integer digits.</param>
            /// <returns>Resulting big integer length.</returns>
            private static unsafe uint ClassicMultiply(uint* digitsPtr1, uint length1, uint* digitsPtr2, uint length2, uint* digitsResPtr)
            {
                ulong c;

                // External cycle must be always smaller
                if (length1 < length2)
                {
                    // First must be bigger - swap
                    uint lengthTemp = length1;
                    length1 = length2;
                    length2 = lengthTemp;

                    uint* ptrTemp = digitsPtr1;
                    digitsPtr1 = digitsPtr2;
                    digitsPtr2 = ptrTemp;
                }

                // Prepare end pointers
                uint* digitsPtr1End = digitsPtr1 + length1;
                uint* digitsPtr2End = digitsPtr2 + length2;

                // We must always clear first "length1" digits in result
                DigitHelper.SetBlockDigits(digitsResPtr, length1, 0U);

                // Perform digits multiplication
                uint* ptr1, ptrRes = null;
                for (; digitsPtr2 < digitsPtr2End; ++digitsPtr2, ++digitsResPtr)
                {
                    // Check for zero (sometimes may help). There is no sense to make this check in internal cycle -
                    // it would give performance gain only here
                    if (*digitsPtr2 == 0) continue;

                    c = 0;
                    for (ptr1 = digitsPtr1, ptrRes = digitsResPtr; ptr1 < digitsPtr1End; ++ptr1, ++ptrRes)
                    {
                        c += (ulong)*digitsPtr2 * *ptr1 + *ptrRes;
                        *ptrRes = (uint)c;
                        c >>= 32;
                    }
                    *ptrRes = (uint)c;
                }

                uint newLength = length1 + length2;
                if (newLength > 0 && (ptrRes == null || *ptrRes == 0))
                {
                    --newLength;
                }
                return newLength;
            }
        }
        #endregion

        #region IntXParser
        internal static class IntXParser
        {
            /// <summary>
            /// Regex pattern used on parsing stage to determine number sign and/or base
            /// </summary>
            private const string ParseRegexPattern = "(?<Sign>[+-]?)((?<BaseHex>0[Xx])|(?<BaseOct>0))?";

            /// <summary>
            /// Regex object used on parsing stage to determine number sign and/or base
            /// </summary>
            private static readonly Regex ParseRegex = new Regex(ParseRegexPattern, RegexOptions.Compiled);

            #region Pow2Parse
            /// <summary>
            /// Parses provided string representation of <see cref="IntX" /> object.
            /// </summary>
            /// <param name="value">Number as string.</param>
            /// <param name="startIndex">Index inside string from which to start.</param>
            /// <param name="endIndex">Index inside string on which to end.</param>
            /// <param name="numberBase">Number base.</param>
            /// <param name="charToDigits">Char->digit dictionary.</param>
            /// <param name="digitsRes">Resulting digits.</param>
            /// <returns>Parsed integer length.</returns>
            private static uint Pow2Parse(string value, int startIndex, int endIndex, uint numberBase, IDictionary<char, uint> charToDigits, uint[] digitsRes)
            {
                // Calculate length of input string
                int bitsInChar = Bits.Msb(numberBase);
                uint valueLength = (uint)(endIndex - startIndex + 1);
                ulong valueBitLength = (ulong)valueLength * (ulong)bitsInChar;

                // Calculate needed digits length and first shift
                uint digitsLength = (uint)(valueBitLength / Constants.DigitBitCount) + 1;
                uint digitIndex = digitsLength - 1;
                int initialShift = (int)(valueBitLength % Constants.DigitBitCount);

                // Probably correct digits length
                if (initialShift == 0)
                {
                    --digitsLength;
                }

                // Do parsing in big cycle
                uint digit;
                for (int i = startIndex; i <= endIndex; ++i)
                {
                    digit = StrRepHelper.GetDigit(charToDigits, value[i], numberBase);

                    // Correct initial digit shift
                    if (initialShift == 0)
                    {
                        // If shift is equals to zero then char is not on digit elements bounds,
                        // so just go to the previous digit
                        initialShift = Constants.DigitBitCount - bitsInChar;
                        --digitIndex;
                    }
                    else
                    {
                        // Here shift might be negative, but it's okay
                        initialShift -= bitsInChar;
                    }

                    // Insert new digit in correct place
                    digitsRes[digitIndex] |= initialShift < 0 ? digit >> -initialShift : digit << initialShift;

                    // In case if shift was negative we also must modify previous digit
                    if (initialShift < 0)
                    {
                        initialShift += Constants.DigitBitCount;
                        digitsRes[--digitIndex] |= digit << initialShift;
                    }
                }

                if (digitsRes[digitsLength - 1] == 0)
                {
                    --digitsLength;
                }
                return digitsLength;
            }
            #endregion

            #region BaseParse
            /// <summary>
            /// Parses provided string representation of <see cref="IntX" /> object.
            /// </summary>
            /// <param name="value">Number as string.</param>
            /// <param name="numberBase">Number base.</param>
            /// <param name="charToDigits">Char->digit dictionary.</param>
            /// <param name="checkFormat">Check actual format of number (0 or 0x at start).</param>
            /// <returns>Parsed object.</returns>
            /// <exception cref="ArgumentNullException"><paramref name="value" /> is a null reference.</exception>
            /// <exception cref="ArgumentException"><paramref name="numberBase" /> is less then 2 or more then 16.</exception>
            /// <exception cref="FormatException"><paramref name="value" /> is not in valid format.</exception>
            public static IntX Parse(string value, uint numberBase, IDictionary<char, uint> charToDigits, bool checkFormat)
            {
                // Exceptions
                if (value == null)
                {
                    throw new ArgumentNullException("value");
                }
                if (charToDigits == null)
                {
                    throw new ArgumentNullException("charToDigits");
                }
                if (numberBase < 2 || numberBase > charToDigits.Count)
                {
                    throw new ArgumentException("Base is invalid.", "numberBase");
                }

                // Initially determine start and end indices (Trim is too slow)
                int startIndex = 0;
                for (; startIndex < value.Length && char.IsWhiteSpace(value[startIndex]); ++startIndex) ;
                int endIndex = value.Length - 1;
                for (; endIndex >= startIndex && char.IsWhiteSpace(value[endIndex]); --endIndex) ;

                bool negative = false; // number sign
                bool stringNotEmpty = false; // true if string is already guaranteed to be non-empty

                // Determine sign and/or base
                Match match = ParseRegex.Match(value, startIndex, endIndex - startIndex + 1);
                if (match.Groups["Sign"].Value == "-")
                {
                    negative = true;
                }
                if (match.Groups["BaseHex"].Length != 0)
                {
                    if (checkFormat)
                    {
                        // 0x before the number - this is hex number
                        numberBase = 16U;
                    }
                    else
                    {
                        // This is an error
                        throw new FormatException("Invalid character in input.");
                    }
                }
                else if (match.Groups["BaseOct"].Length != 0)
                {
                    if (checkFormat)
                    {
                        // 0 before the number - this is octal number
                        numberBase = 8U;
                    }

                    stringNotEmpty = true;
                }

                // Skip leading sign and format
                startIndex += match.Length;

                // If on this stage string is empty, this may mean an error
                if (startIndex > endIndex && !stringNotEmpty)
                {
                    throw new FormatException("No digits in string.");
                }

                // Iterate thru string and skip all leading zeroes
                for (; startIndex <= endIndex && value[startIndex] == '0'; ++startIndex) ;

                // Return zero if length is zero
                if (startIndex > endIndex) return new IntX();

                // Determine length of new digits array and create new IntX object with given length
                int valueLength = endIndex - startIndex + 1;
                uint digitsLength = (uint)System.Math.Ceiling(System.Math.Log(numberBase) / Constants.DigitBaseLog * valueLength);
                IntX newInt = new IntX(digitsLength, negative);

                // Now we have only (in)valid string which consists from numbers only.
                // Parse it
                newInt._length = Parse(value, startIndex, endIndex, numberBase, charToDigits, newInt._digits);

                return newInt;
            }

            /// <summary>
            /// Parses provided string representation of <see cref="IntX" /> object.
            /// </summary>
            /// <param name="value">Number as string.</param>
            /// <param name="startIndex">Index inside string from which to start.</param>
            /// <param name="endIndex">Index inside string on which to end.</param>
            /// <param name="numberBase">Number base.</param>
            /// <param name="charToDigits">Char->digit dictionary.</param>
            /// <param name="digitsRes">Resulting digits.</param>
            /// <returns>Parsed integer length.</returns>
            private static uint BaseParse(string value, int startIndex, int endIndex, uint numberBase, IDictionary<char, uint> charToDigits, uint[] digitsRes)
            {
                // Default implementation - always call pow2 parser if numberBase is pow of 2
                return numberBase == 1U << Bits.Msb(numberBase)
                    ? Pow2Parse(value, startIndex, endIndex, numberBase, charToDigits, digitsRes)
                    : 0;
            }
            #endregion

            #region FastParser
            /// <summary>
            /// Parses provided string representation of <see cref="IntX" /> object.
            /// </summary>
            /// <param name="value">Number as string.</param>
            /// <param name="startIndex">Index inside string from which to start.</param>
            /// <param name="endIndex">Index inside string on which to end.</param>
            /// <param name="numberBase">Number base.</param>
            /// <param name="charToDigits">Char->digit dictionary.</param>
            /// <param name="digitsRes">Resulting digits.</param>
            /// <returns>Parsed integer length.</returns>
            private static unsafe uint Parse(string value, int startIndex, int endIndex, uint numberBase, IDictionary<char, uint> charToDigits, uint[] digitsRes)
            {
                uint newLength = BaseParse(value, startIndex, endIndex, numberBase, charToDigits, digitsRes);

                // Maybe base method already parsed this number
                if (newLength != 0) return newLength;

                // Check length - maybe use classic parser instead
                uint initialLength = (uint)digitsRes.LongLength;
                if (initialLength < Constants.FastParseLengthLowerBound || initialLength > Constants.FastParseLengthUpperBound)
                {
                    return ClassicParse(value, startIndex, endIndex, numberBase, charToDigits, digitsRes);
                }

                uint valueLength = (uint)(endIndex - startIndex + 1);
                uint digitsLength = 1U << Bits.CeilLog2(valueLength);

                // Prepare array for digits in other base
                uint[] valueDigits = ArrayPool<uint>.Instance.GetArray(digitsLength);

                // This second array will store integer lengths initially
                uint[] valueDigits2 = ArrayPool<uint>.Instance.GetArray(digitsLength);

                fixed (uint* valueDigitsStartPtr = valueDigits, valueDigitsStartPtr2 = valueDigits2)
                {
                    // In the string first digit means last in digits array
                    uint* valueDigitsPtr = valueDigitsStartPtr + valueLength - 1;
                    uint* valueDigitsPtr2 = valueDigitsStartPtr2 + valueLength - 1;

                    // Reverse copy characters into digits
                    fixed (char* valueStartPtr = value)
                    {
                        char* valuePtr = valueStartPtr + startIndex;
                        char* valueEndPtr = valuePtr + valueLength;
                        for (; valuePtr < valueEndPtr; ++valuePtr, --valueDigitsPtr, --valueDigitsPtr2)
                        {
                            // Get digit itself - this call will throw an exception if char is invalid
                            *valueDigitsPtr = StrRepHelper.GetDigit(charToDigits, *valuePtr, numberBase);

                            // Set length of this digit (zero for zero)
                            *valueDigitsPtr2 = *valueDigitsPtr == 0U ? 0U : 1U;
                        }
                    }

                    // We have retrieved lengths array from pool - it needs to be cleared before using
                    DigitHelper.SetBlockDigits(valueDigitsStartPtr2 + valueLength, digitsLength - valueLength, 0);

                    // Now start from the digit arrays beginning
                    valueDigitsPtr = valueDigitsStartPtr;
                    valueDigitsPtr2 = valueDigitsStartPtr2;

                    // Here base in needed power will be stored
                    IntX baseInt = null;

                    // Temporary variables used on swapping
                    uint[] tempDigits;
                    uint* tempPtr;

                    // Variables used in cycle
                    uint* ptr1, ptr2, valueDigitsPtrEnd;
                    uint loLength, hiLength;

                    // Outer cycle instead of recursion
                    for (uint innerStep = 1, outerStep = 2; innerStep < digitsLength; innerStep <<= 1, outerStep <<= 1)
                    {
                        // Maybe baseInt must be multiplied by itself
                        baseInt = baseInt == null ? numberBase : baseInt * baseInt;

                        // Using unsafe here
                        fixed (uint* baseDigitsPtr = baseInt._digits)
                        {
                            // Start from arrays beginning
                            ptr1 = valueDigitsPtr;
                            ptr2 = valueDigitsPtr2;

                            // vauleDigits array end
                            valueDigitsPtrEnd = valueDigitsPtr + digitsLength;

                            // Cycle thru all digits and their lengths
                            for (; ptr1 < valueDigitsPtrEnd; ptr1 += outerStep, ptr2 += outerStep)
                            {
                                // Get lengths of "lower" and "higher" value parts
                                loLength = *ptr2;
                                hiLength = *(ptr2 + innerStep);

                                if (hiLength != 0)
                                {
                                    // We always must clear an array before multiply
                                    DigitHelper.SetBlockDigits(ptr2, outerStep, 0U);

                                    // Multiply per baseInt
                                    hiLength = IntXMultiplier.Multiply(baseDigitsPtr, baseInt._length, ptr1 + innerStep, hiLength, ptr2);
                                }

                                // Sum results
                                if (hiLength != 0 || loLength != 0)
                                {
                                    *ptr1 = DigitOpHelper.Add(ptr2, hiLength, ptr1, loLength, ptr2);
                                }
                                else
                                {
                                    *ptr1 = 0U;
                                }
                            }
                        }

                        // After inner cycle valueDigits will contain lengths and valueDigits2 will contain actual values
                        // so we need to swap them here
                        tempDigits = valueDigits;
                        valueDigits = valueDigits2;
                        valueDigits2 = tempDigits;

                        tempPtr = valueDigitsPtr;
                        valueDigitsPtr = valueDigitsPtr2;
                        valueDigitsPtr2 = tempPtr;
                    }
                }

                // Determine real length of converted number
                uint realLength = valueDigits2[0];

                // Copy to result
                Array.Copy(valueDigits, digitsRes, realLength);

                // Return arrays to pool
                ArrayPool<uint>.Instance.AddArray(valueDigits);
                ArrayPool<uint>.Instance.AddArray(valueDigits2);

                return realLength;
            }
            #endregion

            #region ClassicParser
            /// <summary>
            /// Parses provided string representation of <see cref="System.IntX" /> object.
            /// </summary>
            /// <param name="value">Number as string.</param>
            /// <param name="startIndex">Index inside string from which to start.</param>
            /// <param name="endIndex">Index inside string on which to end.</param>
            /// <param name="numberBase">Number base.</param>
            /// <param name="charToDigits">Char->digit dictionary.</param>
            /// <param name="digitsRes">Resulting digits.</param>
            /// <returns>Parsed integer length.</returns>
            private static uint ClassicParse(string value, int startIndex, int endIndex, uint numberBase, IDictionary<char, uint> charToDigits, uint[] digitsRes)
            {
                uint newLength = BaseParse(value, startIndex, endIndex, numberBase, charToDigits, digitsRes);

                // Maybe base method already parsed this number
                if (newLength != 0) return newLength;

                // Do parsing in big cycle
                ulong numberBaseLong = numberBase;
                ulong digit;
                for (int i = startIndex; i <= endIndex; ++i)
                {
                    digit = StrRepHelper.GetDigit(charToDigits, value[i], numberBase);

                    // Next multiply existing values by base and add this value to them
                    if (newLength == 0)
                    {
                        if (digit != 0)
                        {
                            digitsRes[0] = (uint)digit;
                            newLength = 1;
                        }
                    }
                    else
                    {
                        for (uint j = 0; j < newLength; ++j)
                        {
                            digit += digitsRes[j] * numberBaseLong;
                            digitsRes[j] = (uint)digit;
                            digit >>= 32;
                        }
                        if (digit != 0)
                        {
                            digitsRes[newLength++] = (uint)digit;
                        }
                    }
                }

                return newLength;
            }
            #endregion

        }
        #endregion

        #region IntXStringConverter
        internal static class IntXStringConverter
        {
            /// <summary>
            /// Returns string representation of <see cref="IntX" /> object in given base.
            /// </summary>
            /// <param name="intX">Big integer to convert.</param>
            /// <param name="numberBase">Base of system in which to do output.</param>
            /// <param name="alphabet">Alphabet which contains chars used to represent big integer, char position is coresponding digit value.</param>
            /// <returns>Object string representation.</returns>
            /// <exception cref="ArgumentException"><paramref name="numberBase" /> is less then 2 or <paramref name="intX" /> is too big to fit in string.</exception>
            public static string ToString(IntX intX, uint numberBase, char[] alphabet)
            {
                // Test base
                if (numberBase < 2 || numberBase > 65536)
                {
                    throw new ArgumentException("Base must be between 2 and 65536.", "numberBase");
                }

                // Special processing for zero values
                if (intX._length == 0)
                    return "0";

                // Calculate output array length
                uint outputLength = (uint)System.Math.Ceiling(Constants.DigitBaseLog / System.Math.Log(numberBase) * intX._length);

                // Define length coefficient for string builder
                bool isBigBase = numberBase > alphabet.Length;
                uint lengthCoef = isBigBase ? (uint)System.Math.Ceiling(System.Math.Log10(numberBase)) + 2U : 1U;

                // Determine maximal possible length of string
                ulong maxBuilderLength = (ulong)outputLength * lengthCoef + 1UL;
                if (maxBuilderLength > int.MaxValue)
                {
                    // This big integer can't be transformed to string
                    throw new ArgumentException("One of the operated big integers is too big.", "intX");
                }

                // Transform digits into another base
                uint[] outputArray = FastToString(intX._digits, intX._length, numberBase, ref outputLength);

                // Output everything to the string builder
                StringBuilder outputBuilder = new StringBuilder((int)(outputLength * lengthCoef + 1));

                // Maybe append minus sign
                if (intX._negative)
                {
                    outputBuilder.Append(Constants.DigitsMinusChar);
                }

                // Output all digits
                for (uint i = outputLength - 1; i < outputLength; --i)
                {
                    if (!isBigBase)
                    {
                        // Output char-by-char for bases up to covered by alphabet
                        outputBuilder.Append(alphabet[(int)outputArray[i]]);
                    }
                    else
                    {
                        // Output digits in brackets for bigger bases
                        outputBuilder.Append(Constants.DigitOpeningBracet);
                        outputBuilder.Append(outputArray[i].ToString());
                        outputBuilder.Append(Constants.DigitClosingBracet);
                    }
                }

                return outputBuilder.ToString();
            }

            #region BaseToString
            /// <summary>
            /// Converts digits from internal representation into given base.
            /// </summary>
            /// <param name="digits">Big integer digits.</param>
            /// <param name="length">Big integer length.</param>
            /// <param name="numberBase">Base to use for output.</param>
            /// <param name="outputLength">Calculated output length (will be corrected inside).</param>
            /// <returns>Conversion result (later will be transformed to string).</returns>
            private static uint[] BaseToString(uint[] digits, uint length, uint numberBase, ref uint outputLength)
            {
                // Default implementation - always call pow2 converter if numberBase is power of 2
                return numberBase == 1U << Bits.Msb(numberBase)
                    ? Pow2ToString(digits, length, numberBase, ref outputLength)
                    : null;
            }
            #endregion

            #region FastToString
            /// <summary>
            /// Converts digits from internal representation into given base.
            /// </summary>
            /// <param name="digits">Big integer digits.</param>
            /// <param name="length">Big integer length.</param>
            /// <param name="numberBase">Base to use for output.</param>
            /// <param name="outputLength">Calculated output length (will be corrected inside).</param>
            /// <returns>Conversion result (later will be transformed to string).</returns>
            private static unsafe uint[] FastToString(uint[] digits, uint length, uint numberBase, ref uint outputLength)
            {
                uint[] outputArray = BaseToString(digits, length, numberBase, ref outputLength);

                // Maybe base method already converted this number
                if (outputArray != null) return outputArray;

                // Check length - maybe use classic converter instead
                if (length < Constants.FastConvertLengthLowerBound || length > Constants.FastConvertLengthUpperBound)
                {
                    return ClassicToString(digits, length, numberBase, ref outputLength);
                }

                int resultLengthLog2 = Bits.CeilLog2(outputLength);
                uint resultLength = 1U << resultLengthLog2;

                // Create and initially fill array for transformed numbers storing
                uint[] resultArray = ArrayPool<uint>.Instance.GetArray(resultLength);
                Array.Copy(digits, resultArray, length);

                // Create and initially fill array with lengths
                uint[] resultArray2 = ArrayPool<uint>.Instance.GetArray(resultLength);
                resultArray2[0] = length;

                // Generate all needed powers of numberBase in stack
                Stack baseIntStack = new Stack(resultLengthLog2);
                IntX baseInt = null;
                for (int i = 0; i < resultLengthLog2; ++i)
                {
                    baseInt = baseInt == null ? numberBase : IntXMultiplier.Multiply(baseInt, baseInt);
                    baseIntStack.Push(baseInt);
                }

                // Create temporary buffer for second digits when doing div operation
                uint[] tempBuffer = new uint[baseInt._length];

                // We will use unsafe code here
                fixed (uint* resultPtr1Const = resultArray, resultPtr2Const = resultArray2, tempBufferPtr = tempBuffer)
                {
                    // Results pointers which will be modified (on swap)
                    uint* resultPtr1 = resultPtr1Const;
                    uint* resultPtr2 = resultPtr2Const;

                    // Temporary variables used on swapping
                    uint[] tempArray;
                    uint* tempPtr;

                    // Variables used in cycle
                    uint* ptr1, ptr2, ptr1end;
                    uint loLength;

                    // Outer cycle instead of recursion
                    for (uint innerStep = resultLength >> 1, outerStep = resultLength; innerStep > 0; innerStep >>= 1, outerStep >>= 1)
                    {
                        // Prepare pointers
                        ptr1 = resultPtr1;
                        ptr2 = resultPtr2;
                        ptr1end = resultPtr1 + resultLength;

                        // Get baseInt from stack and fix it too
                        baseInt = (IntX)baseIntStack.Pop();
                        fixed (uint* baseIntPtr = baseInt._digits)
                        {
                            // Cycle thru all digits and their lengths
                            for (; ptr1 < ptr1end; ptr1 += outerStep, ptr2 += outerStep)
                            {
                                // Divide ptr1 (with length in *ptr2) by baseIntPtr here.
                                // Results are stored in ptr2 & (ptr2 + innerStep), lengths - in *ptr1 and (*ptr1 + innerStep)
                                loLength = *ptr2;
                                *(ptr1 + innerStep) = IntXDivider.DivMod(
                                    ptr1,
                                    ptr2,
                                    ref loLength,
                                    baseIntPtr,
                                    tempBufferPtr,
                                    baseInt._length,
                                    ptr2 + innerStep,
                                    DivModResultFlags.Div | DivModResultFlags.Mod,
                                    -2);
                                *ptr1 = loLength;
                            }
                        }

                        // After inner cycle resultArray will contain lengths and resultArray2 will contain actual values
                        // so we need to swap them here
                        tempArray = resultArray;
                        resultArray = resultArray2;
                        resultArray2 = tempArray;

                        tempPtr = resultPtr1;
                        resultPtr1 = resultPtr2;
                        resultPtr2 = tempPtr;
                    }

                    // Retrieve real output length
                    outputLength = DigitHelper.GetRealDigitsLength(resultArray2, outputLength);

                    // Create output array
                    outputArray = new uint[outputLength];

                    // Copy each digit but only if length is not null
                    fixed (uint* outputPtr = outputArray)
                    {
                        for (uint i = 0; i < outputLength; ++i)
                        {
                            if (resultPtr2[i] != 0)
                            {
                                outputPtr[i] = resultPtr1[i];
                            }
                        }
                    }
                }

                // Return temporary arrays to pool
                ArrayPool<uint>.Instance.AddArray(resultArray);
                ArrayPool<uint>.Instance.AddArray(resultArray2);

                return outputArray;
            }
            #endregion

            #region ClassicToString
            /// <summary>
            /// Converts digits from internal representaion into given base.
            /// </summary>
            /// <param name="digits">Big integer digits.</param>
            /// <param name="length">Big integer length.</param>
            /// <param name="numberBase">Base to use for output.</param>
            /// <param name="outputLength">Calculated output length (will be corrected inside).</param>
            /// <returns>Conversion result (later will be transformed to string).</returns>
            private static uint[] ClassicToString(uint[] digits, uint length, uint numberBase, ref uint outputLength)
            {
                uint[] outputArray = BaseToString(digits, length, numberBase, ref outputLength);

                // Maybe base method already converted this number
                if (outputArray != null)
                    return outputArray;

                // Create an output array for storing of number in other base
                outputArray = new uint[outputLength + 1];

                // Make a copy of initial data
                uint[] digitsCopy = new uint[length];
                Array.Copy(digits, digitsCopy, length);

                // Calculate output numbers by dividing
                uint outputIndex;
                for (outputIndex = 0; length > 0; ++outputIndex)
                {
                    length = DigitOpHelper.DivMod(digitsCopy, length, numberBase, digitsCopy, out outputArray[outputIndex]);
                }

                outputLength = outputIndex;
                return outputArray;
            }
            #endregion

            #region Pow2ToString
            /// <summary>
            /// Converts digits from internal representation into given base.
            /// </summary>
            /// <param name="digits">Big integer digits.</param>
            /// <param name="length">Big integer length.</param>
            /// <param name="numberBase">Base to use for output.</param>
            /// <param name="outputLength">Calculated output length (will be corrected inside).</param>
            /// <returns>Conversion result (later will be transformed to string).</returns>
            private static uint[] Pow2ToString(uint[] digits, uint length, uint numberBase, ref uint outputLength)
            {
                // Calculate real output length
                int bitsInChar = Bits.Msb(numberBase);
                ulong digitsBitLength = (ulong)(length - 1) * Constants.DigitBitCount + (ulong)Bits.Msb(digits[length - 1]) + 1UL;
                uint realOutputLength = (uint)(digitsBitLength / (ulong)bitsInChar);
                if (digitsBitLength % (ulong)bitsInChar != 0)
                {
                    ++realOutputLength;
                }

                // Prepare shift variables
                int nextDigitShift = Constants.DigitBitCount - bitsInChar; // after this shift next digit must be used
                int initialShift = 0;

                // We will also need bitmask for copying digits
                uint digitBitMask = numberBase - 1;

                // Create an output array for storing of number in other base
                uint[] outputArray = new uint[realOutputLength];

                // Walk thru original digits and fill output
                uint outputDigit;
                for (uint outputIndex = 0, digitIndex = 0; outputIndex < realOutputLength; ++outputIndex)
                {
                    // Get part of current digit
                    outputDigit = digits[digitIndex] >> initialShift;

                    // Maybe we need to go to the next digit
                    if (initialShift >= nextDigitShift)
                    {
                        // Go to the next digit
                        ++digitIndex;

                        // Maybe we also need a part of the next digit
                        if (initialShift != nextDigitShift && digitIndex < length)
                        {
                            outputDigit |= digits[digitIndex] << (Constants.DigitBitCount - initialShift);
                        }

                        // Modify shift so that it will be valid for the next digit
                        initialShift = (initialShift + bitsInChar) % Constants.DigitBitCount;
                    }
                    else
                    {
                        // Modify shift as usual
                        initialShift += bitsInChar;
                    }

                    // Write masked result to the output
                    outputArray[outputIndex] = outputDigit & digitBitMask;
                }

                outputLength = realOutputLength;
                return outputArray;
            }
            #endregion

        }
        #endregion

        #region Bits
        /// <summary>
        /// Contains helping methods to with with bits in dword (<see cref="UInt32" />).
        /// </summary>
        internal static class Bits
        {
            /// <summary>
            /// Returns number of leading zero bits in int.
            /// </summary>
            /// <param name="x">Int value.</param>
            /// <returns>Number of leading zero bits.</returns>
            static public int Nlz(uint x)
            {
                if (x == 0) return 32;

                int n = 1;
                if ((x >> 16) == 0) { n += 16; x <<= 16; }
                if ((x >> 24) == 0) { n += 8; x <<= 8; }
                if ((x >> 28) == 0) { n += 4; x <<= 4; }
                if ((x >> 30) == 0) { n += 2; x <<= 2; }
                return n - (int)(x >> 31);
            }

            /// <summary>
            /// Counts position of the most significant bit in int.
            /// Can also be used as Floor(Log2(<paramref name="x" />)).
            /// </summary>
            /// <param name="x">Int value.</param>
            /// <returns>Position of the most significant one bit (-1 if all zeroes).</returns>
            static public int Msb(uint x)
            {
                return 31 - Nlz(x);
            }

            /// <summary>
            /// Ceil(Log2(<paramref name="x" />)).
            /// </summary>
            /// <param name="x">Int value.</param>
            /// <returns>Ceil of the Log2.</returns>
            static public int CeilLog2(uint x)
            {
                int msb = Msb(x);
                if (x != 1U << msb)
                {
                    ++msb;
                }
                return msb;
            }
        }
        #endregion

        #region DivModResultFlags
        /// <summary>
        /// <see cref="IntX" /> divide results to return.
        /// </summary>
        [Flags]
        internal enum DivModResultFlags
        {
            /// <summary>
            /// Dividend is returned.
            /// </summary>
            Div = 1,
            /// <summary>
            /// Remainder is returned.
            /// </summary>
            Mod = 2
        }
        #endregion

        #region Constants
        /// <summary>
        /// Constants used in <see cref="System.IntX" /> and helping classes.
        /// </summary>
        static internal class Constants
        {
            #region .cctor

            static Constants()
            {
                BaseCharToDigits = StrRepHelper.CharDictionaryFromAlphabet(new string(BaseUpperChars), 16U);
                for (int i = 10; i < BaseLowerChars.Length; i++)
                {
                    BaseCharToDigits.Add(BaseLowerChars[i], (uint)i);
                }
            }

            #endregion .cctor

            #region ToString constants

            /// <summary>
            /// Chars used to parse/output big integers (upper case).
            /// </summary>
            public static readonly char[] BaseUpperChars = "0123456789ABCDEF".ToCharArray();

            /// <summary>
            /// Chars used to parse/output big integers (lower case).
            /// </summary>
            public static readonly char[] BaseLowerChars = "0123456789abcdef".ToCharArray();

            /// <summary>
            /// Standard char->digit dictionary.
            /// </summary>
            static readonly public IDictionary<char, uint> BaseCharToDigits;

            /// <summary>
            /// Digit opening bracket (used for bases bigger then 16).
            /// </summary>
            public const char DigitOpeningBracet = '{';

            /// <summary>
            /// Digit closing bracket (used for bases bigger then 16).
            /// </summary>
            public const char DigitClosingBracet = '}';

            /// <summary>
            /// Minus char (-).
            /// </summary>
            public const char DigitsMinusChar = '-';

            /// <summary>
            /// Natural logarithm of digits base (log(2^32)).
            /// </summary>
            public static readonly double DigitBaseLog = System.Math.Log(1UL << DigitBitCount);

            #endregion ToString constants

            #region Pools constants

            /// <summary>
            /// Minimal Log2(array length) which will be pooled using any array pool.
            /// </summary>
            public const int MinPooledArraySizeLog2 = 17;

            /// <summary>
            /// Maximal Log2(array length) which will be pooled using any array pool.
            /// </summary>
            public const int MaxPooledArraySizeLog2 = 31;

            /// <summary>
            /// Maximal allowed array pool items count in each stack.
            /// </summary>
            public const int MaxArrayPoolCount = 1024;

            #endregion Pools constants

            #region FHT constants

            /// <summary>
            /// <see cref="System.IntX" /> length from which FHT is used (in auto-FHT mode).
            /// Before this length usual multiply algorithm works faster.
            /// </summary>
            public const uint AutoFhtLengthLowerBound = 1U << 9;

            /// <summary>
            /// <see cref="System.IntX" /> length 'till which FHT is used (in auto-FHT mode).
            /// After this length using of FHT may be unsafe due to big precision errors.
            /// </summary>
            public const uint AutoFhtLengthUpperBound = 1U << 26;

            /// <summary>
            /// Number of lower digits used to check FHT multiplication result validity.
            /// </summary>
            public const uint FhtValidityCheckDigitCount = 10;

            #endregion FHT constants

            #region Newton constants

            /// <summary>
            /// <see cref="System.IntX" /> length from which Newton approach is used (in auto-Newton mode).
            /// Before this length usual divide algorithm works faster.
            /// </summary>
            public const uint AutoNewtonLengthLowerBound = 1U << 13;

            /// <summary>
            /// <see cref="System.IntX" /> length 'till which Newton approach is used (in auto-Newton mode).
            /// After this length using of fast division may be slow.
            /// </summary>
            public const uint AutoNewtonLengthUpperBound = 1U << 26;

            #endregion Newton constants

            #region Parsing constants

            /// <summary>
            /// <see cref="System.IntX" /> length from which fast parsing is used (in Fast parsing mode).
            /// Before this length usual parsing algorithm works faster.
            /// </summary>
            public const uint FastParseLengthLowerBound = 32;

            /// <summary>
            /// <see cref="System.IntX" /> length 'till which fast parsing is used (in Fast parsing mode).
            /// After this length using of parsing will be slow.
            /// </summary>
            public const uint FastParseLengthUpperBound = uint.MaxValue;

            #endregion Parsing constants

            #region ToString convertion constants

            /// <summary>
            /// <see cref="System.IntX" /> length from which fast conversion is used (in Fast convert mode).
            /// Before this length usual conversion algorithm works faster.
            /// </summary>
            public const uint FastConvertLengthLowerBound = 16;

            /// <summary>
            /// <see cref="System.IntX" /> length 'till which fast conversion is used (in Fast convert mode).
            /// After this length using of conversion will be slow.
            /// </summary>
            public const uint FastConvertLengthUpperBound = uint.MaxValue;

            #endregion ToString convertion constants

            /// <summary>
            /// Count of bits in one <see cref="System.IntX" /> digit.
            /// </summary>
            public const int DigitBitCount = 32;

            /// <summary>
            /// Maximum count of bits which can fit in <see cref="System.IntX" />.
            /// </summary>
            public const ulong MaxBitCount = uint.MaxValue * 32UL;

            /// <summary>
            /// 2^<see cref="DigitBitCount"/>.
            /// </summary>
            public const ulong BitCountStepOf2 = 1UL << 32;
        }
        #endregion

        #region ArrayPool
        /// <summary>
        /// Generic arrays pool on weak references.
        /// </summary>
        sealed internal class ArrayPool<T>
        {
            #region Fields

            /// <summary>
            /// Singleton instance.
            /// </summary>
            static readonly public ArrayPool<T> Instance = new ArrayPool<T>(
                Constants.MinPooledArraySizeLog2,
                Constants.MaxPooledArraySizeLog2,
                Constants.MaxArrayPoolCount);

            // Minimal and maximal Log2(uint[] length) which will be pooled
            int _minPooledArraySizeLog2;
            int _maxPooledArraySizeLog2;

            // Maximal pool items count
            int _maxPoolCount;

            Stack<WeakReference>[] _pools; // ArrayPool pools

            #endregion Fields

            #region Constructor

            // Singleton
            private ArrayPool(int minPooledArraySizeLog2, int maxPooledArraySizeLog2, int maxPoolCount)
            {
                _minPooledArraySizeLog2 = minPooledArraySizeLog2;
                _maxPooledArraySizeLog2 = maxPooledArraySizeLog2;
                _maxPoolCount = maxPoolCount;

                // Init pools
                _pools = new Stack<WeakReference>[maxPooledArraySizeLog2 - minPooledArraySizeLog2 + 1];
                for (int i = 0; i < _pools.Length; ++i)
                {
                    // Calls to those pools are sync in code
                    _pools[i] = new Stack<WeakReference>();
                }
            }

            #endregion Constructor

            #region Pool management methods

            /// <summary>
            /// Either returns array of given size from pool or creates it.
            /// </summary>
            /// <param name="length">Array length (always pow of 2).</param>
            /// <returns>Always array instance ready to use.</returns>
            public T[] GetArray(uint length)
            {
                int lengthLog2 = Bits.Msb(length);

                // Check if we can search in pool
                if (lengthLog2 >= _minPooledArraySizeLog2 && lengthLog2 <= _maxPooledArraySizeLog2)
                {
                    // Get needed pool
                    Stack<WeakReference> pool = _pools[lengthLog2 - _minPooledArraySizeLog2];

                    // Try to find at least one not collected array of given size
                    while (pool.Count > 0)
                    {
                        WeakReference arrayRef;
                        lock (pool)
                        {
                            // Double-guard here
                            if (pool.Count > 0)
                            {
                                arrayRef = pool.Pop();
                            }
                            else
                            {
                                // Well, we can exit here
                                break;
                            }
                        }

                        // Maybe return found array if link is alive
                        T[] array = (T[])arrayRef.Target;
                        if (arrayRef.IsAlive) return array;
                    }
                }

                // Array can't be found in pool - create new one
                return new T[length];
            }

            /// <summary>
            /// Adds array to pool.
            /// </summary>
            /// <param name="array">Array to add (it/s length is always pow of 2).</param>
            public void AddArray(T[] array)
            {
                int lengthLog2 = Bits.Msb((uint)array.LongLength);

                // Check if we can add in pool
                if (lengthLog2 >= _minPooledArraySizeLog2 && lengthLog2 <= _maxPooledArraySizeLog2)
                {
                    // Get needed pool
                    Stack<WeakReference> pool = _pools[lengthLog2 - _minPooledArraySizeLog2];

                    // Add array to pool (only if pool size is not too big)
                    if (pool.Count <= _maxPoolCount)
                    {
                        lock (pool)
                        {
                            // Double-guard here
                            if (pool.Count <= _maxPoolCount)
                            {
                                pool.Push(new WeakReference(array));
                            }
                        }
                    }
                }
            }

            #endregion Pool management methods
        }
        #endregion

        #region StrRepHelper
        /// <summary>
        /// Helps to work with <see cref="IntX" /> string representations.
        /// </summary>
        static internal class StrRepHelper
        {
            /// <summary>
            /// Returns digit for given char.
            /// </summary>
            /// <param name="charToDigits">Char->digit dictionary.</param>
            /// <param name="ch">Char which represents big integer digit.</param>
            /// <param name="numberBase">String representation number base.</param>
            /// <returns>Digit.</returns>
            /// <exception cref="FormatException"><paramref name="ch" /> is not in valid format.</exception>
            static public uint GetDigit(IDictionary<char, uint> charToDigits, char ch, uint numberBase)
            {
                if (charToDigits == null)
                {
                    throw new ArgumentNullException("charToDigits");
                }

                // Try to identify this digit
                uint digit;
                if (!charToDigits.TryGetValue(ch, out digit))
                {
                    throw new FormatException("Invalid character in input.");
                }
                if (digit >= numberBase)
                {
                    throw new FormatException("Digit is too big for this base.");
                }
                return digit;
            }

            /// <summary>
            /// Verfies string alphabet provider by user for validity.
            /// </summary>
            /// <param name="alphabet">Alphabet.</param>
            /// <param name="numberBase">String representation number base.</param>
            static public void AssertAlphabet(string alphabet, uint numberBase)
            {
                if (alphabet == null)
                {
                    throw new ArgumentNullException("alphabet");
                }

                // Ensure that alphabet has enough characters to represent numbers in given base
                if (alphabet.Length < numberBase)
                {
                    throw new ArgumentException(string.Format("Alphabet is too small to represent numbers in base {0}.", numberBase), "alphabet");
                }

                // Ensure that all the characters in alphabet are unique
                char[] sortedChars = alphabet.ToCharArray();
                Array.Sort(sortedChars);
                for (int i = 0; i < sortedChars.Length; i++)
                {
                    if (i > 0 && sortedChars[i] == sortedChars[i - 1])
                    {
                        throw new ArgumentException("Alphabet characters must be unique.", "alphabet");
                    }
                }
            }

            /// <summary>
            /// Generates char->digit dictionary from alphabet.
            /// </summary>
            /// <param name="alphabet">Alphabet.</param>
            /// <param name="numberBase">String representation number base.</param>
            /// <returns>Char->digit dictionary.</returns>
            static public IDictionary<char, uint> CharDictionaryFromAlphabet(string alphabet, uint numberBase)
            {
                AssertAlphabet(alphabet, numberBase);
                Dictionary<char, uint> charToDigits = new Dictionary<char, uint>((int)numberBase);
                for (int i = 0; i < numberBase; i++)
                {
                    charToDigits.Add(alphabet[i], (uint)i);
                }
                return charToDigits;
            }
        }
        #endregion

        #region OpHelper
        /// <summary>
        /// Contains helping methods for operations over <see cref="IntX" />.
        /// </summary>
        static internal class OpHelper
        {
            #region Add operation

            /// <summary>
            /// Adds two big integers.
            /// </summary>
            /// <param name="int1">First big integer.</param>
            /// <param name="int2">Second big integer.</param>
            /// <returns>Resulting big integer.</returns>
            /// <exception cref="ArgumentException"><paramref name="int1" /> or <paramref name="int2" /> is too big for add operation.</exception>
            static public IntX Add(IntX int1, IntX int2)
            {
                // Process zero values in special way
                if (int2._length == 0) return new IntX(int1);
                if (int1._length == 0)
                {
                    IntX x = new IntX(int2);
                    x._negative = int1._negative; // always get sign of the first big integer
                    return x;
                }

                // Determine big int with lower length
                IntX smallerInt;
                IntX biggerInt;
                DigitHelper.GetMinMaxLengthObjects(int1, int2, out smallerInt, out biggerInt);

                // Check for add operation possibility
                if (biggerInt._length == uint.MaxValue)
                {
                    throw new ArgumentException("One of the operated big integers is too big.");
                }

                // Create new big int object of needed length
                IntX newInt = new IntX(biggerInt._length + 1, int1._negative);

                // Do actual addition
                newInt._length = DigitOpHelper.Add(
                    biggerInt._digits,
                    biggerInt._length,
                    smallerInt._digits,
                    smallerInt._length,
                    newInt._digits);

                // Normalization may be needed
                newInt.TryNormalize();

                return newInt;
            }

            #endregion Add operation

            #region Subtract operation

            /// <summary>
            /// Subtracts two big integers.
            /// </summary>
            /// <param name="int1">First big integer.</param>
            /// <param name="int2">Second big integer.</param>
            /// <returns>Resulting big integer.</returns>
            static public IntX Sub(IntX int1, IntX int2)
            {
                // Process zero values in special way
                if (int1._length == 0) return new IntX(int2._digits, true);
                if (int2._length == 0) return new IntX(int1);

                // Determine lower big int (without sign)
                IntX smallerInt;
                IntX biggerInt;
                int compareResult = DigitOpHelper.Cmp(int1._digits, int1._length, int2._digits, int2._length);
                if (compareResult == 0) return new IntX(); // integers are equal
                if (compareResult < 0)
                {
                    smallerInt = int1;
                    biggerInt = int2;
                }
                else
                {
                    smallerInt = int2;
                    biggerInt = int1;
                }

                // Create new big int object
                IntX newInt = new IntX(biggerInt._length, ReferenceEquals(int1, smallerInt) ^ int1._negative);

                // Do actual subtraction
                newInt._length = DigitOpHelper.Sub(
                    biggerInt._digits,
                    biggerInt._length,
                    smallerInt._digits,
                    smallerInt._length,
                    newInt._digits);

                // Normalization may be needed
                newInt.TryNormalize();

                return newInt;
            }

            #endregion Subtract operation

            #region Add/Subtract operation - common methods

            /// <summary>
            /// Adds/subtracts one <see cref="IntX" /> to/from another.
            /// Determines which operation to use basing on operands signs.
            /// </summary>
            /// <param name="int1">First big integer.</param>
            /// <param name="int2">Second big integer.</param>
            /// <param name="subtract">Was subtraction initially.</param>
            /// <returns>Add/subtract operation result.</returns>
            /// <exception cref="ArgumentNullException"><paramref name="int1" /> or <paramref name="int2" /> is a null reference.</exception>
            static public IntX AddSub(IntX int1, IntX int2, bool subtract)
            {
                // Exceptions
                if (ReferenceEquals(int1, null))
                {
                    throw new ArgumentNullException("int1", "Operands can't be null.");
                }
                else if (ReferenceEquals(int2, null))
                {
                    throw new ArgumentNullException("int2", "Operands can't be null.");
                }

                // Determine real operation type and result sign
                return subtract ^ int1._negative == int2._negative ? Add(int1, int2) : Sub(int1, int2);
            }

            #endregion Add/Subtract operation - common methods

            #region Power operation

            /// <summary>
            /// Returns a specified big integer raised to the specified power.
            /// </summary>
            /// <param name="value">Number to raise.</param>
            /// <param name="power">Power.</param>
            /// <returns>Number in given power.</returns>
            /// <exception cref="ArgumentNullException"><paramref name="value" /> is a null reference.</exception>
            static public IntX Pow(IntX value, uint power)
            {
                // Exception
                if (ReferenceEquals(value, null))
                {
                    throw new ArgumentNullException("value");
                }

                // Return one for zero pow
                if (power == 0) return 1;

                // Return the number itself from a power of one
                if (power == 1) return new IntX(value);

                // Return zero for a zero
                if (value._length == 0) return new IntX();

                // Get first one bit
                int msb = Bits.Msb(power);

                // Do actual raising
                IntX res = value;
                for (uint powerMask = 1U << (msb - 1); powerMask != 0; powerMask >>= 1)
                {
                    // Always square
                    res = IntXMultiplier.Multiply(res, res);

                    // Maybe mul
                    if ((power & powerMask) != 0)
                    {
                        res = IntXMultiplier.Multiply(res, value);
                    }
                }
                return res;
            }

            #endregion Power operation

            #region Compare operation

            /// <summary>
            /// Compares 2 <see cref="IntX" /> objects.
            /// Returns "-2" if any argument is null, "-1" if <paramref name="int1" /> < <paramref name="int2" />,
            /// "0" if equal and "1" if >.
            /// </summary>
            /// <param name="int1">First big integer.</param>
            /// <param name="int2">Second big integer.</param>
            /// <param name="throwNullException">Raises or not <see cref="NullReferenceException" />.</param>
            /// <returns>Comparison result.</returns>
            /// <exception cref="ArgumentNullException"><paramref name="int1" /> or <paramref name="int2" /> is a null reference and <paramref name="throwNullException" /> is set to true.</exception>
            static public int Cmp(IntX int1, IntX int2, bool throwNullException)
            {
                // If one of the operands is null, throw exception or return -2
                bool isNull1 = ReferenceEquals(int1, null);
                bool isNull2 = ReferenceEquals(int2, null);
                if (isNull1 || isNull2)
                {
                    if (throwNullException)
                    {
                        throw new ArgumentNullException(isNull1 ? "int1" : "int2", "Can't use null in comparsion operations.");
                    }
                    else
                    {
                        return isNull1 && isNull2 ? 0 : -2;
                    }
                }

                // Compare sign
                if (int1._negative && !int2._negative) return -1;
                if (!int1._negative && int2._negative) return 1;

                // Compare presentation
                return DigitOpHelper.Cmp(int1._digits, int1._length, int2._digits, int2._length) * (int1._negative ? -1 : 1);
            }

            /// <summary>
            /// Compares <see cref="IntX" /> object to int.
            /// Returns "-1" if <paramref name="int1" /> < <paramref name="int2" />, "0" if equal and "1" if >.
            /// </summary>
            /// <param name="int1">First big integer.</param>
            /// <param name="int2">Second integer.</param>
            /// <returns>Comparison result.</returns>
            static public int Cmp(IntX int1, int int2)
            {
                // Special processing for zero
                if (int2 == 0) return int1._length == 0 ? 0 : (int1._negative ? -1 : 1);
                if (int1._length == 0) return int2 > 0 ? -1 : 1;

                // Compare presentation
                if (int1._length > 1) return int1._negative ? -1 : 1;
                uint digit2;
                bool negative2;
                DigitHelper.ToUInt32WithSign(int2, out digit2, out negative2);

                // Compare sign
                if (int1._negative && !negative2) return -1;
                if (!int1._negative && negative2) return 1;

                return int1._digits[0] == digit2 ? 0 : (int1._digits[0] < digit2 ^ negative2 ? -1 : 1);
            }

            /// <summary>
            /// Compares <see cref="IntX" /> object to unsigned int.
            /// Returns "-1" if <paramref name="int1" /> < <paramref name="int2" />, "0" if equal and "1" if >.
            /// For internal use.
            /// </summary>
            /// <param name="int1">First big integer.</param>
            /// <param name="int2">Second unsigned integer.</param>
            /// <returns>Comparsion result.</returns>
            static public int Cmp(IntX int1, uint int2)
            {
                // Special processing for zero
                if (int2 == 0) return int1._length == 0 ? 0 : (int1._negative ? -1 : 1);
                if (int1._length == 0) return -1;

                // Compare presentation
                if (int1._negative) return -1;
                if (int1._length > 1) return 1;
                return int1._digits[0] == int2 ? 0 : (int1._digits[0] < int2 ? -1 : 1);
            }

            #endregion Compare operation

            #region Shift operation

            /// <summary>
            /// Shifts <see cref="IntX" /> object.
            /// Determines which operation to use basing on shift sign.
            /// </summary>
            /// <param name="intX">Big integer.</param>
            /// <param name="shift">Bits count to shift.</param>
            /// <param name="toLeft">If true the shifting to the left.</param>
            /// <returns>Bitwise shift operation result.</returns>
            /// <exception cref="ArgumentNullException"><paramref name="intX" /> is a null reference.</exception>
            static public IntX Sh(IntX intX, long shift, bool toLeft)
            {
                // Exceptions
                if (ReferenceEquals(intX, null))
                {
                    throw new ArgumentNullException("intX", "Operand can't be null.");
                }

                // Zero can't be shifted
                if (intX._length == 0) return new IntX();

                // Can't shift on zero value
                if (shift == 0) return new IntX(intX);

                // Determine real bits count and direction
                ulong bitCount;
                bool negativeShift;
                DigitHelper.ToUInt64WithSign(shift, out bitCount, out negativeShift);
                toLeft ^= negativeShift;

                // Get position of the most significant bit in intX and amount of bits in intX
                int msb = Bits.Msb(intX._digits[intX._length - 1]);
                ulong intXBitCount = (ulong)(intX._length - 1) * Constants.DigitBitCount + (ulong)msb + 1UL;

                // If shifting to the right and shift is too big then return zero
                if (!toLeft && bitCount >= intXBitCount) return new IntX();

                // Calculate new bit count
                ulong newBitCount = toLeft ? intXBitCount + bitCount : intXBitCount - bitCount;

                // If shifting to the left and shift is too big to fit in big integer, throw an exception
                if (toLeft && newBitCount > Constants.MaxBitCount)
                {
                    throw new ArgumentException("One of the operated big integers is too big.", "intX");
                }

                // Get exact length of new big integer (no normalize is ever needed here).
                // Create new big integer with given length
                uint newLength = (uint)(newBitCount / Constants.DigitBitCount + (newBitCount % Constants.DigitBitCount == 0 ? 0UL : 1UL));
                IntX newInt = new IntX(newLength, intX._negative);

                // Get full and small shift values
                uint fullDigits = (uint)(bitCount / Constants.DigitBitCount);
                int smallShift = (int)(bitCount % Constants.DigitBitCount);

                // We can just copy (no shift) if small shift is zero
                if (smallShift == 0)
                {
                    if (toLeft)
                    {
                        Array.Copy(intX._digits, 0, newInt._digits, fullDigits, intX._length);
                    }
                    else
                    {
                        Array.Copy(intX._digits, fullDigits, newInt._digits, 0, newLength);
                    }
                }
                else
                {
                    // Do copy with real shift in the needed direction
                    if (toLeft)
                    {
                        DigitOpHelper.Shr(intX._digits, 0, intX._length, newInt._digits, fullDigits + 1, Constants.DigitBitCount - smallShift);
                    }
                    else
                    {
                        // If new result length is smaller then original length we shouldn't lose any digits
                        if (newLength < intX._length)
                        {
                            newLength++;
                        }

                        DigitOpHelper.Shr(intX._digits, fullDigits, newLength, newInt._digits, 0, smallShift);
                    }
                }

                return newInt;
            }

            #endregion Shift operation
        }
        #endregion

        #region NewtonHelper
        /// <summary>
        /// Contains helping methods for fast division
        /// using Newton approximation approach and fast multiplication.
        /// </summary>
        static internal class NewtonHelper
        {
            /// <summary>
            /// Generates integer opposite to the given one using approximation.
            /// Uses algorithm from Khuth vol. 2 3rd Edition (4.3.3).
            /// </summary>
            /// <param name="digitsPtr">Initial big integer digits.</param>
            /// <param name="length">Initial big integer length.</param>
            /// <param name="maxLength">Precision length.</param>
            /// <param name="bufferPtr">Buffer in which shifted big integer may be stored.</param>
            /// <param name="newLength">Resulting big integer length.</param>
            /// <param name="rightShift">How much resulting big integer is shifted to the left (or: must be shifted to the right).</param>
            /// <returns>Resulting big integer digits.</returns>
            static unsafe public uint[] GetIntegerOpposite(uint* digitsPtr, uint length, uint maxLength, uint* bufferPtr, out uint newLength, out ulong rightShift)
            {
                // Maybe initially shift original digits a bit to the left
                // (it must have MSB on 2nd position in the highest digit)
                int msb = Bits.Msb(digitsPtr[length - 1]);
                rightShift = (ulong)(length - 1) * Constants.DigitBitCount + (ulong)msb + 1U;

                if (msb != 2)
                {
                    // Shift to the left (via actually right shift)
                    int leftShift = (2 - msb + Constants.DigitBitCount) % Constants.DigitBitCount;
                    length = DigitOpHelper.Shr(digitsPtr, length, bufferPtr + 1, Constants.DigitBitCount - leftShift, true) + 1U;
                }
                else
                {
                    // Simply use the same digits without any shifting
                    bufferPtr = digitsPtr;
                }

                // Calculate possible result length
                int lengthLog2 = Bits.CeilLog2(maxLength);
                uint newLengthMax = 1U << (lengthLog2 + 1);
                int lengthLog2Bits = lengthLog2 + Bits.Msb(Constants.DigitBitCount);

                // Create result digits
                uint[] resultDigits = ArrayPool<uint>.Instance.GetArray(newLengthMax); //new uint[newLengthMax];
                uint resultLength;

                // Create temporary digits for squared result (twice more size)
                uint[] resultDigitsSqr = ArrayPool<uint>.Instance.GetArray(newLengthMax); //new uint[newLengthMax];
                uint resultLengthSqr;

                // Create temporary digits for squared result * buffer
                uint[] resultDigitsSqrBuf = new uint[newLengthMax + length];
                uint resultLengthSqrBuf;

                // Fix some digits
                fixed (uint* resultPtrFixed = resultDigits, resultSqrPtrFixed = resultDigitsSqr, resultSqrBufPtr = resultDigitsSqrBuf)
                {
                    uint* resultPtr = resultPtrFixed;
                    uint* resultSqrPtr = resultSqrPtrFixed;

                    // Cache two first digits
                    uint bufferDigitN1 = bufferPtr[length - 1];
                    uint bufferDigitN2 = bufferPtr[length - 2];

                    // Prepare result.
                    // Initially result = floor(32 / (4*v1 + 2*v2 + v3)) / 4
                    // (last division is not floored - here we emulate fixed point)
                    resultDigits[0] = 32 / bufferDigitN1;
                    resultLength = 1;

                    // Prepare variables
                    uint nextBufferTempStorage = 0;
                    int nextBufferTempShift;
                    uint nextBufferLength = 1U;
                    uint* nextBufferPtr = &nextBufferTempStorage;

                    ulong bitsAfterDotResult;
                    ulong bitsAfterDotResultSqr;
                    ulong bitsAfterDotNextBuffer;
                    ulong bitShift;
                    uint shiftOffset;

                    uint* tempPtr;
                    uint[] tempDigits;

                    // Iterate 'till result will be precise enough
                    for (int k = 0; k < lengthLog2Bits; ++k)
                    {
                        // Get result squared
                        resultLengthSqr = IntXMultiplier.Multiply(
                            resultPtr,
                            resultLength,
                            resultPtr,
                            resultLength,
                            resultSqrPtr);

                        // Calculate current result bits after dot
                        bitsAfterDotResult = (1UL << k) + 1UL;
                        bitsAfterDotResultSqr = bitsAfterDotResult << 1;

                        // Here we will get the next portion of data from bufferPtr
                        if (k < 4)
                        {
                            // For now buffer intermediate has length 1 and we will use this fact
                            nextBufferTempShift = 1 << (k + 1);
                            nextBufferTempStorage =
                                bufferDigitN1 << nextBufferTempShift |
                                bufferDigitN2 >> (Constants.DigitBitCount - nextBufferTempShift);

                            // Calculate amount of bits after dot (simple formula here)
                            bitsAfterDotNextBuffer = (ulong)nextBufferTempShift + 3UL;
                        }
                        else
                        {
                            // Determine length to get from bufferPtr
                            nextBufferLength = System.Math.Min((1U << (k - 4)) + 1U, length);
                            nextBufferPtr = bufferPtr + (length - nextBufferLength);

                            // Calculate amount of bits after dot (simple formula here)
                            bitsAfterDotNextBuffer = (ulong)(nextBufferLength - 1U) * Constants.DigitBitCount + 3UL;
                        }

                        // Multiply result ^ 2 and nextBuffer + calculate new amount of bits after dot
                        resultLengthSqrBuf = IntXMultiplier.Multiply(
                            resultSqrPtr,
                            resultLengthSqr,
                            nextBufferPtr,
                            nextBufferLength,
                            resultSqrBufPtr);

                        bitsAfterDotNextBuffer += bitsAfterDotResultSqr;

                        // Now calculate 2 * result - resultSqrBufPtr
                        --bitsAfterDotResult;
                        --bitsAfterDotResultSqr;

                        // Shift result on a needed amount of bits to the left
                        bitShift = bitsAfterDotResultSqr - bitsAfterDotResult;
                        shiftOffset = (uint)(bitShift / Constants.DigitBitCount);
                        resultLength =
                            shiftOffset + 1U +
                            DigitOpHelper.Shr(
                                resultPtr,
                                resultLength,
                                resultSqrPtr + shiftOffset + 1U,
                                Constants.DigitBitCount - (int)(bitShift % Constants.DigitBitCount),
                                true);

                        // Swap resultPtr and resultSqrPtr pointers
                        tempPtr = resultPtr;
                        resultPtr = resultSqrPtr;
                        resultSqrPtr = tempPtr;

                        tempDigits = resultDigits;
                        resultDigits = resultDigitsSqr;
                        resultDigitsSqr = tempDigits;

                        DigitHelper.SetBlockDigits(resultPtr, shiftOffset, 0U);

                        bitShift = bitsAfterDotNextBuffer - bitsAfterDotResultSqr;
                        shiftOffset = (uint)(bitShift / Constants.DigitBitCount);

                        if (shiftOffset < resultLengthSqrBuf)
                        {
                            // Shift resultSqrBufPtr on a needed amount of bits to the right
                            resultLengthSqrBuf = DigitOpHelper.Shr(
                                resultSqrBufPtr + shiftOffset,
                                resultLengthSqrBuf - shiftOffset,
                                resultSqrBufPtr,
                                (int)(bitShift % Constants.DigitBitCount),
                                false);

                            // Now perform actual subtraction
                            resultLength = DigitOpHelper.Sub(
                                resultPtr,
                                resultLength,
                                resultSqrBufPtr,
                                resultLengthSqrBuf,
                                resultPtr);
                        }
                        else
                        {
                            // Actually we can assume resultSqrBufPtr == 0 here and have nothing to do
                        }
                    }
                }

                // Return some arrays to pool
                ArrayPool<uint>.Instance.AddArray(resultDigitsSqr);

                rightShift += (1UL << lengthLog2Bits) + 1UL;
                newLength = resultLength;
                return resultDigits;
            }
        }
        #endregion

        #region FhtHelper
        /// <summary>
        /// Contains helping methods for work with FHT (Fast Hartley Transform).
        /// FHT is a better alternative of FFT (Fast Fourier Transform) - at least for <see cref="System.IntX" />.
        /// </summary>
        static unsafe internal class FhtHelper
        {
            #region struct TrigValues

            /// <summary>
            /// Trigonometry values.
            /// </summary>
            internal struct TrigValues
            {
                /// <summary>
                /// Sin value from <see cref="SineTable" />.
                /// </summary>
                public double TableSin;

                /// <summary>
                /// Cos value from <see cref="SineTable" />.
                /// </summary>
                public double TableCos;

                /// <summary>
                /// Sin value.
                /// </summary>
                public double Sin;

                /// <summary>
                /// Cos value.
                /// </summary>
                public double Cos;
            }

            #endregion struct SinCos

            #region Private constants (or static readonly fields)

            // double[] data base
            const int DoubleDataBytes = 1;
            const int DoubleDataLengthShift = 2 - (DoubleDataBytes >> 1);
            const int DoubleDataDigitShift = DoubleDataBytes << 3;
            const long DoubleDataBaseInt = 1L << DoubleDataDigitShift;
            const double DoubleDataBase = DoubleDataBaseInt;
            const double DoubleDataBaseDiv2 = DoubleDataBase / 2.0;

            // SQRT(2) and SQRT(2) / 2
            static readonly double Sqrt2 = System.Math.Sqrt(2.0);
            static readonly double Sqrt2Div2 = Sqrt2 / 2.0;

            // SIN() table
            static readonly double[] SineTable = new double[31];

            #endregion Private constants (or static readonly fields)

            #region Constructors

            // .cctor
            static FhtHelper()
            {
                // Initialize SinTable
                FillSineTable(SineTable);
            }

            #endregion Constructors

            #region Data conversion methods

            /// <summary>
            /// Converts <see cref="System.IntX" /> digits into real representation (used in FHT).
            /// </summary>
            /// <param name="digits">Big integer digits.</param>
            /// <param name="length"><paramref name="digits" /> length.</param>
            /// <param name="newLength">Multiplication result length (must be pow of 2).</param>
            /// <returns>Double array.</returns>
            static public double[] ConvertDigitsToDouble(uint[] digits, uint length, uint newLength)
            {
                fixed (uint* digitsPtr = digits)
                {
                    return ConvertDigitsToDouble(digitsPtr, length, newLength);
                }
            }

            /// <summary>
            /// Converts <see cref="System.IntX" /> digits into real representation (used in FHT).
            /// </summary>
            /// <param name="digitsPtr">Big integer digits.</param>
            /// <param name="length"><paramref name="digitsPtr" /> length.</param>
            /// <param name="newLength">Multiplication result length (must be pow of 2).</param>
            /// <returns>Double array.</returns>
            static public double[] ConvertDigitsToDouble(uint* digitsPtr, uint length, uint newLength)
            {
                // Maybe fix newLength (make it the nearest bigger pow of 2)
                newLength = 1U << Bits.CeilLog2(newLength);

                // For better FHT accuracy we will choose length smaller then dwords.
                // So new length must be modified accordingly
                newLength <<= DoubleDataLengthShift;
                double[] data = ArrayPool<double>.Instance.GetArray(newLength);

                // Run in unsafe context
                fixed (double* slice = data)
                {
                    // Amount of units pointed by digitsPtr
                    uint unitCount = length << DoubleDataLengthShift;

                    // Copy all words from digits into new double[]
                    byte* unitDigitsPtr = (byte*)digitsPtr;
                    for (uint i = 0; i < unitCount; ++i)
                    {
                        slice[i] = unitDigitsPtr[i];
                    }

                    // Clear remaining double values (this array is from pool and may be dirty)
                    DigitHelper.SetBlockDigits(slice + unitCount, newLength - unitCount, 0.0);

                    // FHT (as well as FFT) works more accurate with "balanced" data, so let's balance it
                    double carry = 0, dataDigit;
                    for (uint i = 0; i < unitCount || i < newLength && carry != 0; ++i)
                    {
                        dataDigit = slice[i] + carry;
                        if (dataDigit >= DoubleDataBaseDiv2)
                        {
                            dataDigit -= DoubleDataBase;
                            carry = 1.0;
                        }
                        else
                        {
                            carry = 0;
                        }
                        slice[i] = dataDigit;
                    }

                    if (carry > 0)
                    {
                        slice[0] -= carry;
                    }
                }

                return data;
            }

            /// <summary>
            /// Converts real digits representation (result of FHT) into usual <see cref="System.IntX" /> digits.
            /// </summary>
            /// <param name="array">Real digits representation.</param>
            /// <param name="length"><paramref name="array" /> length.</param>
            /// <param name="digitsLength">New digits array length (we always do know the upper value for this array).</param>
            /// <param name="digitsRes">Big integer digits.</param>
            static unsafe public void ConvertDoubleToDigits(double[] array, uint length, uint digitsLength, uint[] digitsRes)
            {
                fixed (double* slice = array)
                fixed (uint* digitsResPtr = digitsRes)
                {
                    ConvertDoubleToDigits(slice, length, digitsLength, digitsResPtr);
                }
            }

            /// <summary>
            /// Converts real digits representation (result of FHT) into usual <see cref="System.IntX" /> digits.
            /// </summary>
            /// <param name="slice">Real digits representation.</param>
            /// <param name="length"><paramref name="slice" /> length.</param>
            /// <param name="digitsLength">New digits array length (we always do know the upper value for this array).</param>
            /// <param name="digitsResPtr">Resulting digits storage.</param>
            /// <returns>Big integer digits (dword values).</returns>
            static unsafe public void ConvertDoubleToDigits(double* slice, uint length, uint digitsLength, uint* digitsResPtr)
            {
                // Calculate data multiplier (don't forget about additional div 2)
                double normalizeMultiplier = 0.5 / length;

                // Count of units in digits
                uint unitCount = digitsLength << DoubleDataLengthShift;

                // Carry and current digit
                double carry = 0, dataDigit;
                long carryInt = 0, dataDigitInt;

                // Walk thru all double digits
                byte* unitDigitsPtr = (byte*)digitsResPtr;
                for (uint i = 0; i < length; ++i)
                {
                    // Get data digit (don't forget it might be balanced)
                    dataDigit = slice[i] * normalizeMultiplier;

                    // Round to the nearest
                    dataDigitInt = (long)(dataDigit < 0 ? dataDigit - 0.5 : dataDigit + 0.5) + carryInt;

                    // Get next carry floored; maybe modify data digit
                    carry = dataDigitInt / DoubleDataBase;
                    if (carry < 0)
                    {
                        carry += carry % 1.0;
                    }
                    carryInt = (long)carry;

                    dataDigitInt -= carryInt << DoubleDataDigitShift;
                    if (dataDigitInt < 0)
                    {
                        dataDigitInt += DoubleDataBaseInt;
                        --carryInt;
                    }

                    // Maybe add to the digits
                    if (i < unitCount)
                    {
                        unitDigitsPtr[i] = (byte)dataDigitInt;
                    }
                }

                // Last carry must be accounted
                if (carryInt < 0)
                {
                    digitsResPtr[0] -= (uint)-carryInt;
                }
                else if (carryInt > 0)
                {
                    uint digitsCarry = (uint)carryInt, oldDigit;
                    for (uint i = 0; digitsCarry != 0 && i < digitsLength; ++i)
                    {
                        oldDigit = digitsResPtr[i];
                        digitsResPtr[i] += digitsCarry;

                        // Check for an overflow
                        digitsCarry = digitsResPtr[i] < oldDigit ? 1U : 0U;
                    }
                }
            }

            #endregion Data conversion methods

            #region FHT

            /// <summary>
            /// Performs FHT "in place" for given double[] array.
            /// </summary>
            /// <param name="array">Double array.</param>
            /// <param name="length">Array length.</param>
            static public void Fht(double[] array, uint length)
            {
                fixed (double* slice = array)
                {
                    Fht(slice, length, Bits.Msb(length));
                }
            }

            /// <summary>
            /// Performs FHT "in place" for given double[] array slice.
            /// </summary>
            /// <param name="slice">Double array slice.</param>
            /// <param name="length">Slice length.</param>
            /// <param name="lengthLog2">Log2(<paramref name="length" />).</param>
            static public void Fht(double* slice, uint length, int lengthLog2)
            {
                // Special fast processing for length == 4
                if (length == 4)
                {
                    Fht4(slice);
                    return;
                }

                // Divide data into 2 recursively processed parts
                length >>= 1;
                --lengthLog2;
                double* rightSlice = slice + length;

                uint lengthDiv2 = length >> 1;
                uint lengthDiv4 = length >> 2;

                // Perform initial "butterfly" operations over left and right array parts
                double leftDigit = slice[0];
                double rightDigit = rightSlice[0];
                slice[0] = leftDigit + rightDigit;
                rightSlice[0] = leftDigit - rightDigit;

                leftDigit = slice[lengthDiv2];
                rightDigit = rightSlice[lengthDiv2];
                slice[lengthDiv2] = leftDigit + rightDigit;
                rightSlice[lengthDiv2] = leftDigit - rightDigit;

                // Get initial trig values
                //TrigValues trigValues = GetInitialTrigValues(lengthLog2);
                TrigValues trigValues = new TrigValues();
                GetInitialTrigValues(&trigValues, lengthLog2);

                // Perform "butterfly"
                for (uint i = 1; i < lengthDiv4; ++i)
                {
                    FhtButterfly(slice, rightSlice, i, length - i, trigValues.Cos, trigValues.Sin);
                    FhtButterfly(slice, rightSlice, lengthDiv2 - i, lengthDiv2 + i, trigValues.Sin, trigValues.Cos);

                    // Get next trig values
                    NextTrigValues(&trigValues);
                }

                // Final "butterfly"
                FhtButterfly(slice, rightSlice, lengthDiv4, length - lengthDiv4, Sqrt2Div2, Sqrt2Div2);

                // Finally perform recursive run
                Fht(slice, length, lengthLog2);
                Fht(rightSlice, length, lengthLog2);
            }

            /// <summary>
            /// Performs FHT "in place" for given double[] array slice.
            /// Fast version for length == 4.
            /// </summary>
            /// <param name="slice">Double array slice.</param>
            static private void Fht4(double* slice)
            {
                // Get 4 digits
                double d0 = slice[0];
                double d1 = slice[1];
                double d2 = slice[2];
                double d3 = slice[3];

                // Perform fast "butterfly" addition/subtraction for them.
                // In case when length == 4 we can do it without trigonometry
                double d02 = d0 + d2;
                double d13 = d1 + d3;
                slice[0] = d02 + d13;
                slice[1] = d02 - d13;

                d02 = d0 - d2;
                d13 = d1 - d3;
                slice[2] = d02 + d13;
                slice[3] = d02 - d13;
            }

            #endregion FHT

            #region FHT results multiplication

            /// <summary>
            /// Multiplies two FHT results and stores multiplication in first one.
            /// </summary>
            /// <param name="data">First FHT result.</param>
            /// <param name="data2">Second FHT result.</param>
            /// <param name="length">FHT results length.</param>
            static public void MultiplyFhtResults(double[] data, double[] data2, uint length)
            {
                fixed (double* slice = data, slice2 = data2)
                {
                    MultiplyFhtResults(slice, slice2, length);
                }
            }

            /// <summary>
            /// Multiplies two FHT results and stores multiplication in first one.
            /// </summary>
            /// <param name="slice">First FHT result.</param>
            /// <param name="slice2">Second FHT result.</param>
            /// <param name="length">FHT results length.</param>
            static public void MultiplyFhtResults(double* slice, double* slice2, uint length)
            {
                // Step0 and Step1
                slice[0] *= 2.0 * slice2[0];
                slice[1] *= 2.0 * slice2[1];

                // Perform all other steps
                double d11, d12, d21, d22, ad, sd;
                for (uint stepStart = 2, stepEnd = 4, index1, index2; stepStart < length; stepStart *= 2, stepEnd *= 2)
                {
                    for (index1 = stepStart, index2 = stepEnd - 1; index1 < stepEnd; index1 += 2, index2 -= 2)
                    {
                        d11 = slice[index1];
                        d12 = slice[index2];
                        d21 = slice2[index1];
                        d22 = slice2[index2];

                        ad = d11 + d12;
                        sd = d11 - d12;

                        slice[index1] = d21 * ad + d22 * sd;
                        slice[index2] = d22 * ad - d21 * sd;
                    }
                }
            }

            #endregion FHT results multiplication

            #region Reverse FHT

            /// <summary>
            /// Performs FHT reverse "in place" for given double[] array.
            /// </summary>
            /// <param name="array">Double array.</param>
            /// <param name="length">Array length.</param>
            static public void ReverseFht(double[] array, uint length)
            {
                fixed (double* slice = array)
                {
                    ReverseFht(slice, length, Bits.Msb(length));
                }
            }

            /// <summary>
            /// Performs reverse FHT "in place" for given double[] array slice.
            /// </summary>
            /// <param name="slice">Double array slice.</param>
            /// <param name="length">Slice length.</param>
            /// <param name="lengthLog2">Log2(<paramref name="length" />).</param>
            static public void ReverseFht(double* slice, uint length, int lengthLog2)
            {
                // Special fast processing for length == 8
                if (length == 8)
                {
                    ReverseFht8(slice);
                    return;
                }

                // Divide data into 2 recursively processed parts
                length >>= 1;
                --lengthLog2;
                double* rightSlice = slice + length;

                uint lengthDiv2 = length >> 1;
                uint lengthDiv4 = length >> 2;

                // Perform recursive run
                ReverseFht(slice, length, lengthLog2);
                ReverseFht(rightSlice, length, lengthLog2);

                // Get initial trig values
                TrigValues trigValues = new TrigValues();
                GetInitialTrigValues(&trigValues, lengthLog2);

                // Perform "butterfly"
                for (uint i = 1; i < lengthDiv4; ++i)
                {
                    ReverseFhtButterfly(slice, rightSlice, i, length - i, trigValues.Cos, trigValues.Sin);
                    ReverseFhtButterfly(slice, rightSlice, lengthDiv2 - i, lengthDiv2 + i, trigValues.Sin, trigValues.Cos);

                    // Get next trig values
                    NextTrigValues(&trigValues);
                }

                // Final "butterfly"
                ReverseFhtButterfly(slice, rightSlice, lengthDiv4, length - lengthDiv4, Sqrt2Div2, Sqrt2Div2);
                ReverseFhtButterfly2(slice, rightSlice, 0, 0, 1.0, 0);
                ReverseFhtButterfly2(slice, rightSlice, lengthDiv2, lengthDiv2, 0, 1.0);
            }

            /// <summary>
            /// Performs reverse FHT "in place" for given double[] array slice.
            /// Fast version for length == 8.
            /// </summary>
            /// <param name="slice">Double array slice.</param>
            static private void ReverseFht8(double* slice)
            {
                // Get 8 digits
                double d0 = slice[0];
                double d1 = slice[1];
                double d2 = slice[2];
                double d3 = slice[3];
                double d4 = slice[4];
                double d5 = slice[5];
                double d6 = slice[6];
                double d7 = slice[7];

                // Calculate add and subtract pairs for first 4 digits
                double da01 = d0 + d1;
                double ds01 = d0 - d1;
                double da23 = d2 + d3;
                double ds23 = d2 - d3;

                // Calculate add and subtract pairs for first pairs
                double daa0123 = da01 + da23;
                double dsa0123 = da01 - da23;
                double das0123 = ds01 + ds23;
                double dss0123 = ds01 - ds23;

                // Calculate add and subtract pairs for next 4 digits
                double da45 = d4 + d5;
                double ds45 = (d4 - d5) * Sqrt2;
                double da67 = d6 + d7;
                double ds67 = (d6 - d7) * Sqrt2;

                // Calculate add and subtract pairs for next pairs
                double daa4567 = da45 + da67;
                double dsa4567 = da45 - da67;

                // Store digits values
                slice[0] = daa0123 + daa4567;
                slice[4] = daa0123 - daa4567;
                slice[2] = dsa0123 + dsa4567;
                slice[6] = dsa0123 - dsa4567;
                slice[1] = das0123 + ds45;
                slice[5] = das0123 - ds45;
                slice[3] = dss0123 + ds67;
                slice[7] = dss0123 - ds67;
            }

            #endregion Reverse FHT

            #region "Butterfly" methods for FHT

            /// <summary>
            /// Performs "butterfly" operation for <see cref="Fht(double*, uint, int)" />.
            /// </summary>
            /// <param name="slice1">First data array slice.</param>
            /// <param name="slice2">Second data array slice.</param>
            /// <param name="index1">First slice index.</param>
            /// <param name="index2">Second slice index.</param>
            /// <param name="cos">Cos value.</param>
            /// <param name="sin">Sin value.</param>
            static private void FhtButterfly(double* slice1, double* slice2, uint index1, uint index2, double cos, double sin)
            {
                double d11 = slice1[index1];
                double d12 = slice1[index2];

                double temp = slice2[index1];
                slice1[index1] = d11 + temp;
                d11 -= temp;

                temp = slice2[index2];
                slice1[index2] = d12 + temp;
                d12 -= temp;

                slice2[index1] = d11 * cos + d12 * sin;
                slice2[index2] = d11 * sin - d12 * cos;
            }

            /// <summary>
            /// Performs "butterfly" operation for <see cref="ReverseFht(double*, uint, int)" />.
            /// </summary>
            /// <param name="slice1">First data array slice.</param>
            /// <param name="slice2">Second data array slice.</param>
            /// <param name="index1">First slice index.</param>
            /// <param name="index2">Second slice index.</param>
            /// <param name="cos">Cos value.</param>
            /// <param name="sin">Sin value.</param>
            static private void ReverseFhtButterfly(double* slice1, double* slice2, uint index1, uint index2, double cos, double sin)
            {
                double d21 = slice2[index1];
                double d22 = slice2[index2];

                double temp = slice1[index1];
                double temp2 = d21 * cos + d22 * sin;
                slice1[index1] = temp + temp2;
                slice2[index1] = temp - temp2;

                temp = slice1[index2];
                temp2 = d21 * sin - d22 * cos;
                slice1[index2] = temp + temp2;
                slice2[index2] = temp - temp2;
            }

            /// <summary>
            /// Performs "butterfly" operation for <see cref="ReverseFht(double*, uint, int)" />.
            /// Another version.
            /// </summary>
            /// <param name="slice1">First data array slice.</param>
            /// <param name="slice2">Second data array slice.</param>
            /// <param name="index1">First slice index.</param>
            /// <param name="index2">Second slice index.</param>
            /// <param name="cos">Cos value.</param>
            /// <param name="sin">Sin value.</param>
            static private void ReverseFhtButterfly2(double* slice1, double* slice2, uint index1, uint index2, double cos, double sin)
            {
                double temp = slice1[index1];
                double temp2 = slice2[index1] * cos + slice2[index2] * sin;
                slice1[index1] = temp + temp2;
                slice2[index2] = temp - temp2;
            }

            #endregion "Butterfly" methods for FHT

            #region Trigonometry working methods

            /// <summary>
            /// Fills sine table for FHT.
            /// </summary>
            /// <param name="sineTable">Sine table to fill.</param>
            static private void FillSineTable(double[] sineTable)
            {
                for (int i = 0, p = 1; i < sineTable.Length; ++i, p *= 2)
                {
                    sineTable[i] = System.Math.Sin(System.Math.PI / p);
                }
            }

            /// <summary>
            /// Initializes trigonometry values for FHT.
            /// </summary>
            /// <param name="valuesPtr">Values to init.</param>
            /// <param name="lengthLog2">Log2(processing slice length).</param>
            static private void GetInitialTrigValues(TrigValues* valuesPtr, int lengthLog2)
            {
                valuesPtr->TableSin = SineTable[lengthLog2];
                valuesPtr->TableCos = SineTable[lengthLog2 + 1];
                valuesPtr->TableCos *= -2.0 * valuesPtr->TableCos;

                valuesPtr->Sin = valuesPtr->TableSin;
                valuesPtr->Cos = valuesPtr->TableCos + 1.0;
            }

            /// <summary>
            /// Generates next trigonometry values for FHT basing on previous ones.
            /// </summary>
            /// <param name="valuesPtr">Current trig values.</param>
            static private void NextTrigValues(TrigValues* valuesPtr)
            {
                double oldCos = valuesPtr->Cos;
                valuesPtr->Cos = valuesPtr->Cos * valuesPtr->TableCos - valuesPtr->Sin * valuesPtr->TableSin + valuesPtr->Cos;
                valuesPtr->Sin = valuesPtr->Sin * valuesPtr->TableCos + oldCos * valuesPtr->TableSin + valuesPtr->Sin;
            }

            #endregion Trigonometry working methods
        }
        #endregion

        #region DigitOpHelper
        /// <summary>
        /// Contains helping methods for operations over <see cref="System.IntX" /> digits as arrays.
        /// </summary>
        static internal class DigitOpHelper
        {
            #region Add operation

            /// <summary>
            /// Adds two big integers.
            /// </summary>
            /// <param name="digits1">First big integer digits.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="digits2">Second big integer digits.</param>
            /// <param name="length2">Second big integer length.</param>
            /// <param name="digitsRes">Resulting big integer digits.</param>
            /// <returns>Resulting big integer length.</returns>
            static unsafe public uint Add(uint[] digits1, uint length1, uint[] digits2, uint length2, uint[] digitsRes)
            {
                fixed (uint* digitsPtr1 = digits1, digitsPtr2 = digits2, digitsResPtr = digitsRes)
                {
                    return Add(digitsPtr1, length1, digitsPtr2, length2, digitsResPtr);
                }
            }

            /// <summary>
            /// Adds two big integers using pointers.
            /// </summary>
            /// <param name="digitsPtr1">First big integer digits.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="digitsPtr2">Second big integer digits.</param>
            /// <param name="length2">Second big integer length.</param>
            /// <param name="digitsResPtr">Resulting big integer digits.</param>
            /// <returns>Resulting big integer length.</returns>
            static unsafe public uint Add(uint* digitsPtr1, uint length1, uint* digitsPtr2, uint length2, uint* digitsResPtr)
            {
                ulong c = 0;

                if (length1 < length2)
                {
                    // First must be bigger - swap
                    uint lengthTemp = length1;
                    length1 = length2;
                    length2 = lengthTemp;

                    uint* ptrTemp = digitsPtr1;
                    digitsPtr1 = digitsPtr2;
                    digitsPtr2 = ptrTemp;
                }

                // Perform digits adding
                for (uint i = 0; i < length2; ++i)
                {
                    c += (ulong)digitsPtr1[i] + digitsPtr2[i];
                    digitsResPtr[i] = (uint)c;
                    c >>= 32;
                }

                // Perform digits + carry moving
                for (uint i = length2; i < length1; ++i)
                {
                    c += digitsPtr1[i];
                    digitsResPtr[i] = (uint)c;
                    c >>= 32;
                }

                // Account last carry
                if (c != 0)
                {
                    digitsResPtr[length1++] = (uint)c;
                }

                return length1;
            }

            #endregion Add operation

            #region Subtract operation

            /// <summary>
            /// Subtracts two big integers.
            /// </summary>
            /// <param name="digits1">First big integer digits.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="digits2">Second big integer digits.</param>
            /// <param name="length2">Second big integer length.</param>
            /// <param name="digitsRes">Resulting big integer digits.</param>
            /// <returns>Resulting big integer length.</returns>
            static unsafe public uint Sub(uint[] digits1, uint length1, uint[] digits2, uint length2, uint[] digitsRes)
            {
                fixed (uint* digitsPtr1 = digits1, digitsPtr2 = digits2, digitsResPtr = digitsRes)
                {
                    return Sub(digitsPtr1, length1, digitsPtr2, length2, digitsResPtr);
                }
            }

            /// <summary>
            /// Subtracts two big integers using pointers.
            /// </summary>
            /// <param name="digitsPtr1">First big integer digits.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="digitsPtr2">Second big integer digits.</param>
            /// <param name="length2">Second big integer length.</param>
            /// <param name="digitsResPtr">Resulting big integer digits.</param>
            /// <returns>Resulting big integer length.</returns>
            static unsafe public uint Sub(uint* digitsPtr1, uint length1, uint* digitsPtr2, uint length2, uint* digitsResPtr)
            {
                ulong c = 0;

                // Perform digits subtraction
                for (uint i = 0; i < length2; ++i)
                {
                    c = (ulong)digitsPtr1[i] - digitsPtr2[i] - c;
                    digitsResPtr[i] = (uint)c;
                    c >>= 63;
                }

                // Perform digits + carry moving
                for (uint i = length2; i < length1; ++i)
                {
                    c = digitsPtr1[i] - c;
                    digitsResPtr[i] = (uint)c;
                    c >>= 63;
                }

                return DigitHelper.GetRealDigitsLength(digitsResPtr, length1);
            }

            #endregion Subtract operation

            #region Divide/modulo operation - when second length == 1

            /// <summary>
            /// Divides one big integer represented by it's digits on another one big integer.
            /// Reminder is always filled (but not the result).
            /// </summary>
            /// <param name="digits1">First big integer digits.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="int2">Second integer.</param>
            /// <param name="divRes">Div result (can be null - not filled in this case).</param>
            /// <param name="modRes">Remainder (always filled).</param>
            /// <returns>Result length (0 if result is null).</returns>
            static unsafe public uint DivMod(uint[] digits1, uint length1, uint int2, uint[] divRes, out uint modRes)
            {
                fixed (uint* digits1Ptr = digits1, divResPtr = divRes)
                {
                    return DivMod(digits1Ptr, length1, int2, divResPtr, out modRes);
                }
            }

            /// <summary>
            /// Divides one big integer represented by it's digits on another one big integer.
            /// Reminder is always filled (but not the result).
            /// </summary>
            /// <param name="digitsPtr1">First big integer digits.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="int2">Second integer.</param>
            /// <param name="divResPtr">Div result (can be null - not filled in this case).</param>
            /// <param name="modRes">Remainder (always filled).</param>
            /// <returns>Result length (0 if result is null).</returns>
            static unsafe public uint DivMod(uint* digitsPtr1, uint length1, uint int2, uint* divResPtr, out uint modRes)
            {
                ulong c = 0;
                uint res;
                for (uint index = length1 - 1; index < length1; --index)
                {
                    c = (c << Constants.DigitBitCount) + digitsPtr1[index];
                    res = (uint)(c / int2);
                    c -= (ulong)res * int2;

                    divResPtr[index] = res;
                }
                modRes = (uint)c;

                return length1 - (divResPtr[length1 - 1] == 0 ? 1U : 0U);
            }

            /// <summary>
            /// Divides one big integer represented by it's digits on another one big integer.
            /// Only remainder is filled.
            /// </summary>
            /// <param name="digits1">First big integer digits.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="int2">Second integer.</param>
            /// <returns>Remainder.</returns>
            static unsafe public uint Mod(uint[] digits1, uint length1, uint int2)
            {
                fixed (uint* digitsPtr1 = digits1)
                {
                    return Mod(digitsPtr1, length1, int2);
                }
            }

            /// <summary>
            /// Divides one big integer represented by it's digits on another one big integer.
            /// Only remainder is filled.
            /// </summary>
            /// <param name="digitsPtr1">First big integer digits.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="int2">Second integer.</param>
            /// <returns>Remainder.</returns>
            static unsafe public uint Mod(uint* digitsPtr1, uint length1, uint int2)
            {
                ulong c = 0;
                uint res;
                for (uint* ptr1 = digitsPtr1 + length1 - 1; ptr1 >= digitsPtr1; --ptr1)
                {
                    c = (c << Constants.DigitBitCount) + *ptr1;
                    res = (uint)(c / int2);
                    c -= (ulong)res * int2;
                }

                return (uint)c;
            }

            #endregion Divide/modulo operation - when second length == 1

            #region Compare operation

            /// <summary>
            /// Compares 2 <see cref="System.IntX" /> objects represented by digits only (not taking sign into account).
            /// Returns "-1" if <paramref name="digits1" /> < <paramref name="digits2" />, "0" if equal and "1" if >.
            /// </summary>
            /// <param name="digits1">First big integer digits.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="digits2">Second big integer digits.</param>
            /// <param name="length2">Second big integer length.</param>
            /// <returns>Comparison result.</returns>
            static unsafe public int Cmp(uint[] digits1, uint length1, uint[] digits2, uint length2)
            {
                // Always compare length if one of the integers has zero length
                if (length1 == 0 || length2 == 0) return CmpLen(length1, length2);

                fixed (uint* digitsPtr1 = digits1, digitsPtr2 = digits2)
                {
                    return Cmp(digitsPtr1, length1, digitsPtr2, length2);
                }
            }

            /// <summary>
            /// Compares 2 <see cref="System.IntX" /> objects represented by pointers only (not taking sign into account).
            /// Returns "-1" if <paramref name="digitsPtr1" /> < <paramref name="digitsPtr2" />, "0" if equal and "1" if >.
            /// </summary>
            /// <param name="digitsPtr1">First big integer digits.</param>
            /// <param name="length1">First big integer length.</param>
            /// <param name="digitsPtr2">Second big integer digits.</param>
            /// <param name="length2">Second big integer length.</param>
            /// <returns>Comparison result.</returns>
            static unsafe public int Cmp(uint* digitsPtr1, uint length1, uint* digitsPtr2, uint length2)
            {
                // Maybe length comparing will be enough
                int res = CmpLen(length1, length2);
                if (res != -2) return res;

                for (uint index = length1 - 1; index < length1; --index)
                {
                    if (digitsPtr1[index] != digitsPtr2[index]) return digitsPtr1[index] < digitsPtr2[index] ? -1 : 1;
                }
                return 0;
            }

            /// <summary>
            /// Compares two integers lengths. Returns -2 if further comparing is needed.
            /// </summary>
            /// <param name="length1">First big integer length.</param>
            /// <param name="length2">Second big integer length.</param>
            /// <returns>Comparison result.</returns>
            static int CmpLen(uint length1, uint length2)
            {
                if (length1 < length2) return -1;
                if (length1 > length2) return 1;
                return length1 == 0 ? 0 : -2;
            }

            #endregion Compare operation

            #region Shift operation

            /// <summary>
            /// Shifts big integer.
            /// </summary>
            /// <param name="digits">Big integer digits.</param>
            /// <param name="offset">Big integer digits offset.</param>
            /// <param name="length">Big integer length.</param>
            /// <param name="digitsRes">Resulting big integer digits.</param>
            /// <param name="resOffset">Resulting big integer digits offset.</param>
            /// <param name="rightShift">Shift to the right (always between 1 an 31).</param>
            static unsafe public void Shr(uint[] digits, uint offset, uint length, uint[] digitsRes, uint resOffset, int rightShift)
            {
                fixed (uint* digitsPtr = digits, digitsResPtr = digitsRes)
                {
                    Shr(digitsPtr + offset, length, digitsResPtr + resOffset, rightShift, resOffset != 0);
                }
            }

            /// <summary>
            /// Shifts big integer.
            /// </summary>
            /// <param name="digitsPtr">Big integer digits.</param>
            /// <param name="length">Big integer length.</param>
            /// <param name="digitsResPtr">Resulting big integer digits.</param>
            /// <param name="rightShift">Shift to the right (always between 1 an 31).</param>
            /// <param name="resHasOffset">True if <paramref name="digitsResPtr" /> has offset.</param>
            /// <returns>Resulting big integer length.</returns>
            unsafe static public uint Shr(uint* digitsPtr, uint length, uint* digitsResPtr, int rightShift, bool resHasOffset)
            {
                int rightShiftRev = Constants.DigitBitCount - rightShift;

                // Shift first digit in special way
                if (resHasOffset)
                {
                    digitsResPtr[-1] = digitsPtr[0] << rightShiftRev;
                }

                if (rightShift == 0)
                {
                    // Handle special situation here - only memcpy is needed (maybe)
                    if (digitsPtr != digitsResPtr)
                    {
                        DigitHelper.DigitsBlockCopy(digitsPtr, digitsResPtr, length);
                    }
                }
                else
                {
                    // Shift all digits except last one
                    uint* digitsPtrEndPrev = digitsPtr + length - 1;
                    uint* digitsPtrNext = digitsPtr + 1;
                    for (; digitsPtr < digitsPtrEndPrev; ++digitsPtr, ++digitsPtrNext, ++digitsResPtr)
                    {
                        *digitsResPtr = *digitsPtr >> rightShift | *digitsPtrNext << rightShiftRev;
                    }

                    // Shift last digit in special way
                    uint lastValue = *digitsPtr >> rightShift;
                    if (lastValue != 0)
                    {
                        *digitsResPtr = lastValue;
                    }
                    else
                    {
                        --length;
                    }
                }

                return length;
            }

            #endregion Shift operation
        }
        #endregion

        #region DigitHelper
        /// <summary>
        /// Contains big integer uint[] digits utility methods.
        /// </summary>
        static internal class DigitHelper
        {
            #region Working with digits length methods

            /// <summary>
            /// Returns real length of digits array (excluding leading zeroes).
            /// </summary>
            /// <param name="digits">Big integer digits.</param>
            /// <param name="length">Initial big integers length.</param>
            /// <returns>Real length.</returns>
            static public uint GetRealDigitsLength(uint[] digits, uint length)
            {
                for (; length > 0 && digits[length - 1] == 0; --length) ;
                return length;
            }

            /// <summary>
            /// Returns real length of digits array (excluding leading zeroes).
            /// </summary>
            /// <param name="digits">Big integer digits.</param>
            /// <param name="length">Initial big integers length.</param>
            /// <returns>Real length.</returns>
            static unsafe public uint GetRealDigitsLength(uint* digits, uint length)
            {
                for (; length > 0 && digits[length - 1] == 0; --length) ;
                return length;
            }

            /// <summary>
            /// Determines <see cref="IntX" /> object with lower length.
            /// </summary>
            /// <param name="int1">First big integer.</param>
            /// <param name="int2">Second big integer.</param>
            /// <param name="smallerInt">Resulting smaller big integer (by length only).</param>
            /// <param name="biggerInt">Resulting bigger big integer (by length only).</param>
            static public void GetMinMaxLengthObjects(IntX int1, IntX int2, out IntX smallerInt, out IntX biggerInt)
            {
                if (int1._length < int2._length)
                {
                    smallerInt = int1;
                    biggerInt = int2;
                }
                else
                {
                    smallerInt = int2;
                    biggerInt = int1;
                }
            }

            #endregion Working with digits length methods

            #region Signed to unsigned+sign conversion methods

            /// <summary>
            /// Converts int value to uint digit and value sign.
            /// </summary>
            /// <param name="value">Initial value.</param>
            /// <param name="resultValue">Resulting unsigned part.</param>
            /// <param name="negative">Resulting sign.</param>
            static public void ToUInt32WithSign(int value, out uint resultValue, out bool negative)
            {
                negative = value < 0;
                resultValue = !negative
                    ? (uint)value
                    : value != int.MinValue ? (uint)-value : int.MaxValue + 1U;
            }

            /// <summary>
            /// Converts long value to ulong digit and value sign.
            /// </summary>
            /// <param name="value">Initial value.</param>
            /// <param name="resultValue">Resulting unsigned part.</param>
            /// <param name="negative">Resulting sign.</param>
            static public void ToUInt64WithSign(long value, out ulong resultValue, out bool negative)
            {
                negative = value < 0;
                resultValue = !negative
                    ? (ulong)value
                    : value != long.MinValue ? (ulong)-value : long.MaxValue + 1UL;
            }

            #endregion Signed to unsigned+sign conversion methods

            #region Working with digits directly methods

            /// <summary>
            /// Sets digits in given block to given value.
            /// </summary>
            /// <param name="block">Block start pointer.</param>
            /// <param name="blockLength">Block length.</param>
            /// <param name="value">Value to set.</param>
            static unsafe public void SetBlockDigits(uint* block, uint blockLength, uint value)
            {
                for (uint* blockEnd = block + blockLength; block < blockEnd; *block++ = value) ;
            }

            /// <summary>
            /// Sets digits in given block to given value.
            /// </summary>
            /// <param name="block">Block start pointer.</param>
            /// <param name="blockLength">Block length.</param>
            /// <param name="value">Value to set.</param>
            unsafe static public void SetBlockDigits(double* block, uint blockLength, double value)
            {
                for (double* blockEnd = block + blockLength; block < blockEnd; *block++ = value) ;
            }

            /// <summary>
            /// Copies digits from one block to another.
            /// </summary>
            /// <param name="blockFrom">From block start pointer.</param>
            /// <param name="blockTo">To block start pointer.</param>
            /// <param name="count">Count of dwords to copy.</param>
            static unsafe public void DigitsBlockCopy(uint* blockFrom, uint* blockTo, uint count)
            {
                for (uint* blockFromEnd = blockFrom + count; blockFrom < blockFromEnd; *blockTo++ = *blockFrom++) ;
            }

            #endregion Working with digits directly methods
        }
        #endregion

        #endregion

        internal uint[] _digits; // big integer digits
		internal uint _length; // big integer digits length
		internal bool _negative; // big integer sign ("-" if true)

		#region Constructors

		/// <summary>
		/// Creates new big integer with zero value.
		/// </summary>
		public IntX() : this(0) {}

		/// <summary>
		/// Creates new big integer from integer value.
		/// </summary>
		/// <param name="value">Integer value to create big integer from.</param>
		public IntX(int value)
		{
			if (value == 0)
			{
				// Very specific fast processing for zero values
				InitFromZero();
			}
			else
			{
				// Prepare internal fields
				_digits = new uint[_length = 1];

				// Fill the only big integer digit
				DigitHelper.ToUInt32WithSign(value, out _digits[0], out _negative);
			}
		}

		/// <summary>
		/// Creates new big integer from unsigned integer value.
		/// </summary>
		/// <param name="value">Unsigned integer value to create big integer from.</param>
		public IntX(uint value)
		{
			if (value == 0)
			{
				// Very specific fast processing for zero values
				InitFromZero();
			}
			else
			{
				// Prepare internal fields
				_digits = new uint[] { value };
				_length = 1;
			}
		}

		/// <summary>
		/// Creates new big integer from long value.
		/// </summary>
		/// <param name="value">Long value to create big integer from.</param>
		public IntX(long value)
		{
			if (value == 0)
			{
				// Very specific fast processing for zero values
				InitFromZero();
			}
			else
			{
				// Fill the only big integer digit
				ulong newValue;
				DigitHelper.ToUInt64WithSign(value, out newValue, out _negative);
				InitFromUlong(newValue);
			}
		}

		/// <summary>
		/// Creates new big integer from unsigned long value.
		/// </summary>
		/// <param name="value">Unsigned long value to create big integer from.</param>
		public IntX(ulong value)
		{
			if (value == 0)
			{
				// Very specific fast processing for zero values
				InitFromZero();
			}
			else
			{
				InitFromUlong(value);
			}
		}

		/// <summary>
		/// Creates new big integer from array of it's "digits".
		/// Digit with lower index has less weight.
		/// </summary>
		/// <param name="digits">Array of <see cref="IntX" /> digits.</param>
		/// <param name="negative">True if this number is negative.</param>
		/// <exception cref="ArgumentNullException"><paramref name="digits" /> is a null reference.</exception>
		public IntX(uint[] digits, bool negative)
		{
			// Exceptions
			if (digits == null)
			{
				throw new ArgumentNullException("values");
			}

			InitFromDigits(digits, negative, DigitHelper.GetRealDigitsLength(digits, (uint)digits.LongLength));
		}

		/// <summary>
		/// Creates new <see cref="IntX" /> from string.
		/// </summary>
		/// <param name="value">Number as string.</param>
		public IntX(string value)
		{
			IntX intX = Parse(value);
			InitFromIntX(intX);
		}

		/// <summary>
		/// Creates new <see cref="IntX" /> from string.
		/// </summary>
		/// <param name="value">Number as string.</param>
		/// <param name="numberBase">Number base.</param>
		public IntX(string value, uint numberBase)
		{
			IntX intX = Parse(value, numberBase);
			InitFromIntX(intX);
		}

		/// <summary>
		/// Copy constructor.
		/// </summary>
		/// <param name="value">Value to copy from.</param>
		/// <exception cref="ArgumentNullException"><paramref name="value" /> is a null reference.</exception>
		public IntX(IntX value)
		{
			// Exceptions
			if (value == null)
			{
				throw new ArgumentNullException("value");
			}

			InitFromIntX(value);
		}

		/// <summary>
		/// Creates new empty big integer with desired sign and length.
		///
		/// For internal use.
		/// </summary>
		/// <param name="length">Desired digits length.</param>
		/// <param name="negative">Desired integer sign.</param>
		internal IntX(uint length, bool negative)
		{
			_digits = new uint[_length = length];
			_negative = negative;
		}

		/// <summary>
		/// Creates new big integer from array of it's "digits" but with given length.
		/// Digit with lower index has less weight.
		///
		/// For internal use.
		/// </summary>
		/// <param name="digits">Array of <see cref="IntX" /> digits.</param>
		/// <param name="negative">True if this number is negative.</param>
		/// <param name="length">Length to use for internal digits array.</param>
		/// <exception cref="ArgumentNullException"><paramref name="digits" /> is a null reference.</exception>
		internal IntX(uint[] digits, bool negative, uint length)
		{
			// Exceptions
			if (digits == null)
			{
				throw new ArgumentNullException("values");
			}

			InitFromDigits(digits, negative, length);
		}

		#endregion Constructors

		#region Operators

		#region operator==

		/// <summary>
		/// Compares two <see cref="IntX" /> objects and returns true if their internal state is equal.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if equals.</returns>
		static public bool operator ==(IntX int1, IntX int2)
		{
			return OpHelper.Cmp(int1, int2, false) == 0;
		}

		/// <summary>
		/// Compares <see cref="IntX" /> object with integer and returns true if their internal state is equal.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second integer.</param>
		/// <returns>True if equals.</returns>
		static public bool operator ==(IntX int1, int int2)
		{
			return OpHelper.Cmp(int1, int2) == 0;
		}

		/// <summary>
		/// Compares integer with <see cref="IntX" /> object and returns true if their internal state is equal.
		/// </summary>
		/// <param name="int1">First integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if equals.</returns>
		static public bool operator ==(int int1, IntX int2)
		{
			return OpHelper.Cmp(int2, int1) == 0;
		}

		/// <summary>
		/// Compares <see cref="IntX" /> object with unsinged integer and returns true if their internal state is equal.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second unsinged integer.</param>
		/// <returns>True if equals.</returns>
		static public bool operator ==(IntX int1, uint int2)
		{
			return OpHelper.Cmp(int1, int2) == 0;
		}

		/// <summary>
		/// Compares unsinged integer with <see cref="IntX" /> object and returns true if their internal state is equal.
		/// </summary>
		/// <param name="int1">First unsinged integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if equals.</returns>
		static public bool operator ==(uint int1, IntX int2)
		{
			return OpHelper.Cmp(int2, int1) == 0;
		}

		#endregion operator==

		#region operator!=

		/// <summary>
		/// Compares two <see cref="IntX" /> objects and returns true if their internal state is not equal.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if not equals.</returns>
		static public bool operator !=(IntX int1, IntX int2)
		{
			return OpHelper.Cmp(int1, int2, false) != 0;
		}

		/// <summary>
		/// Compares <see cref="IntX" /> object with integer and returns true if their internal state is not equal.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second integer.</param>
		/// <returns>True if not equals.</returns>
		static public bool operator !=(IntX int1, int int2)
		{
			return OpHelper.Cmp(int1, int2) != 0;
		}

		/// <summary>
		/// Compares integer with <see cref="IntX" /> object and returns true if their internal state is not equal.
		/// </summary>
		/// <param name="int1">First integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if not equals.</returns>
		static public bool operator !=(int int1, IntX int2)
		{
			return OpHelper.Cmp(int2, int1) != 0;
		}

		/// <summary>
		/// Compares <see cref="IntX" /> object with unsigned integer and returns true if their internal state is not equal.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second unsigned integer.</param>
		/// <returns>True if not equals.</returns>
		static public bool operator !=(IntX int1, uint int2)
		{
			return OpHelper.Cmp(int1, int2) != 0;
		}

		/// <summary>
		/// Compares unsigned integer with <see cref="IntX" /> object and returns true if their internal state is not equal.
		/// </summary>
		/// <param name="int1">First unsigned integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if not equals.</returns>
		static public bool operator !=(uint int1, IntX int2)
		{
			return OpHelper.Cmp(int2, int1) != 0;
		}

		#endregion operator!=

		#region operator>

		/// <summary>
		/// Compares two <see cref="IntX" /> objects and returns true if first is greater.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if first is greater.</returns>
		static public bool operator >(IntX int1, IntX int2)
		{
			return OpHelper.Cmp(int1, int2, true) > 0;
		}

		/// <summary>
		/// Compares <see cref="IntX" /> object with integer and returns true if first is greater.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second integer.</param>
		/// <returns>True if first is greater.</returns>
		static public bool operator >(IntX int1, int int2)
		{
			return OpHelper.Cmp(int1, int2) > 0;
		}

		/// <summary>
		/// Compares integer with <see cref="IntX" /> object and returns true if first is greater.
		/// </summary>
		/// <param name="int1">First integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if first is greater.</returns>
		static public bool operator >(int int1, IntX int2)
		{
			return OpHelper.Cmp(int2, int1) < 0;
		}

		/// <summary>
		/// Compares <see cref="IntX" /> object with unsigned integer and returns true if first is greater.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second unsigned integer.</param>
		/// <returns>True if first is greater.</returns>
		static public bool operator >(IntX int1, uint int2)
		{
			return OpHelper.Cmp(int1, int2) > 0;
		}

		/// <summary>
		/// Compares unsigned integer with <see cref="IntX" /> object and returns true if first is greater.
		/// </summary>
		/// <param name="int1">First unsigned integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if first is greater.</returns>
		static public bool operator >(uint int1, IntX int2)
		{
			return OpHelper.Cmp(int2, int1) < 0;
		}

		#endregion operator>

		#region operator>=

		/// <summary>
		/// Compares two <see cref="IntX" /> objects and returns true if first is greater or equal.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if first is greater or equal.</returns>
		static public bool operator >=(IntX int1, IntX int2)
		{
			return OpHelper.Cmp(int1, int2, true) >= 0;
		}

		/// <summary>
		/// Compares <see cref="IntX" /> object with integer and returns true if first is greater or equal.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second integer.</param>
		/// <returns>True if first is greater or equal.</returns>
		static public bool operator >=(IntX int1, int int2)
		{
			return OpHelper.Cmp(int1, int2) >= 0;
		}

		/// <summary>
		/// Compares integer with <see cref="IntX" /> object and returns true if first is greater or equal.
		/// </summary>
		/// <param name="int1">First integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if first is greater or equal.</returns>
		static public bool operator >=(int int1, IntX int2)
		{
			return OpHelper.Cmp(int2, int1) <= 0;
		}

		/// <summary>
		/// Compares <see cref="IntX" /> object with unsinged integer and returns true if first is greater or equal.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second unsinged integer.</param>
		/// <returns>True if first is greater or equal.</returns>
		static public bool operator >=(IntX int1, uint int2)
		{
			return OpHelper.Cmp(int1, int2) >= 0;
		}

		/// <summary>
		/// Compares unsinged integer with <see cref="IntX" /> object and returns true if first is greater or equal.
		/// </summary>
		/// <param name="int1">First unsinged integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if first is greater or equal.</returns>
		static public bool operator >=(uint int1, IntX int2)
		{
			return OpHelper.Cmp(int2, int1) <= 0;
		}

		#endregion operator>=

		#region operator<

		/// <summary>
		/// Compares two <see cref="IntX" /> objects and returns true if first is lighter.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if first is lighter.</returns>
		static public bool operator <(IntX int1, IntX int2)
		{
			return OpHelper.Cmp(int1, int2, true) < 0;
		}

		/// <summary>
		/// Compares <see cref="IntX" /> object with integer and returns true if first is lighter.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second integer.</param>
		/// <returns>True if first is lighter.</returns>
		static public bool operator <(IntX int1, int int2)
		{
			return OpHelper.Cmp(int1, int2) < 0;
		}

		/// <summary>
		/// Compares integer with <see cref="IntX" /> object and returns true if first is lighter.
		/// </summary>
		/// <param name="int1">First integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if first is lighter.</returns>
		static public bool operator <(int int1, IntX int2)
		{
			return OpHelper.Cmp(int2, int1) > 0;
		}

		/// <summary>
		/// Compares <see cref="IntX" /> object with unsinged integer and returns true if first is lighter.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second unsinged integer.</param>
		/// <returns>True if first is lighter.</returns>
		static public bool operator <(IntX int1, uint int2)
		{
			return OpHelper.Cmp(int1, int2) < 0;
		}

		/// <summary>
		/// Compares unsinged integer with <see cref="IntX" /> object and returns true if first is lighter.
		/// </summary>
		/// <param name="int1">First unsinged integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if first is lighter.</returns>
		static public bool operator <(uint int1, IntX int2)
		{
			return OpHelper.Cmp(int2, int1) > 0;
		}

		#endregion operator<

		#region operator<=

		/// <summary>
		/// Compares two <see cref="IntX" /> objects and returns true if first is lighter or equal.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if first is lighter or equal.</returns>
		static public bool operator <=(IntX int1, IntX int2)
		{
			return OpHelper.Cmp(int1, int2, true) <= 0;
		}

		/// <summary>
		/// Compares <see cref="IntX" /> object with integer and returns true if first is lighter or equal.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second integer.</param>
		/// <returns>True if first is lighter or equal.</returns>
		static public bool operator <=(IntX int1, int int2)
		{
			return OpHelper.Cmp(int1, int2) <= 0;
		}

		/// <summary>
		/// Compares integer with <see cref="IntX" /> object and returns true if first is lighter or equal.
		/// </summary>
		/// <param name="int1">First integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if first is lighter or equal.</returns>
		static public bool operator <=(int int1, IntX int2)
		{
			return OpHelper.Cmp(int2, int1) >= 0;
		}

		/// <summary>
		/// Compares <see cref="IntX" /> object with unsinged integer and returns true if first is lighter or equal.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second unsinged integer.</param>
		/// <returns>True if first is lighter or equal.</returns>
		static public bool operator <=(IntX int1, uint int2)
		{
			return OpHelper.Cmp(int1, int2) <= 0;
		}

		/// <summary>
		/// Compares unsinged integer with <see cref="IntX" /> object and returns true if first is lighter or equal.
		/// </summary>
		/// <param name="int1">First unsinged integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>True if first is lighter or equal.</returns>
		static public bool operator <=(uint int1, IntX int2)
		{
			return OpHelper.Cmp(int2, int1) >= 0;
		}

		#endregion operator<=

		#region operator+ and operator-

		/// <summary>
		/// Adds one <see cref="IntX" /> object to another.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>Addition result.</returns>
		static public IntX operator +(IntX int1, IntX int2)
		{
			return OpHelper.AddSub(int1, int2, false);
		}

		/// <summary>
		/// Subtracts one <see cref="IntX" /> object from another.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>Subtraction result.</returns>
		static public IntX operator -(IntX int1, IntX int2)
		{
			return OpHelper.AddSub(int1, int2, true);
		}

		#endregion operator+ and operator-

		#region operator*

		/// <summary>
		/// Multiplies one <see cref="IntX" /> object on another.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>Multiply result.</returns>
		static public IntX operator *(IntX int1, IntX int2)
        {
            return IntXMultiplier.Multiply(int1, int2);
		}

		#endregion operator*

		#region operator/ and operator%

		/// <summary>
		/// Divides one <see cref="IntX" /> object by another.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>Division result.</returns>
		static public IntX operator /(IntX int1, IntX int2)
		{
			IntX modRes;
			return IntXDivider.DivMod(int1, int2, out modRes, DivModResultFlags.Div);
		}

		/// <summary>
		/// Divides one <see cref="IntX" /> object by another and returns division modulo.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>Modulo result.</returns>
		static public IntX operator %(IntX int1, IntX int2)
		{
			IntX modRes;
			IntXDivider.DivMod(int1, int2, out modRes, DivModResultFlags.Mod);
			return modRes;
		}

		#endregion operator/ and operator%

		#region operator<< and operator>>

        /// <summary>
        /// Shifts <see cref="IntX" /> object on selected bits count to the left.
        /// </summary>
        /// <param name="intX">Big integer.</param>
        /// <param name="shift">Bits count.</param>
        /// <returns>Shifting result.</returns>
        static public IntX operator <<(IntX intX, int shift)
        {
            return OpHelper.Sh(intX, shift, true);
        }

        /// <summary>
        /// Shifts <see cref="IntX" /> object on selected bits count to the right.
        /// </summary>
        /// <param name="intX">Big integer.</param>
        /// <param name="shift">Bits count.</param>
        /// <returns>Shifting result.</returns>
        static public IntX operator >>(IntX intX, int shift)
        {
            return OpHelper.Sh(intX, shift, false);
        }

		#endregion operator<< and operator>>

		#region +, -, ++, -- unary operators

		/// <summary>
		/// Returns the same <see cref="IntX" /> value.
		/// </summary>
		/// <param name="value">Initial value.</param>
		/// <returns>The same value, but new object.</returns>
		/// <exception cref="ArgumentNullException"><paramref name="value" /> is a null reference.</exception>
		static public IntX operator +(IntX value)
		{
			// Exception
			if (ReferenceEquals(value, null))
			{
				throw new ArgumentNullException("value");
			}

			return new IntX(value);
		}

		/// <summary>
		/// Returns the same <see cref="IntX" /> value, but with other sign.
		/// </summary>
		/// <param name="value">Initial value.</param>
		/// <returns>The same value, but with other sign.</returns>
		/// <exception cref="ArgumentNullException"><paramref name="value" /> is a null reference.</exception>
		static public IntX operator -(IntX value)
		{
			// Exception
			if (ReferenceEquals(value, null))
			{
				throw new ArgumentNullException("value");
			}

			IntX newValue = new IntX(value);
			if (newValue._length != 0)
			{
				newValue._negative = !newValue._negative;
			}
			return newValue;
		}

		/// <summary>
		/// Returns increased <see cref="IntX" /> value.
		/// </summary>
		/// <param name="value">Initial value.</param>
		/// <returns>Increased value.</returns>
		/// <exception cref="ArgumentNullException"><paramref name="value" /> is a null reference.</exception>
		static public IntX operator ++(IntX value)
		{
			// Exception
			if (ReferenceEquals(value, null))
			{
				throw new ArgumentNullException("value");
			}

			return value + 1U;
		}

		/// <summary>
		/// Returns decreased <see cref="IntX" /> value.
		/// </summary>
		/// <param name="value">Initial value.</param>
		/// <returns>Decreased value.</returns>
		/// <exception cref="ArgumentNullException"><paramref name="value" /> is a null reference.</exception>
		static public IntX operator --(IntX value)
		{
			// Exception
			if (ReferenceEquals(value, null))
			{
				throw new ArgumentNullException("value");
			}

			return value - 1U;
		}

		#endregion +, -, ++, -- unary operators

		#region Conversion operators

		#region To IntX (Implicit)

		/// <summary>
		/// Implicitly converts <see cref="Int32" /> to <see cref="IntX" />.
		/// </summary>
		/// <param name="value">Value to convert.</param>
		/// <returns>Conversion result.</returns>
		static public implicit operator IntX(int value)
		{
			return new IntX(value);
		}

		/// <summary>
		/// Implicitly converts <see cref="UInt32" /> to <see cref="IntX" />.
		/// </summary>
		/// <param name="value">Value to convert.</param>
		/// <returns>Conversion result.</returns>
		static public implicit operator IntX(uint value)
		{
			return new IntX(value);
		}

		/// <summary>
		/// Implicitly converts <see cref="UInt16" /> to <see cref="IntX" />.
		/// </summary>
		/// <param name="value">Value to convert.</param>
		/// <returns>Conversion result.</returns>
		static public implicit operator IntX(ushort value)
		{
			return new IntX(value);
		}

		/// <summary>
		/// Implicitly converts <see cref="Int64" /> to <see cref="IntX" />.
		/// </summary>
		/// <param name="value">Value to convert.</param>
		/// <returns>Conversion result.</returns>
		static public implicit operator IntX(long value)
		{
			return new IntX(value);
		}

		/// <summary>
		/// Implicitly converts <see cref="UInt64" /> to <see cref="IntX" />.
		/// </summary>
		/// <param name="value">Value to convert.</param>
		/// <returns>Conversion result.</returns>
		static public implicit operator IntX(ulong value)
		{
			return new IntX(value);
		}

		#endregion To IntX (Implicit)

		#region From IntX (Explicit)

		/// <summary>
		/// Explicitly converts <see cref="IntX" /> to <see cref="int" />.
		/// </summary>
		/// <param name="value">Value to convert.</param>
		/// <returns>Conversion result.</returns>
		static public explicit operator int(IntX value)
		{
			int res = (int)(uint)value;
			return value._negative ? -res : res;
		}

		/// <summary>
		/// Explicitly converts <see cref="IntX" /> to <see cref="uint" />.
		/// </summary>
		/// <param name="value">Value to convert.</param>
		/// <returns>Conversion result.</returns>
		static public explicit operator uint(IntX value)
		{
			if (value == null)
			{
				throw new ArgumentNullException("value");
			}

			if (value._length == 0) return 0;
			return value._digits[0];
		}

		/// <summary>
		/// Explicitly converts <see cref="IntX" /> to <see cref="long" />.
		/// </summary>
		/// <param name="value">Value to convert.</param>
		/// <returns>Conversion result.</returns>
		static public explicit operator long(IntX value)
		{
			long res = (long)(ulong)value;
			return value._negative ? -res : res;
		}

		/// <summary>
		/// Explicitly converts <see cref="IntX" /> to <see cref="ulong" />.
		/// </summary>
		/// <param name="value">Value to convert.</param>
		/// <returns>Conversion result.</returns>
		static public explicit operator ulong(IntX value)
		{
			ulong res = (uint)value;
			if (value._length > 1)
			{
				res |= (ulong)value._digits[1] << Constants.DigitBitCount;
			}
			return res;
		}

		/// <summary>
		/// Explicitly converts <see cref="IntX" /> to <see cref="ushort" />.
		/// </summary>
		/// <param name="value">Value to convert.</param>
		/// <returns>Conversion result.</returns>
		static public explicit operator ushort(IntX value)
		{
			return (ushort)(uint)value;
		}

		#endregion From IntX (Explicit)

		#endregion Conversion operators

		#endregion Operators

		#region Math static methods

		#region Multiply

		/// <summary>
		/// Multiplies one <see cref="IntX" /> object on another.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>Multiply result.</returns>
		static public IntX Multiply(IntX int1, IntX int2)
		{
            return IntXMultiplier.Multiply(int1, int2);
		}

		#endregion Multiply

		#region Divide/modulo

		/// <summary>
		/// Divides one <see cref="IntX" /> object by another.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>Division result.</returns>
		static public IntX Divide(IntX int1, IntX int2)
		{
			IntX modRes;
            return IntXDivider.DivMod(int1, int2, out modRes, DivModResultFlags.Div);
		}

		/// <summary>
		/// Divides one <see cref="IntX" /> object by another and returns division modulo.
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <returns>Modulo result.</returns>
		static public IntX Modulo(IntX int1, IntX int2)
		{
			IntX modRes;
            IntXDivider.DivMod(int1, int2, out modRes, DivModResultFlags.Mod);
			return modRes;
		}

		/// <summary>
		/// Divides one <see cref="IntX" /> object on another.
		/// Returns both divident and remainder
		/// </summary>
		/// <param name="int1">First big integer.</param>
		/// <param name="int2">Second big integer.</param>
		/// <param name="modRes">Remainder big integer.</param>
		/// <returns>Division result.</returns>
		static public IntX DivideModulo(IntX int1, IntX int2, out IntX modRes)
		{
            return IntXDivider.DivMod(int1, int2, out modRes, DivModResultFlags.Div | DivModResultFlags.Mod);
		}

		#endregion Divide/modulo

		#region Pow

		/// <summary>
		/// Returns a specified big integer raised to the specified power.
		/// </summary>
		/// <param name="value">Number to raise.</param>
		/// <param name="power">Power.</param>
		/// <returns>Number in given power.</returns>
		static public IntX Pow(IntX value, uint power)
		{
			return OpHelper.Pow(value, power);
		}

		#endregion Pow

		#endregion Math static methods

		#region ToString override

		/// <summary>
		/// Returns decimal string representation of this <see cref="IntX" /> object.
		/// </summary>
		/// <returns>Decimal number in string.</returns>
		override public string ToString()
		{
			return ToString(10U, true);
		}

		/// <summary>
		/// Returns string representation of this <see cref="IntX" /> object in given base.
		/// </summary>
		/// <param name="numberBase">Base of system in which to do output.</param>
		/// <returns>Object string representation.</returns>
		public string ToString(uint numberBase)
		{
			return ToString(numberBase, true);
		}

		/// <summary>
		/// Returns string representation of this <see cref="IntX" /> object in given base.
		/// </summary>
		/// <param name="numberBase">Base of system in which to do output.</param>
		/// <param name="upperCase">Use uppercase for bases from 11 to 16 (which use letters A-F).</param>
		/// <returns>Object string representation.</returns>
		public string ToString(uint numberBase, bool upperCase)
		{
			return IntXStringConverter.ToString(this, numberBase, upperCase ? Constants.BaseUpperChars : Constants.BaseLowerChars);
		}

		/// <summary>
		/// Returns string representation of this <see cref="IntX" /> object in given base using custom alphabet.
		/// </summary>
		/// <param name="numberBase">Base of system in which to do output.</param>
		/// <param name="alphabet">Alphabet which contains chars used to represent big integer, char position is coresponding digit value.</param>
		/// <returns>Object string representation.</returns>
		public string ToString(uint numberBase, string alphabet)
		{
			StrRepHelper.AssertAlphabet(alphabet, numberBase);
            return IntXStringConverter.ToString(this, numberBase, alphabet.ToCharArray());
		}

		#endregion ToString override

		#region Parsing methods

		/// <summary>
		/// Parses provided string representation of <see cref="IntX" /> object in decimal base.
		/// If number starts from "0" then it's treated as octal; if number starts fropm "0x"
		/// then it's treated as hexadecimal.
		/// </summary>
		/// <param name="value">Number as string.</param>
		/// <returns>Parsed object.</returns>
		static public IntX Parse(string value)
		{
			return IntXParser.Parse(value, 10U, Constants.BaseCharToDigits, true);
		}

		/// <summary>
		/// Parses provided string representation of <see cref="IntX" /> object.
		/// </summary>
		/// <param name="value">Number as string.</param>
		/// <param name="numberBase">Number base.</param>
		/// <returns>Parsed object.</returns>
		static public IntX Parse(string value, uint numberBase)
		{
            return IntXParser.Parse(value, numberBase, Constants.BaseCharToDigits, false);
		}

		/// <summary>
		/// Parses provided string representation of <see cref="IntX" /> object using custom alphabet.
		/// </summary>
		/// <param name="value">Number as string.</param>
		/// <param name="numberBase">Number base.</param>
		/// <param name="alphabet">Alphabet which contains chars used to represent big integer, char position is coresponding digit value.</param>
		/// <returns>Parsed object.</returns>
		static public IntX Parse(string value, uint numberBase, string alphabet)
		{
            return IntXParser.Parse(value, numberBase, StrRepHelper.CharDictionaryFromAlphabet(alphabet, numberBase), false);
		}

		#endregion Parsing methods

		#region IEquatable/Equals/GetHashCode implementation/overrides

		/// <summary>
		/// Returns equality of this <see cref="IntX" /> with another big integer.
		/// </summary>
		/// <param name="n">Big integer to compare with.</param>
		/// <returns>True if equals.</returns>
		public bool Equals(IntX n)
		{
			return base.Equals(n) || this == n;
		}

		/// <summary>
		/// Returns equality of this <see cref="IntX" /> with another integer.
		/// </summary>
		/// <param name="n">Integer to compare with.</param>
		/// <returns>True if equals.</returns>
		public bool Equals(int n)
		{
			return this == n;
		}

		/// <summary>
		/// Returns equality of this <see cref="IntX" /> with another unsigned integer.
		/// </summary>
		/// <param name="n">Unsigned integer to compare with.</param>
		/// <returns>True if equals.</returns>
		public bool Equals(uint n)
		{
			return this == n;
		}

		/// <summary>
		/// Returns equality of this <see cref="IntX" /> with another long integer.
		/// </summary>
		/// <param name="n">Long integer to compare with.</param>
		/// <returns>True if equals.</returns>
		public bool Equals(long n)
		{
			return this == n;
		}

		/// <summary>
		/// Returns equality of this <see cref="IntX" /> with another unsigned long integer.
		/// </summary>
		/// <param name="n">Unsigned long integer to compare with.</param>
		/// <returns>True if equals.</returns>
		public bool Equals(ulong n)
		{
			return this == n;
		}

		/// <summary>
		/// Returns equality of this <see cref="IntX" /> with another object.
		/// </summary>
		/// <param name="obj">Object to compare with.</param>
		/// <returns>True if equals.</returns>
		override public bool Equals(object obj)
		{
			return obj is IntX && Equals((IntX)obj);
		}

		/// <summary>
		/// Returns hash code for this <see cref="IntX" /> object.
		/// </summary>
		/// <returns>Object hash code.</returns>
		override public int GetHashCode()
		{
			switch (_length)
			{
				case 0:
					return 0;
				case 1:
					return (int)(_digits[0] ^ _length ^ (_negative ? 1 : 0));
				default:
					return (int)(_digits[0] ^ _digits[_length - 1] ^ _length ^ (_negative ? 1 : 0));
			}
		}

		#endregion Equals/GetHashCode implementation/overrides

		#region IComparable implementation

		/// <summary>
		/// Compares current object with another big integer.
		/// </summary>
		/// <param name="n">Big integer to compare with.</param>
		/// <returns>1 if object is bigger than <paramref name="n" />, -1 if object is smaller than <paramref name="n" />, 0 if they are equal.</returns>
		public int CompareTo(IntX n)
		{
			return OpHelper.Cmp(this, n, true);
		}

		/// <summary>
		/// Compares current object with another integer.
		/// </summary>
		/// <param name="n">Integer to compare with.</param>
		/// <returns>1 if object is bigger than <paramref name="n" />, -1 if object is smaller than <paramref name="n" />, 0 if they are equal.</returns>
		public int CompareTo(int n)
		{
			return OpHelper.Cmp(this, n);
		}

		/// <summary>
		/// Compares current object with another unsigned integer.
		/// </summary>
		/// <param name="n">Unsigned integer to compare with.</param>
		/// <returns>1 if object is bigger than <paramref name="n" />, -1 if object is smaller than <paramref name="n" />, 0 if they are equal.</returns>
		public int CompareTo(uint n)
		{
			return OpHelper.Cmp(this, n);
		}

		/// <summary>
		/// Compares current object with another long integer.
		/// </summary>
		/// <param name="n">Long integer to compare with.</param>
		/// <returns>1 if object is bigger than <paramref name="n" />, -1 if object is smaller than <paramref name="n" />, 0 if they are equal.</returns>
		public int CompareTo(long n)
		{
			return OpHelper.Cmp(this, n, true);
		}

		/// <summary>
		/// Compares current object with another unsigned long integer.
		/// </summary>
		/// <param name="n">Unsigned long integer to compare with.</param>
		/// <returns>1 if object is bigger than <paramref name="n" />, -1 if object is smaller than <paramref name="n" />, 0 if they are equal.</returns>
		public int CompareTo(ulong n)
		{
			return OpHelper.Cmp(this, n, true);
		}

		/// <summary>
		/// Compares current object with another object.
		/// </summary>
		/// <param name="obj">Object to compare with.</param>
		/// <returns>1 if object is bigger than <paramref name="obj" />, -1 if object is smaller than <paramref name="obj" />, 0 if they are equal.</returns>
		public int CompareTo(object obj)
		{
			if (obj is IntX)
			{
				return CompareTo((IntX)obj);
			}
			else if (obj is int)
			{
				return CompareTo((int)obj);
			}
			else if (obj is uint)
			{
				return CompareTo((uint)obj);
			}
			else if (obj is long)
			{
				return CompareTo((long)obj);
			}
			else if (obj is ulong)
			{
				return CompareTo((ulong)obj);
			}

			throw new ArgumentException("Can't compare with provided argument.", "obj");
		}

		#endregion IComparable implementation

		#region Other public methods

		/// <summary>
		/// Frees extra space not used by digits.
		/// </summary>
		public void Normalize()
		{
			if (_digits.LongLength > _length)
			{
				uint[] newDigits = new uint[_length];
				Array.Copy(_digits, newDigits, _length);
				_digits = newDigits;
			}

			if (_length == 0)
			{
				_negative = false;
			}
		}

		/// <summary>
		/// Retrieves this <see cref="IntX" /> internal state as digits array and sign.
		/// Can be used for serialization and other purposes.
		/// Note: please use constructor instead to clone <see cref="IntX" /> object.
		/// </summary>
		/// <param name="digits">Digits array.</param>
		/// <param name="negative">Is negative integer.</param>
		public void GetInternalState(out uint[] digits, out bool negative)
		{
			digits = new uint[_length];
			Array.Copy(_digits, digits, _length);

			negative = _negative;
		}

		#endregion Other public methods

		#region Init utilitary methods

		/// <summary>
		/// Initializes class instance from zero.
		/// For internal use.
		/// </summary>
		void InitFromZero()
		{
			_length = 0;
			_digits = new uint[0];
		}

		/// <summary>
		/// Initializes class instance from <see cref="UInt64" /> value.
		/// Doesn't initialize sign.
		/// For internal use.
		/// </summary>
		/// <param name="value">Unsigned long value.</param>
		void InitFromUlong(ulong value)
		{
			// Divide ulong into 2 uint values
			uint low = (uint)value;
			uint high = (uint)(value >> Constants.DigitBitCount);

			// Prepare internal fields
			if (high == 0)
			{
				_digits = new uint[] { low };
			}
			else
			{
				_digits = new uint[] { low, high };
			}
			_length = (uint)_digits.Length;
		}

		/// <summary>
		/// Initializes class instance from another <see cref="IntX" /> value.
		/// For internal use.
		/// </summary>
		/// <param name="value">Big integer value.</param>
		void InitFromIntX(IntX value)
		{
			_digits = value._digits;
			_length = value._length;
			_negative = value._negative;
		}

		/// <summary>
		/// Initializes class instance from digits array.
		/// For internal use.
		/// </summary>
		/// <param name="digits">Big integer digits.</param>
		/// <param name="negative">Big integer sign.</param>
		/// <param name="length">Big integer length.</param>
		void InitFromDigits(uint[] digits, bool negative, uint length)
		{
			_digits = new uint[_length = length];
			Array.Copy(digits, _digits, System.Math.Min((uint)digits.LongLength, length));
			if (length != 0)
			{
				_negative = negative;
			}
		}

		#endregion Init utilitary methods

		#region Other utilitary methods

		/// <summary>
		/// Frees extra space not used by digits.
		/// </summary>
		internal void TryNormalize()
		{
            Normalize();
		}

		#endregion Other utilitary methods

        #region IDisposable Implementation
        /// <summary>
        /// Disposes of the resources
        /// </summary>
        public void Dispose()
        {
            this._digits = new uint[0];
            this._digits = null;
            System.GC.Collect();
        }
        #endregion

        #region IClonable Implementation
        /// <summary>
        /// Creates a clone of the current instance.
        /// </summary>
        /// <returns>The cloned instance.</returns>
        object ICloneable.Clone()
        {
            return new IntX(this);
        }
        #endregion

        /// <summary>
        /// Converts this IntX to a byte array.
        /// </summary>
        /// <returns></returns>
        public byte[] ToByteArray()
        {
            System.IO.MemoryStream m = new IO.MemoryStream();
            System.IO.BinaryWriter b = new IO.BinaryWriter(m);
            for (int i = 0; i < _digits.Length; i++)
            {
                b.Write(_digits[i]);
            }
            b.Flush();
            return m.GetBuffer();
        }

        private static readonly IntX _zero = new IntX(0);
        /// <summary>
        /// Zero.
        /// </summary>
        public static IntX Zero
        {
            get
            {
                return _zero;
            }
        }
    }
}

redpajama_set_name: RedPajamaGithub