BigInteger.cs

// ==++==
// 
//   Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// ==--==
/*=============================================================================
**
** Struct: BigInteger
**
** Purpose: Represents an arbitrary precision integer.
**
=============================================================================*/

using System;
using System.Diagnostics.Contracts;
using System.Collections.Generic;
using System.Globalization;
using System.Numerics;
using System.Text;
using Conditional = System.Diagnostics.ConditionalAttribute;

namespace System.Numerics
{
#if !SILVERLIGHT
    [Serializable]
#endif // !SILVERLIGHT
    public struct BigInteger : IFormattable, IComparable, IComparable<BigInteger>, IEquatable<BigInteger>                             
    {
        // ---- SECTION:  members supporting exposed properties -------------*
        #region members supporting exposed properties
        private const int knMaskHighBit = int.MinValue;
        private const uint kuMaskHighBit = unchecked((uint)int.MinValue);
        private const int kcbitUint = 32;
        private const int kcbitUlong = 64;
        private const int DecimalScaleFactorMask = 0x00FF0000;
        private const int DecimalSignMask = unchecked((int)0x80000000);

        // For values int.MinValue < n <= int.MaxValue, the value is stored in sign
        // and _bits is null. For all other values, sign is +1 or -1 and the bits are in _bits
        internal int _sign;
        internal uint[] _bits;

        // We have to make a choice of how to represent int.MinValue. This is the one
        // value that fits in an int, but whose negation does not fit in an int.
        // We choose to use a large representation, so we're symmetric with respect to negation.
        private static readonly BigInteger s_bnMinInt = new BigInteger(-1, new uint[] { kuMaskHighBit });
        private static readonly BigInteger s_bnOneInt = new BigInteger(1);
        private static readonly BigInteger s_bnZeroInt = new BigInteger(0);
        private static readonly BigInteger s_bnMinusOneInt = new BigInteger(-1);

#if CONTRACTS_FULL
        [ContractInvariantMethod]
        private void ObjectInvariant()
        {
            Contract.Invariant((_bits == null) ? _sign > Int32.MinValue :
                ((_sign == 1 || _sign == -1) && Length(_bits) > 0));
            Contract.Invariant(_bits == null || Length(_bits) > 1 || _bits[0] >= kuMaskHighBit
                , "One element array stores integers whose absolute value is between 0x80000000 and 0xFFFFFFFF");
        }
#endif

        [Conditional("DEBUG")]
        private void AssertValid()
        {
            if (_bits != null)
            {
                Contract.Assert(_sign == 1 || _sign == -1 /*, "_sign must be +1 or -1 when _bits is non-null"*/);
                Contract.Assert(Length(_bits) > 0 /*, "_bits must contain at least 1 element or be null"*/);
                if (Length(_bits) == 1)
                    Contract.Assert(_bits[0] >= kuMaskHighBit /*, "Wasted space _bits[0] could have been packed into _sign"*/);
            }
            else
                Contract.Assert(_sign > int.MinValue /*, "Int32.MinValue should not be stored in the _sign field"*/);
        }
        #endregion members supporting exposed properties

        // ---- SECTION: public properties --------------*
        #region public properties

        public static BigInteger Zero
        {
            get { return s_bnZeroInt; }
        }

        public static BigInteger One
        {
            get { return s_bnOneInt; }
        }

        public static BigInteger MinusOne
        {
            get { return s_bnMinusOneInt; }
        }       

        public bool IsPowerOfTwo
        {
            get
            {
                AssertValid();

                if (_bits == null)
                    return (_sign & (_sign - 1)) == 0 && _sign != 0;

                if (_sign != 1)
                    return false;
                int iu = Length(_bits) - 1;
                if ((_bits[iu] & (_bits[iu] - 1)) != 0)
                    return false;
                while (--iu >= 0)
                {
                    if (_bits[iu] != 0)
                        return false;
                }
                return true;
            }
        }

        public bool IsZero { get { AssertValid(); return _sign == 0; } }

        public bool IsOne { get { AssertValid(); return _sign == 1 && _bits == null; } }

        public bool IsEven { get { AssertValid(); return _bits == null ? (_sign & 1) == 0 : (_bits[0] & 1) == 0; } }

        public int Sign
        {
            get { AssertValid(); return (_sign >> (kcbitUint - 1)) - (-_sign >> (kcbitUint - 1)); }
        }
        
        #endregion public properties


        // ---- SECTION: public instance methods --------------*
        #region public instance methods

        public override bool Equals(object obj)
        {
            AssertValid();

            if (!(obj is BigInteger))
                return false;
            return Equals((BigInteger)obj);
        }

        public override int GetHashCode()
        {
            AssertValid();

            if (_bits == null)
                return _sign;
            int hash = _sign;
            for (int iv = Length(_bits); --iv >= 0; )
                hash = NumericsHelpers.CombineHash(hash, (int)_bits[iv]);
            return hash;
        }

        public bool Equals(Int64 other)
        {
            AssertValid();

            if (_bits == null)
                return _sign == other;

            int cu;
            if ((_sign ^ other) < 0 || (cu = Length(_bits)) > 2)
                return false;

            ulong uu = other < 0 ? (ulong)-other : (ulong)other;
            if (cu == 1)
                return _bits[0] == uu;
 
            return NumericsHelpers.MakeUlong(_bits[1], _bits[0]) == uu;
        }

        [CLSCompliant(false)]
        public bool Equals(UInt64 other)
        {
            AssertValid();

            if (_sign < 0)
                return false;
            if (_bits == null)
                return (ulong)_sign == other;

            int cu = Length(_bits);
            if (cu > 2)
                return false;
            if (cu == 1)
                return _bits[0] == other;
            return NumericsHelpers.MakeUlong(_bits[1], _bits[0]) == other;
        }

        public bool Equals(BigInteger other)
        {
            AssertValid();
            other.AssertValid();

            if (_sign != other._sign)
                return false;
            if (_bits == other._bits) 
                // _sign == other._sign && _bits == null && other._bits == null
                return true;

            if (_bits == null || other._bits == null)
                return false;
            int cu = Length(_bits);
            if (cu != Length(other._bits))
                return false;
            int cuDiff = GetDiffLength(_bits, other._bits, cu);
            return cuDiff == 0;
        }

        public int CompareTo(Int64 other)
        {
            AssertValid();

            if (_bits == null)
                return ((long)_sign).CompareTo(other);
            int cu;
            if ((_sign ^ other) < 0 || (cu = Length(_bits)) > 2)
                return _sign;
            ulong uu = other < 0 ? (ulong)-other : (ulong)other;
            ulong uuTmp = cu == 2 ? NumericsHelpers.MakeUlong(_bits[1], _bits[0]) : _bits[0];
            return _sign * uuTmp.CompareTo(uu);
        }

        [CLSCompliant(false)]
        public int CompareTo(UInt64 other)
        {
            AssertValid();

            if (_sign < 0)
                return -1;
            if (_bits == null)
                return ((ulong)_sign).CompareTo(other);
            int cu = Length(_bits);
            if (cu > 2)
                return +1;
            ulong uuTmp = cu == 2 ? NumericsHelpers.MakeUlong(_bits[1], _bits[0]) : _bits[0];
            return uuTmp.CompareTo(other);
        }

