+++ /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
