dev4/psychlops/extention/math/BigInt.cs

   1 // http://www.fractal-landscapes.co.uk/bigint.html\r
   2 \r
   3 using System;\r
   4 \r
   5 namespace BigNum\r
   6 {\r
   7     /// <summary>\r
   8     /// Specifies the desired precision for a BigInt or a BigFloat. \r
   9     /// </summary>\r
  10     public struct PrecisionSpec\r
  11     {\r
  12         /// <summary>\r
  13         /// Precision can be specified in a choice of 8 bases.\r
  14         /// Note that precision for decimals is approximate.\r
  15         /// </summary>\r
  16         public enum BaseType\r
  17         {\r
  18             /// <summary>\r
  19             /// Binary base\r
  20             /// </summary>\r
  21             BIN,\r
  22             /// <summary>\r
  23             /// Octal base\r
  24             /// </summary>\r
  25             OCT,\r
  26             /// <summary>\r
  27             /// Decimal base\r
  28             /// </summary>\r
  29             DEC,\r
  30             /// <summary>\r
  31             /// Hexadecimal base\r
  32             /// </summary>\r
  33             HEX,\r
  34             /// <summary>\r
  35             /// 8-bits per digit\r
  36             /// </summary>\r
  37             BYTES,\r
  38             /// <summary>\r
  39             /// 16-bits per digit\r
  40             /// </summary>\r
  41             WORDS,\r
  42             /// <summary>\r
  43             /// 32-bits per digit\r
  44             /// </summary>\r
  45             DWORDS,\r
  46             /// <summary>\r
  47             /// 64-bits per digit\r
  48             /// </summary>\r
  49             QWORDS\r
  50         }\r
  51 \r
  52         /// <summary>\r
  53         /// Constructor: Constructs a precision specification\r
  54         /// </summary>\r
  55         /// <param name="precision">The number of digits</param>\r
  56         /// <param name="numberBase">The base of the digits</param>\r
  57         public PrecisionSpec(int precision, BaseType numberBase)\r
  58         {\r
  59             this.prec = precision;\r
  60             this.nB = numberBase;\r
  61         }\r
  62 \r
  63         /// <summary>\r
  64         /// Explicit cast from integer value.\r
  65         /// </summary>\r
  66         /// <param name="value">The value in bits for the new precision specification</param>\r
  67         /// <returns>A new precision specification with the number of bits specified</returns>\r
  68         public static explicit operator PrecisionSpec(int value)\r
  69         {\r
  70             return new PrecisionSpec(value, BaseType.BIN);\r
  71         }\r
  72 \r
  73         /// <summary>\r
  74         /// Equality test\r
  75         /// </summary>\r
  76         /// <param name="spec1">the first parameter</param>\r
  77         /// <param name="spec2">the second parameter</param>\r
  78         /// <returns>true iff both precisions have the same number of bits</returns>\r
  79         public static bool operator ==(PrecisionSpec spec1, PrecisionSpec spec2)\r
  80         {\r
  81             return (spec1.NumBits == spec2.NumBits);\r
  82         }\r
  83 \r
  84         /// <summary>\r
  85         /// Inequality operator\r
  86         /// </summary>\r
  87         /// <param name="spec1">the first parameter</param>\r
  88         /// <param name="spec2">the second parameter</param>\r
  89         /// <returns>true iff the parameters do not have the same number of bits</returns>\r
  90         public static bool operator !=(PrecisionSpec spec1, PrecisionSpec spec2)\r
  91         {\r
  92             return !(spec1 == spec2);\r
  93         }\r
  94 \r
  95         /// <summary>\r
  96         /// Object equality override\r
  97         /// </summary>\r
  98         /// <param name="obj">the PrecisionSpec struct to compare</param>\r
  99         /// <returns>true iff obj has the same number of bits as this</returns>\r
 100         public override bool Equals(object obj)\r
 101         {\r
 102             return NumBits == ((PrecisionSpec)obj).NumBits;     \r
 103         }\r
 104 \r
 105         /// <summary>\r
 106         /// Override of the hash code\r
 107         /// </summary>\r
 108         /// <returns>A basic hash</returns>\r
 109         public override int GetHashCode()\r
 110         {\r
 111             return NumBits * prec + NumBits;\r
 112         }\r
 113 \r
 114         /// <summary>\r
 115         /// The precision in units specified by the base type (e.g. number of decimal digits)\r
 116         /// </summary>\r
 117         public int Precision\r
 118         {\r
 119             get { return prec; }\r
 120         }\r
 121 \r
 122         /// <summary>\r
 123         /// The base type in which precision is specified\r
 124         /// </summary>\r
 125         public BaseType NumberBaseType\r
 126         {\r
 127             get { return nB; }\r
 128         }\r
 129 \r
 130         /// <summary>\r
 131         /// Converts the number-base to an integer\r
 132         /// </summary>\r
 133         public int NumberBase\r
 134         {\r
 135             get { return (int)nB; }\r
 136         }\r
 137 \r
 138         /// <summary>\r
 139         /// The number of bits that this PrecisionSpec structure specifies.\r
 140         /// </summary>\r
 141         public int NumBits\r
 142         {\r
 143             get\r
 144             {\r
 145                 if (nB == BaseType.BIN) return prec;\r
 146                 if (nB == BaseType.OCT) return prec * 3;\r
 147                 if (nB == BaseType.HEX) return prec * 4;\r
 148                 if (nB == BaseType.BYTES) return prec * 8;\r
 149                 if (nB == BaseType.WORDS) return prec * 16;\r
 150                 if (nB == BaseType.DWORDS) return prec * 32;\r
 151                 if (nB == BaseType.QWORDS) return prec * 64;\r
 152 \r
 153                 double factor = 3.322;\r
 154                 int bits = ((int)Math.Ceiling(factor * (double)prec));\r
 155                 return bits;\r
 156             }\r
 157         }\r
 158 \r
 159         private int prec;\r
 160         private BaseType nB;\r
 161     }\r
 162 \r
 163     \r
 164     /// <summary>\r
 165     /// An arbitrary-precision integer class\r
 166     /// \r
 167     /// Format:\r
 168     /// Each number consists of an array of 32-bit unsigned integers, and a bool sign\r
 169     /// value.\r
 170     /// \r
 171     /// Applicability and Performance:\r
 172     /// This class is designed to be used for small extended precisions. It may not be\r
 173     /// safe (and certainly won't be fast) to use it with mixed-precision arguments.\r
 174     /// It does support, but will not be efficient for, numbers over around 2048 bits.\r
 175     /// \r
 176     /// Notes:\r
 177     /// All conversions to and from strings are slow.\r
 178     /// \r
 179     /// Conversions from simple integer types Int32, Int64, UInt32, UInt64 are performed\r
 180     /// using the appropriate constructor, and are relatively fast.\r
 181     /// \r
 182     /// The class is written entirely in managed C# code, with not native or managed\r
 183     /// assembler. The use of native assembler would speed up the multiplication operations\r
 184     /// many times over, and therefore all higher-order operations too.\r
 185     /// </summary>\r
 186     public class BigInt\r
 187     {\r
 188         //*************** Constructors ******************\r
 189 \r
 190         /// <summary>\r
 191         /// Constructs an empty BigInt to the desired precision.\r
 192         /// </summary>\r
 193         /// <param name="precision"></param>\r
 194         public BigInt(PrecisionSpec precision)\r
 195         {\r
 196             Init(precision);\r
 197         }\r
 198 \r
 199         /// <summary>\r
 200         /// Constructs a BigInt from a string, using the string length to determine the precision\r
 201         /// Note, operations on BigInts of non-matching precision are slow, so avoid using this constructor\r
 202         /// </summary>\r
 203         /// <param name="init"></param>\r
 204         public BigInt(string init)\r
 205         {\r
 206             InitFromString(init, (PrecisionSpec)init.Length, 10);\r
 207         }\r
 208 \r
 209         /// <summary>\r
 210         /// Constructor for copying length and precision\r
 211         /// </summary>\r
 212         /// <param name="inputToCopy">The BigInt to copy</param>\r
 213         /// <param name="precision">The precision of the new BigInt</param>\r
 214         /// <param name="bCopyLengthOnly">decides whether to copy the actual input, or just its digit length</param>\r
 215         /// <example><code>//Create an integer\r
 216         /// BigInt four = new BigInt(4, new PrecisionSpec(128, PrecisionSpec.BaseType.BIN));\r
 217         /// \r
 218         /// //Pad four to double its usual number of digits (this does not affect the precision)\r
 219         /// four.Pad();\r
 220         /// \r
 221         /// //Create a new, empty integer with matching precision, also padded to twice the usual length\r
 222         /// BigInt newCopy = new BigInt(four, four.Precision, true);</code></example>\r
 223         public BigInt(BigInt inputToCopy, PrecisionSpec precision, bool bCopyLengthOnly)\r
 224         {\r
 225             digitArray = new uint[inputToCopy.digitArray.Length];\r
 226             workingSet = new uint[inputToCopy.digitArray.Length];\r
 227             if (!bCopyLengthOnly) Array.Copy(inputToCopy.digitArray, digitArray, digitArray.Length);\r
 228             sign = inputToCopy.sign;\r
 229             pres = inputToCopy.pres;\r
 230         }\r
 231 \r
 232         /// <summary>\r
 233         /// Constructs a bigint from the string, with the desired precision, using base 10\r
 234         /// </summary>\r
 235         /// <param name="init"></param>\r
 236         /// <param name="precision"></param>\r
 237         public BigInt(string init, PrecisionSpec precision)\r
 238         {\r
 239             InitFromString(init, precision, 10);\r
 240         }\r
 241 \r
 242         /// <summary>\r
 243         /// Constructs a BigInt from a string, using the specified precision and base\r
 244         /// </summary>\r
 245         /// <param name="init"></param>\r
 246         /// <param name="precision"></param>\r
 247         /// <param name="numberBase"></param>\r
 248         public BigInt(string init, PrecisionSpec precision, int numberBase)\r
 249         {\r
 250             InitFromString(init, precision, numberBase);\r
 251         }\r
 252 \r
 253         /// <summary>\r
 254         /// Constructs a bigint from the input.\r
 255         /// </summary>\r
 256         /// <param name="input"></param>\r
 257         public BigInt(BigInt input)\r
 258         {\r
 259             digitArray = new uint[input.digitArray.Length];\r
 260             workingSet = new uint[input.digitArray.Length];\r
 261             Array.Copy(input.digitArray, digitArray, digitArray.Length);\r
 262             sign = input.sign;\r
 263             pres = input.pres;\r
 264         }\r
 265 \r
 266         /// <summary>\r
 267         /// Constructs a bigint from the input, matching the new precision provided\r
 268         /// </summary>\r
 269         public BigInt(BigInt input, PrecisionSpec precision)\r
 270         {\r
 271             //Casts the input to the new precision.\r
 272             Init(precision);\r
 273             int Min = (input.digitArray.Length < digitArray.Length) ? input.digitArray.Length : digitArray.Length;\r
 274 \r
 275             for (int i = 0; i < Min; i++)\r
 276             {\r
 277                 digitArray[i] = input.digitArray[i];\r
 278             }\r
 279 \r
 280             sign = input.sign;\r
 281         }\r
 282 \r
 283         /// <summary>\r
 284         /// Constructs a BigInt from a UInt32\r
 285         /// </summary>\r
 286         /// <param name="input"></param>\r
 287         /// <param name="precision"></param>\r
 288         public BigInt(UInt32 input, PrecisionSpec precision)\r
 289         {\r
 290             Init(precision);\r
 291             digitArray[0] = input;\r
 292         }\r
 293 \r
 294         /// <summary>\r
 295         /// Constructs a BigInt from a UInt64\r
 296         /// </summary>\r
 297         /// <param name="input"></param>\r
 298         /// <param name="precision"></param>\r
 299         public BigInt(UInt64 input, PrecisionSpec precision)\r
 300         {\r
 301             Init(precision);\r
 302             digitArray[0] = (UInt32)(input & 0xffffffff);\r
 303             if (digitArray.Length > 1) digitArray[1] = (UInt32)(input >> 32);\r
 304         }\r
 305 \r
 306         /// <summary>\r
 307         /// Constructs a BigInt from an Int32\r
 308         /// </summary>\r
 309         /// <param name="input"></param>\r
 310         /// <param name="precision"></param>\r
 311         public BigInt(Int32 input, PrecisionSpec precision)\r
 312         {\r
 313             Init(precision);\r
 314             if (input < 0)\r
 315             {\r
 316                 sign = true;\r
 317 \r
 318                 if (input == Int32.MinValue)\r
 319                 {\r
 320                     digitArray[0] = 0x80000000;\r
 321                 }\r
 322                 else\r
 323                 {\r
 324                     digitArray[0] = (UInt32)(-input);\r
 325                 }\r
 326             }\r
 327             else\r
 328             {\r
 329                 digitArray[0] = ((UInt32)input);\r
 330             }\r
 331         }\r
 332 \r
 333         /// <summary>\r
 334         /// Constructs a BigInt from a UInt32\r
 335         /// </summary>\r
 336         /// <param name="input"></param>\r
 337         /// <param name="precision"></param>\r
 338         public BigInt(Int64 input, PrecisionSpec precision)\r
 339         {\r
 340             Init(precision);\r
 341             if (input < 0) sign = true;\r
 342 \r
 343             digitArray[0] = (UInt32)(input & 0xffffffff);\r
 344 \r
 345             if (digitArray.Length >= 2)\r
 346             {\r
 347                 if (input == Int64.MinValue)\r
 348                 {\r
 349                     digitArray[1] = 0x80000000;\r
 350                 }\r
 351                 else\r
 352                 {\r
 353                     digitArray[1] = (UInt32)((input >> 32) & 0x7fffffff);\r
 354                 }\r
 355             }\r
 356         }\r
 357 \r
 358         //***************** Properties *******************\r
 359 \r
 360         /// <summary>\r
 361         /// true iff the number is negative\r
 362         /// </summary>\r
 363         public bool Sign { get { return sign; } set { sign = value; } }\r
 364 \r
 365         /// <summary>\r
 366         /// The precision of the number.\r
 367         /// </summary>\r
 368         public PrecisionSpec Precision { get { return pres; } }\r
 369 \r
 370         //*************** Utility Functions **************\r
 371 \r
 372         /// <summary>\r
 373         /// Casts a BigInt to the new precision provided.\r
 374         /// Note: This will return the input if the precision already matches.\r
 375         /// </summary>\r
 376         /// <param name="input"></param>\r
 377         /// <param name="precision"></param>\r
 378         /// <returns></returns>\r
 379         public static BigInt CastToPrecision(BigInt input, PrecisionSpec precision)\r
 380         {\r
 381             if (input.pres == precision) return input;\r
 382             return new BigInt(input, precision);\r
 383         }\r
 384 \r
 385 \r
 386         //*************** Member Functions ***************\r
 387 \r
 388         /// <summary>\r
 389         /// Addition and assignment - without intermediate memory allocation.\r
 390         /// </summary>\r
 391         /// <param name="n2"></param>\r
 392         /// <returns></returns>\r
 393         public uint Add(BigInt n2)\r
 394         {\r
 395             if (n2.digitArray.Length != digitArray.Length) MakeSafe(ref n2);\r
 396 \r
 397             if (sign == n2.sign)\r
 398             {\r
 399                 return AddInternalBits(n2.digitArray);\r
 400             }\r
 401             else\r
 402             {\r
 403                 bool lessThan = LtInt(this, n2);\r
 404 \r
 405                 if (lessThan)\r
 406                 {\r
 407                     int Length = digitArray.Length;\r
 408 \r
 409                     for (int i = 0; i < Length; i++)\r
 410                     {\r
 411                         workingSet[i] = digitArray[i];\r
 412                         digitArray[i] = n2.digitArray[i];\r
 413                     }\r
 414 \r
 415                     sign = !sign;\r
 416                     return SubInternalBits(workingSet);\r
 417                 }\r
 418                 else\r
 419                 {\r
 420                     return SubInternalBits(n2.digitArray);\r
 421                 }\r
 422             }\r
 423         }\r
 424 \r
 425         /// <summary>\r
 426         /// Subtraction and assignment - without intermediate memory allocation.\r
 427         /// </summary>\r
 428         /// <param name="n2"></param>\r
 429         public uint Sub(BigInt n2)\r
 430         {\r
 431             if (n2.digitArray.Length != digitArray.Length) MakeSafe(ref n2);\r
 432 \r
 433             if (sign != n2.sign)\r
 434             {\r
 435                 return AddInternalBits(n2.digitArray);\r
 436             }\r
 437             else\r
 438             {\r
 439                 bool lessThan = LtInt(this, n2);\r
 440 \r
 441                 if (lessThan)\r
 442                 {\r
 443                     int Length = digitArray.Length;\r
 444 \r
 445                     for (int i = 0; i < Length; i++)\r
 446                     {\r
 447                         workingSet[i] = digitArray[i];\r
 448                         digitArray[i] = n2.digitArray[i];\r
 449                     }\r
 450 \r
 451                     sign = !sign;\r
 452                     return SubInternalBits(workingSet);\r
 453                 }\r
 454                 else\r
 455                 {\r
 456                     return SubInternalBits(n2.digitArray);\r
 457                 }\r
 458             }\r
 459         }\r
 460 \r
 461         /// <summary>\r
 462         /// Multiplication and assignmnet - with minimal intermediate memory allocation.\r
 463         /// </summary>\r
 464         /// <param name="n2"></param>\r
 465         public void Mul(BigInt n2)\r
 466         {\r
 467             if (n2.digitArray.Length != digitArray.Length) MakeSafe(ref n2);\r
 468 \r
 469             int Length = n2.digitArray.Length;\r
 470 \r
 471             //Inner loop zero-mul avoidance\r
 472             int maxDigit = 0;\r
 473             for (int i = Length - 1; i >= 0; i--)\r
 474             {\r
 475                 if (digitArray[i] != 0)\r
 476                 {\r
 477                     maxDigit = i + 1;\r
 478                     break;\r
 479                 }\r
 480             }\r
 481 \r
 482             //Result is zero, 'this' is unchanged\r
 483             if (maxDigit == 0) return;\r
 484 \r
 485             //Temp storage for source (both working sets are used by the calculation)\r
 486             uint[] thisTemp = new uint [Length];\r
 487             for (int i = 0; i < Length; i++)\r
 488             {\r
 489                 thisTemp[i] = digitArray[i];\r
 490                 digitArray[i] = 0;\r
 491             }\r
 492 \r
 493             for (int i = 0; i < Length; i++)\r
 494             {\r
 495                 //Clear the working set\r
 496                 for (int j = 0; j < i; j++)\r
 497                 {\r
 498                     workingSet[j] = 0;\r
 499                     n2.workingSet[j] = 0;\r
 500                 }\r
 501 \r
 502                 n2.workingSet[i] = 0;\r
 503 \r
 504                 ulong digit = n2.digitArray[i];\r
 505                 if (digit == 0) continue;\r
 506 \r
 507                 for (int j = 0; j + i < Length && j < maxDigit; j++)\r
 508                 {\r
 509                     //Multiply n1 by each of the integer digits of n2.\r
 510                     ulong temp = (ulong)thisTemp[j] * digit;\r
 511                     //n1.workingSet stores the low bits of each piecewise multiplication\r
 512                     workingSet[j + i] = (uint)(temp & 0xffffffff);\r
 513                     if (j + i + 1 < Length)\r
 514                     {\r
 515                         //n2.workingSet stores the high bits of each multiplication\r
 516                         n2.workingSet[j + i + 1] = (uint)(temp >> 32);\r
 517                     }\r
 518                 }\r
 519 \r
 520                 AddInternalBits(workingSet);\r
 521                 AddInternalBits(n2.workingSet);\r
 522             }\r
 523 \r
 524             sign = (sign != n2.sign);\r
 525         }\r
 526 \r
 527         /// <summary>\r
 528         /// Squares the number.\r
 529         /// </summary>\r
 530         public void Square()\r
 531         {\r
 532             int Length = digitArray.Length;\r
 533 \r
 534             //Inner loop zero-mul avoidance\r
 535             int maxDigit = 0;\r
 536             for (int i = Length - 1; i >= 0; i--)\r
 537             {\r
 538                 if (digitArray[i] != 0)\r
 539                 {\r
 540                     maxDigit = i + 1;\r
 541                     break;\r
 542                 }\r
 543             }\r
 544 \r
 545             //Result is zero, 'this' is unchanged\r
 546             if (maxDigit == 0) return;\r
 547 \r
 548             //Temp storage for source (both working sets are used by the calculation)\r
 549             uint[] thisTemp = new uint[Length];\r
 550             for (int i = 0; i < Length; i++)\r
 551             {\r
 552                 thisTemp[i] = digitArray[i];\r
 553                 digitArray[i] = 0;\r
 554             }\r
 555 \r
 556             UInt32 [] workingSet2 = new UInt32[Length];\r
 557 \r
 558             for (int i = 0; i < Length; i++)\r
 559             {\r
 560                 //Clear the working set\r
 561                 for (int j = 0; j < i; j++)\r
 562                 {\r
 563                     workingSet[j] = 0;\r
 564                     workingSet2[j] = 0;\r
 565                 }\r
 566 \r
 567                 workingSet2[i] = 0;\r
 568 \r
 569                 ulong digit = thisTemp[i];\r
 570                 if (digit == 0) continue;\r
 571 \r
 572                 for (int j = 0; j + i < Length && j < maxDigit; j++)\r
 573                 {\r
 574                     //Multiply n1 by each of the integer digits of n2.\r
 575                     ulong temp = (ulong)thisTemp[j] * digit;\r
 576                     //n1.workingSet stores the low bits of each piecewise multiplication\r
 577                     workingSet[j + i] = (uint)(temp & 0xffffffff);\r
 578                     if (j + i + 1 < Length)\r
 579                     {\r
 580                         //n2.workingSet stores the high bits of each multiplication\r
 581                         workingSet2[j + i + 1] = (uint)(temp >> 32);\r
 582                     }\r
 583                 }\r
 584 \r
 585                 AddInternalBits(workingSet);\r
 586                 AddInternalBits(workingSet2);\r
 587             }\r
 588 \r
 589             sign = false;\r
 590         }\r
 591 \r
 592         /// <summary>\r
 593         /// Used for floating-point multiplication\r
 594         /// Stores the high bits of the multiplication only (the carry bit from the\r
 595         /// lower bits is missing, so the true answer might be 1 greater).\r
 596         /// </summary>\r
 597         /// <param name="n2"></param>\r
 598         public void MulHi(BigInt n2)\r
 599         {\r
 600             if (n2.digitArray.Length != digitArray.Length) MakeSafe(ref n2);\r
 601 \r
 602             int Length = n2.digitArray.Length;\r
 603 \r
 604             //Inner loop zero-mul avoidance\r
 605             int maxDigit = 0;\r
 606             for (int i = Length - 1; i >= 0; i--)\r
 607             {\r
 608                 if (digitArray[i] != 0)\r
 609                 {\r
 610                     maxDigit = i + 1;\r
 611                     break;\r
 612                 }\r
 613             }\r
 614 \r
 615             //Result is zero, 'this' is unchanged\r
 616             if (maxDigit == 0) return;\r
 617 \r
 618             //Temp storage for source (both working sets are used by the calculation)\r
 619             uint[] thisTemp = new uint[Length];\r
 620             for (int i = 0; i < Length; i++)\r
 621             {\r
 622                 thisTemp[i] = digitArray[i];\r
 623                 digitArray[i] = 0;\r
 624             }\r
 625 \r
 626             for (int i = 0; i < Length; i++)\r
 627             {\r
 628                 //Clear the working set\r
 629                 for (int j = 0; j < Length; j++)\r
 630                 {\r
 631                     workingSet[j] = 0;\r
 632                     n2.workingSet[j] = 0;\r
 633                 }\r
 634 \r
 635                 n2.workingSet[i] = 0;\r
 636 \r
 637                 ulong digit = n2.digitArray[i];\r
 638                 if (digit == 0) continue;\r
 639 \r
 640                 //Only the high bits\r
 641                 if (maxDigit + i < Length - 1) continue;\r
 642 \r
 643                 for (int j = 0; j < maxDigit; j++)\r
 644                 {\r
 645                     if (j + i + 1 < Length) continue;\r
 646                     //Multiply n1 by each of the integer digits of n2.\r
 647                     ulong temp = (ulong)thisTemp[j] * digit;\r
 648                     //n1.workingSet stores the low bits of each piecewise multiplication\r
 649                     if (j + i >= Length)\r
 650                     {\r
 651                         workingSet[j + i - Length] = (uint)(temp & 0xffffffff);\r
 652                     }\r
 653                     \r
 654                     //n2.workingSet stores the high bits of each multiplication\r
 655                     n2.workingSet[j + i + 1 - Length] = (uint)(temp >> 32);\r
 656                 }\r
 657 \r
 658                 AddInternalBits(workingSet);\r
 659                 AddInternalBits(n2.workingSet);\r
 660             }\r
 661 \r
 662             sign = (sign != n2.sign);\r
 663         }\r
 664 \r
 665         /// <summary>\r
 666         /// Floating-point helper function.\r
 667         /// Squares the number and keeps the high bits of the calculation.\r
 668         /// Takes a temporary BigInt as a working set.\r
 669         /// </summary>\r
 670         public void SquareHiFast(BigInt scratch)\r
 671         {\r
 672             int Length = digitArray.Length;\r
 673             uint[] tempDigits = scratch.digitArray;\r
 674             uint[] workingSet2 = scratch.workingSet;\r
 675 \r
 676             //Temp storage for source (both working sets are used by the calculation)\r
 677             for (int i = 0; i < Length; i++)\r
 678             {\r
 679                 tempDigits[i] = digitArray[i];\r
 680                 digitArray[i] = 0;\r
 681             }\r
 682 \r
 683             for (int i = 0; i < Length; i++)\r
 684             {\r
 685                 //Clear the working set\r
 686                 for (int j = i; j < Length; j++)\r
 687                 {\r
 688                     workingSet[j] = 0;\r
 689                     workingSet2[j] = 0;\r
 690                 }\r
 691 \r
 692                 if (i - 1 >= 0) workingSet[i - 1] = 0;\r
 693 \r
 694                 ulong digit = tempDigits[i];\r
 695                 if (digit == 0) continue;\r
 696 \r
 697                 for (int j = 0; j < Length; j++)\r
 698                 {\r
 699                     if (j + i + 1 < Length) continue;\r
 700                     //Multiply n1 by each of the integer digits of n2.\r
 701                     ulong temp = (ulong)tempDigits[j] * digit;\r
 702                     //n1.workingSet stores the low bits of each piecewise multiplication\r
 703                     if (j + i >= Length)\r
 704                     {\r
 705                         workingSet[j + i - Length] = (uint)(temp & 0xffffffff);\r
 706                     }\r
 707 \r
 708                     //n2.workingSet stores the high bits of each multiplication\r
 709                     workingSet2[j + i + 1 - Length] = (uint)(temp >> 32);\r
 710                 }\r
 711 \r
 712                 AddInternalBits(workingSet);\r
 713                 AddInternalBits(workingSet2);\r
 714             }\r
 715 \r
 716             sign = false;\r
 717         }\r
 718 \r
 719         /// <summary>\r
 720         /// This uses the schoolbook division algorithm, as decribed by http://www.treskal.com/kalle/exjobb/original-report.pdf\r
 721         /// Algorithms 3.1 (implemented by Div_31) and 3.2 (implemented by Div_32)\r
 722         /// </summary>\r
 723         /// <param name="n2"></param>\r
 724         public void Div(BigInt n2)\r
 725         {\r
 726             if (n2.digitArray.Length != digitArray.Length) MakeSafe(ref n2);\r
 727 \r
 728             int OldLength = digitArray.Length;\r
 729 \r
 730             //First, we need to prepare the operands for division using Div_32, which requires\r
 731             //That the most significant digit of n2 be set. To do this, we need to shift n2 (and therefore n1) up.\r
 732             //This operation can potentially increase the precision of the operands.\r
 733             int shift = MakeSafeDiv(this, n2);\r
 734 \r
 735             BigInt Q = new BigInt(this, this.pres, true);\r
 736             BigInt R = new BigInt(this, this.pres, true);\r
 737 \r
 738             Div_32(this, n2, Q, R);\r
 739 \r
 740             //Restore n2 to its pre-shift value\r
 741             n2.RSH(shift);\r
 742             AssignInt(Q);\r
 743             sign = (sign != n2.sign);\r
 744 \r
 745             //Reset the lengths of the operands\r
 746             SetNumDigits(OldLength);\r
 747             n2.SetNumDigits(OldLength);\r
 748         }\r
 749 \r
 750         /// <summary>\r
 751         /// This function is used for floating-point division.\r
 752         /// </summary>\r
 753         /// <param name="n2"></param>\r
 754         //Given two numbers:\r
 755         //  In floating point 1 <= a, b < 2, meaning that both numbers have their top bits set.\r
 756         //  To calculate a / b, maintaining precision, we:\r
 757         //    1. Double the number of digits available to both numbers.\r
 758         //    2. set a = a * 2^d (where d is the number of digits)\r
 759         //    3. calculate the quotient a <- q:  2^(d-1) <= q < 2^(d+1)\r
 760         //    4. if a >= 2^d, s = 1, else s = 0\r
 761         //    6. shift a down by s, and undo the precision extension\r
 762         //    7. return 1 - shift (change necessary to exponent)\r
 763         public int DivAndShift(BigInt n2)\r
 764         {\r
 765             if (n2.IsZero()) return -1;\r
 766             if (digitArray.Length != n2.digitArray.Length) MakeSafe(ref n2);\r
 767 \r
 768             int oldLength = digitArray.Length;\r
 769 \r
 770             //Double the number of digits, and shift a into the higher digits.\r
 771             Pad();\r
 772             n2.Extend();\r
 773 \r
 774             //Do the divide (at double precision, ouch!)\r
 775             Div(n2);\r
 776 \r
 777             //Shift down if 'this' >= 2^d\r
 778             int ret = 1;\r
 779 \r
 780             if (digitArray[oldLength] != 0)\r
 781             {\r
 782                 RSH(1);\r
 783                 ret--;\r
 784             }\r
 785 \r
 786             SetNumDigits(oldLength);\r
 787             n2.SetNumDigits(oldLength);\r
 788 \r
 789             return ret;\r
 790         }\r
 791 \r
 792         /// <summary>\r
 793         /// Calculates 'this' mod n2 (using the schoolbook division algorithm as above)\r
 794         /// </summary>\r
 795         /// <param name="n2"></param>\r
 796         public void Mod(BigInt n2)\r
 797         {\r
 798             if (n2.digitArray.Length != digitArray.Length) MakeSafe(ref n2);\r
 799 \r
 800             int OldLength = digitArray.Length;\r
 801 \r
 802             //First, we need to prepare the operands for division using Div_32, which requires\r
 803             //That the most significant digit of n2 be set. To do this, we need to shift n2 (and therefore n1) up.\r
 804             //This operation can potentially increase the precision of the operands.\r
 805             int shift = MakeSafeDiv(this, n2);\r
 806 \r
 807             BigInt Q = new BigInt(this.pres);\r
 808             BigInt R = new BigInt(this.pres);\r
 809 \r
 810             Q.digitArray = new UInt32[this.digitArray.Length];\r
 811             R.digitArray = new UInt32[this.digitArray.Length];\r
 812 \r
 813             Div_32(this, n2, Q, R);\r
 814 \r
 815             //Restore n2 to its pre-shift value\r
 816             n2.RSH(shift);\r
 817             R.RSH(shift);\r
 818             R.sign = (sign != n2.sign);\r
 819             AssignInt(R);\r
 820 \r
 821             //Reset the lengths of the operands\r
 822             SetNumDigits(OldLength);\r
 823             n2.SetNumDigits(OldLength);\r
 824         }\r
 825 \r
 826         /// <summary>\r
 827         /// Logical left shift\r
 828         /// </summary>\r
 829         /// <param name="shift"></param>\r
 830         public void LSH(int shift)\r
 831         {\r
 832             if (shift <= 0) return;\r
 833             int length = digitArray.Length;\r
 834             int digits = shift >> 5;\r
 835             int rem = shift & 31;\r
 836 \r
 837             for (int i = length - 1; i >= digits; i--)\r
 838             {\r
 839                 digitArray[i] = digitArray[i - digits];\r
 840             }\r
 841 \r
 842             if (digits > 0)\r
 843             {\r
 844                 for (int i = digits - 1; i >= 0; i--)\r
 845                 {\r
 846                     digitArray[i] = 0;\r
 847                 }\r
 848             }\r
 849 \r
 850             UInt64 lastShift = 0;\r
 851 \r
 852             for (int i = 0; i < length; i++)\r
 853             {\r
 854                 UInt64 temp = (((UInt64)digitArray[i]) << rem) | lastShift;\r
 855                 digitArray[i] = (UInt32)(temp & 0xffffffff);\r
 856                 lastShift = temp >> 32;\r
 857             }\r
 858         }\r
 859 \r
 860         /// <summary>\r
 861         /// Logical right-shift\r
 862         /// </summary>\r
 863         /// <param name="shift"></param>\r
 864         public void RSH(int shift)\r
 865         {\r
 866             if (shift < 0) return;\r
 867             int length = digitArray.Length;\r
 868             int digits = shift >> 5;\r
 869             int rem = shift & 31;\r
 870 \r
 871             for (int i = 0; i < length - digits; i++)\r
 872             {\r
 873                 digitArray[i] = digitArray[i + digits];\r
 874             }\r
 875 \r
 876             int start = (length - digits);\r
 877             if (start < 0) start = 0;\r
 878 \r
 879             for (int i = start; i < length; i++)\r
 880             {\r
 881                 digitArray[i] = 0;\r
 882             }\r
 883 \r
 884             UInt64 lastShift = 0;\r
 885 \r
 886             for (int i = length - 1; i >= 0; i--)\r
 887             {\r
 888                 UInt64 temp = ((((UInt64)digitArray[i]) << 32) >> rem) | lastShift;\r
 889                 digitArray[i] = (UInt32)(temp >> 32);\r
 890                 lastShift = (temp & 0xffffffff) << 32;\r
 891             }\r
 892         }\r
 893 \r
 894         /// <summary>\r
 895         /// Changes the sign of the number\r
 896         /// </summary>\r
 897         public void Negate()\r
 898         {\r
 899             sign = !sign;\r
 900         }\r
 901 \r
 902         /// <summary>\r
 903         /// Increments the number.\r
 904         /// </summary>\r
 905         public void Increment()\r
 906         {\r
 907             if (sign)\r
 908             {\r
 909                 DecrementInt();\r
 910             }\r
 911             else\r
 912             {\r
 913                 IncrementInt();\r
 914             }\r
 915         }\r
 916 \r
 917         /// <summary>\r
 918         /// Decrements the number.\r
 919         /// </summary>\r
 920         public void Decrement()\r
 921         {\r
 922             if (sign)\r
 923             {\r
 924                 IncrementInt();\r
 925             }\r
 926             else\r
 927             {\r
 928                 DecrementInt();\r
 929             }\r
 930         }\r
 931 \r
 932         /// <summary>\r
 933         /// Calculates the factorial 'this'!\r
 934         /// </summary>\r
 935         public void Factorial()\r
 936         {\r
 937             if (sign) return;\r
 938 \r
 939             //Clamp to a reasonable range.\r
 940             int factToUse = (int)(digitArray[0]);\r
 941             if (factToUse > 65536) factToUse = 65536;\r
 942 \r
 943             Zero();\r
 944             digitArray[0] = 1;\r
 945 \r
 946             for (uint i = 1; i <= factToUse; i++)\r
 947             {\r
 948                 MulInternal(i);\r
 949             }\r
 950         }\r
 951 \r
 952         /// <summary>\r
 953         /// Calculates 'this'^power\r
 954         /// </summary>\r
 955         /// <param name="power"></param>\r
 956         public void Power(BigInt power)\r
 957         {\r
 958             if (power.IsZero() || power.sign)\r
 959             {\r
 960                 Zero();\r
 961                 digitArray[0] = 1;\r
 962                 return;\r
 963             }\r
 964 \r
 965             BigInt pow = new BigInt(power);\r
 966             BigInt temp = new BigInt(this);\r
 967             BigInt powTerm = new BigInt(this);\r
 968 \r
 969             pow.Decrement();\r
 970             for (; !pow.IsZero(); pow.RSH(1))\r
 971             {\r
 972                 if ((pow.digitArray[0] & 1) == 1)\r
 973                 {\r
 974                     temp.Mul(powTerm);\r
 975                 }\r
 976 \r
 977                 powTerm.Square();\r
 978             }\r
 979 \r
 980             Assign(temp);\r
 981         }\r
 982 \r
 983         //***************** Comparison member functions *****************\r
 984 \r
 985         /// <summary>\r
 986         /// returns true if this bigint == 0\r
 987         /// </summary>\r
 988         /// <returns></returns>\r
 989         public bool IsZero()\r
 990         {\r
 991             for (int i = 0; i < digitArray.Length; i++)\r
 992             {\r
 993                 if (digitArray[i] != 0) return false;\r
 994             }\r
 995 \r
 996             return true;\r
 997         }\r
 998 \r
 999         /// <summary>\r
1000         /// true iff n2 (precision adjusted to this) is less than 'this'\r
1001         /// </summary>\r
1002         /// <param name="n2"></param>\r
1003         /// <returns></returns>\r
1004         public bool LessThan(BigInt n2)\r
1005         {\r
1006             if (digitArray.Length != n2.digitArray.Length) MakeSafe(ref n2);\r
1007 \r
1008             if (sign)\r
1009             {\r
1010                 if (!n2.sign) return true;\r
1011                 return GtInt(this, n2);\r
1012             }\r
1013             else\r
1014             {\r
1015                 if (n2.sign) return false;\r
1016                 return LtInt(this, n2);\r
1017             }\r
1018         }\r
1019 \r
1020         /// <summary>\r
1021         /// true iff n2 (precision adjusted to this) is greater than 'this'\r
1022         /// </summary>\r
1023         /// <param name="n2"></param>\r
1024         /// <returns></returns>\r
1025         public bool GreaterThan(BigInt n2)\r
1026         {\r
1027             if (digitArray.Length != n2.digitArray.Length) MakeSafe(ref n2);\r
1028 \r
1029             if (sign)\r
1030             {\r
1031                 if (!n2.sign) return false;\r
1032                 return LtInt(this, n2);\r
1033             }\r
1034             else\r
1035             {\r
1036                 if (n2.sign) return true;\r
1037                 return GtInt(this, n2);\r
1038             }\r
1039         }\r
1040 \r
1041         /// <summary>\r
1042         /// Override of base-class equals\r
1043         /// </summary>\r
1044         /// <param name="obj"></param>\r
1045         /// <returns></returns>\r
1046         public override bool Equals(object obj)\r
1047         {\r
1048             BigInt n2 = ((BigInt)obj);\r
1049             return Equals(n2);\r
1050         }\r
1051 \r
1052         /// <summary>\r
1053         /// Get hash code\r
1054         /// </summary>\r
1055         /// <returns></returns>\r
1056         public override int GetHashCode()\r
1057         {\r
1058             return (Int32)digitArray[0];\r
1059         }\r
1060 \r
1061         /// <summary>\r
1062         /// True iff n2 (precision-adjusted to this) == n1\r
1063         /// </summary>\r
1064         /// <param name="n2"></param>\r
1065         /// <returns></returns>\r
1066         public bool Equals(BigInt n2)\r
1067         {\r
1068             if (IsZero() && n2.IsZero()) return true;\r
1069 \r
1070             if (sign != n2.sign) return false;\r
1071 \r
1072             int Length = digitArray.Length;\r
1073             if (n2.digitArray.Length != Length) MakeSafe(ref n2);\r
1074 \r
1075             for (int i = 0; i < Length; i++)\r
1076             {\r
1077                 if (digitArray[i] != n2.digitArray[i]) return false;\r
1078             }\r
1079 \r
1080             return true;\r
1081         }\r
1082 \r
1083         //******************* Bitwise member functions ********************\r
1084 \r
1085         /// <summary>\r
1086         /// Takes the bitwise complement of the number\r
1087         /// </summary>\r
1088         public void Complement()\r
1089         {\r
1090             int Length = digitArray.Length;\r
1091 \r
1092             for (int i = 0; i < Length; i++)\r
1093             {\r
1094                 digitArray[i] = ~digitArray[i];\r
1095             }\r
1096         }\r
1097 \r
1098         /// <summary>\r
1099         /// Bitwise And\r
1100         /// </summary>\r
1101         /// <param name="n2"></param>\r
1102         public void And(BigInt n2)\r
1103         {\r
1104             int Length = digitArray.Length;\r
1105             if (n2.digitArray.Length != Length) MakeSafe(ref n2);\r
1106 \r
1107             for (int i = 0; i < Length; i++)\r
1108             {\r
1109                 digitArray[i] &= n2.digitArray[i];\r
1110             }\r
1111 \r
1112             sign &= n2.sign;\r
1113         }\r
1114 \r
1115         /// <summary>\r
1116         /// Bitwise Or\r
1117         /// </summary>\r
1118         /// <param name="n2"></param>\r
1119         public void Or(BigInt n2)\r
1120         {\r
1121             int Length = digitArray.Length;\r
1122             if (n2.digitArray.Length != Length) MakeSafe(ref n2);\r
1123 \r
1124             for (int i = 0; i < Length; i++)\r
1125             {\r
1126                 digitArray[i] |= n2.digitArray[i];\r
1127             }\r
1128 \r
1129             sign |= n2.sign;\r
1130         }\r
1131 \r
1132         /// <summary>\r
1133         /// Bitwise Xor\r
1134         /// </summary>\r
1135         /// <param name="n2"></param>\r
1136         public void Xor(BigInt n2)\r
1137         {\r
1138             int Length = digitArray.Length;\r
1139             if (n2.digitArray.Length != Length) MakeSafe(ref n2);\r
1140 \r
1141             for (int i = 0; i < Length; i++)\r
1142             {\r
1143                 digitArray[i] ^= n2.digitArray[i];\r
1144             }\r
1145 \r
1146             sign ^= n2.sign;\r
1147         }\r
1148 \r
1149         //*************** Fast Static Arithmetic Functions *****************\r
1150 \r
1151         /// <summary>\r
1152         /// Adds n1 and n2 and puts result in dest, without intermediate memory allocation\r
1153         /// (unsafe if n1 and n2 disagree in precision, safe even if dest is n1 or n2)\r
1154         /// </summary>\r
1155         /// <param name="dest"></param>\r
1156         /// <param name="n1"></param>\r
1157         /// <param name="n2"></param>\r
1158         public static void AddFast(BigInt dest, BigInt n1, BigInt n2)\r
1159         {\r
1160             //We cast to the highest input precision...\r
1161             if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
1162 \r
1163             //Then we up the output precision if less than the input precision.\r
1164             if (dest.digitArray.Length < n1.digitArray.Length) n1.MakeSafe(ref dest);\r
1165 \r
1166             int Length = n1.digitArray.Length;\r
1167 \r
1168             if (n1.sign == n2.sign)\r
1169             {\r
1170                 //Copies sources into digit array and working set for all cases, to avoid\r
1171                 //problems when dest is n1 or n2\r
1172                 for (int i = 0; i < Length; i++)\r
1173                 {\r
1174                     dest.workingSet[i] = n2.digitArray[i];\r
1175                     dest.digitArray[i] = n1.digitArray[i];\r
1176                 }\r
1177                 dest.AddInternalBits(dest.workingSet);\r
1178                 dest.sign = n1.sign;\r
1179             }\r
1180             else\r
1181             {\r
1182                 bool lessThan = LtInt(n1, n2);\r
1183 \r
1184                 if (lessThan)\r
1185                 {\r
1186                     for (int i = 0; i < Length; i++)\r
1187                     {\r
1188                         dest.workingSet[i] = n1.digitArray[i];\r
1189                         dest.digitArray[i] = n2.digitArray[i];\r
1190                     }\r
1191                     dest.SubInternalBits(dest.workingSet);\r
1192                     dest.sign = !n1.sign;\r
1193                 }\r
1194                 else\r
1195                 {\r
1196                     for (int i = 0; i < Length; i++)\r
1197                     {\r
1198                         dest.workingSet[i] = n2.digitArray[i];\r
1199                         dest.digitArray[i] = n1.digitArray[i];\r
1200                     }\r
1201                     dest.SubInternalBits(dest.workingSet);\r
1202                     dest.sign = n1.sign;\r
1203                 }\r
1204             }\r
1205         }\r
1206 \r
1207         /// <summary>\r
1208         /// Adds n1 and n2 and puts result in dest, without intermediate memory allocation\r
1209         /// (unsafe if n1 and n2 disagree in precision, safe even if dest is n1 or n2)\r
1210         /// </summary>\r
1211         /// <param name="dest"></param>\r
1212         /// <param name="n1"></param>\r
1213         /// <param name="n2"></param>\r
1214         public static void SubFast(BigInt dest, BigInt n1, BigInt n2)\r
1215         {\r
1216             //We cast to the highest input precision...\r
1217             if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
1218 \r
1219             //Then we up the output precision if less than the input precision.\r
1220             if (dest.digitArray.Length < n1.digitArray.Length) n1.MakeSafe(ref dest);\r
1221 \r
1222             int Length = n1.digitArray.Length;\r
1223 \r
1224             if (n1.sign != n2.sign)\r
1225             {\r
1226                 //Copies sources into digit array and working set for all cases, to avoid\r
1227                 //problems when dest is n1 or n2\r
1228                 for (int i = 0; i < Length; i++)\r
1229                 {\r
1230                     dest.workingSet[i] = n2.digitArray[i];\r
1231                     dest.digitArray[i] = n1.digitArray[i];\r
1232                 }\r
1233                 dest.AddInternalBits(dest.workingSet);\r
1234                 dest.sign = n1.sign;\r
1235             }\r
1236             else\r
1237             {\r
1238                 bool lessThan = LtInt(n1, n2);\r
1239 \r
1240                 if (lessThan)\r
1241                 {\r
1242                     for (int i = 0; i < Length; i++)\r
1243                     {\r
1244                         dest.workingSet[i] = n1.digitArray[i];\r
1245                         dest.digitArray[i] = n2.digitArray[i];\r
1246                     }\r
1247                     dest.SubInternalBits(dest.workingSet);\r
1248                     dest.sign = !n1.sign;\r
1249                 }\r
1250                 else\r
1251                 {\r
1252                     for (int i = 0; i < Length; i++)\r
1253                     {\r
1254                         dest.workingSet[i] = n2.digitArray[i];\r
1255                         dest.digitArray[i] = n1.digitArray[i];\r
1256                     }\r
1257                     dest.SubInternalBits(dest.workingSet);\r
1258                     dest.sign = n1.sign;\r
1259                 }\r
1260             }\r
1261         }\r
1262 \r
1263         //*************** Static Arithmetic Functions ***************\r
1264 \r
1265         /// <summary>\r
1266         /// signed addition of 2 numbers.\r
1267         /// </summary>\r
1268         /// <param name="n1"></param>\r
1269         /// <param name="n2"></param>\r
1270         /// <returns></returns>\r
1271         public static BigInt Add(BigInt n1, BigInt n2)\r
1272         {\r
1273             if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
1274             BigInt result; \r
1275 \r
1276             if (n1.sign == n2.sign)\r
1277             {\r
1278                 result = new BigInt(n1);\r
1279                 result.AddInternal(n2);\r
1280                 result.sign = n1.sign;\r
1281             }\r
1282             else\r
1283             {\r
1284                 bool lessThan = LtInt(n1, n2);\r
1285 \r
1286                 if (lessThan)\r
1287                 {\r
1288                     result = new BigInt(n2);\r
1289                     result.SubInternal(n1);\r
1290                     result.sign = !n1.sign;\r
1291                 }\r
1292                 else\r
1293                 {\r
1294                     result = new BigInt(n1);\r
1295                     result.SubInternal(n2);\r
1296                     result.sign = n1.sign;\r
1297                 }\r
1298             }\r
1299 \r
1300             return result;\r
1301         }\r
1302 \r
1303         /// <summary>\r
1304         /// signed subtraction of 2 numbers.\r
1305         /// </summary>\r
1306         /// <param name="n1"></param>\r
1307         /// <param name="n2"></param>\r
1308         /// <returns></returns>\r
1309         public static BigInt Sub(BigInt n1, BigInt n2)\r
1310         {\r
1311             if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
1312             BigInt result;\r
1313 \r
1314             if ((n1.sign && !n2.sign) || (!n1.sign && n2.sign))\r
1315             {\r
1316                 result = new BigInt(n1);\r
1317                 result.AddInternal(n2);\r
1318                 result.sign = n1.sign;\r
1319             }\r
1320             else\r
1321             {\r
1322                 bool lessThan = LtInt(n1, n2);\r
1323 \r
1324                 if (lessThan)\r
1325                 {\r
1326                     result = new BigInt(n2);\r
1327                     result.SubInternal(n1);\r
1328                     result.sign = !n1.sign;\r
1329                 }\r
1330                 else\r
1331                 {\r
1332                     result = new BigInt(n1);\r
1333                     result.SubInternal(n2);\r
1334                     result.sign = n1.sign;\r
1335                 }\r
1336             }\r
1337 \r
1338             return result;\r
1339         }\r
1340 \r
1341         /// <summary>\r
1342         /// Multiplication of two BigInts\r
1343         /// </summary>\r
1344         /// <param name="n1"></param>\r
1345         /// <param name="n2"></param>\r
1346         /// <returns></returns>\r
1347         public static BigInt Mul(BigInt n1, BigInt n2)\r
1348         {\r
1349             if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
1350             \r
1351             BigInt result = new BigInt(n1);\r
1352             result.Mul(n2);\r
1353             return result;\r
1354         }\r
1355 \r
1356         /// <summary>\r
1357         /// True arbitrary precision divide.\r
1358         /// </summary>\r
1359         /// <param name="n1"></param>\r
1360         /// <param name="n2"></param>\r
1361         /// <returns></returns>\r
1362         public static BigInt Div(BigInt n1, BigInt n2)\r
1363         {\r
1364             if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
1365             BigInt res = new BigInt(n1);\r
1366             res.Div(n2);\r
1367             return res;\r
1368         }\r
1369 \r
1370         /// <summary>\r
1371         /// True arbitrary-precision mod operation\r
1372         /// </summary>\r
1373         /// <param name="n1"></param>\r
1374         /// <param name="n2"></param>\r
1375         /// <returns></returns>\r
1376         public static BigInt Mod(BigInt n1, BigInt n2)\r
1377         {\r
1378             if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
1379             BigInt res = new BigInt(n1);\r
1380             res.Mod(n2);\r
1381             return res;\r
1382         }\r
1383 \r
1384         /// <summary>\r
1385         /// Unsigned multiplication of a BigInt by a small number\r
1386         /// </summary>\r
1387         /// <param name="n1"></param>\r
1388         /// <param name="n2"></param>\r
1389         /// <returns></returns>\r
1390         public static BigInt Mul(BigInt n1, uint n2)\r
1391         {\r
1392             BigInt result = new BigInt(n1);\r
1393             result.MulInternal(n2);\r
1394             return result;\r
1395         }\r
1396 \r
1397         /// <summary>\r
1398         /// Division of a BigInt by a small (unsigned) number\r
1399         /// </summary>\r
1400         /// <param name="n1"></param>\r
1401         /// <param name="n2"></param>\r
1402         /// <returns></returns>\r
1403         public static BigInt Div(BigInt n1, uint n2)\r
1404         {\r
1405             BigInt result = new BigInt(n1);\r
1406             result.DivInternal(n2);\r
1407             return result;\r
1408         }\r
1409 \r
1410         /// <summary>\r
1411         /// Division and remainder of a BigInt by a small (unsigned) number\r
1412         /// n1 / n2 = div remainder mod\r
1413         /// </summary>\r
1414         /// <param name="n1">The number to divide (dividend)</param>\r
1415         /// <param name="n2">The number to divide by (divisor)</param>\r
1416         /// <param name="div">The quotient (output parameter)</param>\r
1417         /// <param name="mod">The remainder (output parameter)</param>\r
1418         public static void DivMod(BigInt n1, uint n2, out BigInt div, out BigInt mod)\r
1419         {\r
1420             div = Div(n1, n2);\r
1421             mod = Mul(div, n2);\r
1422             mod = Sub(n1, mod);\r
1423         }\r
1424 \r
1425         //**************** Static Comparison Functions ***************\r
1426 \r
1427         /// <summary>\r
1428         /// true iff n1 is less than n2\r
1429         /// </summary>\r
1430         /// <param name="n1"></param>\r
1431         /// <param name="n2"></param>\r
1432         /// <returns></returns>\r
1433         public static bool LessThan(BigInt n1, BigInt n2)\r
1434         {\r
1435             if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
1436 \r
1437             if (n1.sign)\r
1438             {\r
1439                 if (!n2.sign) return true;\r
1440                 return GtInt(n1, n2);\r
1441             }\r
1442             else\r
1443             {\r
1444                 if (n2.sign) return false;\r
1445                 return LtInt(n1, n2);\r
1446             }\r
1447         }\r
1448 \r
1449         /// <summary>\r
1450         /// true iff n1 is greater than n2\r
1451         /// </summary>\r
1452         /// <param name="n1"></param>\r
1453         /// <param name="n2"></param>\r
1454         /// <returns></returns>\r
1455         public static bool GreaterThan(BigInt n1, BigInt n2)\r
1456         {\r
1457             if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
1458 \r
1459             if (n1.sign)\r
1460             {\r
1461                 if (!n2.sign) return false;\r
1462                 return LtInt(n1, n2);\r
1463             }\r
1464             else\r
1465             {\r
1466                 if (n2.sign) return true;\r
1467                 return GtInt(n1, n2);\r
1468             }\r
1469         }\r
1470 \r
1471         /// <summary>\r
1472         /// true iff n1 == n2\r
1473         /// </summary>\r
1474         /// <param name="n1"></param>\r
1475         /// <param name="n2"></param>\r
1476         /// <returns></returns>\r
1477         public static bool Equals(BigInt n1, BigInt n2)\r
1478         {\r
1479             return n1.Equals(n2);\r
1480         }\r
1481 \r
1482         //***************** Static Bitwise Functions *****************\r
1483 \r
1484         /// <summary>\r
1485         /// Bitwise And\r
1486         /// </summary>\r
1487         /// <param name="n1"></param>\r
1488         /// <param name="n2"></param>\r
1489         /// <returns></returns>\r
1490         public static BigInt And(BigInt n1, BigInt n2)\r
1491         {\r
1492             if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
1493             BigInt res = new BigInt(n1);\r
1494             res.And(n2);\r
1495             return res;\r
1496         }\r
1497 \r
1498         /// <summary>\r
1499         /// Bitwise Or\r
1500         /// </summary>\r
1501         /// <param name="n1"></param>\r
1502         /// <param name="n2"></param>\r
1503         /// <returns></returns>\r
1504         public static BigInt Or(BigInt n1, BigInt n2)\r
1505         {\r
1506             if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
1507             BigInt res = new BigInt(n1);\r
1508             res.Or(n2);\r
1509             return res;\r
1510         }\r
1511 \r
1512         /// <summary>\r
1513         /// Bitwise Xor\r
1514         /// </summary>\r
1515         /// <param name="n1"></param>\r
1516         /// <param name="n2"></param>\r
1517         /// <returns></returns>\r
1518         public static BigInt Xor(BigInt n1, BigInt n2)\r
1519         {\r
1520             if (n1.digitArray.Length != n2.digitArray.Length) MakeSafe(ref n1, ref n2);\r
1521             BigInt res = new BigInt(n1);\r
1522             res.And(n2);\r
1523             return res;\r
1524         }\r
1525 \r
1526         //**************** Static Operator Overloads *****************\r
1527 \r
1528         /// <summary>\r
1529         /// Addition operator\r
1530         /// </summary>\r
1531         public static BigInt operator +(BigInt n1, BigInt n2)\r
1532         {\r
1533             return Add(n1, n2);\r
1534         }\r
1535 \r
1536         /// <summary>\r
1537         /// The subtraction operator\r
1538         /// </summary>\r
1539         public static BigInt operator -(BigInt n1, BigInt n2)\r
1540         {\r
1541             return Sub(n1, n2);\r
1542         }\r
1543 \r
1544         /// <summary>\r
1545         /// The multiplication operator\r
1546         /// </summary>\r
1547         public static BigInt operator *(BigInt n1, BigInt n2)\r
1548         {\r
1549             return Mul(n1, n2);\r
1550         }\r
1551 \r
1552         /// <summary>\r
1553         /// The division operator\r
1554         /// </summary>\r
1555         public static BigInt operator /(BigInt n1, BigInt n2)\r
1556         {\r
1557             return Div(n1, n2);\r
1558         }\r
1559 \r
1560         /// <summary>\r
1561         /// The remainder (mod) operator\r
1562         /// </summary>\r
1563         public static BigInt operator %(BigInt n1, BigInt n2)\r
1564         {\r
1565             return Mod(n1, n2);\r
1566         }\r
1567 \r
1568         /// <summary>\r
1569         /// The left-shift operator\r
1570         /// </summary>\r
1571         public static BigInt operator <<(BigInt n1, int n2)\r
1572         {\r
1573             BigInt res = new BigInt(n1);\r
1574             res.LSH(n2);\r
1575             return res;\r
1576         }\r
1577 \r
1578         /// <summary>\r
1579         /// The right-shift operator\r
1580         /// </summary>\r
1581         public static BigInt operator >>(BigInt n1, int n2)\r
1582         {\r
1583             BigInt res = new BigInt(n1);\r
1584             res.RSH(n2);\r
1585             return res;\r
1586         }\r
1587 \r
1588         /// <summary>\r
1589         /// The less than operator\r
1590         /// </summary>\r
1591         public static bool operator <(BigInt n1, BigInt n2)\r
1592         {\r
1593             return LessThan(n1, n2);\r
1594         }\r
1595 \r
1596         /// <summary>\r
1597         /// The greater than operator\r
1598         /// </summary>\r
1599         public static bool operator >(BigInt n1, BigInt n2)\r
1600         {\r
1601             return GreaterThan(n1, n2);\r
1602         }\r
1603 \r
1604         /// <summary>\r
1605         /// The less than or equal to operator\r
1606         /// </summary>\r
1607         public static bool operator <=(BigInt n1, BigInt n2)\r
1608         {\r
1609             return !GreaterThan(n1, n2);\r
1610         }\r
1611 \r
1612         /// <summary>\r
1613         /// The greater than or equal to operator\r
1614         /// </summary>\r
1615         public static bool operator >=(BigInt n1, BigInt n2)\r
1616         {\r
1617             return !LessThan(n1, n2);\r
1618         }\r
1619 \r
1620         /// <summary>\r
1621         /// The equality operator\r
1622         /// </summary>\r
1623         public static bool operator ==(BigInt n1, BigInt n2)\r
1624         {\r
1625             return Equals(n1, n2);\r
1626         }\r
1627 \r
1628         /// <summary>\r
1629         /// The inequality operator\r
1630         /// </summary>\r
1631         public static bool operator !=(BigInt n1, BigInt n2)\r
1632         {\r
1633             return !Equals(n1, n2);\r
1634         }\r
1635 \r
1636         /// <summary>\r
1637         /// The bitwise AND operator\r
1638         /// </summary>\r
1639         public static BigInt operator &(BigInt n1, BigInt n2)\r
1640         {\r
1641             return And(n1, n2);\r
1642         }\r
1643 \r
1644         /// <summary>\r
1645         /// The bitwise OR operator\r
1646         /// </summary>\r
1647         public static BigInt operator |(BigInt n1, BigInt n2)\r
1648         {\r
1649             return Or(n1, n2);\r
1650         }\r
1651 \r
1652         /// <summary>\r
1653         /// The bitwise eXclusive OR operator\r
1654         /// </summary>\r
1655         public static BigInt operator ^(BigInt n1, BigInt n2)\r
1656         {\r
1657             return Xor(n1, n2);\r
1658         }\r
1659 \r
1660         /// <summary>\r
1661         /// The increment operator\r
1662         /// </summary>\r
1663         public static BigInt operator ++(BigInt n1)\r
1664         {\r
1665             n1.Increment();\r
1666             return n1;\r
1667         }\r
1668 \r
1669         /// <summary>\r
1670         /// The decrement operator\r
1671         /// </summary>\r
1672         public static BigInt operator --(BigInt n1)\r
1673         {\r
1674             n1.Decrement();\r
1675             return n1;\r
1676         }\r
1677 \r
1678         //**************** Private Member Functions *****************\r
1679 \r
1680         /// <summary>\r
1681         /// Unsigned multiplication and assignment by a small number\r
1682         /// </summary>\r
1683         /// <param name="n2"></param>\r
1684         private void MulInternal(uint n2)\r
1685         {\r
1686             int Length = digitArray.Length;\r
1687             ulong n2long = (ulong)n2;\r
1688 \r
1689             for (int i = 0; i < Length; i++)\r
1690             {\r
1691                 workingSet[i] = 0;\r
1692             }\r
1693 \r
1694             for (int i = 0; i < Length; i++)\r
1695             {\r
1696                 if (digitArray[i] == 0) continue;\r
1697                 ulong temp = (ulong)digitArray[i] * n2long;\r
1698                 digitArray[i] = (uint)(temp & 0xffffffff);\r
1699                 if (i + 1 < Length) workingSet[i + 1] = (uint)(temp >> 32);\r
1700             }\r
1701 \r
1702             AddInternalBits(workingSet);\r
1703         }\r
1704 \r
1705         /// <summary>\r
1706         /// Unsigned division and assignment by a small number\r
1707         /// </summary>\r
1708         /// <param name="n2"></param>\r
1709         private void DivInternal(uint n2)\r
1710         {\r
1711             int Length = digitArray.Length;\r
1712             ulong carry = 0;\r
1713 \r
1714             //Divide each digit by the small number.\r
1715             for (int i = Length - 1; i >= 0; i--)\r
1716             {\r
1717                 ulong temp = (ulong)digitArray[i] + (carry << 32);\r
1718                 digitArray[i] = (uint)(temp / (ulong)n2);\r
1719                 carry = temp % (ulong)n2;\r
1720             }\r
1721         }\r
1722 \r
1723         /// <summary>\r
1724         /// Adds a signed integer to the number.\r
1725         /// </summary>\r
1726         /// <param name="n1"></param>\r
1727         private void AddInternal(int n1)\r
1728         {\r
1729             if (n1 < 0)\r
1730             {\r
1731                 SubInternal(-n1);\r
1732                 return;\r
1733             }\r
1734 \r
1735             uint carry = 0;\r
1736             int length = digitArray.Length;\r
1737 \r
1738             for (int i = 0; i < length && !(n1 == 0 && carry == 0); i++)\r
1739             {\r
1740                 uint temp = digitArray[i];\r
1741                 digitArray[i] += (uint)n1 + carry;\r
1742 \r
1743                 carry = (digitArray[i] <= temp) ? 1u: 0u;\r
1744                 \r
1745                 n1 = 0;\r
1746             }\r
1747         }\r
1748 \r
1749         /// <summary>\r
1750         /// Subtract a signed integer from the number.\r
1751         /// This is internal because it will fail spectacularly if this number is negative or if n1 is bigger than this number.\r
1752         /// </summary>\r
1753         /// <param name="n1"></param>\r
1754         private void SubInternal(int n1)\r
1755         {\r
1756             if (n1 < 0)\r
1757             {\r
1758                 AddInternal(-n1);\r
1759                 return;\r
1760             }\r
1761 \r
1762             uint carry = 0;\r
1763             int length = digitArray.Length;\r
1764 \r
1765             for (int i = 0; i < length && !(n1 == 0 && carry == 0); i++)\r
1766             {\r
1767                 uint temp = digitArray[i];\r
1768                 digitArray[i] -= ((uint)n1 + carry);\r
1769 \r
1770                 carry = (digitArray[i] >= temp) ? 1u: 0u;\r
1771 \r
1772                 n1 = 0;\r
1773             }\r
1774         }\r
1775 \r
1776         /// <summary>\r
1777         /// Adds a signed integer to the number.\r
1778         /// </summary>\r
1779         /// <param name="n1"></param>\r
1780         private bool AddInternal(uint n1)\r
1781         {\r
1782             uint carry = 0;\r
1783             int length = digitArray.Length;\r
1784 \r
1785             for (int i = 0; i < length && !(n1 == 0 && carry == 0); i++)\r
1786             {\r
1787                 uint temp = digitArray[i];\r
1788                 digitArray[i] += n1 + carry;\r
1789 \r
1790                 carry = (digitArray[i] <= temp) ? 1u: 0u;\r
1791 \r
1792                 n1 = 0;\r
1793             }\r
1794 \r
1795             return (carry != 0);\r
1796         }\r
1797 \r
1798         /// <summary>\r
1799         /// Internally subtracts a uint from the number (sign insensitive)\r
1800         /// </summary>\r
1801         /// <param name="n1"></param>\r
1802         /// <returns></returns>\r
1803         private bool SubInternal(uint n1)\r
1804         {\r
1805             uint carry = 0;\r
1806             int length = digitArray.Length;\r
1807 \r
1808             for (int i = 0; i < length && !(n1 == 0 && carry == 0); i++)\r
1809             {\r
1810                 uint temp = digitArray[i];\r
1811                 digitArray[i] -= (n1 + carry);\r
1812 \r
1813                 carry = (digitArray[i] >= temp) ? 1u: 0u;\r
1814 \r
1815                 n1 = 0;\r
1816             }\r
1817 \r
1818             return (carry != 0);\r
1819         }\r
1820 \r
1821         /// <summary>\r
1822         /// Internal increment function (sign insensitive)\r
1823         /// </summary>\r
1824         private bool IncrementInt()\r
1825         {\r
1826             uint carry = 1;\r
1827 \r
1828             int length = digitArray.Length;\r
1829 \r
1830             for (int i = 0; i < length && carry != 0; i++)\r
1831             {\r
1832                 uint temp = digitArray[i];\r
1833                 digitArray[i]++;\r
1834 \r
1835                 if (digitArray[i] > temp) carry = 0;\r
1836             }\r
1837 \r
1838             return (carry != 0);\r
1839         }\r
1840 \r
1841         /// <summary>\r
1842         /// Internal increment function (sign insensitive)\r
1843         /// </summary>\r
1844         private bool DecrementInt()\r
1845         {\r
1846             uint carry = 1;\r
1847 \r
1848             int length = digitArray.Length;\r
1849 \r
1850             for (int i = 0; i < length && carry != 0; i++)\r
1851             {\r
1852                 uint temp = digitArray[i];\r
1853                 digitArray[i]--;\r
1854 \r
1855                 if (digitArray[i] < temp) carry = 0;\r
1856             }\r
1857 \r
1858             return (carry != 0);\r
1859         }\r
1860 \r
1861         /// <summary>\r
1862         /// Used to add a digit array to a big int.\r
1863         /// </summary>\r
1864         /// <param name="digitsToAdd"></param>\r
1865         private uint AddInternalBits(uint[] digitsToAdd)\r
1866         {\r
1867             uint carry = 0;\r
1868 \r
1869             int Length = digitArray.Length;\r
1870 \r
1871             for (int i = 0; i < Length; i++)\r
1872             {\r
1873                 //Necessary because otherwise the carry calculation could go bad.\r
1874                 if (digitsToAdd[i] == 0 && carry == 0) continue;\r
1875 \r
1876                 uint temp = digitArray[i];\r
1877                 digitArray[i] += (digitsToAdd[i] + carry);\r
1878 \r
1879                 carry = 0;\r
1880                 if (digitArray[i] <= temp) carry = 1;\r
1881             }\r
1882 \r
1883             return carry;\r
1884         }\r
1885 \r
1886         /// <summary>\r
1887         /// Used to add with matching signs (true addition of the digit arrays)\r
1888         /// This is internal because it will fail spectacularly if n1 is negative.\r
1889         /// </summary>\r
1890         /// <param name="n1"></param>\r
1891         private uint AddInternal(BigInt n1)\r
1892         {\r
1893             return AddInternalBits(n1.digitArray);\r
1894         }\r
1895 \r
1896         private uint SubInternalBits(uint[] digitsToAdd)\r
1897         {\r
1898             uint carry = 0;\r
1899 \r
1900             int Length = digitArray.Length;\r
1901 \r
1902             for (int i = 0; i < Length; i++)\r
1903             {\r
1904                 //Necessary because otherwise the carry calculation could go bad.\r
1905                 if (digitsToAdd[i] == 0 && carry == 0) continue;\r
1906 \r
1907                 uint temp = digitArray[i];\r
1908                 digitArray[i] -= (digitsToAdd[i] + carry);\r
1909 \r
1910                 carry = 0;\r
1911                 if (digitArray[i] >= temp) carry = 1;\r
1912             }\r
1913 \r
1914             return carry;\r
1915         }\r
1916 \r
1917         /// <summary>\r
1918         /// Used to subtract n1 (true subtraction of digit arrays) - n1 must be less than or equal to this number\r
1919         /// </summary>\r
1920         /// <param name="n1"></param>\r
1921         private uint SubInternal(BigInt n1)\r
1922         {\r
1923             return SubInternalBits(n1.digitArray);\r
1924         }\r
1925 \r
1926         /// <summary>\r
1927         /// Returns the length of the BigInt in 32-bit words for a given decimal precision\r
1928         /// </summary>\r
1929         /// <param name="precision"></param>\r
1930         /// <returns></returns>\r
1931         private static int GetRequiredDigitsForPrecision(PrecisionSpec precision)\r
1932         {\r
1933             int bits = precision.NumBits;\r
1934             return ((bits - 1) >> 5) + 1;\r
1935         }\r
1936 \r
1937         /// <summary>\r
1938         /// Initialises the BigInt to a desired decimal precision\r
1939         /// </summary>\r
1940         /// <param name="precision"></param>\r
1941         private void Init(PrecisionSpec precision)\r
1942         {\r
1943             int numDigits = GetRequiredDigitsForPrecision(precision);\r
1944             digitArray = new uint[numDigits];\r
1945             workingSet = new uint[numDigits];\r
1946             pres = precision;\r
1947         }\r
1948 \r
1949         /// <summary>\r
1950         /// Initialises the BigInt from a string, given a base and precision\r
1951         /// </summary>\r
1952         /// <param name="init"></param>\r
1953         /// <param name="precision"></param>\r
1954         /// <param name="numberBase"></param>\r
1955         private void InitFromString(string init, PrecisionSpec precision, int numberBase)\r
1956         {\r
1957             PrecisionSpec test;\r
1958             if (numberBase == 2)\r
1959             {\r
1960                 test = new PrecisionSpec(init.Length, PrecisionSpec.BaseType.BIN);\r
1961             }\r
1962             else if (numberBase == 8)\r
1963             {\r
1964                 test = new PrecisionSpec(init.Length, PrecisionSpec.BaseType.OCT);\r
1965             }\r
1966             else if (numberBase == 10)\r
1967             {\r
1968                 test = new PrecisionSpec(init.Length, PrecisionSpec.BaseType.DEC);\r
1969             }\r
1970             else if (numberBase == 16)\r
1971             {\r
1972                 test = new PrecisionSpec(init.Length, PrecisionSpec.BaseType.HEX);\r
1973             }\r
1974             else\r
1975             {\r
1976                 throw new ArgumentOutOfRangeException();\r
1977             }\r
1978 \r
1979             //if (test.NumBits > precision.NumBits) precision = test;\r
1980             Init(precision);\r
1981             FromStringInt(init, numberBase);\r
1982         }\r
1983 \r
1984         //************ Helper Functions for floating point *************\r
1985 \r
1986         /// <summary>\r
1987         /// Returns true if only the top bit is set: i.e. if the floating-point number is a power of 2\r
1988         /// </summary>\r
1989         /// <returns></returns>\r
1990         public bool IsTopBitOnlyBit()\r
1991         {\r
1992             int length = digitArray.Length;\r
1993 \r
1994             if (digitArray[length - 1] != 0x80000000u) return false;\r
1995             length--;\r
1996             for (int i = 0; i < length; i++)\r
1997             {\r
1998                 if (digitArray[i] != 0) return false;\r
1999             }\r
2000 \r
2001             return true;\r
2002         }\r
2003 \r
2004         /// <summary>\r
2005         /// Zeroes the n most significant bits of the number\r
2006         /// </summary>\r
2007         /// <param name="bits"></param>\r
2008         public void ZeroBitsHigh(int bits)\r
2009         {\r
2010             //Already done.\r
2011             if (bits <= 0) return;\r
2012 \r
2013             int length = digitArray.Length;\r
2014 \r
2015             //The entire digit array.\r
2016             if ((bits >> 5) > length)\r
2017             {\r
2018                 bits = length << 5;\r
2019             }\r
2020 \r
2021             int remBits = (bits & 31);\r
2022             int startDigit = length - ((bits >> 5) + 1);\r
2023 \r
2024             if (remBits != 0)\r
2025             {\r
2026                 digitArray[startDigit] = digitArray[startDigit] & (0xffffffffu >> remBits);\r
2027             }\r
2028 \r
2029             for (int i = startDigit + 1; i < length; i++)\r
2030             {\r
2031                 digitArray[i] = 0;\r
2032             }\r
2033         }\r
2034 \r
2035         /// <summary>\r
2036         /// Zeroes the least-significant n bits.\r
2037         /// </summary>\r
2038         /// <param name="bits"></param>\r
2039         public void ZeroBits(int bits)\r
2040         {\r
2041             //Already done.\r
2042             if (bits <= 0) return;\r
2043 \r
2044             //The entire digit array.\r
2045             if ((bits >> 5) > digitArray.Length)\r
2046             {\r
2047                 bits = digitArray.Length << 5;\r
2048             }\r
2049 \r
2050             int remBits = (bits & 31);\r
2051             int startDigit = bits >> 5;\r
2052             \r
2053             if (remBits != 0)\r
2054             {\r
2055                 UInt32 startMask = 0xffffffffu & ~(UInt32)(((1 << remBits) - 1));\r
2056                 digitArray[startDigit] = digitArray[startDigit] & startMask;\r
2057             }\r
2058 \r
2059             for (int i = startDigit - 1; i >= 0; i--)\r
2060             {\r
2061                 digitArray[i] = 0;\r
2062             }\r
2063         }\r
2064 \r
2065         /// <summary>\r
2066         /// Sets the number to 0\r
2067         /// </summary>\r
2068         public void Zero()\r
2069         {\r
2070             int length = digitArray.Length;\r
2071 \r
2072             for (int i = 0; i < length; i++)\r
2073             {\r
2074                 digitArray[i] = 0;\r
2075             }\r
2076         }\r
2077 \r
2078         /// <summary>\r
2079         /// Rounds off the least significant bits of the number.\r
2080         /// Can only round off up to 31 bits.\r
2081         /// </summary>\r
2082         /// <param name="bits">number of bits to round</param>\r
2083         /// <returns></returns>\r
2084         public bool Round(int bits)\r
2085         {\r
2086             //Always less than 32 bits, please!\r
2087             if (bits < 32)\r
2088             {\r
2089                 uint pow2 = 1u << bits;\r
2090                 uint test = digitArray[0] & (pow2 >> 1);\r
2091 \r
2092                 //Zero the lower bits\r
2093                 digitArray[0] = digitArray[0] & ~(pow2 - 1);\r
2094 \r
2095                 if (test != 0)\r
2096                 {\r
2097                     bool bRet = AddInternal(pow2);\r
2098                     digitArray[digitArray.Length - 1] = digitArray[digitArray.Length - 1] | 0x80000000;\r
2099                     return bRet;\r
2100                 }\r
2101             }\r
2102 \r
2103             return false;\r
2104         }\r
2105 \r
2106         /// <summary>\r
2107         /// Used for casting between BigFloats of different precisions - this assumes\r
2108         /// that the number is a normalised mantissa.\r
2109         /// </summary>\r
2110         /// <param name="n2"></param>\r
2111         /// <returns>true if a round-up caused the high bits to become zero</returns>\r
2112         public bool AssignHigh(BigInt n2)\r
2113         {\r
2114             int length = digitArray.Length;\r
2115             int length2 = n2.digitArray.Length;\r
2116             int minWords = (length < length2) ? length: length2;\r
2117             bool bRet = false;\r
2118 \r
2119             for (int i = 1; i <= minWords; i++)\r
2120             {\r
2121                 digitArray[length - i] = n2.digitArray[length2 - i];\r
2122             }\r
2123 \r
2124             if (length2 > length && n2.digitArray[length2 - (length + 1)] >= 0x80000000)\r
2125             {\r
2126                 bRet = IncrementInt();\r
2127 \r
2128                 //Because we are assuming normalisation, we set the top bit (it will already be set if\r
2129                 //bRet is false.\r
2130                 digitArray[length - 1] = digitArray[length - 1] | 0x80000000;\r
2131             }\r
2132 \r
2133             sign = n2.sign;\r
2134 \r
2135             return bRet;\r
2136         }\r
2137 \r
2138         /// <summary>\r
2139         /// Used for casting between long ints or doubles and floating-point numbers\r
2140         /// </summary>\r
2141         /// <param name="digits"></param>\r
2142         public void SetHighDigits(Int64 digits)\r
2143         {\r
2144             digitArray[digitArray.Length - 1] = (uint)(digits >> 32);\r
2145             if (digitArray.Length > 1) digitArray[digitArray.Length - 2] = (uint)(digits & 0xffffffff);\r
2146         }\r
2147 \r
2148         /// <summary>\r
2149         /// Used for casting between ints and doubles or floats.\r
2150         /// </summary>\r
2151         /// <param name="digit"></param>\r
2152         public void SetHighDigit(UInt32 digit)\r
2153         {\r
2154             digitArray[digitArray.Length - 1] = digit;\r
2155         }\r
2156 \r
2157         /// <summary>\r
2158         /// Helper function for floating-point - extends the number to twice the precision\r
2159         /// and shifts the digits into the upper bits.\r
2160         /// </summary>\r
2161         public void Pad()\r
2162         {\r
2163             int length = digitArray.Length;\r
2164             int digits = length << 1;\r
2165 \r
2166             UInt32[] newDigitArray = new UInt32[digits];\r
2167             workingSet = new UInt32[digits];\r
2168 \r
2169             for (int i = 0; i < length; i++)\r
2170             {\r
2171                 newDigitArray[i + length] = digitArray[i];\r
2172             }\r
2173 \r
2174             digitArray = newDigitArray;\r
2175         }\r
2176 \r
2177         /// <summary>\r
2178         /// Helper function for floating-point - extends the number to twice the precision...\r
2179         /// This is a necessary step in floating-point division.\r
2180         /// </summary>\r
2181         public void Extend()\r
2182         {\r
2183             SetNumDigits(digitArray.Length * 2);\r
2184         }\r
2185 \r
2186         /// <summary>\r
2187         /// Gets the highest big of the integer (used for floating point stuff)\r
2188         /// </summary>\r
2189         /// <returns></returns>\r
2190         public uint GetTopBit()\r
2191         {\r
2192             return (digitArray[digitArray.Length - 1] >> 31);\r
2193         }\r
2194 \r
2195         /// <summary>\r
2196         /// Used for floating point multiplication, this shifts the number so that\r
2197         /// the highest bit is set, and returns the number of places shifted.\r
2198         /// </summary>\r
2199         /// <returns></returns>\r
2200         public int Normalise()\r
2201         {\r
2202             if (IsZero()) return 0;\r
2203 \r
2204             int MSD = GetMSD();\r
2205             int digitShift = (digitArray.Length - (MSD + 1));\r
2206             int bitShift = (31 - GetMSB(digitArray[MSD])) + (digitShift << 5);\r
2207             LSH(bitShift);\r
2208             return bitShift;\r
2209         }\r
2210 \r
2211         /// <summary>\r
2212         /// Gets the most significant bit\r
2213         /// </summary>\r
2214         /// <param name="value">the input to search for the MSB in</param>\r
2215         /// <returns>-1 if the input was zero, the position of the MSB otherwise</returns>\r
2216         public static int GetMSB(UInt32 value)\r
2217         {\r
2218             if (value == 0) return -1;\r
2219 \r
2220             uint mask1 = 0xffff0000;\r
2221             uint mask2 = 0xff00;\r
2222             uint mask3 = 0xf0;\r
2223             uint mask4 = 0xc;   //1100 in binary\r
2224             uint mask5 = 0x2;   //10 in binary\r
2225 \r
2226             int iPos = 0;\r
2227 \r
2228             //Unrolled binary search for the most significant bit.\r
2229             if ((value & mask1) != 0) iPos += 16;\r
2230             mask2 <<= iPos;\r
2231 \r
2232             if ((value & mask2) != 0) iPos += 8;\r
2233             mask3 <<= iPos;\r
2234 \r
2235             if ((value & mask3) != 0) iPos += 4;\r
2236             mask4 <<= iPos;\r
2237 \r
2238             if ((value & mask4) != 0) iPos += 2;\r
2239             mask5 <<= iPos;\r
2240 \r
2241             if ((value & mask5) != 0) iPos++;\r
2242 \r
2243             return iPos;\r
2244         }\r
2245 \r
2246         /// <summary>\r
2247         /// Gets the most significant bit\r
2248         /// </summary>\r
2249         /// <param name="value">the input to search for the MSB in</param>\r
2250         /// <returns>-1 if the input was zero, the position of the MSB otherwise</returns>\r
2251         public static int GetMSB(UInt64 value)\r
2252         {\r
2253             if (value == 0) return -1;\r
2254 \r
2255             UInt64 mask0 = 0xffffffff00000000ul;\r
2256             UInt64 mask1 = 0xffff0000;\r
2257             UInt64 mask2 = 0xff00;\r
2258             UInt64 mask3 = 0xf0;\r
2259             UInt64 mask4 = 0xc;   //1100 in binary\r
2260             UInt64 mask5 = 0x2;   //10 in binary\r
2261 \r
2262             int iPos = 0;\r
2263 \r
2264             //Unrolled binary search for the most significant bit.\r
2265             if ((value & mask0) != 0) iPos += 32;\r
2266             mask1 <<= iPos;\r
2267 \r
2268             if ((value & mask1) != 0) iPos += 16;\r
2269             mask2 <<= iPos;\r
2270 \r
2271             if ((value & mask2) != 0) iPos += 8;\r
2272             mask3 <<= iPos;\r
2273 \r
2274             if ((value & mask3) != 0) iPos += 4;\r
2275             mask4 <<= iPos;\r
2276 \r
2277             if ((value & mask4) != 0) iPos += 2;\r
2278             mask5 <<= iPos;\r
2279 \r
2280             if ((value & mask5) != 0) iPos++;\r
2281 \r
2282             return iPos;\r
2283         }\r
2284 \r
2285         /// <summary>\r
2286         /// Gets the most significant bit\r
2287         /// </summary>\r
2288         /// <param name="value">the input to search for the MSB in</param>\r
2289         /// <returns>-1 if the input was zero, the position of the MSB otherwise</returns>\r
2290         public static int GetMSB(BigInt value)\r
2291         {\r
2292             int digit = value.GetMSD();\r
2293             int bit = GetMSB(value.digitArray[digit]);\r
2294             return (digit << 5) + bit;\r
2295         }\r
2296 \r
2297         //**************** Helper Functions for Div ********************\r
2298 \r
2299         /// <summary>\r
2300         /// Gets the index of the most significant digit\r
2301         /// </summary>\r
2302         /// <returns></returns>\r
2303         private int GetMSD()\r
2304         {\r
2305             for (int i = digitArray.Length - 1; i >= 0; i--)\r
2306             {\r
2307                 if (digitArray[i] != 0) return i;\r
2308             }\r
2309 \r
2310             return 0;\r
2311         }\r
2312 \r
2313         /// <summary>\r
2314         /// Gets the required bitshift for the Div_32 algorithm\r
2315         /// </summary>\r
2316         /// <returns></returns>\r
2317         private int GetDivBitshift()\r
2318         {\r
2319             uint digit = digitArray[GetMSD()];\r
2320             uint mask1 = 0xffff0000;\r
2321             uint mask2 = 0xff00;\r
2322             uint mask3 = 0xf0;  \r
2323             uint mask4 = 0xc;   //1100 in binary\r
2324             uint mask5 = 0x2;   //10 in binary\r
2325 \r
2326             int iPos = 0;\r
2327 \r
2328             //Unrolled binary search for the most significant bit.\r
2329             if ((digit & mask1) != 0) iPos += 16;\r
2330             mask2 <<= iPos;\r
2331 \r
2332             if ((digit & mask2) != 0) iPos += 8;\r
2333             mask3 <<= iPos;\r
2334             \r
2335             if ((digit & mask3) != 0) iPos += 4;\r
2336             mask4 <<= iPos;\r
2337 \r
2338             if ((digit & mask4) != 0) iPos += 2;\r
2339             mask5 <<= iPos;\r
2340 \r
2341             if ((digit & mask5) != 0) return 30 - iPos;\r
2342 \r
2343             return 31 - iPos;\r
2344         }\r
2345 \r
2346         /// <summary>\r
2347         /// Shifts and optionally precision-extends the arguments to prepare for Div_32\r
2348         /// </summary>\r
2349         /// <param name="n1"></param>\r
2350         /// <param name="n2"></param>\r
2351         private static int MakeSafeDiv(BigInt n1, BigInt n2)\r
2352         {\r
2353             int shift = n2.GetDivBitshift();\r
2354             int n1MSD = n1.GetMSD();\r
2355 \r
2356             uint temp = n1.digitArray[n1MSD];\r
2357             if (n1MSD == n1.digitArray.Length - 1 && ((temp << shift) >> shift) != n1.digitArray[n1MSD])\r
2358             {\r
2359                 //Precision-extend n1 and n2 if necessary\r
2360                 int digits = n1.digitArray.Length;\r
2361                 n1.SetNumDigits(digits + 1);\r
2362                 n2.SetNumDigits(digits + 1);\r
2363             }\r
2364 \r
2365             //Logical left-shift n1 and n2\r
2366             n1.LSH(shift);\r
2367             n2.LSH(shift);\r
2368 \r
2369             return shift;\r
2370         }\r
2371 \r
2372         /// <summary>\r
2373         /// Schoolbook division helper function.\r
2374         /// </summary>\r
2375         /// <param name="n1"></param>\r
2376         /// <param name="n2"></param>\r
2377         /// <param name="Q">Quotient output value</param>\r
2378         /// <param name="R">Remainder output value</param>\r
2379         private static void Div_31(BigInt n1, BigInt n2, BigInt Q, BigInt R)\r
2380         {\r
2381             int digitsN1 = n1.GetMSD() + 1;\r
2382             int digitsN2 = n2.GetMSD() + 1;            \r
2383 \r
2384             if ((digitsN1 > digitsN2))\r
2385             {\r
2386                 BigInt n1New = new BigInt(n2);\r
2387                 n1New.DigitShiftSelfLeft(1);\r
2388 \r
2389                 //If n1 >= n2 * 2^32\r
2390                 if (!LtInt(n1, n1New))\r
2391                 {\r
2392                     n1New.sign = n1.sign;\r
2393                     SubFast(n1New, n1, n1New);\r
2394 \r
2395                     Div_32(n1New, n2, Q, R);\r
2396 \r
2397                     //Q = (A - B*2^32)/B + 2^32\r
2398                     Q.Add2Pow32Self();\r
2399                     return;\r
2400                 }\r
2401             }\r
2402 \r
2403             UInt32 q = 0;\r
2404 \r
2405             if (digitsN1 >= 2)\r
2406             {\r
2407                 UInt64 q64 = ((((UInt64)n1.digitArray[digitsN1 - 1]) << 32) + n1.digitArray[digitsN1 - 2]) / (UInt64)n2.digitArray[digitsN2 - 1];\r
2408 \r
2409                 if (q64 > 0xfffffffful)\r
2410                 {\r
2411                     q = 0xffffffff;\r
2412                 }\r
2413                 else\r
2414                 {\r
2415                     q = (UInt32)q64;\r
2416                 }\r
2417             }\r
2418 \r
2419             BigInt temp = Mul(n2, q);\r
2420 \r
2421             if (GtInt(temp, n1))\r
2422             {\r
2423                 temp.SubInternalBits(n2.digitArray);\r
2424                 q--;\r
2425 \r
2426                 if (GtInt(temp, n1))\r
2427                 {\r
2428                     temp.SubInternalBits(n2.digitArray);\r
2429                     q--;\r
2430                 }\r
2431             }\r
2432 \r
2433             Q.Zero();\r
2434             Q.digitArray[0] = q;\r
2435             R.Assign(n1);\r
2436             R.SubInternalBits(temp.digitArray);\r
2437         }\r
2438 \r
2439         /// <summary>\r
2440         /// Schoolbook division algorithm\r
2441         /// </summary>\r
2442         /// <param name="n1"></param>\r
2443         /// <param name="n2"></param>\r
2444         /// <param name="Q"></param>\r
2445         /// <param name="R"></param>\r
2446         private static void Div_32(BigInt n1, BigInt n2, BigInt Q, BigInt R)\r
2447         {\r
2448             int digitsN1 = n1.GetMSD() + 1;\r
2449             int digitsN2 = n2.GetMSD() + 1;\r
2450 \r
2451             //n2 is bigger than n1\r
2452             if (digitsN1 < digitsN2)\r
2453             {\r
2454                 R.AssignInt(n1);\r
2455                 Q.Zero();\r
2456                 return;\r
2457             }\r
2458 \r
2459             if (digitsN1 == digitsN2)\r
2460             {\r
2461                 //n2 is bigger than n1\r
2462                 if (LtInt(n1, n2))\r
2463                 {\r
2464                     R.AssignInt(n1);\r
2465                     Q.Zero();\r
2466                     return;\r
2467                 }\r
2468 \r
2469                 //n2 >= n1, but less the 2x n1 (initial conditions make this certain)\r
2470                 Q.Zero();\r
2471                 Q.digitArray[0] = 1;\r
2472                 R.Assign(n1);\r
2473                 R.SubInternalBits(n2.digitArray);\r
2474                 return;\r
2475             }\r
2476 \r
2477             int digits = digitsN1 - (digitsN2 + 1);\r
2478 \r
2479             //Algorithm Div_31 can be used to get the answer in O(n) time.\r
2480             if (digits == 0)\r
2481             {\r
2482                 Div_31(n1, n2, Q, R);\r
2483                 return;\r
2484             }\r
2485 \r
2486             BigInt n1New = DigitShiftRight(n1, digits);\r
2487             BigInt s = DigitTruncate(n1, digits);\r
2488 \r
2489             BigInt Q2 = new BigInt(n1, n1.pres, true);\r
2490             BigInt R2 = new BigInt(n1, n1.pres, true);\r
2491 \r
2492             Div_31(n1New, n2, Q2, R2);\r
2493 \r
2494             R2.DigitShiftSelfLeft(digits);\r
2495             R2.Add(s);\r
2496 \r
2497             Div_32(R2, n2, Q, R);\r
2498 \r
2499             Q2.DigitShiftSelfLeft(digits);\r
2500             Q.Add(Q2);\r
2501         }\r
2502 \r
2503         /// <summary>\r
2504         /// Sets the n-th bit of the number to 1\r
2505         /// </summary>\r
2506         /// <param name="bit">the index of the bit to set</param>\r
2507         public void SetBit(int bit)\r
2508         {\r
2509             int digit = (bit >> 5);\r
2510             if (digit >= digitArray.Length) return;\r
2511             digitArray[digit] = digitArray[digit] | (1u << (bit - (digit << 5)));\r
2512         }\r
2513 \r
2514         /// <summary>\r
2515         /// Sets the n-th bit of the number to 0\r
2516         /// </summary>\r
2517         /// <param name="bit">the index of the bit to set</param>\r
2518         public void ClearBit(int bit)\r
2519         {\r
2520             int digit = (bit >> 5);\r
2521             if (digit >= digitArray.Length) return;\r
2522             digitArray[digit] = digitArray[digit] & (~(1u << (bit - (digit << 5))));\r
2523         }\r
2524 \r
2525         /// <summary>\r
2526         /// Returns the n-th bit, counting from the MSB to the LSB\r
2527         /// </summary>\r
2528         /// <param name="bit">the index of the bit to return</param>\r
2529         /// <returns>1 if the bit is 1, 0 otherwise</returns>\r
2530         public uint GetBitFromTop(int bit)\r
2531         {\r
2532             if (bit < 0) return 0;\r
2533             int wordCount = (bit >> 5);\r
2534             int upBit = 31 - (bit & 31);\r
2535             if (wordCount >= digitArray.Length) return 0;\r
2536 \r
2537             return ((digitArray[digitArray.Length - (wordCount + 1)] & (1u << upBit)) >> upBit);\r
2538         }\r
2539 \r
2540         /// <summary>\r
2541         /// Assigns n2 to 'this'\r
2542         /// </summary>\r
2543         /// <param name="n2"></param>\r
2544         public void Assign(BigInt n2)\r
2545         {\r
2546             if (digitArray.Length != n2.digitArray.Length) MakeSafe(ref n2);\r
2547             sign = n2.sign;\r
2548             AssignInt(n2);\r
2549         }\r
2550 \r
2551         /// <summary>\r
2552         /// Assign n2 to 'this', safe only if precision-matched\r
2553         /// </summary>\r
2554         /// <param name="n2"></param>\r
2555         /// <returns></returns>\r
2556         private void AssignInt(BigInt n2)\r
2557         {\r
2558             int Length = digitArray.Length;\r
2559 \r
2560             for (int i = 0; i < Length; i++)\r
2561             {\r
2562                 digitArray[i] = n2.digitArray[i];\r
2563             }\r
2564         }\r
2565 \r
2566         private static BigInt DigitShiftRight(BigInt n1, int digits)\r
2567         {\r
2568             BigInt res = new BigInt(n1);\r
2569 \r
2570             int Length = res.digitArray.Length;\r
2571 \r
2572             for (int i = 0; i < Length - digits; i++)\r
2573             {\r
2574                 res.digitArray[i] = res.digitArray[i + digits];\r
2575             }\r
2576 \r
2577             for (int i = Length - digits; i < Length; i++)\r
2578             {\r
2579                 res.digitArray[i] = 0;\r
2580             }\r
2581 \r
2582             return res;\r
2583         }\r
2584 \r
2585         private void DigitShiftSelfRight(int digits)\r
2586         {\r
2587             for (int i = digits; i < digitArray.Length; i++)\r
2588             {\r
2589                 digitArray[i - digits] = digitArray[i];\r
2590             }\r
2591 \r
2592             for (int i = digitArray.Length - digits; i < digitArray.Length; i++)\r
2593             {\r
2594                 digitArray[i] = 0;\r
2595             }\r
2596         }\r
2597 \r
2598         private void DigitShiftSelfLeft(int digits)\r
2599         {\r
2600             for (int i = digitArray.Length - 1; i >= digits; i--)\r
2601             {\r
2602                 digitArray[i] = digitArray[i - digits];\r
2603             }\r
2604 \r
2605             for (int i = digits - 1; i >= 0; i--)\r
2606             {\r
2607                 digitArray[i] = 0;\r
2608             }\r
2609         }\r
2610 \r
2611         private static BigInt DigitTruncate(BigInt n1, int digits)\r
2612         {\r
2613             BigInt res = new BigInt(n1);\r
2614 \r
2615             for (int i = res.digitArray.Length - 1; i >= digits; i--)\r
2616             {\r
2617                 res.digitArray[i] = 0;\r
2618             }\r
2619 \r
2620             return res;\r
2621         }\r
2622 \r
2623         private void Add2Pow32Self()\r
2624         {\r
2625             int Length = digitArray.Length;\r
2626 \r
2627             uint carry = 1;\r
2628 \r
2629             for (int i = 1; i < Length; i++)\r
2630             {\r
2631                 uint temp = digitArray[i];\r
2632                 digitArray[i] += carry;\r
2633                 if (digitArray[i] > temp) return;\r
2634             }\r
2635 \r
2636             return;\r
2637         }\r
2638 \r
2639         /// <summary>\r
2640         /// Sets the number of digits without changing the precision\r
2641         /// This method is made public only to facilitate fixed-point operations\r
2642         /// It should under no circumstances be used for anything else, because\r
2643         /// it breaks the BigNum(PrecisionSpec precision) constructor in dangerous\r
2644         /// and unpredictable ways.\r
2645         /// </summary>\r
2646         /// <param name="digits"></param>\r
2647         public void SetNumDigits(int digits)\r
2648         {\r
2649             if (digits == digitArray.Length) return;\r
2650 \r
2651             UInt32[] newDigitArray = new UInt32[digits];\r
2652             workingSet = new UInt32[digits];\r
2653 \r
2654             int numCopy = (digits < digitArray.Length) ? digits : digitArray.Length;\r
2655 \r
2656             for (int i = 0; i < numCopy; i++)\r
2657             {\r
2658                 newDigitArray[i] = digitArray[i];\r
2659             }\r
2660 \r
2661             digitArray = newDigitArray;\r
2662         }\r
2663 \r
2664         //********************** Explicit casts ***********************\r
2665 \r
2666         /// <summary>\r
2667         /// Cast to int\r
2668         /// </summary>\r
2669         /// <param name="value"></param>\r
2670         /// <returns></returns>\r
2671         public static explicit operator Int32(BigInt value)\r
2672         {\r
2673             if (value.digitArray[0] == 0x80000000 && value.sign) return Int32.MinValue;\r
2674             int res = (int)(value.digitArray[0] & 0x7fffffff);\r
2675             if (value.sign) res = -res;\r
2676             return res;\r
2677         }\r
2678 \r
2679         /// <summary>\r
2680         /// explicit cast to unsigned int.\r
2681         /// </summary>\r
2682         /// <param name="value"></param>\r
2683         /// <returns></returns>\r
2684         public static explicit operator UInt32(BigInt value)\r
2685         {\r
2686             if (value.sign) return (UInt32)((Int32)(value));\r
2687             return (UInt32)value.digitArray[0];\r
2688         }\r
2689 \r
2690         /// <summary>\r
2691         /// explicit cast to 64-bit signed integer.\r
2692         /// </summary>\r
2693         /// <param name="value"></param>\r
2694         /// <returns></returns>\r
2695         public static explicit operator Int64(BigInt value)\r
2696         {\r
2697             if (value.digitArray.Length < 2) return (value.sign ? -((Int64)value.digitArray[0]): ((Int64)value.digitArray[0]));\r
2698             UInt64 ret = (((UInt64)value.digitArray[1]) << 32) + (UInt64)value.digitArray[0];\r
2699             if (ret == 0x8000000000000000L && value.sign) return Int64.MinValue;\r
2700             Int64 signedRet = (Int64)(ret & 0x7fffffffffffffffL);\r
2701             if (value.sign) signedRet = -signedRet;\r
2702             return signedRet;\r
2703         }\r
2704 \r
2705         /// <summary>\r
2706         /// Explicit cast to UInt64\r
2707         /// </summary>\r
2708         /// <param name="value"></param>\r
2709         /// <returns></returns>\r
2710         public static explicit operator UInt64(BigInt value)\r
2711         {\r
2712             if (value.sign) return (UInt64)((Int64)(value));\r
2713             if (value.digitArray.Length < 2) return (UInt64)value.digitArray[0];\r
2714             return ((((UInt64)value.digitArray[1]) << 32) + (UInt64)value.digitArray[0]);\r
2715         }\r
2716 \r
2717         /// <summary>\r
2718         /// Cast to string\r
2719         /// </summary>\r
2720         /// <param name="value"></param>\r
2721         /// <returns></returns>\r
2722         public static explicit operator string(BigInt value)\r
2723         {\r
2724             return value.ToString();\r
2725         }\r
2726 \r
2727         /// <summary>\r
2728         /// Cast from string - this is not wholly safe, because precision is not\r
2729         /// specified. You should try to construct a BigInt with the appropriate\r
2730         /// constructor instead.\r
2731         /// </summary>\r
2732         /// <param name="value">The decimal string to convert to a BigInt</param>\r
2733         /// <returns>A BigInt of the precision required to encompass the string</returns>\r
2734         public static explicit operator BigInt(string value)\r
2735         {\r
2736             return new BigInt(value);\r
2737         }\r
2738 \r
2739         //********************* ToString members **********************\r
2740 \r
2741         /// <summary>\r
2742         /// Converts this to a string, in the specified base\r
2743         /// </summary>\r
2744         /// <param name="numberBase">the base to use (min 2, max 16)</param>\r
2745         /// <returns>a string representation of the number</returns>\r
2746         public string ToString(int numberBase)\r
2747         {\r
2748             char[] digitChars = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };\r
2749 \r
2750             string output = "";\r
2751 \r
2752             BigInt clone = new BigInt(this);\r
2753             clone.sign = false;\r
2754 \r
2755             int numDigits = 0;\r
2756             while (!clone.IsZero())\r
2757             {\r
2758                 if (numberBase == 10 && (numDigits % 3) == 0 && numDigits != 0)\r
2759                 {\r
2760                     output = String.Format(",{0}", output);\r
2761                 }\r
2762                 else if (numberBase != 10 && (numDigits % 8) == 0 && numDigits != 0)\r
2763                 {\r
2764                     output = String.Format(" {0}", output);\r
2765                 }\r
2766 \r
2767                 BigInt div, mod;\r
2768                 DivMod(clone, (uint)numberBase, out div, out mod);\r
2769                 int iMod = (int)mod;\r
2770                 output = String.Format("{0}{1}", digitChars[(int)mod], output);\r
2771 \r
2772                 numDigits++;\r
2773 \r
2774                 clone = div;\r
2775             }\r
2776 \r
2777             if (output.Length == 0) output = String.Format("0");\r
2778 \r
2779             if (sign) output = String.Format("-{0}", output);\r
2780 \r
2781             return output;\r
2782         }\r
2783 \r
2784         /// <summary>\r
2785         /// Converts the number to a string, in base 10\r
2786         /// </summary>\r
2787         /// <returns>a string representation of the number in base 10</returns>\r
2788         public override string ToString()\r
2789         {\r
2790             return ToString(10);\r
2791         }\r
2792 \r
2793         //***************** Internal helper functions *****************\r
2794 \r
2795         private void FromStringInt(string init, int numberBase)\r
2796         {\r
2797             char [] digitChars = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};\r
2798 \r
2799             string formattedInput = init.Trim().ToUpper();\r
2800 \r
2801             for (int i = 0; i < formattedInput.Length; i++)\r
2802             {\r
2803                 int digitIndex = Array.IndexOf(digitChars, formattedInput[i]);\r
2804 \r
2805                 //Skip fractional part altogether\r
2806                 if (formattedInput[i] == '.') break;\r
2807 \r
2808                 //skip non-digit characters.\r
2809                 if (digitIndex < 0) continue;\r
2810 \r
2811                 //Multiply\r
2812                 MulInternal((uint)numberBase);\r
2813               \r
2814                 //Add\r
2815                 AddInternal(digitIndex);\r
2816             }\r
2817 \r
2818             if (init.Length > 0 && init[0] == '-') sign = true;\r
2819         }\r
2820 \r
2821         /// <summary>\r
2822         /// Sign-insensitive less than comparison. \r
2823         /// unsafe if n1 and n2 disagree in precision\r
2824         /// </summary>\r
2825         /// <param name="n1"></param>\r
2826         /// <param name="n2"></param>\r
2827         /// <returns></returns>\r
2828         private static bool LtInt(BigInt n1, BigInt n2)\r
2829         {\r
2830             //MakeSafe(ref n1, ref n2);\r
2831 \r
2832             for (int i = n1.digitArray.Length - 1; i >= 0; i--)\r
2833             {\r
2834                 if (n1.digitArray[i] < n2.digitArray[i]) return true;\r
2835                 if (n1.digitArray[i] > n2.digitArray[i]) return false;\r
2836             }\r
2837 \r
2838             //equal\r
2839             return false;\r
2840         }\r
2841 \r
2842         /// <summary>\r
2843         /// Sign-insensitive greater than comparison. \r
2844         /// unsafe if n1 and n2 disagree in precision\r
2845         /// </summary>\r
2846         /// <param name="n1"></param>\r
2847         /// <param name="n2"></param>\r
2848         /// <returns></returns>\r
2849         private static bool GtInt(BigInt n1, BigInt n2)\r
2850         {\r
2851             //MakeSafe(ref n1, ref n2);\r
2852 \r
2853             for (int i = n1.digitArray.Length - 1; i >= 0; i--)\r
2854             {\r
2855                 if (n1.digitArray[i] > n2.digitArray[i]) return true;\r
2856                 if (n1.digitArray[i] < n2.digitArray[i]) return false;\r
2857             }\r
2858 \r
2859             //equal\r
2860             return false;\r
2861         }\r
2862 \r
2863         /// <summary>\r
2864         /// Makes sure the numbers have matching precisions\r
2865         /// </summary>\r
2866         /// <param name="n1"></param>\r
2867         /// <param name="n2"></param>\r
2868         private static void MakeSafe(ref BigInt n1, ref BigInt n2)\r
2869         {\r
2870             if (n1.digitArray.Length == n2.digitArray.Length)\r
2871             {\r
2872                 return;\r
2873             }\r
2874             else if (n1.digitArray.Length > n2.digitArray.Length)\r
2875             {\r
2876                 n2 = new BigInt(n2, n1.pres);\r
2877             }\r
2878             else\r
2879             {\r
2880                 n1 = new BigInt(n1, n2.pres);\r
2881             }\r
2882         }\r
2883 \r
2884         /// <summary>\r
2885         /// Makes sure the numbers have matching precisions\r
2886         /// </summary>\r
2887         /// <param name="n2">the number to match to this</param>\r
2888         private void MakeSafe(ref BigInt n2)\r
2889         {\r
2890             n2 = new BigInt(n2, pres);\r
2891             n2.SetNumDigits(digitArray.Length);\r
2892         }\r
2893 \r
2894 \r
2895         private PrecisionSpec pres;\r
2896         private bool sign;\r
2897         private uint[] digitArray;\r
2898         private uint[] workingSet;\r
2899     }\r
2900 \r
2901 }