        public int CompareTo(BigInteger other)
        {
            AssertValid();
            other.AssertValid();

            if ((_sign ^ other._sign) < 0)
            {
                // Different signs, so the comparison is easy.
                return _sign < 0 ? -1 : +1;
            }

            // Same signs
            if (_bits == null)
            {
                if (other._bits == null)
                    return _sign < other._sign ? -1 : _sign > other._sign ? +1 : 0;
                return -other._sign;
            }
            int cuThis, cuOther;
            if (other._bits == null || (cuThis = Length(_bits)) > (cuOther = Length(other._bits)))
                return _sign;
            if (cuThis < cuOther)
                return -_sign;

            int cuDiff = GetDiffLength(_bits, other._bits, cuThis);
            if (cuDiff == 0)
                return 0;
            return _bits[cuDiff - 1] < other._bits[cuDiff - 1] ? -_sign : _sign;
        }

        public int CompareTo(Object obj)
        {
            if (obj == null)
                return 1;
            if (!(obj is BigInteger))
                throw new ArgumentException(SR.GetString(SR.Argument_MustBeBigInt));
            return this.CompareTo((BigInteger)obj);
        }

        
        // Return the value of this BigInteger as a little-endian twos-complement
        // byte array, using the fewest number of bytes possible. If the value is zero,
        // return an array of one byte whose element is 0x00.
        public byte[] ToByteArray() {
            if (_bits == null && _sign == 0)
                return new byte[] { 0 };

            // We could probably make this more efficient by eliminating one of the passes.
            // The current code does one pass for uint array -> byte array conversion,
            // and then another pass to remove unneeded bytes at the top of the array.
            uint[] dwords;
            byte highByte;

            if (_bits == null) {
                dwords = new uint[] { (uint)_sign };
                highByte = (byte)((_sign < 0) ? 0xff : 0x00);
            }
            else if(_sign == -1) {
                dwords = (uint[])_bits.Clone();
                NumericsHelpers.DangerousMakeTwosComplement(dwords);  // mutates dwords
                highByte = 0xff;
            } else {
                dwords = _bits;
                highByte = 0x00;
            }

            byte[] bytes = new byte[checked(4 * dwords.Length)];
            int curByte = 0;
            uint dword;
            for (int i = 0; i < dwords.Length; i++) {
                dword = dwords[i];
                for (int j = 0; j < 4; j++) {
                    bytes[curByte++] = (byte)(dword & 0xff);
                    dword >>= 8;
                }
            }

            // find highest significant byte
            int msb;
            for (msb = bytes.Length - 1; msb > 0; msb--) {
                if (bytes[msb] != highByte) break;
            }
            // ensure high bit is 0 if positive, 1 if negative
            bool needExtraByte = (bytes[msb] & 0x80) != (highByte & 0x80);

            byte[] trimmedBytes = new byte[msb + 1 + (needExtraByte ? 1 : 0)];
            Array.Copy(bytes, trimmedBytes, msb + 1);

            if (needExtraByte) trimmedBytes[trimmedBytes.Length - 1] = highByte;
            return trimmedBytes;
        }

        // Return the value of this BigInteger as a little-endian twos-complement
        // uint array, using the fewest number of uints possible. If the value is zero,
        // return an array of one uint whose element is 0.
        private UInt32[] ToUInt32Array() {
            if (_bits == null && _sign == 0)
                return new uint[] { 0 };

            uint[] dwords;
            uint highDWord;

            if (_bits == null) {
                dwords = new uint[] { (uint)_sign };
                highDWord = (_sign < 0) ? UInt32.MaxValue : 0;
            }
            else if(_sign == -1) {
                dwords = (uint[])_bits.Clone();
                NumericsHelpers.DangerousMakeTwosComplement(dwords);  // mutates dwords
                highDWord = UInt32.MaxValue;
            } else {
                dwords = _bits;
                highDWord = 0;
            }

            // find highest significant byte
            int msb;
            for (msb = dwords.Length - 1; msb > 0; msb--) {
                if (dwords[msb] != highDWord) break;
            }
            // ensure high bit is 0 if positive, 1 if negative
            bool needExtraByte = (dwords[msb] & 0x80000000) != (highDWord & 0x80000000);

            uint[] trimmed = new uint[msb + 1 + (needExtraByte ? 1 : 0)];
            Array.Copy(dwords, trimmed, msb + 1);

            if (needExtraByte) trimmed[trimmed.Length - 1] = highDWord;
            return trimmed;
        }


        public override String ToString() {
            return BigNumber.FormatBigInteger(this, null, NumberFormatInfo.CurrentInfo);
        }
    
        public String ToString(IFormatProvider provider) {
            return BigNumber.FormatBigInteger(this, null, NumberFormatInfo.GetInstance(provider));
        }
    
        public String ToString(String format) {
            return BigNumber.FormatBigInteger(this, format, NumberFormatInfo.CurrentInfo);
        }

        public String ToString(String format, IFormatProvider provider) {
            return BigNumber.FormatBigInteger(this, format, NumberFormatInfo.GetInstance(provider));
        }
        #endregion public instance methods

        // -------- SECTION: constructors -----------------*
        #region constructors
        public BigInteger(int value)
        {
            if (value == Int32.MinValue)
                this = s_bnMinInt;
            else {
                _sign = value;
                _bits = null;
            }
            AssertValid();
        }

        [CLSCompliant(false)]
        public BigInteger(uint value)
        {
            if (value <= Int32.MaxValue)
            {
                _sign = (int)value;
                _bits = null;
            }
            else
            {
                _sign = +1;
                _bits = new uint[1];
                _bits[0] = value;
            }
            AssertValid();
        }

        public BigInteger(Int64 value)
        {
            if (Int32.MinValue <= value && value <= Int32.MaxValue)
            {
                if (value == Int32.MinValue)
                    this = s_bnMinInt;
                else
                {
                    _sign = (int)value;
                    _bits = null;
                }
                AssertValid();
                return;
            }

            ulong x = 0;
            if (value < 0)
            {
                x = (ulong)-value;
                _sign = -1;
            }
            else
            {
                Contract.Assert(value != 0);
                x = (ulong)value;
                _sign = +1;
            }

            _bits = new uint[2];
            _bits[0] = (uint)x;
            _bits[1] = (uint)(x >> kcbitUint);
            AssertValid();
        }

        [CLSCompliant(false)]
        public BigInteger(UInt64 value)
        {
            if (value <= Int32.MaxValue)
            {
                _sign = (int)value;
                _bits = null;
            }
            else
            {
                _sign = +1;
                _bits = new uint[2];
                _bits[0] = (uint)value;
                _bits[1] = (uint)(value >> kcbitUint);
            }
            AssertValid();
        }

        public BigInteger(Single value)
        {
            if (Single.IsInfinity(value))
                throw new OverflowException(SR.GetString(SR.Overflow_BigIntInfinity));
            if (Single.IsNaN(value))
                throw new OverflowException(SR.GetString(SR.Overflow_NotANumber));
            Contract.EndContractBlock();

            _sign = 0;
            _bits = null;
            SetBitsFromDouble(value);
            AssertValid();
        }

