// ==++== // // 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, IEquatable { // ---- 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 } }