--- /dev/null
+// http://www.fractal-landscapes.co.uk/bigint.html\r
+\r
+using System;\r
+\r
+namespace BigNum\r
+{\r
+ /// <summary>\r
+ /// Specifies the desired precision for a BigInt or a BigFloat. \r
+ /// </summary>\r
+ public struct PrecisionSpec\r
+ {\r
+ /// <summary>\r
+ /// Precision can be specified in a choice of 8 bases.\r
+ /// Note that precision for decimals is approximate.\r
+ /// </summary>\r
+ public enum BaseType\r
+ {\r
+ /// <summary>\r
+ /// Binary base\r
+ /// </summary>\r
+ BIN,\r
+ /// <summary>\r
+ /// Octal base\r
+ /// </summary>\r
+ OCT,\r
+ /// <summary>\r
+ /// Decimal base\r
+ /// </summary>\r
+ DEC,\r
+ /// <summary>\r
+ /// Hexadecimal base\r
+ /// </summary>\r
+ HEX,\r
+ /// <summary>\r
+ /// 8-bits per digit\r
+ /// </summary>\r
+ BYTES,\r
+ /// <summary>\r
+ /// 16-bits per digit\r
+ /// </summary>\r
+ WORDS,\r
+ /// <summary>\r
+ /// 32-bits per digit\r
+ /// </summary>\r
+ DWORDS,\r
+ /// <summary>\r
+ /// 64-bits per digit\r
+ /// </summary>\r
+ QWORDS\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructor: Constructs a precision specification\r
+ /// </summary>\r
+ /// <param name="precision">The number of digits</param>\r
+ /// <param name="numberBase">The base of the digits</param>\r
+ public PrecisionSpec(int precision, BaseType numberBase)\r
+ {\r
+ this.prec = precision;\r
+ this.nB = numberBase;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Explicit cast from integer value.\r
+ /// </summary>\r
+ /// <param name="value">The value in bits for the new precision specification</param>\r
+ /// <returns>A new precision specification with the number of bits specified</returns>\r
+ public static explicit operator PrecisionSpec(int value)\r
+ {\r
+ return new PrecisionSpec(value, BaseType.BIN);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Equality test\r
+ /// </summary>\r
+ /// <param name="spec1">the first parameter</param>\r
+ /// <param name="spec2">the second parameter</param>\r
+ /// <returns>true iff both precisions have the same number of bits</returns>\r
+ public static bool operator ==(PrecisionSpec spec1, PrecisionSpec spec2)\r
+ {\r
+ return (spec1.NumBits == spec2.NumBits);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Inequality operator\r
+ /// </summary>\r
+ /// <param name="spec1">the first parameter</param>\r
+ /// <param name="spec2">the second parameter</param>\r
+ /// <returns>true iff the parameters do not have the same number of bits</returns>\r
+ public static bool operator !=(PrecisionSpec spec1, PrecisionSpec spec2)\r
+ {\r
+ return !(spec1 == spec2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Object equality override\r
+ /// </summary>\r
+ /// <param name="obj">the PrecisionSpec struct to compare</param>\r
+ /// <returns>true iff obj has the same number of bits as this</returns>\r
+ public override bool Equals(object obj)\r
+ {\r
+ return NumBits == ((PrecisionSpec)obj).NumBits; \r
+ }\r
+\r
+ /// <summary>\r
+ /// Override of the hash code\r
+ /// </summary>\r
+ /// <returns>A basic hash</returns>\r
+ public override int GetHashCode()\r
+ {\r
+ return NumBits * prec + NumBits;\r
+ }\r
+\r
+ /// <summary>\r
+ /// The precision in units specified by the base type (e.g. number of decimal digits)\r
+ /// </summary>\r
+ public int Precision\r
+ {\r
+ get { return prec; }\r
+ }\r
+\r
+ /// <summary>\r
+ /// The base type in which precision is specified\r
+ /// </summary>\r
+ public BaseType NumberBaseType\r
+ {\r
+ get { return nB; }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Converts the number-base to an integer\r
+ /// </summary>\r
+ public int NumberBase\r
+ {\r
+ get { return (int)nB; }\r
+ }\r
+\r
+ /// <summary>\r
+ /// The number of bits that this PrecisionSpec structure specifies.\r
+ /// </summary>\r
+ public int NumBits\r
+ {\r
+ get\r
+ {\r
+ if (nB == BaseType.BIN) return prec;\r
+ if (nB == BaseType.OCT) return prec * 3;\r
+ if (nB == BaseType.HEX) return prec * 4;\r
+ if (nB == BaseType.BYTES) return prec * 8;\r
+ if (nB == BaseType.WORDS) return prec * 16;\r
+ if (nB == BaseType.DWORDS) return prec * 32;\r
+ if (nB == BaseType.QWORDS) return prec * 64;\r
+\r
+ double factor = 3.322;\r
+ int bits = ((int)Math.Ceiling(factor * (double)prec));\r
+ return bits;\r
+ }\r
+ }\r
+\r
+ private int prec;\r
+ private BaseType nB;\r
+ }\r
+\r
+ \r
+ /// <summary>\r
+ /// An arbitrary-precision integer class\r
+ /// \r
+ /// Format:\r
+ /// Each number consists of an array of 32-bit unsigned integers, and a bool sign\r
+ /// value.\r
+ /// \r
+ /// Applicability and Performance:\r
+ /// This class is designed to be used for small extended precisions. It may not be\r
+ /// safe (and certainly won't be fast) to use it with mixed-precision arguments.\r
+ /// It does support, but will not be efficient for, numbers over around 2048 bits.\r
+ /// \r
+ /// Notes:\r
+ /// All conversions to and from strings are slow.\r
+ /// \r
+ /// Conversions from simple integer types Int32, Int64, UInt32, UInt64 are performed\r
+ /// using the appropriate constructor, and are relatively fast.\r
+ /// \r
+ /// The class is written entirely in managed C# code, with not native or managed\r
+ /// assembler. The use of native assembler would speed up the multiplication operations\r
+ /// many times over, and therefore all higher-order operations too.\r
+ /// </summary>\r
+ public class BigInt\r
+ {\r
+ //*************** Constructors ******************\r
+\r
+ /// <summary>\r
+ /// Constructs an empty BigInt to the desired precision.\r
+ /// </summary>\r
+ /// <param name="precision"></param>\r
+ public BigInt(PrecisionSpec precision)\r
+ {\r
+ Init(precision);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a BigInt from a string, using the string length to determine the precision\r
+ /// Note, operations on BigInts of non-matching precision are slow, so avoid using this constructor\r
+ /// </summary>\r
+ /// <param name="init"></param>\r
+ public BigInt(string init)\r
+ {\r
+ InitFromString(init, (PrecisionSpec)init.Length, 10);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructor for copying length and precision\r
+ /// </summary>\r
+ /// <param name="inputToCopy">The BigInt to copy</param>\r
+ /// <param name="precision">The precision of the new BigInt</param>\r
+ /// <param name="bCopyLengthOnly">decides whether to copy the actual input, or just its digit length</param>\r
+ /// <example><code>//Create an integer\r
+ /// BigInt four = new BigInt(4, new PrecisionSpec(128, PrecisionSpec.BaseType.BIN));\r
+ /// \r
+ /// //Pad four to double its usual number of digits (this does not affect the precision)\r
+ /// four.Pad();\r
+ /// \r
+ /// //Create a new, empty integer with matching precision, also padded to twice the usual length\r
+ /// BigInt newCopy = new BigInt(four, four.Precision, true);</code></example>\r
+ public BigInt(BigInt inputToCopy, PrecisionSpec precision, bool bCopyLengthOnly)\r
+ {\r
+ digitArray = new uint[inputToCopy.digitArray.Length];\r
+ workingSet = new uint[inputToCopy.digitArray.Length];\r
+ if (!bCopyLengthOnly) Array.Copy(inputToCopy.digitArray, digitArray, digitArray.Length);\r
+ sign = inputToCopy.sign;\r
+ pres = inputToCopy.pres;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a bigint from the string, with the desired precision, using base 10\r
+ /// </summary>\r
+ /// <param name="init"></param>\r
+ /// <param name="precision"></param>\r
+ public BigInt(string init, PrecisionSpec precision)\r
+ {\r
+ InitFromString(init, precision, 10);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a BigInt from a string, using the specified precision and base\r
+ /// </summary>\r
+ /// <param name="init"></param>\r
+ /// <param name="precision"></param>\r
+ /// <param name="numberBase"></param>\r
+ public BigInt(string init, PrecisionSpec precision, int numberBase)\r
+ {\r
+ InitFromString(init, precision, numberBase);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a bigint from the input.\r
+ /// </summary>\r
+ /// <param name="input"></param>\r
+ public BigInt(BigInt input)\r
+ {\r
+ digitArray = new uint[input.digitArray.Length];\r
+ workingSet = new uint[input.digitArray.Length];\r
+ Array.Copy(input.digitArray, digitArray, digitArray.Length);\r
+ sign = input.sign;\r
+ pres = input.pres;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a bigint from the input, matching the new precision provided\r
+ /// </summary>\r
+ public BigInt(BigInt input, PrecisionSpec precision)\r
+ {\r
+ //Casts the input to the new precision.\r
+ Init(precision);\r
+ int Min = (input.digitArray.Length < digitArray.Length) ? input.digitArray.Length : digitArray.Length;\r
+\r
+ for (int i = 0; i < Min; i++)\r
+ {\r
+ digitArray[i] = input.digitArray[i];\r
+ }\r
+\r
+ sign = input.sign;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a BigInt from a UInt32\r
+ /// </summary>\r
+ /// <param name="input"></param>\r
+ /// <param name="precision"></param>\r
+ public BigInt(UInt32 input, PrecisionSpec precision)\r
+ {\r
+ Init(precision);\r
+ digitArray[0] = input;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a BigInt from a UInt64\r
+ /// </summary>\r
+ /// <param name="input"></param>\r
+ /// <param name="precision"></param>\r
+ public BigInt(UInt64 input, PrecisionSpec precision)\r
+ {\r
+ Init(precision);\r
+ digitArray[0] = (UInt32)(input & 0xffffffff);\r
+ if (digitArray.Length > 1) digitArray[1] = (UInt32)(input >> 32);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a BigInt from an Int32\r
+ /// </summary>\r
+ /// <param name="input"></param>\r
+ /// <param name="precision"></param>\r
+ public BigInt(Int32 input, PrecisionSpec precision)\r
+ {\r
+ Init(precision);\r
+ if (input < 0)\r
+ {\r
+ sign = true;\r
+\r
+ if (input == Int32.MinValue)\r
+ {\r
+ digitArray[0] = 0x80000000;\r
+ }\r
+ else\r
+ {\r
+ digitArray[0] = (UInt32)(-input);\r
+ }\r
+ }\r
+ else\r
+ {\r
+ digitArray[0] = ((UInt32)input);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a BigInt from a UInt32\r
+ /// </summary>\r
+ /// <param name="input"></param>\r
+ /// <param name="precision"></param>\r
+ public BigInt(Int64 input, PrecisionSpec precision)\r
+ {\r
+ Init(precision);\r
+ if (input < 0) sign = true;\r
+\r
+ digitArray[0] = (UInt32)(input & 0xffffffff);\r
+\r
+ if (digitArray.Length >= 2)\r
+ {\r
+ if (input == Int64.MinValue)\r
+ {\r
+ digitArray[1] = 0x80000000;\r
+ }\r
+ else\r
+ {\r
+ digitArray[1] = (UInt32)((input >> 32) & 0x7fffffff);\r
+ }\r
+ }\r
+ }\r
+\r
+ //***************** Properties *******************\r
+\r
+ /// <summary>\r
+ /// true iff the number is negative\r
+ /// </summary>\r
+ public bool Sign { get { return sign; } set { sign = value; } }\r
+\r
+ /// <summary>\r
+ /// The precision of the number.\r
+ /// </summary>\r
+ public PrecisionSpec Precision { get { return pres; } }\r
+\r
+ //*************** Utility Functions **************\r
+\r
+ /// <summary>\r
+ /// Casts a BigInt to the new precision provided.\r
+ /// Note: This will return the input if the precision already matches.\r
+ /// </summary>\r
+ /// <param name="input"></param>\r
+ /// <param name="precision"></param>\r
+ /// <returns></returns>\r
+ public static BigInt CastToPrecision(BigInt input, PrecisionSpec precision)\r
+ {\r
+ if (input.pres == precision) return input;\r
+ return new BigInt(input, precision);\r
+ }\r
+\r
+\r
+ //*************** Member Functions ***************\r
+\r
+ /// <summary>\r
+ /// Addition and assignment - without intermediate memory allocation.\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public uint Add(BigInt n2)\r
+ {\r
+ if (n2.digitArray.Length != digitArray.Length) MakeSafe(ref n2);\r
+\r
+ if (sign == n2.sign)\r
+ {\r
+ return AddInternalBits(n2.digitArray);\r
+ }\r
+ else\r
+ {\r
+ bool lessThan = LtInt(this, n2);\r
+\r
+ if (lessThan)\r
+ {\r
+ int Length = digitArray.Length;\r
+\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ workingSet[i] = digitArray[i];\r
+ digitArray[i] = n2.digitArray[i];\r
+ }\r
+\r
+ sign = !sign;\r
+ return SubInternalBits(workingSet);\r
+ }\r
+ else\r
+ {\r
+ return SubInternalBits(n2.digitArray);\r
+ }\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Subtraction and assignment - without intermediate memory allocation.\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ public uint Sub(BigInt n2)\r
+ {\r
+ if (n2.digitArray.Length != digitArray.Length) MakeSafe(ref n2);\r
+\r
+ if (sign != n2.sign)\r
+ {\r
+ return AddInternalBits(n2.digitArray);\r
+ }\r
+ else\r
+ {\r
+ bool lessThan = LtInt(this, n2);\r
+\r
+ if (lessThan)\r
+ {\r
+ int Length = digitArray.Length;\r
+\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ workingSet[i] = digitArray[i];\r
+ digitArray[i] = n2.digitArray[i];\r
+ }\r
+\r
+ sign = !sign;\r
+ return SubInternalBits(workingSet);\r
+ }\r
+ else\r
+ {\r
+ return SubInternalBits(n2.digitArray);\r
+ }\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Multiplication and assignmnet - with minimal intermediate memory allocation.\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ public void Mul(BigInt n2)\r
+ {\r
+ if (n2.digitArray.Length != digitArray.Length) MakeSafe(ref n2);\r
+\r
+ int Length = n2.digitArray.Length;\r
+\r
+ //Inner loop zero-mul avoidance\r
+ int maxDigit = 0;\r
+ for (int i = Length - 1; i >= 0; i--)\r
+ {\r
+ if (digitArray[i] != 0)\r
+ {\r
+ maxDigit = i + 1;\r
+ break;\r
+ }\r
+ }\r
+\r
+ //Result is zero, 'this' is unchanged\r
+ if (maxDigit == 0) return;\r
+\r
+ //Temp storage for source (both working sets are used by the calculation)\r
+ uint[] thisTemp = new uint [Length];\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ thisTemp[i] = digitArray[i];\r
+ digitArray[i] = 0;\r
+ }\r
+\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ //Clear the working set\r
+ for (int j = 0; j < i; j++)\r
+ {\r
+ workingSet[j] = 0;\r
+ n2.workingSet[j] = 0;\r
+ }\r
+\r
+ n2.workingSet[i] = 0;\r
+\r
+ ulong digit = n2.digitArray[i];\r
+ if (digit == 0) continue;\r
+\r
+ for (int j = 0; j + i < Length && j < maxDigit; j++)\r
+ {\r
+ //Multiply n1 by each of the integer digits of n2.\r
+ ulong temp = (ulong)thisTemp[j] * digit;\r
+ //n1.workingSet stores the low bits of each piecewise multiplication\r
+ workingSet[j + i] = (uint)(temp & 0xffffffff);\r
+ if (j + i + 1 < Length)\r
+ {\r
+ //n2.workingSet stores the high bits of each multiplication\r
+ n2.workingSet[j + i + 1] = (uint)(temp >> 32);\r
+ }\r
+ }\r
+\r
+ AddInternalBits(workingSet);\r
+ AddInternalBits(n2.workingSet);\r
+ }\r
+\r
+ sign = (sign != n2.sign);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Squares the number.\r
+ /// </summary>\r
+ public void Square()\r
+ {\r
+ int Length = digitArray.Length;\r
+\r
+ //Inner loop zero-mul avoidance\r
+ int maxDigit = 0;\r
+ for (int i = Length - 1; i >= 0; i--)\r
+ {\r
+ if (digitArray[i] != 0)\r
+ {\r
+ maxDigit = i + 1;\r
+ break;\r
+ }\r
+ }\r
+\r
+ //Result is zero, 'this' is unchanged\r
+ if (maxDigit == 0) return;\r
+\r
+ //Temp storage for source (both working sets are used by the calculation)\r
+ uint[] thisTemp = new uint[Length];\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ thisTemp[i] = digitArray[i];\r
+ digitArray[i] = 0;\r
+ }\r
+\r
+ UInt32 [] workingSet2 = new UInt32[Length];\r
+\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ //Clear the working set\r
+ for (int j = 0; j < i; j++)\r
+ {\r
+ workingSet[j] = 0;\r
+ workingSet2[j] = 0;\r
+ }\r
+\r
+ workingSet2[i] = 0;\r
+\r
+ ulong digit = thisTemp[i];\r
+ if (digit == 0) continue;\r
+\r
+ for (int j = 0; j + i < Length && j < maxDigit; j++)\r
+ {\r
+ //Multiply n1 by each of the integer digits of n2.\r
+ ulong temp = (ulong)thisTemp[j] * digit;\r
+ //n1.workingSet stores the low bits of each piecewise multiplication\r
+ workingSet[j + i] = (uint)(temp & 0xffffffff);\r
+ if (j + i + 1 < Length)\r
+ {\r
+ //n2.workingSet stores the high bits of each multiplication\r
+ workingSet2[j + i + 1] = (uint)(temp >> 32);\r
+ }\r
+ }\r
+\r
+ AddInternalBits(workingSet);\r
+ AddInternalBits(workingSet2);\r
+ }\r
+\r
+ sign = false;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Used for floating-point multiplication\r
+ /// Stores the high bits of the multiplication only (the carry bit from the\r
+ /// lower bits is missing, so the true answer might be 1 greater).\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ public void MulHi(BigInt n2)\r
+ {\r
+ if (n2.digitArray.Length != digitArray.Length) MakeSafe(ref n2);\r
+\r
+ int Length = n2.digitArray.Length;\r
+\r
+ //Inner loop zero-mul avoidance\r
+ int maxDigit = 0;\r
+ for (int i = Length - 1; i >= 0; i--)\r
+ {\r
+ if (digitArray[i] != 0)\r
+ {\r
+ maxDigit = i + 1;\r
+ break;\r
+ }\r
+ }\r
+\r
+ //Result is zero, 'this' is unchanged\r
+ if (maxDigit == 0) return;\r
+\r
+ //Temp storage for source (both working sets are used by the calculation)\r
+ uint[] thisTemp = new uint[Length];\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ thisTemp[i] = digitArray[i];\r
+ digitArray[i] = 0;\r
+ }\r
+\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ //Clear the working set\r
+ for (int j = 0; j < Length; j++)\r
+ {\r
+ workingSet[j] = 0;\r
+ n2.workingSet[j] = 0;\r
+ }\r
+\r
+ n2.workingSet[i] = 0;\r
+\r
+ ulong digit = n2.digitArray[i];\r
+ if (digit == 0) continue;\r
+\r
+ //Only the high bits\r
+ if (maxDigit + i < Length - 1) continue;\r
+\r
+ for (int j = 0; j < maxDigit; j++)\r
+ {\r
+ if (j + i + 1 < Length) continue;\r
+ //Multiply n1 by each of the integer digits of n2.\r
+ ulong temp = (ulong)thisTemp[j] * digit;\r
+ //n1.workingSet stores the low bits of each piecewise multiplication\r
+ if (j + i >= Length)\r
+ {\r
+ workingSet[j + i - Length] = (uint)(temp & 0xffffffff);\r
+ }\r
+ \r
+ //n2.workingSet stores the high bits of each multiplication\r
+ n2.workingSet[j + i + 1 - Length] = (uint)(temp >> 32);\r
+ }\r
+\r
+ AddInternalBits(workingSet);\r
+ AddInternalBits(n2.workingSet);\r
+ }\r
+\r
+ sign = (sign != n2.sign);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Floating-point helper function.\r
+ /// Squares the number and keeps the high bits of the calculation.\r
+ /// Takes a temporary BigInt as a working set.\r
+ /// </summary>\r
+ public void SquareHiFast(BigInt scratch)\r
+ {\r
+ int Length = digitArray.Length;\r
+ uint[] tempDigits = scratch.digitArray;\r
+ uint[] workingSet2 = scratch.workingSet;\r
+\r
+ //Temp storage for source (both working sets are used by the calculation)\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ tempDigits[i] = digitArray[i];\r
+ digitArray[i] = 0;\r
+ }\r
+\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ //Clear the working set\r
+ for (int j = i; j < Length; j++)\r
+ {\r
+ workingSet[j] = 0;\r
+ workingSet2[j] = 0;\r
+ }\r
+\r
+ if (i - 1 >= 0) workingSet[i - 1] = 0;\r
+\r
+ ulong digit = tempDigits[i];\r
+ if (digit == 0) continue;\r
+\r
+ for (int j = 0; j < Length; j++)\r
+ {\r
+ if (j + i + 1 < Length) continue;\r
+ //Multiply n1 by each of the integer digits of n2.\r
+ ulong temp = (ulong)tempDigits[j] * digit;\r
+ //n1.workingSet stores the low bits of each piecewise multiplication\r
+ if (j + i >= Length)\r
+ {\r
+ workingSet[j + i - Length] = (uint)(temp & 0xffffffff);\r
+ }\r
+\r
+ //n2.workingSet stores the high bits of each multiplication\r
+ workingSet2[j + i + 1 - Length] = (uint)(temp >> 32);\r
+ }\r
+\r
+ AddInternalBits(workingSet);\r
+ AddInternalBits(workingSet2);\r
+ }\r
+\r
+ sign = false;\r
+ }\r
+\r
+ /// <summary>\r
+ /// This uses the schoolbook division algorithm, as decribed by http://www.treskal.com/kalle/exjobb/original-report.pdf\r
+ /// Algorithms 3.1 (implemented by Div_31) and 3.2 (implemented by Div_32)\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ public void Div(BigInt n2)\r
+ {\r
+ if (n2.digitArray.Length != digitArray.Length) MakeSafe(ref n2);\r
+\r
+ int OldLength = digitArray.Length;\r
+\r
+ //First, we need to prepare the operands for division using Div_32, which requires\r
+ //That the most significant digit of n2 be set. To do this, we need to shift n2 (and therefore n1) up.\r
+ //This operation can potentially increase the precision of the operands.\r
+ int shift = MakeSafeDiv(this, n2);\r
+\r
+ BigInt Q = new BigInt(this, this.pres, true);\r
+ BigInt R = new BigInt(this, this.pres, true);\r
+\r
+ Div_32(this, n2, Q, R);\r
+\r
+ //Restore n2 to its pre-shift value\r
+ n2.RSH(shift);\r
+ AssignInt(Q);\r
+ sign = (sign != n2.sign);\r
+\r
+ //Reset the lengths of the operands\r
+ SetNumDigits(OldLength);\r
+ n2.SetNumDigits(OldLength);\r
+ }\r
+\r
+ /// <summary>\r
+ /// This function is used for floating-point division.\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ //Given two numbers:\r
+ // In floating point 1 <= a, b < 2, meaning that both numbers have their top bits set.\r
+ // To calculate a / b, maintaining precision, we:\r
+ // 1. Double the number of digits available to both numbers.\r
+ // 2. set a = a * 2^d (where d is the number of digits)\r
+ // 3. calculate the quotient a <- q: 2^(d-1) <= q < 2^(d+1)\r
+ // 4. if a >= 2^d, s = 1, else s = 0\r
+ // 6. shift a down by s, and undo the precision extension\r
+ // 7. return 1 - shift (change necessary to exponent)\r
+ public int DivAndShift(BigInt n2)\r
+ {\r
+ if (n2.IsZero()) return -1;\r
+ if (digitArray.Length != n2.digitArray.Length) MakeSafe(ref n2);\r
+\r
+ int oldLength = digitArray.Length;\r
+\r
+ //Double the number of digits, and shift a into the higher digits.\r
+ Pad();\r
+ n2.Extend();\r
+\r
+ //Do the divide (at double precision, ouch!)\r
+ Div(n2);\r
+\r
+ //Shift down if 'this' >= 2^d\r
+ int ret = 1;\r
+\r
+ if (digitArray[oldLength] != 0)\r
+ {\r
+ RSH(1);\r
+ ret--;\r
+ }\r
+\r
+ SetNumDigits(oldLength);\r
+ n2.SetNumDigits(oldLength);\r
+\r
+ return ret;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Calculates 'this' mod n2 (using the schoolbook division algorithm as above)\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ public void Mod(BigInt n2)\r
+ {\r
+ if (n2.digitArray.Length != digitArray.Length) MakeSafe(ref n2);\r
+\r
+ int OldLength = digitArray.Length;\r
+\r
+ //First, we need to prepare the operands for division using Div_32, which requires\r
+ //That the most significant digit of n2 be set. To do this, we need to shift n2 (and therefore n1) up.\r
+ //This operation can potentially increase the precision of the operands.\r
+ int shift = MakeSafeDiv(this, n2);\r
+\r
+ BigInt Q = new BigInt(this.pres);\r
+ BigInt R = new BigInt(this.pres);\r
+\r
+ Q.digitArray = new UInt32[this.digitArray.Length];\r
+ R.digitArray = new UInt32[this.digitArray.Length];\r
+\r
+ Div_32(this, n2, Q, R);\r
+\r
+ //Restore n2 to its pre-shift value\r
+ n2.RSH(shift);\r
+ R.RSH(shift);\r
+ R.sign = (sign != n2.sign);\r
+ AssignInt(R);\r
+\r
+ //Reset the lengths of the operands\r
+ SetNumDigits(OldLength);\r
+ n2.SetNumDigits(OldLength);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Logical left shift\r
+ /// </summary>\r
+ /// <param name="shift"></param>\r
+ public void LSH(int shift)\r
+ {\r
+ if (shift <= 0) return;\r
+ int length = digitArray.Length;\r
+ int digits = shift >> 5;\r
+ int rem = shift & 31;\r
+\r
+ for (int i = length - 1; i >= digits; i--)\r
+ {\r
+ digitArray[i] = digitArray[i - digits];\r
+ }\r
+\r
+ if (digits > 0)\r
+ {\r
+ for (int i = digits - 1; i >= 0; i--)\r
+ {\r
+ digitArray[i] = 0;\r
+ }\r
+ }\r
+\r
+ UInt64 lastShift = 0;\r
+\r
+ for (int i = 0; i < length; i++)\r
+ {\r
+ UInt64 temp = (((UInt64)digitArray[i]) << rem) | lastShift;\r
+ digitArray[i] = (UInt32)(temp & 0xffffffff);\r
+ lastShift = temp >> 32;\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Logical right-shift\r
+ /// </summary>\r
+ /// <param name="shift"></param>\r
+ public void RSH(int shift)\r
+ {\r
+ if (shift < 0) return;\r
+ int length = digitArray.Length;\r
+ int digits = shift >> 5;\r
+ int rem = shift & 31;\r
+\r
+ for (int i = 0; i < length - digits; i++)\r
+ {\r
+ digitArray[i] = digitArray[i + digits];\r
+ }\r
+\r
+ int start = (length - digits);\r
+ if (start < 0) start = 0;\r
+\r
+ for (int i = start; i < length; i++)\r
+ {\r
+ digitArray[i] = 0;\r
+ }\r
+\r
+ UInt64 lastShift = 0;\r
+\r
+ for (int i = length - 1; i >= 0; i--)\r
+ {\r
+ UInt64 temp = ((((UInt64)digitArray[i]) << 32) >> rem) | lastShift;\r
+ digitArray[i] = (UInt32)(temp >> 32);\r
+ lastShift = (temp & 0xffffffff) << 32;\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Changes the sign of the number\r
+ /// </summary>\r
+ public void Negate()\r
+ {\r
+ sign = !sign;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Increments the number.\r
+ /// </summary>\r
+ public void Increment()\r
+ {\r
+ if (sign)\r
+ {\r
+ DecrementInt();\r
+ }\r
+ else\r
+ {\r
+ IncrementInt();\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Decrements the number.\r
+ /// </summary>\r
+ public void Decrement()\r
+ {\r
+ if (sign)\r
+ {\r
+ IncrementInt();\r
+ }\r
+ else\r
+ {\r
+ DecrementInt();\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Calculates the factorial 'this'!\r
+ /// </summary>\r
+ public void Factorial()\r
+ {\r
+ if (sign) return;\r
+\r
+ //Clamp to a reasonable range.\r
+ int factToUse = (int)(digitArray[0]);\r
+ if (factToUse > 65536) factToUse = 65536;\r
+\r
+ Zero();\r
+ digitArray[0] = 1;\r
+\r
+ for (uint i = 1; i <= factToUse; i++)\r
+ {\r
+ MulInternal(i);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Calculates 'this'^power\r
+ /// </summary>\r
+ /// <param name="power"></param>\r
+ public void Power(BigInt power)\r
+ {\r
+ if (power.IsZero() || power.sign)\r
+ {\r
+ Zero();\r
+ digitArray[0] = 1;\r
+ return;\r
+ }\r
+\r
+ BigInt pow = new BigInt(power);\r
+ BigInt temp = new BigInt(this);\r
+ BigInt powTerm = new BigInt(this);\r
+\r
+ pow.Decrement();\r
+ for (; !pow.IsZero(); pow.RSH(1))\r
+ {\r
+ if ((pow.digitArray[0] & 1) == 1)\r
+ {\r
+ temp.Mul(powTerm);\r
+ }\r
+\r
+ powTerm.Square();\r
+ }\r
+\r
+ Assign(temp);\r
+ }\r
+\r
+ //***************** Comparison member functions *****************\r
+\r
+ /// <summary>\r
+ /// returns true if this bigint == 0\r
+ /// </summary>\r
+ /// <returns></returns>\r
+ public bool IsZero()\r
+ {\r
+ for (int i = 0; i < digitArray.Length; i++)\r
+ {\r
+ if (digitArray[i] != 0) return false;\r
+ }\r
+\r
+ return true;\r
+ }\r
+\r
+ /// <summary>\r
+ /// true iff n2 (precision adjusted to this) is less than 'this'\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public bool LessThan(BigInt n2)\r
+ {\r
+ if (digitArray.Length != n2.digitArray.Length) MakeSafe(ref n2);\r
+\r
+ if (sign)\r
+ {\r
+ if (!n2.sign) return true;\r
+ return GtInt(this, n2);\r
+ }\r
+ else\r
+ {\r
+ if (n2.sign) return false;\r
+ return LtInt(this, n2);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// true iff n2 (precision adjusted to this) is greater than 'this'\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public bool GreaterThan(BigInt n2)\r
+ {\r
+ if (digitArray.Length != n2.digitArray.Length) MakeSafe(ref n2);\r
+\r
+ if (sign)\r
+ {\r
+ if (!n2.sign) return false;\r
+ return LtInt(this, n2);\r
+ }\r
+ else\r
+ {\r
+ if (n2.sign) return true;\r
+ return GtInt(this, n2);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Override of base-class equals\r
+ /// </summary>\r
+ /// <param name="obj"></param>\r
+ /// <returns></returns>\r
+ public override bool Equals(object obj)\r
+ {\r
+ BigInt n2 = ((BigInt)obj);\r
+ return Equals(n2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Get hash code\r
+ /// </summary>\r
+ /// <returns></returns>\r
+ public override int GetHashCode()\r
+ {\r
+ return (Int32)digitArray[0];\r
+ }\r
+\r
+ /// <summary>\r
+ /// True iff n2 (precision-adjusted to this) == n1\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public bool Equals(BigInt n2)\r
+ {\r
+ if (IsZero() && n2.IsZero()) return true;\r
+\r
+ if (sign != n2.sign) return false;\r
+\r
+ int Length = digitArray.Length;\r
+ if (n2.digitArray.Length != Length) MakeSafe(ref n2);\r
+\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ if (digitArray[i] != n2.digitArray[i]) return false;\r
+ }\r
+\r
+ return true;\r
+ }\r
+\r
+ //******************* Bitwise member functions ********************\r
+\r
+ /// <summary>\r
+ /// Takes the bitwise complement of the number\r
+ /// </summary>\r
+ public void Complement()\r
+ {\r
+ int Length = digitArray.Length;\r
+\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ digitArray[i] = ~digitArray[i];\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Bitwise And\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ public void And(BigInt n2)\r
+ {\r
+ int Length = digitArray.Length;\r
+ if (n2.digitArray.Length != Length) MakeSafe(ref n2);\r
+\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ digitArray[i] &= n2.digitArray[i];\r
+ }\r
+\r
+ sign &= n2.sign;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Bitwise Or\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ public void Or(BigInt n2)\r
+ {\r
+ int Length = digitArray.Length;\r
+ if (n2.digitArray.Length != Length) MakeSafe(ref n2);\r
+\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ digitArray[i] |= n2.digitArray[i];\r
+ }\r
+\r
+ sign |= n2.sign;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Bitwise Xor\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ public void Xor(BigInt n2)\r
+ {\r
+ int Length = digitArray.Length;\r
+ if (n2.digitArray.Length != Length) MakeSafe(ref n2);\r
+\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ digitArray[i] ^= n2.digitArray[i];\r
+ }\r
+\r
+ sign ^= n2.sign;\r
+ }\r
+\r
+ //*************** Fast Static Arithmetic Functions *****************\r
+\r
+ /// <summary>\r
+ /// Adds n1 and n2 and puts result in dest, without intermediate memory allocation\r
+ /// (unsafe if n1 and n2 disagree in precision, safe even if dest is n1 or n2)\r
+ /// </summary>\r
+ /// <param name="dest"></param>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ public static void AddFast(BigInt dest, BigInt n1, BigInt n2)\r
+ {\r
+ //We cast to the highest input precision...\r
+ if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
+\r
+ //Then we up the output precision if less than the input precision.\r
+ if (dest.digitArray.Length < n1.digitArray.Length) n1.MakeSafe(ref dest);\r
+\r
+ int Length = n1.digitArray.Length;\r
+\r
+ if (n1.sign == n2.sign)\r
+ {\r
+ //Copies sources into digit array and working set for all cases, to avoid\r
+ //problems when dest is n1 or n2\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ dest.workingSet[i] = n2.digitArray[i];\r
+ dest.digitArray[i] = n1.digitArray[i];\r
+ }\r
+ dest.AddInternalBits(dest.workingSet);\r
+ dest.sign = n1.sign;\r
+ }\r
+ else\r
+ {\r
+ bool lessThan = LtInt(n1, n2);\r
+\r
+ if (lessThan)\r
+ {\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ dest.workingSet[i] = n1.digitArray[i];\r
+ dest.digitArray[i] = n2.digitArray[i];\r
+ }\r
+ dest.SubInternalBits(dest.workingSet);\r
+ dest.sign = !n1.sign;\r
+ }\r
+ else\r
+ {\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ dest.workingSet[i] = n2.digitArray[i];\r
+ dest.digitArray[i] = n1.digitArray[i];\r
+ }\r
+ dest.SubInternalBits(dest.workingSet);\r
+ dest.sign = n1.sign;\r
+ }\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Adds n1 and n2 and puts result in dest, without intermediate memory allocation\r
+ /// (unsafe if n1 and n2 disagree in precision, safe even if dest is n1 or n2)\r
+ /// </summary>\r
+ /// <param name="dest"></param>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ public static void SubFast(BigInt dest, BigInt n1, BigInt n2)\r
+ {\r
+ //We cast to the highest input precision...\r
+ if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
+\r
+ //Then we up the output precision if less than the input precision.\r
+ if (dest.digitArray.Length < n1.digitArray.Length) n1.MakeSafe(ref dest);\r
+\r
+ int Length = n1.digitArray.Length;\r
+\r
+ if (n1.sign != n2.sign)\r
+ {\r
+ //Copies sources into digit array and working set for all cases, to avoid\r
+ //problems when dest is n1 or n2\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ dest.workingSet[i] = n2.digitArray[i];\r
+ dest.digitArray[i] = n1.digitArray[i];\r
+ }\r
+ dest.AddInternalBits(dest.workingSet);\r
+ dest.sign = n1.sign;\r
+ }\r
+ else\r
+ {\r
+ bool lessThan = LtInt(n1, n2);\r
+\r
+ if (lessThan)\r
+ {\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ dest.workingSet[i] = n1.digitArray[i];\r
+ dest.digitArray[i] = n2.digitArray[i];\r
+ }\r
+ dest.SubInternalBits(dest.workingSet);\r
+ dest.sign = !n1.sign;\r
+ }\r
+ else\r
+ {\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ dest.workingSet[i] = n2.digitArray[i];\r
+ dest.digitArray[i] = n1.digitArray[i];\r
+ }\r
+ dest.SubInternalBits(dest.workingSet);\r
+ dest.sign = n1.sign;\r
+ }\r
+ }\r
+ }\r
+\r
+ //*************** Static Arithmetic Functions ***************\r
+\r
+ /// <summary>\r
+ /// signed addition of 2 numbers.\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public static BigInt Add(BigInt n1, BigInt n2)\r
+ {\r
+ if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
+ BigInt result; \r
+\r
+ if (n1.sign == n2.sign)\r
+ {\r
+ result = new BigInt(n1);\r
+ result.AddInternal(n2);\r
+ result.sign = n1.sign;\r
+ }\r
+ else\r
+ {\r
+ bool lessThan = LtInt(n1, n2);\r
+\r
+ if (lessThan)\r
+ {\r
+ result = new BigInt(n2);\r
+ result.SubInternal(n1);\r
+ result.sign = !n1.sign;\r
+ }\r
+ else\r
+ {\r
+ result = new BigInt(n1);\r
+ result.SubInternal(n2);\r
+ result.sign = n1.sign;\r
+ }\r
+ }\r
+\r
+ return result;\r
+ }\r
+\r
+ /// <summary>\r
+ /// signed subtraction of 2 numbers.\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public static BigInt Sub(BigInt n1, BigInt n2)\r
+ {\r
+ if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
+ BigInt result;\r
+\r
+ if ((n1.sign && !n2.sign) || (!n1.sign && n2.sign))\r
+ {\r
+ result = new BigInt(n1);\r
+ result.AddInternal(n2);\r
+ result.sign = n1.sign;\r
+ }\r
+ else\r
+ {\r
+ bool lessThan = LtInt(n1, n2);\r
+\r
+ if (lessThan)\r
+ {\r
+ result = new BigInt(n2);\r
+ result.SubInternal(n1);\r
+ result.sign = !n1.sign;\r
+ }\r
+ else\r
+ {\r
+ result = new BigInt(n1);\r
+ result.SubInternal(n2);\r
+ result.sign = n1.sign;\r
+ }\r
+ }\r
+\r
+ return result;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Multiplication of two BigInts\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public static BigInt Mul(BigInt n1, BigInt n2)\r
+ {\r
+ if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
+ \r
+ BigInt result = new BigInt(n1);\r
+ result.Mul(n2);\r
+ return result;\r
+ }\r
+\r
+ /// <summary>\r
+ /// True arbitrary precision divide.\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public static BigInt Div(BigInt n1, BigInt n2)\r
+ {\r
+ if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
+ BigInt res = new BigInt(n1);\r
+ res.Div(n2);\r
+ return res;\r
+ }\r
+\r
+ /// <summary>\r
+ /// True arbitrary-precision mod operation\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public static BigInt Mod(BigInt n1, BigInt n2)\r
+ {\r
+ if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
+ BigInt res = new BigInt(n1);\r
+ res.Mod(n2);\r
+ return res;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Unsigned multiplication of a BigInt by a small number\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public static BigInt Mul(BigInt n1, uint n2)\r
+ {\r
+ BigInt result = new BigInt(n1);\r
+ result.MulInternal(n2);\r
+ return result;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Division of a BigInt by a small (unsigned) number\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public static BigInt Div(BigInt n1, uint n2)\r
+ {\r
+ BigInt result = new BigInt(n1);\r
+ result.DivInternal(n2);\r
+ return result;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Division and remainder of a BigInt by a small (unsigned) number\r
+ /// n1 / n2 = div remainder mod\r
+ /// </summary>\r
+ /// <param name="n1">The number to divide (dividend)</param>\r
+ /// <param name="n2">The number to divide by (divisor)</param>\r
+ /// <param name="div">The quotient (output parameter)</param>\r
+ /// <param name="mod">The remainder (output parameter)</param>\r
+ public static void DivMod(BigInt n1, uint n2, out BigInt div, out BigInt mod)\r
+ {\r
+ div = Div(n1, n2);\r
+ mod = Mul(div, n2);\r
+ mod = Sub(n1, mod);\r
+ }\r
+\r
+ //**************** Static Comparison Functions ***************\r
+\r
+ /// <summary>\r
+ /// true iff n1 is less than n2\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public static bool LessThan(BigInt n1, BigInt n2)\r
+ {\r
+ if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
+\r
+ if (n1.sign)\r
+ {\r
+ if (!n2.sign) return true;\r
+ return GtInt(n1, n2);\r
+ }\r
+ else\r
+ {\r
+ if (n2.sign) return false;\r
+ return LtInt(n1, n2);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// true iff n1 is greater than n2\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public static bool GreaterThan(BigInt n1, BigInt n2)\r
+ {\r
+ if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
+\r
+ if (n1.sign)\r
+ {\r
+ if (!n2.sign) return false;\r
+ return LtInt(n1, n2);\r
+ }\r
+ else\r
+ {\r
+ if (n2.sign) return true;\r
+ return GtInt(n1, n2);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// true iff n1 == n2\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public static bool Equals(BigInt n1, BigInt n2)\r
+ {\r
+ return n1.Equals(n2);\r
+ }\r
+\r
+ //***************** Static Bitwise Functions *****************\r
+\r
+ /// <summary>\r
+ /// Bitwise And\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public static BigInt And(BigInt n1, BigInt n2)\r
+ {\r
+ if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
+ BigInt res = new BigInt(n1);\r
+ res.And(n2);\r
+ return res;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Bitwise Or\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public static BigInt Or(BigInt n1, BigInt n2)\r
+ {\r
+ if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
+ BigInt res = new BigInt(n1);\r
+ res.Or(n2);\r
+ return res;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Bitwise Xor\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ public static BigInt Xor(BigInt n1, BigInt n2)\r
+ {\r
+ if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
+ BigInt res = new BigInt(n1);\r
+ res.And(n2);\r
+ return res;\r
+ }\r
+\r
+ //**************** Static Operator Overloads *****************\r
+\r
+ /// <summary>\r
+ /// Addition operator\r
+ /// </summary>\r
+ public static BigInt operator +(BigInt n1, BigInt n2)\r
+ {\r
+ return Add(n1, n2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// The subtraction operator\r
+ /// </summary>\r
+ public static BigInt operator -(BigInt n1, BigInt n2)\r
+ {\r
+ return Sub(n1, n2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// The multiplication operator\r
+ /// </summary>\r
+ public static BigInt operator *(BigInt n1, BigInt n2)\r
+ {\r
+ return Mul(n1, n2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// The division operator\r
+ /// </summary>\r
+ public static BigInt operator /(BigInt n1, BigInt n2)\r
+ {\r
+ return Div(n1, n2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// The remainder (mod) operator\r
+ /// </summary>\r
+ public static BigInt operator %(BigInt n1, BigInt n2)\r
+ {\r
+ return Mod(n1, n2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// The left-shift operator\r
+ /// </summary>\r
+ public static BigInt operator <<(BigInt n1, int n2)\r
+ {\r
+ BigInt res = new BigInt(n1);\r
+ res.LSH(n2);\r
+ return res;\r
+ }\r
+\r
+ /// <summary>\r
+ /// The right-shift operator\r
+ /// </summary>\r
+ public static BigInt operator >>(BigInt n1, int n2)\r
+ {\r
+ BigInt res = new BigInt(n1);\r
+ res.RSH(n2);\r
+ return res;\r
+ }\r
+\r
+ /// <summary>\r
+ /// The less than operator\r
+ /// </summary>\r
+ public static bool operator <(BigInt n1, BigInt n2)\r
+ {\r
+ return LessThan(n1, n2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// The greater than operator\r
+ /// </summary>\r
+ public static bool operator >(BigInt n1, BigInt n2)\r
+ {\r
+ return GreaterThan(n1, n2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// The less than or equal to operator\r
+ /// </summary>\r
+ public static bool operator <=(BigInt n1, BigInt n2)\r
+ {\r
+ return !GreaterThan(n1, n2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// The greater than or equal to operator\r
+ /// </summary>\r
+ public static bool operator >=(BigInt n1, BigInt n2)\r
+ {\r
+ return !LessThan(n1, n2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// The equality operator\r
+ /// </summary>\r
+ public static bool operator ==(BigInt n1, BigInt n2)\r
+ {\r
+ return Equals(n1, n2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// The inequality operator\r
+ /// </summary>\r
+ public static bool operator !=(BigInt n1, BigInt n2)\r
+ {\r
+ return !Equals(n1, n2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// The bitwise AND operator\r
+ /// </summary>\r
+ public static BigInt operator &(BigInt n1, BigInt n2)\r
+ {\r
+ return And(n1, n2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// The bitwise OR operator\r
+ /// </summary>\r
+ public static BigInt operator |(BigInt n1, BigInt n2)\r
+ {\r
+ return Or(n1, n2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// The bitwise eXclusive OR operator\r
+ /// </summary>\r
+ public static BigInt operator ^(BigInt n1, BigInt n2)\r
+ {\r
+ return Xor(n1, n2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// The increment operator\r
+ /// </summary>\r
+ public static BigInt operator ++(BigInt n1)\r
+ {\r
+ n1.Increment();\r
+ return n1;\r
+ }\r
+\r
+ /// <summary>\r
+ /// The decrement operator\r
+ /// </summary>\r
+ public static BigInt operator --(BigInt n1)\r
+ {\r
+ n1.Decrement();\r
+ return n1;\r
+ }\r
+\r
+ //**************** Private Member Functions *****************\r
+\r
+ /// <summary>\r
+ /// Unsigned multiplication and assignment by a small number\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ private void MulInternal(uint n2)\r
+ {\r
+ int Length = digitArray.Length;\r
+ ulong n2long = (ulong)n2;\r
+\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ workingSet[i] = 0;\r
+ }\r
+\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ if (digitArray[i] == 0) continue;\r
+ ulong temp = (ulong)digitArray[i] * n2long;\r
+ digitArray[i] = (uint)(temp & 0xffffffff);\r
+ if (i + 1 < Length) workingSet[i + 1] = (uint)(temp >> 32);\r
+ }\r
+\r
+ AddInternalBits(workingSet);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Unsigned division and assignment by a small number\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ private void DivInternal(uint n2)\r
+ {\r
+ int Length = digitArray.Length;\r
+ ulong carry = 0;\r
+\r
+ //Divide each digit by the small number.\r
+ for (int i = Length - 1; i >= 0; i--)\r
+ {\r
+ ulong temp = (ulong)digitArray[i] + (carry << 32);\r
+ digitArray[i] = (uint)(temp / (ulong)n2);\r
+ carry = temp % (ulong)n2;\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Adds a signed integer to the number.\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ private void AddInternal(int n1)\r
+ {\r
+ if (n1 < 0)\r
+ {\r
+ SubInternal(-n1);\r
+ return;\r
+ }\r
+\r
+ uint carry = 0;\r
+ int length = digitArray.Length;\r
+\r
+ for (int i = 0; i < length && !(n1 == 0 && carry == 0); i++)\r
+ {\r
+ uint temp = digitArray[i];\r
+ digitArray[i] += (uint)n1 + carry;\r
+\r
+ carry = (digitArray[i] <= temp) ? 1u: 0u;\r
+ \r
+ n1 = 0;\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Subtract a signed integer from the number.\r
+ /// This is internal because it will fail spectacularly if this number is negative or if n1 is bigger than this number.\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ private void SubInternal(int n1)\r
+ {\r
+ if (n1 < 0)\r
+ {\r
+ AddInternal(-n1);\r
+ return;\r
+ }\r
+\r
+ uint carry = 0;\r
+ int length = digitArray.Length;\r
+\r
+ for (int i = 0; i < length && !(n1 == 0 && carry == 0); i++)\r
+ {\r
+ uint temp = digitArray[i];\r
+ digitArray[i] -= ((uint)n1 + carry);\r
+\r
+ carry = (digitArray[i] >= temp) ? 1u: 0u;\r
+\r
+ n1 = 0;\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Adds a signed integer to the number.\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ private bool AddInternal(uint n1)\r
+ {\r
+ uint carry = 0;\r
+ int length = digitArray.Length;\r
+\r
+ for (int i = 0; i < length && !(n1 == 0 && carry == 0); i++)\r
+ {\r
+ uint temp = digitArray[i];\r
+ digitArray[i] += n1 + carry;\r
+\r
+ carry = (digitArray[i] <= temp) ? 1u: 0u;\r
+\r
+ n1 = 0;\r
+ }\r
+\r
+ return (carry != 0);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Internally subtracts a uint from the number (sign insensitive)\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <returns></returns>\r
+ private bool SubInternal(uint n1)\r
+ {\r
+ uint carry = 0;\r
+ int length = digitArray.Length;\r
+\r
+ for (int i = 0; i < length && !(n1 == 0 && carry == 0); i++)\r
+ {\r
+ uint temp = digitArray[i];\r
+ digitArray[i] -= (n1 + carry);\r
+\r
+ carry = (digitArray[i] >= temp) ? 1u: 0u;\r
+\r
+ n1 = 0;\r
+ }\r
+\r
+ return (carry != 0);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Internal increment function (sign insensitive)\r
+ /// </summary>\r
+ private bool IncrementInt()\r
+ {\r
+ uint carry = 1;\r
+\r
+ int length = digitArray.Length;\r
+\r
+ for (int i = 0; i < length && carry != 0; i++)\r
+ {\r
+ uint temp = digitArray[i];\r
+ digitArray[i]++;\r
+\r
+ if (digitArray[i] > temp) carry = 0;\r
+ }\r
+\r
+ return (carry != 0);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Internal increment function (sign insensitive)\r
+ /// </summary>\r
+ private bool DecrementInt()\r
+ {\r
+ uint carry = 1;\r
+\r
+ int length = digitArray.Length;\r
+\r
+ for (int i = 0; i < length && carry != 0; i++)\r
+ {\r
+ uint temp = digitArray[i];\r
+ digitArray[i]--;\r
+\r
+ if (digitArray[i] < temp) carry = 0;\r
+ }\r
+\r
+ return (carry != 0);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Used to add a digit array to a big int.\r
+ /// </summary>\r
+ /// <param name="digitsToAdd"></param>\r
+ private uint AddInternalBits(uint[] digitsToAdd)\r
+ {\r
+ uint carry = 0;\r
+\r
+ int Length = digitArray.Length;\r
+\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ //Necessary because otherwise the carry calculation could go bad.\r
+ if (digitsToAdd[i] == 0 && carry == 0) continue;\r
+\r
+ uint temp = digitArray[i];\r
+ digitArray[i] += (digitsToAdd[i] + carry);\r
+\r
+ carry = 0;\r
+ if (digitArray[i] <= temp) carry = 1;\r
+ }\r
+\r
+ return carry;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Used to add with matching signs (true addition of the digit arrays)\r
+ /// This is internal because it will fail spectacularly if n1 is negative.\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ private uint AddInternal(BigInt n1)\r
+ {\r
+ return AddInternalBits(n1.digitArray);\r
+ }\r
+\r
+ private uint SubInternalBits(uint[] digitsToAdd)\r
+ {\r
+ uint carry = 0;\r
+\r
+ int Length = digitArray.Length;\r
+\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ //Necessary because otherwise the carry calculation could go bad.\r
+ if (digitsToAdd[i] == 0 && carry == 0) continue;\r
+\r
+ uint temp = digitArray[i];\r
+ digitArray[i] -= (digitsToAdd[i] + carry);\r
+\r
+ carry = 0;\r
+ if (digitArray[i] >= temp) carry = 1;\r
+ }\r
+\r
+ return carry;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Used to subtract n1 (true subtraction of digit arrays) - n1 must be less than or equal to this number\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ private uint SubInternal(BigInt n1)\r
+ {\r
+ return SubInternalBits(n1.digitArray);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns the length of the BigInt in 32-bit words for a given decimal precision\r
+ /// </summary>\r
+ /// <param name="precision"></param>\r
+ /// <returns></returns>\r
+ private static int GetRequiredDigitsForPrecision(PrecisionSpec precision)\r
+ {\r
+ int bits = precision.NumBits;\r
+ return ((bits - 1) >> 5) + 1;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Initialises the BigInt to a desired decimal precision\r
+ /// </summary>\r
+ /// <param name="precision"></param>\r
+ private void Init(PrecisionSpec precision)\r
+ {\r
+ int numDigits = GetRequiredDigitsForPrecision(precision);\r
+ digitArray = new uint[numDigits];\r
+ workingSet = new uint[numDigits];\r
+ pres = precision;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Initialises the BigInt from a string, given a base and precision\r
+ /// </summary>\r
+ /// <param name="init"></param>\r
+ /// <param name="precision"></param>\r
+ /// <param name="numberBase"></param>\r
+ private void InitFromString(string init, PrecisionSpec precision, int numberBase)\r
+ {\r
+ PrecisionSpec test;\r
+ if (numberBase == 2)\r
+ {\r
+ test = new PrecisionSpec(init.Length, PrecisionSpec.BaseType.BIN);\r
+ }\r
+ else if (numberBase == 8)\r
+ {\r
+ test = new PrecisionSpec(init.Length, PrecisionSpec.BaseType.OCT);\r
+ }\r
+ else if (numberBase == 10)\r
+ {\r
+ test = new PrecisionSpec(init.Length, PrecisionSpec.BaseType.DEC);\r
+ }\r
+ else if (numberBase == 16)\r
+ {\r
+ test = new PrecisionSpec(init.Length, PrecisionSpec.BaseType.HEX);\r
+ }\r
+ else\r
+ {\r
+ throw new ArgumentOutOfRangeException();\r
+ }\r
+\r
+ //if (test.NumBits > precision.NumBits) precision = test;\r
+ Init(precision);\r
+ FromStringInt(init, numberBase);\r
+ }\r
+\r
+ //************ Helper Functions for floating point *************\r
+\r
+ /// <summary>\r
+ /// Returns true if only the top bit is set: i.e. if the floating-point number is a power of 2\r
+ /// </summary>\r
+ /// <returns></returns>\r
+ public bool IsTopBitOnlyBit()\r
+ {\r
+ int length = digitArray.Length;\r
+\r
+ if (digitArray[length - 1] != 0x80000000u) return false;\r
+ length--;\r
+ for (int i = 0; i < length; i++)\r
+ {\r
+ if (digitArray[i] != 0) return false;\r
+ }\r
+\r
+ return true;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Zeroes the n most significant bits of the number\r
+ /// </summary>\r
+ /// <param name="bits"></param>\r
+ public void ZeroBitsHigh(int bits)\r
+ {\r
+ //Already done.\r
+ if (bits <= 0) return;\r
+\r
+ int length = digitArray.Length;\r
+\r
+ //The entire digit array.\r
+ if ((bits >> 5) > length)\r
+ {\r
+ bits = length << 5;\r
+ }\r
+\r
+ int remBits = (bits & 31);\r
+ int startDigit = length - ((bits >> 5) + 1);\r
+\r
+ if (remBits != 0)\r
+ {\r
+ digitArray[startDigit] = digitArray[startDigit] & (0xffffffffu >> remBits);\r
+ }\r
+\r
+ for (int i = startDigit + 1; i < length; i++)\r
+ {\r
+ digitArray[i] = 0;\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Zeroes the least-significant n bits.\r
+ /// </summary>\r
+ /// <param name="bits"></param>\r
+ public void ZeroBits(int bits)\r
+ {\r
+ //Already done.\r
+ if (bits <= 0) return;\r
+\r
+ //The entire digit array.\r
+ if ((bits >> 5) > digitArray.Length)\r
+ {\r
+ bits = digitArray.Length << 5;\r
+ }\r
+\r
+ int remBits = (bits & 31);\r
+ int startDigit = bits >> 5;\r
+ \r
+ if (remBits != 0)\r
+ {\r
+ UInt32 startMask = 0xffffffffu & ~(UInt32)(((1 << remBits) - 1));\r
+ digitArray[startDigit] = digitArray[startDigit] & startMask;\r
+ }\r
+\r
+ for (int i = startDigit - 1; i >= 0; i--)\r
+ {\r
+ digitArray[i] = 0;\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Sets the number to 0\r
+ /// </summary>\r
+ public void Zero()\r
+ {\r
+ int length = digitArray.Length;\r
+\r
+ for (int i = 0; i < length; i++)\r
+ {\r
+ digitArray[i] = 0;\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Rounds off the least significant bits of the number.\r
+ /// Can only round off up to 31 bits.\r
+ /// </summary>\r
+ /// <param name="bits">number of bits to round</param>\r
+ /// <returns></returns>\r
+ public bool Round(int bits)\r
+ {\r
+ //Always less than 32 bits, please!\r
+ if (bits < 32)\r
+ {\r
+ uint pow2 = 1u << bits;\r
+ uint test = digitArray[0] & (pow2 >> 1);\r
+\r
+ //Zero the lower bits\r
+ digitArray[0] = digitArray[0] & ~(pow2 - 1);\r
+\r
+ if (test != 0)\r
+ {\r
+ bool bRet = AddInternal(pow2);\r
+ digitArray[digitArray.Length - 1] = digitArray[digitArray.Length - 1] | 0x80000000;\r
+ return bRet;\r
+ }\r
+ }\r
+\r
+ return false;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Used for casting between BigFloats of different precisions - this assumes\r
+ /// that the number is a normalised mantissa.\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ /// <returns>true if a round-up caused the high bits to become zero</returns>\r
+ public bool AssignHigh(BigInt n2)\r
+ {\r
+ int length = digitArray.Length;\r
+ int length2 = n2.digitArray.Length;\r
+ int minWords = (length < length2) ? length: length2;\r
+ bool bRet = false;\r
+\r
+ for (int i = 1; i <= minWords; i++)\r
+ {\r
+ digitArray[length - i] = n2.digitArray[length2 - i];\r
+ }\r
+\r
+ if (length2 > length && n2.digitArray[length2 - (length + 1)] >= 0x80000000)\r
+ {\r
+ bRet = IncrementInt();\r
+\r
+ //Because we are assuming normalisation, we set the top bit (it will already be set if\r
+ //bRet is false.\r
+ digitArray[length - 1] = digitArray[length - 1] | 0x80000000;\r
+ }\r
+\r
+ sign = n2.sign;\r
+\r
+ return bRet;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Used for casting between long ints or doubles and floating-point numbers\r
+ /// </summary>\r
+ /// <param name="digits"></param>\r
+ public void SetHighDigits(Int64 digits)\r
+ {\r
+ digitArray[digitArray.Length - 1] = (uint)(digits >> 32);\r
+ if (digitArray.Length > 1) digitArray[digitArray.Length - 2] = (uint)(digits & 0xffffffff);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Used for casting between ints and doubles or floats.\r
+ /// </summary>\r
+ /// <param name="digit"></param>\r
+ public void SetHighDigit(UInt32 digit)\r
+ {\r
+ digitArray[digitArray.Length - 1] = digit;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Helper function for floating-point - extends the number to twice the precision\r
+ /// and shifts the digits into the upper bits.\r
+ /// </summary>\r
+ public void Pad()\r
+ {\r
+ int length = digitArray.Length;\r
+ int digits = length << 1;\r
+\r
+ UInt32[] newDigitArray = new UInt32[digits];\r
+ workingSet = new UInt32[digits];\r
+\r
+ for (int i = 0; i < length; i++)\r
+ {\r
+ newDigitArray[i + length] = digitArray[i];\r
+ }\r
+\r
+ digitArray = newDigitArray;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Helper function for floating-point - extends the number to twice the precision...\r
+ /// This is a necessary step in floating-point division.\r
+ /// </summary>\r
+ public void Extend()\r
+ {\r
+ SetNumDigits(digitArray.Length * 2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Gets the highest big of the integer (used for floating point stuff)\r
+ /// </summary>\r
+ /// <returns></returns>\r
+ public uint GetTopBit()\r
+ {\r
+ return (digitArray[digitArray.Length - 1] >> 31);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Used for floating point multiplication, this shifts the number so that\r
+ /// the highest bit is set, and returns the number of places shifted.\r
+ /// </summary>\r
+ /// <returns></returns>\r
+ public int Normalise()\r
+ {\r
+ if (IsZero()) return 0;\r
+\r
+ int MSD = GetMSD();\r
+ int digitShift = (digitArray.Length - (MSD + 1));\r
+ int bitShift = (31 - GetMSB(digitArray[MSD])) + (digitShift << 5);\r
+ LSH(bitShift);\r
+ return bitShift;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Gets the most significant bit\r
+ /// </summary>\r
+ /// <param name="value">the input to search for the MSB in</param>\r
+ /// <returns>-1 if the input was zero, the position of the MSB otherwise</returns>\r
+ public static int GetMSB(UInt32 value)\r
+ {\r
+ if (value == 0) return -1;\r
+\r
+ uint mask1 = 0xffff0000;\r
+ uint mask2 = 0xff00;\r
+ uint mask3 = 0xf0;\r
+ uint mask4 = 0xc; //1100 in binary\r
+ uint mask5 = 0x2; //10 in binary\r
+\r
+ int iPos = 0;\r
+\r
+ //Unrolled binary search for the most significant bit.\r
+ if ((value & mask1) != 0) iPos += 16;\r
+ mask2 <<= iPos;\r
+\r
+ if ((value & mask2) != 0) iPos += 8;\r
+ mask3 <<= iPos;\r
+\r
+ if ((value & mask3) != 0) iPos += 4;\r
+ mask4 <<= iPos;\r
+\r
+ if ((value & mask4) != 0) iPos += 2;\r
+ mask5 <<= iPos;\r
+\r
+ if ((value & mask5) != 0) iPos++;\r
+\r
+ return iPos;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Gets the most significant bit\r
+ /// </summary>\r
+ /// <param name="value">the input to search for the MSB in</param>\r
+ /// <returns>-1 if the input was zero, the position of the MSB otherwise</returns>\r
+ public static int GetMSB(UInt64 value)\r
+ {\r
+ if (value == 0) return -1;\r
+\r
+ UInt64 mask0 = 0xffffffff00000000ul;\r
+ UInt64 mask1 = 0xffff0000;\r
+ UInt64 mask2 = 0xff00;\r
+ UInt64 mask3 = 0xf0;\r
+ UInt64 mask4 = 0xc; //1100 in binary\r
+ UInt64 mask5 = 0x2; //10 in binary\r
+\r
+ int iPos = 0;\r
+\r
+ //Unrolled binary search for the most significant bit.\r
+ if ((value & mask0) != 0) iPos += 32;\r
+ mask1 <<= iPos;\r
+\r
+ if ((value & mask1) != 0) iPos += 16;\r
+ mask2 <<= iPos;\r
+\r
+ if ((value & mask2) != 0) iPos += 8;\r
+ mask3 <<= iPos;\r
+\r
+ if ((value & mask3) != 0) iPos += 4;\r
+ mask4 <<= iPos;\r
+\r
+ if ((value & mask4) != 0) iPos += 2;\r
+ mask5 <<= iPos;\r
+\r
+ if ((value & mask5) != 0) iPos++;\r
+\r
+ return iPos;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Gets the most significant bit\r
+ /// </summary>\r
+ /// <param name="value">the input to search for the MSB in</param>\r
+ /// <returns>-1 if the input was zero, the position of the MSB otherwise</returns>\r
+ public static int GetMSB(BigInt value)\r
+ {\r
+ int digit = value.GetMSD();\r
+ int bit = GetMSB(value.digitArray[digit]);\r
+ return (digit << 5) + bit;\r
+ }\r
+\r
+ //**************** Helper Functions for Div ********************\r
+\r
+ /// <summary>\r
+ /// Gets the index of the most significant digit\r
+ /// </summary>\r
+ /// <returns></returns>\r
+ private int GetMSD()\r
+ {\r
+ for (int i = digitArray.Length - 1; i >= 0; i--)\r
+ {\r
+ if (digitArray[i] != 0) return i;\r
+ }\r
+\r
+ return 0;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Gets the required bitshift for the Div_32 algorithm\r
+ /// </summary>\r
+ /// <returns></returns>\r
+ private int GetDivBitshift()\r
+ {\r
+ uint digit = digitArray[GetMSD()];\r
+ uint mask1 = 0xffff0000;\r
+ uint mask2 = 0xff00;\r
+ uint mask3 = 0xf0; \r
+ uint mask4 = 0xc; //1100 in binary\r
+ uint mask5 = 0x2; //10 in binary\r
+\r
+ int iPos = 0;\r
+\r
+ //Unrolled binary search for the most significant bit.\r
+ if ((digit & mask1) != 0) iPos += 16;\r
+ mask2 <<= iPos;\r
+\r
+ if ((digit & mask2) != 0) iPos += 8;\r
+ mask3 <<= iPos;\r
+ \r
+ if ((digit & mask3) != 0) iPos += 4;\r
+ mask4 <<= iPos;\r
+\r
+ if ((digit & mask4) != 0) iPos += 2;\r
+ mask5 <<= iPos;\r
+\r
+ if ((digit & mask5) != 0) return 30 - iPos;\r
+\r
+ return 31 - iPos;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Shifts and optionally precision-extends the arguments to prepare for Div_32\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ private static int MakeSafeDiv(BigInt n1, BigInt n2)\r
+ {\r
+ int shift = n2.GetDivBitshift();\r
+ int n1MSD = n1.GetMSD();\r
+\r
+ uint temp = n1.digitArray[n1MSD];\r
+ if (n1MSD == n1.digitArray.Length - 1 && ((temp << shift) >> shift) != n1.digitArray[n1MSD])\r
+ {\r
+ //Precision-extend n1 and n2 if necessary\r
+ int digits = n1.digitArray.Length;\r
+ n1.SetNumDigits(digits + 1);\r
+ n2.SetNumDigits(digits + 1);\r
+ }\r
+\r
+ //Logical left-shift n1 and n2\r
+ n1.LSH(shift);\r
+ n2.LSH(shift);\r
+\r
+ return shift;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Schoolbook division helper function.\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <param name="Q">Quotient output value</param>\r
+ /// <param name="R">Remainder output value</param>\r
+ private static void Div_31(BigInt n1, BigInt n2, BigInt Q, BigInt R)\r
+ {\r
+ int digitsN1 = n1.GetMSD() + 1;\r
+ int digitsN2 = n2.GetMSD() + 1; \r
+\r
+ if ((digitsN1 > digitsN2))\r
+ {\r
+ BigInt n1New = new BigInt(n2);\r
+ n1New.DigitShiftSelfLeft(1);\r
+\r
+ //If n1 >= n2 * 2^32\r
+ if (!LtInt(n1, n1New))\r
+ {\r
+ n1New.sign = n1.sign;\r
+ SubFast(n1New, n1, n1New);\r
+\r
+ Div_32(n1New, n2, Q, R);\r
+\r
+ //Q = (A - B*2^32)/B + 2^32\r
+ Q.Add2Pow32Self();\r
+ return;\r
+ }\r
+ }\r
+\r
+ UInt32 q = 0;\r
+\r
+ if (digitsN1 >= 2)\r
+ {\r
+ UInt64 q64 = ((((UInt64)n1.digitArray[digitsN1 - 1]) << 32) + n1.digitArray[digitsN1 - 2]) / (UInt64)n2.digitArray[digitsN2 - 1];\r
+\r
+ if (q64 > 0xfffffffful)\r
+ {\r
+ q = 0xffffffff;\r
+ }\r
+ else\r
+ {\r
+ q = (UInt32)q64;\r
+ }\r
+ }\r
+\r
+ BigInt temp = Mul(n2, q);\r
+\r
+ if (GtInt(temp, n1))\r
+ {\r
+ temp.SubInternalBits(n2.digitArray);\r
+ q--;\r
+\r
+ if (GtInt(temp, n1))\r
+ {\r
+ temp.SubInternalBits(n2.digitArray);\r
+ q--;\r
+ }\r
+ }\r
+\r
+ Q.Zero();\r
+ Q.digitArray[0] = q;\r
+ R.Assign(n1);\r
+ R.SubInternalBits(temp.digitArray);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Schoolbook division algorithm\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <param name="Q"></param>\r
+ /// <param name="R"></param>\r
+ private static void Div_32(BigInt n1, BigInt n2, BigInt Q, BigInt R)\r
+ {\r
+ int digitsN1 = n1.GetMSD() + 1;\r
+ int digitsN2 = n2.GetMSD() + 1;\r
+\r
+ //n2 is bigger than n1\r
+ if (digitsN1 < digitsN2)\r
+ {\r
+ R.AssignInt(n1);\r
+ Q.Zero();\r
+ return;\r
+ }\r
+\r
+ if (digitsN1 == digitsN2)\r
+ {\r
+ //n2 is bigger than n1\r
+ if (LtInt(n1, n2))\r
+ {\r
+ R.AssignInt(n1);\r
+ Q.Zero();\r
+ return;\r
+ }\r
+\r
+ //n2 >= n1, but less the 2x n1 (initial conditions make this certain)\r
+ Q.Zero();\r
+ Q.digitArray[0] = 1;\r
+ R.Assign(n1);\r
+ R.SubInternalBits(n2.digitArray);\r
+ return;\r
+ }\r
+\r
+ int digits = digitsN1 - (digitsN2 + 1);\r
+\r
+ //Algorithm Div_31 can be used to get the answer in O(n) time.\r
+ if (digits == 0)\r
+ {\r
+ Div_31(n1, n2, Q, R);\r
+ return;\r
+ }\r
+\r
+ BigInt n1New = DigitShiftRight(n1, digits);\r
+ BigInt s = DigitTruncate(n1, digits);\r
+\r
+ BigInt Q2 = new BigInt(n1, n1.pres, true);\r
+ BigInt R2 = new BigInt(n1, n1.pres, true);\r
+\r
+ Div_31(n1New, n2, Q2, R2);\r
+\r
+ R2.DigitShiftSelfLeft(digits);\r
+ R2.Add(s);\r
+\r
+ Div_32(R2, n2, Q, R);\r
+\r
+ Q2.DigitShiftSelfLeft(digits);\r
+ Q.Add(Q2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Sets the n-th bit of the number to 1\r
+ /// </summary>\r
+ /// <param name="bit">the index of the bit to set</param>\r
+ public void SetBit(int bit)\r
+ {\r
+ int digit = (bit >> 5);\r
+ if (digit >= digitArray.Length) return;\r
+ digitArray[digit] = digitArray[digit] | (1u << (bit - (digit << 5)));\r
+ }\r
+\r
+ /// <summary>\r
+ /// Sets the n-th bit of the number to 0\r
+ /// </summary>\r
+ /// <param name="bit">the index of the bit to set</param>\r
+ public void ClearBit(int bit)\r
+ {\r
+ int digit = (bit >> 5);\r
+ if (digit >= digitArray.Length) return;\r
+ digitArray[digit] = digitArray[digit] & (~(1u << (bit - (digit << 5))));\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns the n-th bit, counting from the MSB to the LSB\r
+ /// </summary>\r
+ /// <param name="bit">the index of the bit to return</param>\r
+ /// <returns>1 if the bit is 1, 0 otherwise</returns>\r
+ public uint GetBitFromTop(int bit)\r
+ {\r
+ if (bit < 0) return 0;\r
+ int wordCount = (bit >> 5);\r
+ int upBit = 31 - (bit & 31);\r
+ if (wordCount >= digitArray.Length) return 0;\r
+\r
+ return ((digitArray[digitArray.Length - (wordCount + 1)] & (1u << upBit)) >> upBit);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Assigns n2 to 'this'\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ public void Assign(BigInt n2)\r
+ {\r
+ if (digitArray.Length != n2.digitArray.Length) MakeSafe(ref n2);\r
+ sign = n2.sign;\r
+ AssignInt(n2);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Assign n2 to 'this', safe only if precision-matched\r
+ /// </summary>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ private void AssignInt(BigInt n2)\r
+ {\r
+ int Length = digitArray.Length;\r
+\r
+ for (int i = 0; i < Length; i++)\r
+ {\r
+ digitArray[i] = n2.digitArray[i];\r
+ }\r
+ }\r
+\r
+ private static BigInt DigitShiftRight(BigInt n1, int digits)\r
+ {\r
+ BigInt res = new BigInt(n1);\r
+\r
+ int Length = res.digitArray.Length;\r
+\r
+ for (int i = 0; i < Length - digits; i++)\r
+ {\r
+ res.digitArray[i] = res.digitArray[i + digits];\r
+ }\r
+\r
+ for (int i = Length - digits; i < Length; i++)\r
+ {\r
+ res.digitArray[i] = 0;\r
+ }\r
+\r
+ return res;\r
+ }\r
+\r
+ private void DigitShiftSelfRight(int digits)\r
+ {\r
+ for (int i = digits; i < digitArray.Length; i++)\r
+ {\r
+ digitArray[i - digits] = digitArray[i];\r
+ }\r
+\r
+ for (int i = digitArray.Length - digits; i < digitArray.Length; i++)\r
+ {\r
+ digitArray[i] = 0;\r
+ }\r
+ }\r
+\r
+ private void DigitShiftSelfLeft(int digits)\r
+ {\r
+ for (int i = digitArray.Length - 1; i >= digits; i--)\r
+ {\r
+ digitArray[i] = digitArray[i - digits];\r
+ }\r
+\r
+ for (int i = digits - 1; i >= 0; i--)\r
+ {\r
+ digitArray[i] = 0;\r
+ }\r
+ }\r
+\r
+ private static BigInt DigitTruncate(BigInt n1, int digits)\r
+ {\r
+ BigInt res = new BigInt(n1);\r
+\r
+ for (int i = res.digitArray.Length - 1; i >= digits; i--)\r
+ {\r
+ res.digitArray[i] = 0;\r
+ }\r
+\r
+ return res;\r
+ }\r
+\r
+ private void Add2Pow32Self()\r
+ {\r
+ int Length = digitArray.Length;\r
+\r
+ uint carry = 1;\r
+\r
+ for (int i = 1; i < Length; i++)\r
+ {\r
+ uint temp = digitArray[i];\r
+ digitArray[i] += carry;\r
+ if (digitArray[i] > temp) return;\r
+ }\r
+\r
+ return;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Sets the number of digits without changing the precision\r
+ /// This method is made public only to facilitate fixed-point operations\r
+ /// It should under no circumstances be used for anything else, because\r
+ /// it breaks the BigNum(PrecisionSpec precision) constructor in dangerous\r
+ /// and unpredictable ways.\r
+ /// </summary>\r
+ /// <param name="digits"></param>\r
+ public void SetNumDigits(int digits)\r
+ {\r
+ if (digits == digitArray.Length) return;\r
+\r
+ UInt32[] newDigitArray = new UInt32[digits];\r
+ workingSet = new UInt32[digits];\r
+\r
+ int numCopy = (digits < digitArray.Length) ? digits : digitArray.Length;\r
+\r
+ for (int i = 0; i < numCopy; i++)\r
+ {\r
+ newDigitArray[i] = digitArray[i];\r
+ }\r
+\r
+ digitArray = newDigitArray;\r
+ }\r
+\r
+ //********************** Explicit casts ***********************\r
+\r
+ /// <summary>\r
+ /// Cast to int\r
+ /// </summary>\r
+ /// <param name="value"></param>\r
+ /// <returns></returns>\r
+ public static explicit operator Int32(BigInt value)\r
+ {\r
+ if (value.digitArray[0] == 0x80000000 && value.sign) return Int32.MinValue;\r
+ int res = (int)(value.digitArray[0] & 0x7fffffff);\r
+ if (value.sign) res = -res;\r
+ return res;\r
+ }\r
+\r
+ /// <summary>\r
+ /// explicit cast to unsigned int.\r
+ /// </summary>\r
+ /// <param name="value"></param>\r
+ /// <returns></returns>\r
+ public static explicit operator UInt32(BigInt value)\r
+ {\r
+ if (value.sign) return (UInt32)((Int32)(value));\r
+ return (UInt32)value.digitArray[0];\r
+ }\r
+\r
+ /// <summary>\r
+ /// explicit cast to 64-bit signed integer.\r
+ /// </summary>\r
+ /// <param name="value"></param>\r
+ /// <returns></returns>\r
+ public static explicit operator Int64(BigInt value)\r
+ {\r
+ if (value.digitArray.Length < 2) return (value.sign ? -((Int64)value.digitArray[0]): ((Int64)value.digitArray[0]));\r
+ UInt64 ret = (((UInt64)value.digitArray[1]) << 32) + (UInt64)value.digitArray[0];\r
+ if (ret == 0x8000000000000000L && value.sign) return Int64.MinValue;\r
+ Int64 signedRet = (Int64)(ret & 0x7fffffffffffffffL);\r
+ if (value.sign) signedRet = -signedRet;\r
+ return signedRet;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Explicit cast to UInt64\r
+ /// </summary>\r
+ /// <param name="value"></param>\r
+ /// <returns></returns>\r
+ public static explicit operator UInt64(BigInt value)\r
+ {\r
+ if (value.sign) return (UInt64)((Int64)(value));\r
+ if (value.digitArray.Length < 2) return (UInt64)value.digitArray[0];\r
+ return ((((UInt64)value.digitArray[1]) << 32) + (UInt64)value.digitArray[0]);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Cast to string\r
+ /// </summary>\r
+ /// <param name="value"></param>\r
+ /// <returns></returns>\r
+ public static explicit operator string(BigInt value)\r
+ {\r
+ return value.ToString();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Cast from string - this is not wholly safe, because precision is not\r
+ /// specified. You should try to construct a BigInt with the appropriate\r
+ /// constructor instead.\r
+ /// </summary>\r
+ /// <param name="value">The decimal string to convert to a BigInt</param>\r
+ /// <returns>A BigInt of the precision required to encompass the string</returns>\r
+ public static explicit operator BigInt(string value)\r
+ {\r
+ return new BigInt(value);\r
+ }\r
+\r
+ //********************* ToString members **********************\r
+\r
+ /// <summary>\r
+ /// Converts this to a string, in the specified base\r
+ /// </summary>\r
+ /// <param name="numberBase">the base to use (min 2, max 16)</param>\r
+ /// <returns>a string representation of the number</returns>\r
+ public string ToString(int numberBase)\r
+ {\r
+ char[] digitChars = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };\r
+\r
+ string output = "";\r
+\r
+ BigInt clone = new BigInt(this);\r
+ clone.sign = false;\r
+\r
+ int numDigits = 0;\r
+ while (!clone.IsZero())\r
+ {\r
+ if (numberBase == 10 && (numDigits % 3) == 0 && numDigits != 0)\r
+ {\r
+ output = String.Format(",{0}", output);\r
+ }\r
+ else if (numberBase != 10 && (numDigits % 8) == 0 && numDigits != 0)\r
+ {\r
+ output = String.Format(" {0}", output);\r
+ }\r
+\r
+ BigInt div, mod;\r
+ DivMod(clone, (uint)numberBase, out div, out mod);\r
+ int iMod = (int)mod;\r
+ output = String.Format("{0}{1}", digitChars[(int)mod], output);\r
+\r
+ numDigits++;\r
+\r
+ clone = div;\r
+ }\r
+\r
+ if (output.Length == 0) output = String.Format("0");\r
+\r
+ if (sign) output = String.Format("-{0}", output);\r
+\r
+ return output;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Converts the number to a string, in base 10\r
+ /// </summary>\r
+ /// <returns>a string representation of the number in base 10</returns>\r
+ public override string ToString()\r
+ {\r
+ return ToString(10);\r
+ }\r
+\r
+ //***************** Internal helper functions *****************\r
+\r
+ private void FromStringInt(string init, int numberBase)\r
+ {\r
+ char [] digitChars = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};\r
+\r
+ string formattedInput = init.Trim().ToUpper();\r
+\r
+ for (int i = 0; i < formattedInput.Length; i++)\r
+ {\r
+ int digitIndex = Array.IndexOf(digitChars, formattedInput[i]);\r
+\r
+ //Skip fractional part altogether\r
+ if (formattedInput[i] == '.') break;\r
+\r
+ //skip non-digit characters.\r
+ if (digitIndex < 0) continue;\r
+\r
+ //Multiply\r
+ MulInternal((uint)numberBase);\r
+ \r
+ //Add\r
+ AddInternal(digitIndex);\r
+ }\r
+\r
+ if (init.Length > 0 && init[0] == '-') sign = true;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Sign-insensitive less than comparison. \r
+ /// unsafe if n1 and n2 disagree in precision\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ private static bool LtInt(BigInt n1, BigInt n2)\r
+ {\r
+ //MakeSafe(ref n1, ref n2);\r
+\r
+ for (int i = n1.digitArray.Length - 1; i >= 0; i--)\r
+ {\r
+ if (n1.digitArray[i] < n2.digitArray[i]) return true;\r
+ if (n1.digitArray[i] > n2.digitArray[i]) return false;\r
+ }\r
+\r
+ //equal\r
+ return false;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Sign-insensitive greater than comparison. \r
+ /// unsafe if n1 and n2 disagree in precision\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <returns></returns>\r
+ private static bool GtInt(BigInt n1, BigInt n2)\r
+ {\r
+ //MakeSafe(ref n1, ref n2);\r
+\r
+ for (int i = n1.digitArray.Length - 1; i >= 0; i--)\r
+ {\r
+ if (n1.digitArray[i] > n2.digitArray[i]) return true;\r
+ if (n1.digitArray[i] < n2.digitArray[i]) return false;\r
+ }\r
+\r
+ //equal\r
+ return false;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Makes sure the numbers have matching precisions\r
+ /// </summary>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ private static void MakeSafe(ref BigInt n1, ref BigInt n2)\r
+ {\r
+ if (n1.digitArray.Length == n2.digitArray.Length)\r
+ {\r
+ return;\r
+ }\r
+ else if (n1.digitArray.Length > n2.digitArray.Length)\r
+ {\r
+ n2 = new BigInt(n2, n1.pres);\r
+ }\r
+ else\r
+ {\r
+ n1 = new BigInt(n1, n2.pres);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Makes sure the numbers have matching precisions\r
+ /// </summary>\r
+ /// <param name="n2">the number to match to this</param>\r
+ private void MakeSafe(ref BigInt n2)\r
+ {\r
+ n2 = new BigInt(n2, pres);\r
+ n2.SetNumDigits(digitArray.Length);\r
+ }\r
+\r
+\r
+ private PrecisionSpec pres;\r
+ private bool sign;\r
+ private uint[] digitArray;\r
+ private uint[] workingSet;\r
+ }\r
+\r
+}
\ No newline at end of file
OSDN Git Service