        public BigInteger(Double value)
        {
            if (Double.IsInfinity(value))
                throw new OverflowException(SR.GetString(SR.Overflow_BigIntInfinity));
            if (Double.IsNaN(value))
                throw new OverflowException(SR.GetString(SR.Overflow_NotANumber));
            Contract.EndContractBlock();

            _sign = 0;
            _bits = null;
            SetBitsFromDouble(value);
            AssertValid();
        }

        public BigInteger(Decimal value)
        {
            // First truncate to get scale to 0 and extract bits
            int[] bits = Decimal.GetBits(Decimal.Truncate(value));

            Contract.Assert(bits.Length == 4 && (bits[3] & DecimalScaleFactorMask) == 0);

            int size = 3;
            while (size > 0 && bits[size - 1] == 0)
                size--;
            if (size == 0) {
                this = s_bnZeroInt;
            }
            else if (size == 1  && bits[0] > 0) {
                // bits[0] is the absolute value of this decimal
                // if bits[0] < 0 then it is too large to be packed into _sign
                _sign = bits[0];
                _sign *= ((bits[3] & DecimalSignMask) != 0) ? -1 : +1;
                _bits = null;
            }
            else {
                _bits = new UInt32[size];
                _bits[0] = (UInt32)bits[0];
                if (size > 1)
                    _bits[1] = (UInt32)bits[1];
                if (size > 2)
                    _bits[2] = (UInt32)bits[2];
                _sign = ((bits[3] & DecimalSignMask) != 0) ? -1 : +1;
            }
            AssertValid();
        }

        [CLSCompliant(false)]
        //
        // Create a BigInteger from a little-endian twos-complement byte array
        //
        public BigInteger(Byte[] value)
        {
            if (value == null)
                throw new ArgumentNullException("value");
            Contract.EndContractBlock();

            int byteCount = value.Length;
            bool isNegative = byteCount > 0 && ((value[byteCount - 1] & 0x80) == 0x80);

            // Try to conserve space as much as possible by checking for wasted leading byte[] entries 
            while (byteCount > 0 && value[byteCount-1] == 0) byteCount--;

            if (byteCount == 0) 
            {
                // BigInteger.Zero
                _sign = 0;
                _bits = null;
                AssertValid();
                return;
            }


            if (byteCount <= 4)
            {
                if (isNegative)
                    _sign = unchecked((int)0xffffffff);
                else
                    _sign = 0;
                for (int i = byteCount - 1; i >= 0; i--)
                {
                    _sign <<= 8;
                    _sign |= value[i];
                }   
                _bits = null;

                if (_sign < 0 && !isNegative)
                {
                    // int32 overflow
                    // example: Int64 value 2362232011 (0xCB, 0xCC, 0xCC, 0x8C, 0x0)
                    // can be naively packed into 4 bytes (due to the leading 0x0)
                    // it overflows into the int32 sign bit
                    _bits = new uint[1];
                    _bits[0] = (uint)_sign;
                    _sign = +1; 
                }
                if (_sign == Int32.MinValue)
                    this = s_bnMinInt;
            }
            else
            {
                int unalignedBytes = byteCount % 4;
                int dwordCount = byteCount / 4 + (unalignedBytes == 0 ? 0 : 1);         
                bool isZero = true;
                uint[] val = new uint[dwordCount];

                // Copy all dwords, except but don't do the last one if it's not a full four bytes
                int curDword, curByte, byteInDword;
                curByte = 3;
                for (curDword = 0; curDword < dwordCount - (unalignedBytes == 0 ? 0 : 1); curDword++) {
                    byteInDword = 0;
                    while (byteInDword < 4) {
                        if (value[curByte] != 0x00) isZero = false;
                        val[curDword] <<= 8;
                        val[curDword] |= value[curByte];
                        curByte--;
                        byteInDword++;
                    }
                    curByte += 8;
                }

                // Copy the last dword specially if it's not aligned
                if (unalignedBytes != 0) {
                    if (isNegative) val[dwordCount - 1] = 0xffffffff;
                    for (curByte = byteCount - 1; curByte >= byteCount - unalignedBytes; curByte--) {
                        if (value[curByte] != 0x00) isZero = false;
                        val[curDword] <<= 8;
                        val[curDword] |= value[curByte];
                    }
                }

                if (isZero) {
                    this = s_bnZeroInt;
                }
                else if (isNegative) {
                    NumericsHelpers.DangerousMakeTwosComplement(val); // mutates val

                    // pack _bits to remove any wasted space after the twos complement
                    int len = val.Length; 
                    while (len > 0 && val[len - 1] == 0)
                        len--;
                    if (len == 1 && ((int)(val[0])) > 0) {
                        if (val[0] == 1 /* abs(-1) */) {
                            this = s_bnMinusOneInt;
                        }
                        else if (val[0] == kuMaskHighBit /* abs(Int32.MinValue) */) {
                            this = s_bnMinInt;
                        }
                        else {
                            _sign = (-1) * ((int)val[0]);
                            _bits = null;
                        }
                    }
                    else if (len != val.Length) {
                        _sign = -1;
                        _bits = new uint[len];
                        Array.Copy(val, _bits, len);
                    }
                    else {
                        _sign = -1;
                        _bits = val;
                    }
                }
                else 
                {
                    _sign = +1;
                    _bits = val;
                }
            }        
            AssertValid();
        }

        internal BigInteger(int n, uint[] rgu)
        {
            _sign = n;
            _bits = rgu;
            AssertValid();
        }

        //
        // BigInteger(uint[] value, bool negative) 
        //
        // Constructor used during bit manipulation and arithmetic
        //
        // The uint[] value is expected to be the absolute value of the number
        // with the bool negative indicating the Sign of the value.
        //
        // When possible the uint[] will be packed into  _sign to conserve space
        //
        internal BigInteger(uint[] value, bool negative)
        {
            if (value == null)
                throw new ArgumentNullException("value");
            Contract.EndContractBlock();

            int len;
            
            // Try to conserve space as much as possible by checking for wasted leading uint[] entries 
            // sometimes the uint[] has leading zeros from bit manipulation operations & and ^
            for(len = value.Length; len > 0 && value[len-1] == 0; len--);

            if (len == 0)
                this = s_bnZeroInt;
            // values like (Int32.MaxValue+1) are stored as "0x80000000" and as such cannot be packed into _sign
            else if (len == 1 && value[0] < kuMaskHighBit)
            {
                _sign = (negative ? -(int)value[0] : (int)value[0]);
                _bits = null;
                // Although Int32.MinValue fits in _sign, we represent this case differently for negate
                if (_sign == Int32.MinValue)
                    this = s_bnMinInt;
            }
            else
            {
                _sign = negative ? -1 : +1;
                _bits = new uint[len];
                Array.Copy(value, _bits, len);
            }
            AssertValid();
        }


        //
        // Create a BigInteger from a little-endian twos-complement UInt32 array
        // When possible, value is assigned directly to this._bits without an array copy
        // so use this ctor with care
        //
        private BigInteger(uint[] value)
        {
            if (value == null)
                throw new ArgumentNullException("value");

            int dwordCount = value.Length;
            bool isNegative = dwordCount > 0 && ((value[dwordCount - 1] & 0x80000000) == 0x80000000);

            // Try to conserve space as much as possible by checking for wasted leading uint[] entries 
            while (dwordCount > 0 && value[dwordCount-1] == 0) dwordCount--;

            if (dwordCount == 0) 
            {
                // BigInteger.Zero
                this = s_bnZeroInt;
                AssertValid();
                return;
            }
            if (dwordCount == 1)
            {
                if ((int)value[0] < 0 && !isNegative) {
                    _bits = new uint[1];
                    _bits[0] = value[0];
                    _sign = +1; 
                }
                // handle the special cases where the BigInteger likely fits into _sign
                else if (Int32.MinValue == (int)value[0]) {
                    this = s_bnMinInt;
                }
                else {
                    _sign = (int)value[0];
                    _bits = null;
                }
                AssertValid();
                return;
            }

            if (!isNegative) {
                // handle the simple postive value cases where the input is already in sign magnitude
                if (dwordCount != value.Length) {
                    _sign = +1;
                    _bits = new uint[dwordCount];
                    Array.Copy(value, _bits, dwordCount);
                }
                // no trimming is possible.  Assign value directly to _bits.  
                else {
                    _sign = +1;
                    _bits = value;
                }
                AssertValid();
                return;
            }


            // finally handle the more complex cases where we must transform the input into sign magnitude
            NumericsHelpers.DangerousMakeTwosComplement(value); // mutates val

            // pack _bits to remove any wasted space after the twos complement
            int len = value.Length; 
            while (len > 0 && value[len - 1] == 0) len--;

            // the number is represented by a single dword
            if (len == 1 && ((int)(value[0])) > 0) {
                if (value[0] == 1 /* abs(-1) */) {
                    this = s_bnMinusOneInt;
                }
                else if (value[0] == kuMaskHighBit /* abs(Int32.MinValue) */) {
                    this = s_bnMinInt;
                }
                else {
                    _sign = (-1) * ((int)value[0]);
                    _bits = null;
                }
            }
            // the number is represented by multiple dwords
            // trim off any wasted uint values when possible
            else if (len != value.Length) {
                _sign = -1;
                _bits = new uint[len];
                Array.Copy(value, _bits, len);
            }
            // no trimming is possible.  Assign value directly to _bits.  
            else {
                _sign = -1;
                _bits = value;
            }
            AssertValid();
            return;
        }


        #endregion constructors


        // -------- SECTION: public static methods -----------------*
        #region public static methods
#if !SILVERLIGHT || FEATURE_NETCORE
        public static BigInteger Parse(String value) {
            return BigNumber.ParseBigInteger(value, NumberStyles.Integer, NumberFormatInfo.CurrentInfo);
        }
    
        public static BigInteger Parse(String value, NumberStyles style) {
            return BigNumber.ParseBigInteger(value, style, NumberFormatInfo.CurrentInfo);
        }

        public static BigInteger Parse(String value, IFormatProvider provider) {
            return BigNumber.ParseBigInteger(value, NumberStyles.Integer, NumberFormatInfo.GetInstance(provider));
        }

    	public static BigInteger Parse(String value, NumberStyles style, IFormatProvider provider) {
            return BigNumber.ParseBigInteger(value, style, NumberFormatInfo.GetInstance(provider));
        }

        public static Boolean TryParse(String value, out BigInteger result) {
            return BigNumber.TryParseBigInteger(value, NumberStyles.Integer, NumberFormatInfo.CurrentInfo, out result);
        }

        public static Boolean TryParse(String value, NumberStyles style, IFormatProvider provider, out BigInteger result) {
            return BigNumber.TryParseBigInteger(value, style, NumberFormatInfo.GetInstance(provider), out result);
        }
#endif //!SILVERLIGHT || FEATURE_NETCORE

        public static Int32 Compare(BigInteger left, BigInteger right)
        {
            return left.CompareTo(right);
        }

        public static BigInteger Abs(BigInteger value)
        {
            return (value >= BigInteger.Zero) ? value : -value;
        }

        public static BigInteger Add(BigInteger left, BigInteger right)
        {
            return left + right;
        }

        public static BigInteger Subtract(BigInteger left, BigInteger right)
        {
            return left - right;
        }

        public static BigInteger Multiply(BigInteger left, BigInteger right)
        {
            return left * right;
        }
            
        public static BigInteger Divide(BigInteger dividend, BigInteger divisor)
        {
            return dividend / divisor;
        }

        public static BigInteger Remainder(BigInteger dividend, BigInteger divisor)
        {
            return dividend % divisor;
        }

        public static BigInteger DivRem(BigInteger dividend, BigInteger divisor, out BigInteger remainder)
        {
            dividend.AssertValid();
            divisor.AssertValid();

            int signNum = +1;
            int signDen = +1;
            BigIntegerBuilder regNum = new BigIntegerBuilder(dividend, ref signNum);
            BigIntegerBuilder regDen = new BigIntegerBuilder(divisor, ref signDen);
            BigIntegerBuilder regQuo = new BigIntegerBuilder();

            // regNum and regQuo are overwritten with the remainder and quotient, respectively
            regNum.ModDiv(ref regDen, ref regQuo);
            remainder = regNum.GetInteger(signNum);
            return regQuo.GetInteger(signNum * signDen);
        }


        public static BigInteger Negate(BigInteger value)
        {
            return -value;
        }

        // Returns the natural (base e) logarithm of a specified number.
        public static Double Log(BigInteger value)
        {                                          
            return BigInteger.Log(value, Math.E);
        }


        public static Double Log(BigInteger value, Double baseValue)
        {
            if (value._sign < 0 || baseValue == 1.0D)
                return Double.NaN;
            if (baseValue == Double.PositiveInfinity)
                return value.IsOne ? 0.0D : Double.NaN;
            if (baseValue == 0.0D && !value.IsOne)
                return Double.NaN;
            if (value._bits == null)
                return Math.Log((double)value._sign, baseValue);

            Double c = 0, d = 0.5D;
            const Double log2 = 0.69314718055994529D;

            int uintLength = Length(value._bits);
            int topbits = BitLengthOfUInt(value._bits[uintLength - 1]);
            int bitlen = (uintLength - 1) * kcbitUint + topbits;
            uint indbit = (uint)(1 << (topbits - 1));

            for(int index = uintLength -1; index >= 0; --index)
            {
                while (indbit != 0)
                {
                    if ((value._bits[index] & indbit) != 0)
                        c += d;
                    d *= 0.5;
                    indbit >>= 1;
                }
                indbit = 0x80000000;
            }
            return (Math.Log(c) + log2 * bitlen) / Math.Log(baseValue);
        }


        public static Double Log10(BigInteger value)
        {
            return BigInteger.Log(value, 10);
        }
                
        public static BigInteger GreatestCommonDivisor(BigInteger left, BigInteger right)
        {
            left.AssertValid();
            right.AssertValid();

            // gcd(0, 0) =  0 
            // gcd(a, 0) = |a|, for a != 0, since any number is a divisor of 0, and the greatest divisor of a is |a|
            if (left._sign == 0) return BigInteger.Abs(right);
            if (right._sign == 0) return BigInteger.Abs(left);

            BigIntegerBuilder reg1 = new BigIntegerBuilder(left);
            BigIntegerBuilder reg2 = new BigIntegerBuilder(right);
            BigIntegerBuilder.GCD(ref reg1, ref reg2);

            return reg1.GetInteger(+1);
        }

        public static BigInteger Max(BigInteger left, BigInteger right)
        {
            if (left.CompareTo(right) < 0)
                return right;
            return left;
        }

        public static BigInteger Min(BigInteger left, BigInteger right)
        {
            if (left.CompareTo(right) <= 0)
                return left;
            return right;
        }


        private static void ModPowUpdateResult(ref BigIntegerBuilder regRes, ref BigIntegerBuilder regVal, ref BigIntegerBuilder regMod, ref BigIntegerBuilder regTmp)
        {
            NumericsHelpers.Swap(ref regRes, ref regTmp);
            regRes.Mul(ref regTmp, ref regVal);   // result = result * value;
            regRes.Mod(ref regMod);               // result = result % modulus;                       
        }

        private static void ModPowSquareModValue(ref BigIntegerBuilder regVal, ref BigIntegerBuilder regMod, ref BigIntegerBuilder regTmp)
        {
            NumericsHelpers.Swap(ref regVal, ref regTmp);
            regVal.Mul(ref regTmp, ref regTmp);   // value = value * value;
            regVal.Mod(ref regMod);               // value = value % modulus;
        }

        private static void ModPowInner(uint exp, ref BigIntegerBuilder regRes, ref BigIntegerBuilder regVal, ref BigIntegerBuilder regMod, ref BigIntegerBuilder regTmp)
        {
            while (exp != 0)          // !(Exponent.IsZero)
            {
                if ((exp & 1) == 1)   // !(Exponent.IsEven)
                    ModPowUpdateResult(ref regRes, ref regVal, ref regMod, ref regTmp);
                if (exp == 1)         // Exponent.IsOne - we can exit early
                    break;
                ModPowSquareModValue(ref regVal, ref regMod, ref regTmp);
                exp >>= 1;
            }
        }

        private static void ModPowInner32(uint exp, ref BigIntegerBuilder regRes, ref BigIntegerBuilder regVal, ref BigIntegerBuilder regMod, ref BigIntegerBuilder regTmp)
        {
            for (int i = 0; i < 32; i++)
            {
                if ((exp & 1) == 1)   // !(Exponent.IsEven)
                    ModPowUpdateResult(ref regRes, ref regVal, ref regMod, ref regTmp);
                ModPowSquareModValue(ref regVal, ref regMod, ref regTmp);
                exp >>= 1;
            }
        }

        public static BigInteger ModPow(BigInteger value, BigInteger exponent, BigInteger modulus)
        {
            if (exponent.Sign < 0)
                throw new ArgumentOutOfRangeException("exponent", SR.GetString(SR.ArgumentOutOfRange_MustBeNonNeg));
            Contract.EndContractBlock();

            value.AssertValid();
            exponent.AssertValid();
            modulus.AssertValid();

            int signRes = +1;
            int signVal = +1;
            int signMod = +1;
            bool expIsEven = exponent.IsEven;
            BigIntegerBuilder regRes = new BigIntegerBuilder(BigInteger.One, ref signRes);
            BigIntegerBuilder regVal = new BigIntegerBuilder(value, ref signVal);
            BigIntegerBuilder regMod = new BigIntegerBuilder(modulus, ref signMod);
            BigIntegerBuilder regTmp = new BigIntegerBuilder(regVal.Size);

            regRes.Mod(ref regMod);   // Handle special case of exponent=0, modulus=1

            if (exponent._bits == null)
            {   // exponent fits into an Int32
                ModPowInner((uint) exponent._sign, ref regRes, ref regVal, ref regMod, ref regTmp);
            }
            else
            {   // very large exponent
                int len = Length(exponent._bits);
                for (int i = 0; i < len - 1; i++)
                {
                    uint exp = exponent._bits[i];
                    ModPowInner32(exp, ref regRes, ref regVal, ref regMod, ref regTmp);
                }
                ModPowInner(exponent._bits[len - 1], ref regRes, ref regVal, ref regMod, ref regTmp);
            }

            return regRes.GetInteger(value._sign > 0 ? +1 : expIsEven ? +1 : -1);
        }

        public static BigInteger Pow(BigInteger value, Int32 exponent)
        {
            if (exponent < 0)
                throw new ArgumentOutOfRangeException("exponent", SR.GetString(SR.ArgumentOutOfRange_MustBeNonNeg));
            Contract.EndContractBlock();

            value.AssertValid();

            if (exponent == 0)
                return BigInteger.One;           
            if (exponent == 1)
                return value;
            if (value._bits == null)
            {
                if (value._sign == 1)
                    return value;
                if (value._sign == -1)
                    return (exponent & 1) != 0 ? value : 1;
                if (value._sign == 0)
                    return value;
            }

            int sign = +1;
            BigIntegerBuilder regSquare = new BigIntegerBuilder(value, ref sign);

            // Get an estimate of the size needed for regSquare and regRes, so we can minimize allocations.
            int cuSquareMin = regSquare.Size;
            int cuSquareMax = cuSquareMin;
            uint uSquareMin = regSquare.High;
            uint uSquareMax = uSquareMin + 1;
            if (uSquareMax == 0)
            {
                cuSquareMax++;
                uSquareMax = 1;
            }
            int cuResMin = 1;
            int cuResMax = 1;
            uint uResMin = 1;
            uint uResMax = 1;

            for (int expTmp = exponent; ; )
            {
                if ((expTmp & 1) != 0)
                {
                    MulUpper(ref uResMax, ref cuResMax, uSquareMax, cuSquareMax);
                    MulLower(ref uResMin, ref cuResMin, uSquareMin, cuSquareMin);
                }

                if ((expTmp >>= 1) == 0)
                    break;

                MulUpper(ref uSquareMax, ref cuSquareMax, uSquareMax, cuSquareMax);
                MulLower(ref uSquareMin, ref cuSquareMin, uSquareMin, cuSquareMin);
            }

            if (cuResMax > 1)
                regSquare.EnsureWritable(cuResMax, 0);
            BigIntegerBuilder regTmp = new BigIntegerBuilder(cuResMax);
            BigIntegerBuilder regRes = new BigIntegerBuilder(cuResMax);
            regRes.Set(1);

            if ((exponent & 1) == 0)
                sign = +1;

            for (int expTmp = exponent; ; )
            {
                if ((expTmp & 1) != 0)
                {
                    NumericsHelpers.Swap(ref regRes, ref regTmp);
                    regRes.Mul(ref regSquare, ref regTmp);
                }
                if ((expTmp >>= 1) == 0)
                    break;
                NumericsHelpers.Swap(ref regSquare, ref regTmp);
                regSquare.Mul(ref regTmp, ref regTmp);
            }

            return regRes.GetInteger(sign);
        }

        #endregion public static methods

        // -------- SECTION: public static operators -----------------*
        #region public static operators
        public static implicit operator BigInteger(Byte value)
        {
            return new BigInteger(value);
        }

        [CLSCompliant(false)]
        public static implicit operator BigInteger(SByte value)
        {
            return new BigInteger(value);
        }

        public static implicit operator BigInteger(Int16 value)
        {
            return new BigInteger(value);
        }

        [CLSCompliant(false)]
        public static implicit operator BigInteger(UInt16 value)
        {
            return new BigInteger(value);
        }


        public static implicit operator BigInteger(int value)
        {
            return new BigInteger(value);
        }

        [CLSCompliant(false)]
        public static implicit operator BigInteger(uint value)
        {
            return new BigInteger(value);
        }

        public static implicit operator BigInteger(long value)
        {
            return new BigInteger(value);
        }

        [CLSCompliant(false)]
        public static implicit operator BigInteger(ulong value)
        {
            return new BigInteger(value);
        }

        public static explicit operator BigInteger(Single value)
        {
            return new BigInteger(value);
        }

        public static explicit operator BigInteger(Double value)
        {
            return new BigInteger(value);
        }

        public static explicit operator BigInteger(Decimal value)
        {
            return new BigInteger(value);
        }

        public static explicit operator Byte(BigInteger value)
        {
            return checked((byte)((int)value));
        }

        [CLSCompliant(false)]
        public static explicit operator SByte(BigInteger value)
        {
            return checked((sbyte)((int)value));
        }

        public static explicit operator Int16(BigInteger value)
        {
            return checked((short)((int)value));
        }

        [CLSCompliant(false)]
        public static explicit operator UInt16(BigInteger value)
        {
            return checked((ushort)((int)value));
        }

        public static explicit operator Int32(BigInteger value)
        {
            value.AssertValid();
            if (value._bits == null) {
                return value._sign;  // value packed into int32 sign
            }
            else if (Length(value._bits) > 1) { // more than 32 bits
                throw new OverflowException(SR.GetString(SR.Overflow_Int32));
            }
            else if (value._sign > 0) {
                return checked((int)value._bits[0]);
            }
            else {
                if (value._bits[0] > kuMaskHighBit) {  // value > Int32.MinValue
                    throw new OverflowException(SR.GetString(SR.Overflow_Int32));
                }
                return unchecked(-(int)value._bits[0]);
            }
        }

        [CLSCompliant(false)]
        public static explicit operator UInt32(BigInteger value)
        {
            value.AssertValid();
            if (value._bits == null) {
                return checked((uint)value._sign);
            }
            else if (Length(value._bits) > 1 || value._sign < 0) {
                throw new OverflowException(SR.GetString(SR.Overflow_UInt32));
            }
            else {
                return value._bits[0];
            }
        }

        public static explicit operator Int64(BigInteger value)
        {
            value.AssertValid();
            if (value._bits == null) {
                return value._sign;
            }

            int len = Length(value._bits);
            if (len > 2) {
                throw new OverflowException(SR.GetString(SR.Overflow_Int64));
            }

            ulong uu;
            if (len > 1) {
                uu = NumericsHelpers.MakeUlong(value._bits[1], value._bits[0]);
            }
            else {
                uu = (ulong)value._bits[0];
            }

            long ll = value._sign > 0 ? (long)uu : -(long)uu;
            if ((ll > 0 && value._sign > 0) || (ll < 0 && value._sign < 0)) {
                // signs match, no overflow
                return ll;
            }
            throw new OverflowException(SR.GetString(SR.Overflow_Int64));
        }

        [CLSCompliant(false)]
        public static explicit operator UInt64(BigInteger value)
        {
            value.AssertValid();
            if (value._bits == null) {
                return checked((ulong)value._sign);
            }

            int len = Length(value._bits);
            if (len > 2 || value._sign < 0) {
                throw new OverflowException(SR.GetString(SR.Overflow_UInt64));
            }

            if (len > 1) {
                return NumericsHelpers.MakeUlong(value._bits[1], value._bits[0]);
            }
            else {
                return value._bits[0];
            }
        }

        public static explicit operator Single(BigInteger value)
        {
            return (Single)((Double)value);
        }

        public static explicit operator Double(BigInteger value)
        {
            value.AssertValid();
            if (value._bits == null)
                return value._sign;

            ulong man;
            int exp;
            int sign = +1;
            BigIntegerBuilder reg = new BigIntegerBuilder(value, ref sign);
            reg.GetApproxParts(out exp, out man);
            return NumericsHelpers.GetDoubleFromParts(sign, exp, man);
        }

        public static explicit operator Decimal(BigInteger value)
        {
            value.AssertValid();
            if (value._bits == null)
                return (Decimal)value._sign;

            int length = Length(value._bits);
            if (length > 3) throw new OverflowException(SR.GetString(SR.Overflow_Decimal));

            int lo = 0, mi = 0, hi = 0;
            if (length > 2) hi = (Int32)value._bits[2];
            if (length > 1) mi = (Int32)value._bits[1];
            if (length > 0) lo = (Int32)value._bits[0];

            return new Decimal(lo, mi, hi, value._sign < 0, 0);
        }

        public static BigInteger operator &(BigInteger left, BigInteger right) {         
            if (left.IsZero || right.IsZero) {
                return BigInteger.Zero;
            }

            uint[] x = left.ToUInt32Array();
            uint[] y = right.ToUInt32Array();
            uint[] z = new uint[Math.Max(x.Length, y.Length)];
            uint xExtend = (left._sign < 0)  ? UInt32.MaxValue : 0;
            uint yExtend = (right._sign < 0) ? UInt32.MaxValue : 0;

            for (int i = 0; i < z.Length; i++) {
                uint xu = (i < x.Length) ? x[i] : xExtend;
                uint yu = (i < y.Length) ? y[i] : yExtend;
                z[i] = xu & yu; 
            }
            return new BigInteger(z);
        }

        public static BigInteger operator |(BigInteger left, BigInteger right) {
            if (left.IsZero)
                return right;
            if (right.IsZero)
                return left;

            uint[] x = left.ToUInt32Array();
            uint[] y = right.ToUInt32Array();
            uint[] z = new uint[Math.Max(x.Length, y.Length)];
            uint xExtend = (left._sign < 0)  ? UInt32.MaxValue : 0;
            uint yExtend = (right._sign < 0) ? UInt32.MaxValue : 0;

            for (int i = 0; i < z.Length; i++) {
                uint xu = (i < x.Length) ? x[i] : xExtend;
                uint yu = (i < y.Length) ? y[i] : yExtend;
                z[i] = xu | yu; 
            }
            return new BigInteger(z);
        }

        public static BigInteger operator ^(BigInteger left, BigInteger right) {
            uint[] x = left.ToUInt32Array();
            uint[] y = right.ToUInt32Array();
            uint[] z = new uint[Math.Max(x.Length, y.Length)];
            uint xExtend = (left._sign < 0)  ? UInt32.MaxValue : 0;
            uint yExtend = (right._sign < 0) ? UInt32.MaxValue : 0;

            for (int i = 0; i < z.Length; i++) {
                uint xu = (i < x.Length) ? x[i] : xExtend;
                uint yu = (i < y.Length) ? y[i] : yExtend;
                z[i] = xu ^ yu; 
            }

            return new BigInteger(z);
        }


        public static BigInteger operator <<(BigInteger value, int shift) {

            if (shift == 0) return value;
            else if (shift == Int32.MinValue) return ((value >> Int32.MaxValue) >> 1);
            else if (shift < 0) return value >> -shift;

            int digitShift = shift / kcbitUint;
            int smallShift = shift - (digitShift * kcbitUint);

            uint[] xd; int xl; bool negx;
            negx = GetPartsForBitManipulation(ref value, out xd, out xl);
            
            int zl = xl + digitShift + 1;
            uint[] zd = new uint[zl];

            if (smallShift == 0) {
                for (int i = 0; i < xl; i++) {
                    zd[i + digitShift] = xd[i];
                }
            } else {
                int carryShift = kcbitUint - smallShift;
                uint carry = 0;
                int i;
                for (i = 0; i < xl; i++) {
                    uint rot = xd[i];
                    zd[i + digitShift] = rot << smallShift | carry;
                    carry = rot >> carryShift;
                }
                zd[i + digitShift] = carry;
            }
            return new BigInteger(zd, negx);
        }

        public static BigInteger operator >>(BigInteger value, int shift) {
            if (shift == 0) return value;
            else if (shift == Int32.MinValue) return ((value << Int32.MaxValue) << 1);
            else if (shift < 0) return value << -shift;

            int digitShift = shift / kcbitUint;
            int smallShift = shift - (digitShift * kcbitUint);

            uint[] xd; int xl; bool negx;
            negx = GetPartsForBitManipulation(ref value, out xd, out xl);

            if (negx) {
                if (shift >= (kcbitUint * xl)) {
                    return BigInteger.MinusOne;
                }
                uint[] temp = new uint[xl];
                Array.Copy(xd /* sourceArray */, temp /* destinationArray */, xl /* length */);  // make a copy of immutable value._bits
                xd = temp;
                NumericsHelpers.DangerousMakeTwosComplement(xd); // mutates xd
            }

            int zl = xl - digitShift;
            if (zl < 0) zl = 0;
            uint[] zd = new uint[zl];

            if (smallShift == 0) {
                for (int i = xl - 1; i >= digitShift; i--) {
                    zd[i - digitShift] = xd[i];
                }
            } else {
                int carryShift = kcbitUint - smallShift;
                uint carry = 0;               
                for (int i = xl - 1; i >= digitShift; i--) {
                    uint rot = xd[i];
                    if (negx && i == xl - 1)
                        // sign-extend the first shift for negative ints then let the carry propagate
                        zd[i - digitShift] = (rot >> smallShift) | (0xFFFFFFFF << carryShift);
                    else
                        zd[i - digitShift] = (rot >> smallShift) | carry;                   
                    carry = rot << carryShift;
                }
            }
            if (negx) {
                NumericsHelpers.DangerousMakeTwosComplement(zd); // mutates zd
            }
            return new BigInteger(zd, negx);
        }


        public static BigInteger operator ~(BigInteger value) {
            return -(value + BigInteger.One);
        }

        public static BigInteger operator -(BigInteger value)
        {
            value.AssertValid();
            value._sign = -value._sign;
            value.AssertValid();
            return value;
        }

        public static BigInteger operator +(BigInteger value)
        {
            value.AssertValid();
            return value;
        }


        public static BigInteger operator ++(BigInteger value)
        {
            return value + BigInteger.One;
        }

        public static BigInteger operator --(BigInteger value)
        {
            return value - BigInteger.One;
        }


        public static BigInteger operator +(BigInteger left, BigInteger right)
        {
            left.AssertValid();
            right.AssertValid();

            if (right.IsZero) return left;
            if (left.IsZero) return right;

            int sign1 = +1;
            int sign2 = +1;
            BigIntegerBuilder reg1 = new BigIntegerBuilder(left, ref sign1);
            BigIntegerBuilder reg2 = new BigIntegerBuilder(right, ref sign2);

            if (sign1 == sign2)
                reg1.Add(ref reg2);
            else
                reg1.Sub(ref sign1, ref reg2);

            return reg1.GetInteger(sign1);
        }

        public static BigInteger operator -(BigInteger left, BigInteger right)
        {
            left.AssertValid();
            right.AssertValid();

            if (right.IsZero) return left;
            if (left.IsZero) return -right;

            int sign1 = +1;
            int sign2 = -1;
            BigIntegerBuilder reg1 = new BigIntegerBuilder(left, ref sign1);
            BigIntegerBuilder reg2 = new BigIntegerBuilder(right, ref sign2);

            if (sign1 == sign2)
                reg1.Add(ref reg2);
            else
                reg1.Sub(ref sign1, ref reg2);

            return reg1.GetInteger(sign1);
        }

        public static BigInteger operator *(BigInteger left, BigInteger right)
        {
            left.AssertValid();
            right.AssertValid();

            int sign = +1;
            BigIntegerBuilder reg1 = new BigIntegerBuilder(left, ref sign);
            BigIntegerBuilder reg2 = new BigIntegerBuilder(right, ref sign);

            reg1.Mul(ref reg2);
            return reg1.GetInteger(sign);
        }

        public static BigInteger operator /(BigInteger dividend, BigInteger divisor)
        {
            dividend.AssertValid();
            divisor.AssertValid();

            int sign = +1;
            BigIntegerBuilder regNum = new BigIntegerBuilder(dividend, ref sign);
            BigIntegerBuilder regDen = new BigIntegerBuilder(divisor, ref sign);

            regNum.Div(ref regDen);
            return regNum.GetInteger(sign);
        }

        public static BigInteger operator %(BigInteger dividend, BigInteger divisor)
        {
            dividend.AssertValid();
            divisor.AssertValid();

            int signNum = +1;
            int signDen = +1;
            BigIntegerBuilder regNum = new BigIntegerBuilder(dividend, ref signNum);
            BigIntegerBuilder regDen = new BigIntegerBuilder(divisor, ref signDen);

            regNum.Mod(ref regDen);
            return regNum.GetInteger(signNum);
        }

        public static bool operator <(BigInteger left, BigInteger right)
        {
            return left.CompareTo(right) < 0;
        }
        public static bool operator <=(BigInteger left, BigInteger right)
        {
            return left.CompareTo(right) <= 0;
        }
        public static bool operator >(BigInteger left, BigInteger right)
        {
            return left.CompareTo(right) > 0;
        }
        public static bool operator >=(BigInteger left, BigInteger right)
        {
            return left.CompareTo(right) >= 0;
        }
        public static bool operator ==(BigInteger left, BigInteger right)
        {
            return left.Equals(right);
        }
        public static bool operator !=(BigInteger left, BigInteger right)
        {
            return !left.Equals(right);
        }     

        public static bool operator <(BigInteger left, Int64 right)
        {
            return left.CompareTo(right) < 0;
        }
        public static bool operator <=(BigInteger left, Int64 right)
        {
            return left.CompareTo(right) <= 0;
        }
        public static bool operator >(BigInteger left, Int64 right)
        {
            return left.CompareTo(right) > 0;
        }
        public static bool operator >=(BigInteger left, Int64 right)
        {
            return left.CompareTo(right) >= 0;
        }
        public static bool operator ==(BigInteger left, Int64 right)
        {
            return left.Equals(right);
        }
        public static bool operator !=(BigInteger left, Int64 right)
        {
            return !left.Equals(right);
        }     

        public static bool operator <(Int64 left, BigInteger right)
        {
            return right.CompareTo(left) > 0;
        }
        public static bool operator <=(Int64 left, BigInteger right)
        {
            return right.CompareTo(left) >= 0;
        }
        public static bool operator >(Int64 left, BigInteger right)
        {
            return right.CompareTo(left) < 0;
        }
        public static bool operator >=(Int64 left, BigInteger right)
        {
            return right.CompareTo(left) <= 0;
        }
        public static bool operator ==(Int64 left, BigInteger right)
        {
            return right.Equals(left);
        }
        public static bool operator !=(Int64 left, BigInteger right)
        {
            return !right.Equals(left);
        }

        [CLSCompliant(false)]
        public static bool operator <(BigInteger left, UInt64 right)
        {
            return left.CompareTo(right) < 0;
        }
        [CLSCompliant(false)]
        public static bool operator <=(BigInteger left, UInt64 right)
        {
            return left.CompareTo(right) <= 0;
        }
        [CLSCompliant(false)]
        public static bool operator >(BigInteger left, UInt64 right)
        {
            return left.CompareTo(right) > 0;
        }
        [CLSCompliant(false)]
        public static bool operator >=(BigInteger left, UInt64 right)
        {
            return left.CompareTo(right) >= 0;
        }
        [CLSCompliant(false)]
        public static bool operator ==(BigInteger left, UInt64 right)
        {
            return left.Equals(right);
        }
        [CLSCompliant(false)]
        public static bool operator !=(BigInteger left, UInt64 right)
        {
            return !left.Equals(right);
        }     

        [CLSCompliant(false)]
        public static bool operator <(UInt64 left, BigInteger right)
        {
            return right.CompareTo(left) > 0;
        }
        [CLSCompliant(false)]
        public static bool operator <=(UInt64 left, BigInteger right)
        {
            return right.CompareTo(left) >= 0;
        }
        [CLSCompliant(false)]
        public static bool operator >(UInt64 left, BigInteger right)
        {
            return right.CompareTo(left) < 0;
        }
        [CLSCompliant(false)]
        public static bool operator >=(UInt64 left, BigInteger right)
        {
            return right.CompareTo(left) <= 0;
        }
        [CLSCompliant(false)]
        public static bool operator ==(UInt64 left, BigInteger right)
        {
            return right.Equals(left);
        }
        [CLSCompliant(false)]
        public static bool operator !=(UInt64 left, BigInteger right)
        {
            return !right.Equals(left);
        }

        #endregion public static operators


        // ----- SECTION: private serialization instance methods  ----------------
        #region private serialization instance methods
        #endregion private serialization instance methods


        // ----- SECTION: internal instance utility methods ----------------*
        #region internal instance utility methods

        private void SetBitsFromDouble(Double value)
        {
            int sign, exp;
            ulong man;
            bool fFinite;
            NumericsHelpers.GetDoubleParts(value, out sign, out exp, out man, out fFinite);
            Contract.Assert(sign == +1 || sign == -1);

            if (man == 0)
            {
                this = BigInteger.Zero;
                return;
            }

            Contract.Assert(man < (1UL << 53));
            Contract.Assert(exp <= 0 || man >= (1UL << 52));

            if (exp <= 0)
            {
                if (exp <= -kcbitUlong)
                {
                    this = BigInteger.Zero;
                    return;
                }
                this = man >> -exp;
                if (sign < 0)
                    _sign = -_sign;
            }
            else if (exp <= 11)
            {
                this = man << exp;
                if (sign < 0)
                    _sign = -_sign;
            }
            else
            {
                // Overflow into at least 3 uints.
                // Move the leading 1 to the high bit.
                man <<= 11;
                exp -= 11;

                // Compute cu and cbit so that exp == 32 * cu - cbit and 0 <= cbit < 32.
                int cu = (exp - 1) / kcbitUint + 1;
                int cbit = cu * kcbitUint - exp;
                Contract.Assert(0 <= cbit && cbit < kcbitUint);
                Contract.Assert(cu >= 1);

                // Populate the uints.
                _bits = new uint[cu + 2];
                _bits[cu + 1] = (uint)(man >> (cbit + kcbitUint));
                _bits[cu] = (uint)(man >> cbit);
                if (cbit > 0)
                    _bits[cu - 1] = (uint)man << (kcbitUint - cbit);
                _sign = sign;
            }
        }
        #endregion internal instance utility methods


        // ----- SECTION: internal static utility methods ----------------*
        #region internal static utility methods
        [Pure]
        internal static int Length(uint[] rgu)
        {
            int cu = rgu.Length;
            if (rgu[cu - 1] != 0)
                return cu;
            Contract.Assert(cu >= 2 && rgu[cu - 2] != 0);
            return cu - 1;
        }

        internal int _Sign { get { return _sign; } }
        internal uint[] _Bits { get { return _bits; } }


        internal static int BitLengthOfUInt(uint x)
        {
            int numBits = 0;
            while (x > 0)
            {
                x >>= 1;
                numBits++;
            }
            return numBits;
        }

        //
        // GetPartsForBitManipulation -
        //
        // Encapsulate the logic of normalizing the "small" and "large" forms of BigInteger
        // into the "large" form so that Bit Manipulation algorithms can be simplified 
        //
        // uint[] xd    =    the UInt32 array containing the entire big integer in "large" (denormalized) form
        //                       E.g., the number one (1) and negative one (-1) are both stored as 0x00000001
        //                       BigInteger values Int32.MinValue < x <= Int32.MaxValue are converted to this
        //                       format for convenience.
        // int xl       =    the length of xd
        // return bool  =    true for negative numbers
        //
        private static bool GetPartsForBitManipulation(ref BigInteger x, out uint[] xd, out int xl) {
            if (x._bits == null) {
                if (x._sign < 0) {
                    xd = new uint[] {(uint)-x._sign};
                }
                else {
                    xd = new uint[] {(uint)x._sign};
                }
            }
            else {
                xd = x._bits;
            }
            xl = (x._bits == null ? 1 : x._bits.Length);         
            return x._sign < 0;
        }

        // Gets an upper bound on the product of uHiRes * (2^32)^(cuRes-1) and uHiMul * (2^32)^(cuMul-1).
        // The result is put int uHiRes and cuRes.
        private static void MulUpper(ref uint uHiRes, ref int cuRes, uint uHiMul, int cuMul)
        {
            ulong uu = (ulong)uHiRes * uHiMul;
            uint uHi = NumericsHelpers.GetHi(uu);
            if (uHi != 0)
            {
                if (NumericsHelpers.GetLo(uu) != 0 && ++uHi == 0)
                {
                    uHi = 1;
                    cuRes++;
                }
                uHiRes = uHi;
                cuRes += cuMul;
            }
            else
            {
                uHiRes = NumericsHelpers.GetLo(uu);
                cuRes += cuMul - 1;
            }
        }

        // Gets a lower bound on the product of uHiRes * (2^32)^(cuRes-1) and uHiMul * (2^32)^(cuMul-1).
        // The result is put int uHiRes and cuRes.
        private static void MulLower(ref uint uHiRes, ref int cuRes, uint uHiMul, int cuMul)
        {
            ulong uu = (ulong)uHiRes * uHiMul;
            uint uHi = NumericsHelpers.GetHi(uu);
            if (uHi != 0)
            {
                uHiRes = uHi;
                cuRes += cuMul;
            }
            else
            {
                uHiRes = NumericsHelpers.GetLo(uu);
                cuRes += cuMul - 1;
            }
        }

        internal static int GetDiffLength(uint[] rgu1, uint[] rgu2, int cu)
        {
            for (int iv = cu; --iv >= 0; )
            {
                if (rgu1[iv] != rgu2[iv])
                    return iv + 1;
            }
            return 0;
        }
        #endregion internal static utility methods
    } 
}