mcs/class/System.Numerics/System.Numerics/BigInteger.cs

   1 //
   2 // System.Numerics.BigInteger
   3 //
   4 // Rodrigo Kumpera (rkumpera@novell.com)
   5
   6 //
   7 // Copyright (C) 2010 Novell, Inc (http://www.novell.com)
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining
  10 // a copy of this software and associated documentation files (the
  11 // "Software"), to deal in the Software without restriction, including
  12 // without limitation the rights to use, copy, modify, merge, publish,
  13 // distribute, sublicense, and/or sell copies of the Software, and to
  14 // permit persons to whom the Software is furnished to do so, subject to
  15 // the following conditions:
  16 //
  17 // The above copyright notice and this permission notice shall be
  18 // included in all copies or substantial portions of the Software.
  19 //
  20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  27 //
  28 // A big chuck of code comes the DLR (as hosted in http://ironpython.codeplex.com),
  29 // which has the following License:
  30 //
  31 /* ****************************************************************************
  32  *
  33  * Copyright (c) Microsoft Corporation.
  34  *
  35  * This source code is subject to terms and conditions of the Microsoft Public License. A
  36  * copy of the license can be found in the License.html file at the root of this distribution. If
  37  * you cannot locate the  Microsoft Public License, please send an email to
  38  * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound
  39  * by the terms of the Microsoft Public License.
  40  *
  41  * You must not remove this notice, or any other, from this software.
  42  *
  43  *
  44  * ***************************************************************************/
  45
  46 using System;
  47 using System.Collections.Generic;
  48 using System.Diagnostics;
  49 using System.Diagnostics.CodeAnalysis;
  50 using System.Globalization;
  51 using System.Text;
  52 using System.Threading;
  53
  54 /*
  55 Optimization
  56         Have proper popcount function for IsPowerOfTwo
  57         Use unsafe ops to avoid bounds check
  58         CoreAdd could avoid some resizes by checking for equal sized array that top overflow
  59         For bitwise operators, hoist the conditionals out of their main loop
  60         Optimize BitScanBackward
  61         Use a carry variable to make shift opts do half the number of array ops.
  62         Schoolbook multiply is O(n^2), use Karatsuba /Toom-3 for large numbers
  63 */
  64 namespace System.Numerics {
  65         public struct BigInteger : IComparable, IFormattable, IComparable<BigInteger>, IEquatable<BigInteger>
  66         {
  67                 //LSB on [0]
  68                 readonly uint[] data;
  69                 readonly short sign;
  70
  71                 static readonly uint[] ZERO = new uint [1];
  72                 static readonly uint[] ONE = new uint [1] { 1 };
  73
  74                 BigInteger (short sign, uint[] data)
  75                 {
  76                         this.sign = sign;
  77                         this.data = data;
  78                 }
  79
  80                 public BigInteger (int value)
  81                 {
  82                         if (value == 0) {
  83                                 sign = 0;
  84                                 data = ZERO;
  85                         } else if (value > 0) {
  86                                 sign = 1;
  87                                 data = new uint[] { (uint) value };
  88                         } else {
  89                                 sign = -1;
  90                                 data = new uint[1] { (uint)-value };
  91                         }
  92                 }
  93
  94                 [CLSCompliantAttribute (false)]
  95                 public BigInteger (uint value)
  96                 {
  97                         if (value == 0) {
  98                                 sign = 0;
  99                                 data = ZERO;
 100                         } else {
 101                                 sign = 1;
 102                                 data = new uint [1] { value };
 103                         }
 104                 }
 105
 106                 public BigInteger (long value)
 107                 {
 108                         if (value == 0) {
 109                                 sign = 0;
 110                                 data = ZERO;
 111                         } else if (value > 0) {
 112                                 sign = 1;
 113                                 uint low = (uint)value;
 114                                 uint high = (uint)(value >> 32);
 115
 116                                 data = new uint [high != 0 ? 2 : 1];
 117                                 data [0] = low;
 118                                 if (high != 0)
 119                                         data [1] = high;
 120                         } else {
 121                                 sign = -1;
 122                                 value = -value;
 123                                 uint low = (uint)value;
 124                                 uint high = (uint)((ulong)value >> 32);
 125
 126                                 data = new uint [high != 0 ? 2 : 1];
 127                                 data [0] = low;
 128                                 if (high != 0)
 129                                         data [1] = high;
 130                         }
 131                 }
 132
 133                 [CLSCompliantAttribute (false)]
 134                 public BigInteger (ulong value)
 135                 {
 136                         if (value == 0) {
 137                                 sign = 0;
 138                                 data = ZERO;
 139                         } else {
 140                                 sign = 1;
 141                                 uint low = (uint)value;
 142                                 uint high = (uint)(value >> 32);
 143
 144                                 data = new uint [high != 0 ? 2 : 1];
 145                                 data [0] = low;
 146                                 if (high != 0)
 147                                         data [1] = high;
 148                         }
 149                 }
 150
 151
 152                 static bool Negative (byte[] v)
 153                 {
 154                         return ((v[7] & 0x80) != 0);
 155                 }
 156
 157                 static ushort Exponent (byte[] v)
 158                 {
 159                         return (ushort)((((ushort)(v[7] & 0x7F)) << (ushort)4) | (((ushort)(v[6] & 0xF0)) >> 4));
 160                 }
 161
 162                 static ulong Mantissa(byte[] v)
 163                 {
 164                         uint i1 = ((uint)v[0] | ((uint)v[1] << 8) | ((uint)v[2] << 16) | ((uint)v[3] << 24));
 165                         uint i2 = ((uint)v[4] | ((uint)v[5] << 8) | ((uint)(v[6] & 0xF) << 16));
 166
 167                         return (ulong)((ulong)i1 | ((ulong)i2 << 32));
 168                 }
 169
 170                 const int bias = 1075;
 171                 public BigInteger (double value)
 172                 {
 173                         if (double.IsNaN (value) || Double.IsInfinity (value))
 174                                 throw new OverflowException ();
 175
 176                         byte[] bytes = BitConverter.GetBytes (value);
 177                         ulong mantissa = Mantissa (bytes);
 178                         if (mantissa == 0) {
 179                                 // 1.0 * 2**exp, we have a power of 2
 180                                 int exponent = Exponent (bytes);
 181                                 if (exponent == 0) {
 182                                         sign = 0;
 183                                         data = ZERO;
 184                                         return;
 185                                 }
 186
 187                                 BigInteger res = Negative (bytes) ? MinusOne : One;
 188                                 res = res << (exponent - 0x3ff);
 189                                 this.sign = res.sign;
 190                                 this.data = res.data;
 191                         } else {
 192                                 // 1.mantissa * 2**exp
 193                                 int exponent = Exponent(bytes);
 194                                 mantissa |= 0x10000000000000ul;
 195                                 BigInteger res = mantissa;
 196                                 res = exponent > bias ? res << (exponent - bias) : res >> (bias - exponent);
 197
 198                                 this.sign = (short) (Negative (bytes) ? -1 : 1);
 199                                 this.data = res.data;
 200                         }
 201                 }
 202
 203                 public BigInteger (float value) : this ((double)value)
 204                 {
 205                 }
 206
 207                 const Int32 DecimalScaleFactorMask = 0x00FF0000;
 208                 const Int32 DecimalSignMask = unchecked((Int32)0x80000000);
 209
 210                 public BigInteger (decimal value)
 211                 {
 212                         // First truncate to get scale to 0 and extract bits
 213                         int[] bits = Decimal.GetBits(Decimal.Truncate(value));
 214
 215                         int size = 3;
 216                         while (size > 0 && bits[size - 1] == 0) size--;
 217
 218                         if (size == 0) {
 219                                 sign = 0;
 220                                 data = ZERO;
 221                                 return;
 222                         }
 223
 224                         sign = (short) ((bits [3] & DecimalSignMask) != 0 ? -1 : 1);
 225
 226                         data = new uint [size];
 227                         data [0] = (uint)bits [0];
 228                         if (size > 1)
 229                                 data [1] = (uint)bits [1];
 230                         if (size > 2)
 231                                 data [2] = (uint)bits [2];
 232                 }
 233
 234                 [CLSCompliantAttribute (false)]
 235                 public BigInteger (byte[] value)
 236                 {
 237                         if (value == null)
 238                                 throw new ArgumentNullException ("value");
 239
 240                         int len = value.Length;
 241
 242                         if (len == 0 || (len == 1 && value [0] == 0)) {
 243                                 sign = 0;
 244                                 data = ZERO;
 245                                 return;
 246                         }
 247
 248                         if ((value [len - 1] & 0x80) != 0)
 249                                 sign = -1;
 250                         else
 251                                 sign = 1;
 252
 253                         if (sign == 1) {
 254                                 while (value [len - 1] == 0) {
 255                                         if (--len == 0) {
 256                                                 sign = 0;
 257                                                 data = ZERO;
 258                                                 return;
 259                                         }
 260                                 }
 261
 262                                 int full_words, size;
 263                                 full_words = size = len / 4;
 264                                 if ((len & 0x3) != 0)
 265                                         ++size;
 266
 267                                 data = new uint [size];
 268                                 int j = 0;
 269                                 for (int i = 0; i < full_words; ++i) {
 270                                         data [i] =      (uint)value [j++] |
 271                                                                 (uint)(value [j++] << 8) |
 272                                                                 (uint)(value [j++] << 16) |
 273                                                                 (uint)(value [j++] << 24);
 274                                 }
 275                                 size = len & 0x3;
 276                                 if (size > 0) {
 277                                         int idx = data.Length - 1;
 278                                         for (int i = 0; i < size; ++i)
 279                                                 data [idx] |= (uint)(value [j++] << (i * 8));
 280                                 }
 281                         } else {
 282                                 int full_words, size;
 283                                 full_words = size = len / 4;
 284                                 if ((len & 0x3) != 0)
 285                                         ++size;
 286
 287                                 data = new uint [size];
 288
 289                                 uint word, borrow = 1;
 290                                 ulong sub = 0;
 291                                 int j = 0;
 292
 293                                 for (int i = 0; i < full_words; ++i) {
 294                                         word =  (uint)value [j++] |
 295                                                         (uint)(value [j++] << 8) |
 296                                                         (uint)(value [j++] << 16) |
 297                                                         (uint)(value [j++] << 24);
 298
 299                                         sub = (ulong)word - borrow;
 300                                         word = (uint)sub;
 301                                         borrow = (uint)(sub >> 32) & 0x1u;
 302                                         data [i] = ~word;
 303                                 }
 304                                 size = len & 0x3;
 305
 306                                 if (size > 0) {
 307                                         word = 0;
 308                                         uint store_mask = 0;
 309                                         for (int i = 0; i < size; ++i) {
 310                                                 word |= (uint)(value [j++] << (i * 8));
 311                                                 store_mask = (store_mask << 8) | 0xFF;
 312                                         }
 313
 314                                         sub = word - borrow;
 315                                         word = (uint)sub;
 316                                         borrow = (uint)(sub >> 32) & 0x1u;
 317
 318                                         data [data.Length - 1] = ~word & store_mask;
 319                                 }
 320                                 if (borrow != 0) //FIXME I believe this can't happen, can someone write a test for it?
 321                                         throw new Exception ("non zero final carry");
 322                         }
 323
 324                 }
 325
 326                 public bool IsEven {
 327                         get { return sign == 0 || (data [0] & 0x1) == 0; }
 328                 }
 329
 330                 public bool IsOne {
 331                         get { return sign == 1 && data.Length == 1 && data [0] == 1; }
 332                 }
 333
 334
 335                 //Gem from Hacker's Delight
 336                 //Returns the number of bits set in @x
 337                 static int PopulationCount (uint x)
 338                 {
 339                         x = x - ((x >> 1) & 0x55555555);
 340                         x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
 341                         x = (x + (x >> 4)) & 0x0F0F0F0F;
 342                         x = x + (x >> 8);
 343                         x = x + (x >> 16);
 344                         return (int)(x & 0x0000003F);
 345                 }
 346
 347                 static int LeadingZeroCount(uint value)
 348                 {
 349                         value |= value >> 1;
 350                         value |= value >> 2;
 351                         value |= value >> 4;
 352                         value |= value >> 8;
 353                         value |= value >> 16;
 354                         return 32 - PopulationCount (value); // 32 = bits in uint
 355                 }
 356
 357                 public bool IsPowerOfTwo {
 358                         get {
 359                                 bool foundBit = false;
 360                                 if (sign != 1)
 361                                         return false;
 362                                 //This function is pop count == 1 for positive numbers
 363                                 for (int i = 0; i < data.Length; ++i) {
 364                                         int p = PopulationCount (data [i]);
 365                                         if (p > 0) {
 366                                                 if (p > 1 || foundBit)
 367                                                         return false;
 368                                                 foundBit = true;
 369                                         }
 370                                 }
 371                                 return foundBit;
 372                         }
 373                 }
 374
 375                 public bool IsZero {
 376                         get { return sign == 0; }
 377                 }
 378
 379                 public int Sign {
 380                         get { return sign; }
 381                 }
 382
 383                 public static BigInteger MinusOne {
 384                         get { return new BigInteger (-1, ONE); }
 385                 }
 386
 387                 public static BigInteger One {
 388                         get { return new BigInteger (1, ONE); }
 389                 }
 390
 391                 public static BigInteger Zero {
 392                         get { return new BigInteger (0, ZERO); }
 393                 }
 394
 395                 public static explicit operator int (BigInteger value)
 396                 {
 397                         if (value.sign == 0)
 398                                 return 0;
 399                         if (value.data.Length > 1)
 400                                 throw new OverflowException ();
 401                         uint data = value.data [0];
 402
 403                         if (value.sign == 1) {
 404                                 if (data > (uint)int.MaxValue)
 405                                         throw new OverflowException ();
 406                                 return (int)data;
 407                         } else if (value.sign == -1) {
 408                                 if (data > 0x80000000u)
 409                                         throw new OverflowException ();
 410                                 return -(int)data;
 411                         }
 412
 413                         return 0;
 414                 }
 415
 416                 [CLSCompliantAttribute (false)]
 417                 public static explicit operator uint (BigInteger value)
 418                 {
 419                         if (value.sign == 0)
 420                                 return 0;
 421                         if (value.data.Length > 1 || value.sign == -1)
 422                                 throw new OverflowException ();
 423                         return value.data [0];
 424                 }
 425
 426                 public static explicit operator short (BigInteger value)
 427                 {
 428                         int val = (int)value;
 429                         if (val < short.MinValue || val > short.MaxValue)
 430                                 throw new OverflowException ();
 431                         return (short)val;
 432                 }
 433
 434                 [CLSCompliantAttribute (false)]
 435                 public static explicit operator ushort (BigInteger value)
 436                 {
 437                         uint val = (uint)value;
 438                         if (val > ushort.MaxValue)
 439                                 throw new OverflowException ();
 440                         return (ushort)val;
 441                 }
 442
 443                 public static explicit operator byte (BigInteger value)
 444                 {
 445                         uint val = (uint)value;
 446                         if (val > byte.MaxValue)
 447                                 throw new OverflowException ();
 448                         return (byte)val;
 449                 }
 450
 451                 [CLSCompliantAttribute (false)]
 452                 public static explicit operator sbyte (BigInteger value)
 453                 {
 454                         int val = (int)value;
 455                         if (val < sbyte.MinValue || val > sbyte.MaxValue)
 456                                 throw new OverflowException ();
 457                         return (sbyte)val;
 458                 }
 459
 460
 461                 public static explicit operator long (BigInteger value)
 462                 {
 463                         if (value.sign == 0)
 464                                 return 0;
 465
 466                         if (value.data.Length > 2)
 467                                 throw new OverflowException ();
 468
 469                         uint low = value.data [0];
 470
 471                         if (value.data.Length == 1) {
 472                                 if (value.sign == 1)
 473                                         return (long)low;
 474                                 long res = (long)low;
 475                                 return -res;
 476                         }
 477
 478                         uint high = value.data [1];
 479
 480                         if (value.sign == 1) {
 481                                 if (high >= 0x80000000u)
 482                                         throw new OverflowException ();
 483                                 return (((long)high) << 32) | low;
 484                         }
 485
 486                         /*
 487                         We cannot represent negative numbers smaller than long.MinValue.
 488                         Those values are encoded into what look negative numbers, so negating
 489                         them produces a positive value, that's why it's safe to check for that
 490                         condition.
 491
 492                         long.MinValue works fine since it's bigint encoding looks like a negative
 493                         number, but since long.MinValue == -long.MinValue, we're good.
 494                         */
 495
 496                         long result = - ((((long)high) << 32) | (long)low);
 497                         if (result > 0)
 498                                 throw new OverflowException ();
 499                         return result;
 500                 }
 501
 502                 [CLSCompliantAttribute (false)]
 503                 public static explicit operator ulong (BigInteger value)
 504                 {
 505                         if (value.sign == 0)
 506                                 return 0;
 507                         if (value.data.Length > 2 || value.sign == -1)
 508                                 throw new OverflowException ();
 509
 510                         uint low = value.data [0];
 511                         if (value.data.Length == 1)
 512                                 return low;
 513
 514                         uint high = value.data [1];
 515                         return (((ulong)high) << 32) | low;
 516                 }
 517
 518                 public static explicit operator double (BigInteger value)
 519                 {
 520                         switch (value.data.Length) {
 521                         case 0:
 522                                 return 0.0;
 523                         case 1:
 524                                 return (value.sign > 0 ? 1 : - 1) * (double)value.data [0];
 525                         case 2:
 526                                 return (value.sign > 0 ? 1 : - 1) * (double)((ulong)value.data [1] << 32 | (ulong)value.data [0]);
 527                         default:
 528                                 var index = value.data.Length - 1;
 529                                 var word = value.data [index];
 530                                 var mantissa = ((ulong)word << 32) | value.data [index - 1];
 531                                 int missing = LeadingZeroCount (word) - 11; // 11 = bits in exponent
 532                                 if (missing > 0) {
 533                                         // add the missing bits from the next word
 534                                         mantissa = (mantissa << missing) | (value.data [index - 2] >> (32 - missing));
 535                                 } else {
 536                                         mantissa >>= -missing;
 537                                 }
 538                                 return (value.sign > 0 ? 1 : - 1) * (double)mantissa * Math.Pow (2, ((value.data.Length - 2) * 32) - missing);
 539                         }
 540         }
 541
 542                 public static explicit operator float (BigInteger value)
 543                 {
 544                         switch (value.data.Length) {
 545                         case 0:
 546                                 return 0.0f;
 547                         case 1:
 548                                 return (value.sign > 0 ? 1 : - 1) * (float)value.data [0];
 549                         default:
 550                                 var index = value.data.Length - 1;
 551                                 var mantissa = value.data [index];
 552                                 int missing = LeadingZeroCount (mantissa) - 8; // 8 = bits in exponent
 553                                 if (missing > 0) {
 554                     // add the missing bits from the next word
 555                                         mantissa = (mantissa << missing) | (value.data [index - 1] >> (32 - missing));
 556                                 } else {
 557                                         mantissa >>= -missing;
 558                                 }
 559                                 return (value.sign > 0 ? 1 : - 1) * (float)(mantissa * Math.Pow (2, ((value.data.Length - 1) * 32) - missing));
 560                         }
 561                 }
 562
 563                 public static explicit operator decimal (BigInteger value)
 564                 {
 565                         if (value.sign == 0)
 566                         return Decimal.Zero;
 567
 568                         uint[] data = value.data;
 569                         if (data.Length > 3)
 570                                 throw new OverflowException ();
 571
 572                         int lo = 0, mi = 0, hi = 0;
 573                         if (data.Length > 2)
 574                                 hi = (Int32)data [2];
 575                         if (data.Length > 1)
 576                                 mi = (Int32)data [1];
 577                         if (data.Length > 0)
 578                                 lo = (Int32)data [0];
 579
 580                         return new Decimal(lo, mi, hi, value.sign < 0, 0);
 581                 }
 582
 583                 public static implicit operator BigInteger (int value)
 584                 {
 585                         return new BigInteger (value);
 586                 }
 587
 588                 [CLSCompliantAttribute (false)]
 589                 public static implicit operator BigInteger (uint value)
 590                 {
 591                         return new BigInteger (value);
 592                 }
 593
 594                 public static implicit operator BigInteger (short value)
 595                 {
 596                         return new BigInteger (value);
 597                 }
 598
 599                 [CLSCompliantAttribute (false)]
 600                 public static implicit operator BigInteger (ushort value)
 601                 {
 602                         return new BigInteger (value);
 603                 }
 604
 605                 public static implicit operator BigInteger (byte value)
 606                 {
 607                         return new BigInteger (value);
 608                 }
 609
 610                 [CLSCompliantAttribute (false)]
 611                 public static implicit operator BigInteger (sbyte value)
 612                 {
 613                         return new BigInteger (value);
 614                 }
 615
 616                 public static implicit operator BigInteger (long value)
 617                 {
 618                         return new BigInteger (value);
 619                 }
 620
 621                 [CLSCompliantAttribute (false)]
 622                 public static implicit operator BigInteger (ulong value)
 623                 {
 624                         return new BigInteger (value);
 625                 }
 626
 627                 public static explicit operator BigInteger (double value)
 628                 {
 629                         return new BigInteger (value);
 630                 }
 631
 632                 public static explicit operator BigInteger (float value)
 633                 {
 634                         return new BigInteger (value);
 635                 }
 636
 637                 public static explicit operator BigInteger (decimal value)
 638                 {
 639                         return new BigInteger (value);
 640                 }
 641
 642                 public static BigInteger operator+ (BigInteger left, BigInteger right)
 643                 {
 644                         if (left.sign == 0)
 645                                 return right;
 646                         if (right.sign == 0)
 647                                 return left;
 648
 649                         if (left.sign == right.sign)
 650                                 return new BigInteger (left.sign, CoreAdd (left.data, right.data));
 651
 652                         int r = CoreCompare (left.data, right.data);
 653
 654                         if (r == 0)
 655                                 return new BigInteger (0, ZERO);
 656
 657                         if (r > 0) //left > right
 658                                 return new BigInteger (left.sign, CoreSub (left.data, right.data));
 659
 660                         return new BigInteger (right.sign, CoreSub (right.data, left.data));
 661                 }
 662
 663                 public static BigInteger operator- (BigInteger left, BigInteger right)
 664                 {
 665                         if (right.sign == 0)
 666                                 return left;
 667                         if (left.sign == 0)
 668                                 return new BigInteger ((short)-right.sign, right.data);
 669
 670                         if (left.sign == right.sign) {
 671                                 int r = CoreCompare (left.data, right.data);
 672
 673                                 if (r == 0)
 674                                         return new BigInteger (0, ZERO);
 675
 676                                 if (r > 0) //left > right
 677                                         return new BigInteger (left.sign, CoreSub (left.data, right.data));
 678
 679                                 return new BigInteger ((short)-right.sign, CoreSub (right.data, left.data));
 680                         }
 681
 682                         return new BigInteger (left.sign, CoreAdd (left.data, right.data));
 683                 }
 684
 685                 public static BigInteger operator* (BigInteger left, BigInteger right)
 686                 {
 687                         if (left.sign == 0 || right.sign == 0)
 688                                 return new BigInteger (0, ZERO);
 689
 690                         if (left.data [0] == 1 && left.data.Length == 1) {
 691                                 if (left.sign == 1)
 692                                         return right;
 693                                 return new BigInteger ((short)-right.sign, right.data);
 694                         }
 695
 696                         if (right.data [0] == 1 && right.data.Length == 1) {
 697                                 if (right.sign == 1)
 698                                         return left;
 699                                 return new BigInteger ((short)-left.sign, left.data);
 700                         }
 701
 702                         uint[] a = left.data;
 703                         uint[] b = right.data;
 704
 705                         uint[] res = new uint [a.Length + b.Length];
 706
 707             for (int i = 0; i < a.Length; ++i) {
 708                 uint ai = a [i];
 709                 int k = i;
 710
 711                 ulong carry = 0;
 712                 for (int j = 0; j < b.Length; ++j) {
 713                     carry = carry + ((ulong)ai) * b [j] + res [k];
 714                     res[k++] = (uint)carry;
 715                     carry >>= 32;
 716                 }
 717
 718                 while (carry != 0) {
 719                     carry += res [k];
 720                     res[k++] = (uint)carry;
 721                     carry >>= 32;
 722                 }
 723             }
 724
 725                         int m;
 726                         for (m = res.Length - 1; m >= 0 && res [m] == 0; --m) ;
 727                         if (m < res.Length - 1)
 728                                 res = Resize (res, m + 1);
 729
 730                         return new BigInteger ((short)(left.sign * right.sign), res);
 731                 }
 732
 733                 public static BigInteger operator/ (BigInteger dividend, BigInteger divisor)
 734                 {
 735                         if (divisor.sign == 0)
 736                                 throw new DivideByZeroException ();
 737
 738                         if (dividend.sign == 0)
 739                                 return dividend;
 740
 741                         uint[] quotient;
 742                         uint[] remainder_value;
 743
 744                         DivModUnsigned (dividend.data, divisor.data, out quotient, out remainder_value);
 745
 746                         int i;
 747                         for (i = quotient.Length - 1; i >= 0 && quotient [i] == 0; --i) ;
 748                         if (i == -1)
 749                                 return new BigInteger (0, ZERO);
 750                         if (i < quotient.Length - 1)
 751                                 quotient = Resize (quotient, i + 1);
 752
 753                         return new BigInteger ((short)(dividend.sign * divisor.sign), quotient);
 754                 }
 755
 756                 public static BigInteger operator% (BigInteger dividend, BigInteger divisor)
 757                 {
 758                         if (divisor.sign == 0)
 759                                 throw new DivideByZeroException ();
 760
 761                         if (dividend.sign == 0)
 762                                 return dividend;
 763
 764                         uint[] quotient;
 765                         uint[] remainder_value;
 766
 767                         DivModUnsigned (dividend.data, divisor.data, out quotient, out remainder_value);
 768
 769                         int i;
 770                         for (i = remainder_value.Length - 1; i >= 0 && remainder_value [i] == 0; --i) ;
 771                         if (i == -1)
 772                                 return new BigInteger (0, ZERO);
 773
 774                         if (i < remainder_value.Length - 1)
 775                                 remainder_value = Resize (remainder_value, i + 1);
 776                         return new BigInteger (dividend.sign, remainder_value);
 777                 }
 778
 779                 public static BigInteger operator- (BigInteger value)
 780                 {
 781                         if (value.sign == 0)
 782                                 return value;
 783                         return new BigInteger ((short)-value.sign, value.data);
 784                 }
 785
 786                 public static BigInteger operator+ (BigInteger value)
 787                 {
 788                         return value;
 789                 }
 790
 791                 public static BigInteger operator++ (BigInteger value)
 792                 {
 793                         if (value.sign == 0)
 794                                 return One;
 795
 796                         short sign = value.sign;
 797                         uint[] data = value.data;
 798                         if (data.Length == 1) {
 799                                 if (sign == -1 && data [0] == 1)
 800                                         return new BigInteger (0, ZERO);
 801                                 if (sign == 0)
 802                                         return new BigInteger (1, ONE);
 803                         }
 804
 805                         if (sign == -1)
 806                                 data = CoreSub (data, 1);
 807                         else
 808                                 data = CoreAdd (data, 1);
 809
 810                         return new BigInteger (sign, data);
 811                 }
 812
 813                 public static BigInteger operator-- (BigInteger value)
 814                 {
 815                         if (value.sign == 0)
 816                                 return MinusOne;
 817
 818                         short sign = value.sign;
 819                         uint[] data = value.data;
 820                         if (data.Length == 1) {
 821                                 if (sign == 1 && data [0] == 1)
 822                                         return new BigInteger (0, ZERO);
 823                                 if (sign == 0)
 824                                         return new BigInteger (-1, ONE);
 825                         }
 826
 827                         if (sign == -1)
 828                                 data = CoreAdd (data, 1);
 829                         else
 830                                 data = CoreSub (data, 1);
 831
 832                         return new BigInteger (sign, data);
 833                 }
 834
 835                 public static BigInteger operator& (BigInteger left, BigInteger right)
 836                 {
 837                         if (left.sign == 0)
 838                                 return left;
 839
 840                         if (right.sign == 0)
 841                                 return right;
 842
 843                         uint[] a = left.data;
 844                         uint[] b = right.data;
 845                         int ls = left.sign;
 846                         int rs = right.sign;
 847
 848                         bool neg_res = (ls == rs) && (ls == -1);
 849
 850                         uint[] result = new uint [Math.Max (a.Length, b.Length)];
 851
 852                         ulong ac = 1, bc = 1, borrow = 1;
 853
 854                         int i;
 855                         for (i = 0; i < result.Length; ++i) {
 856                                 uint va = 0;
 857                                 if (i < a.Length)
 858                                         va = a [i];
 859                                 if (ls == -1) {
 860                                         ac = ~va + ac;
 861                                         va = (uint)ac;
 862                                         ac = (uint)(ac >> 32);
 863                                 }
 864
 865                                 uint vb = 0;
 866                                 if (i < b.Length)
 867                                         vb = b [i];
 868                                 if (rs == -1) {
 869                                         bc = ~vb + bc;
 870                                         vb = (uint)bc;
 871                                         bc = (uint)(bc >> 32);
 872                                 }
 873
 874                                 uint word = va & vb;
 875
 876                                 if (neg_res) {
 877                                         borrow = word - borrow;
 878                                         word = ~(uint)borrow;
 879                                         borrow = (uint)(borrow >> 32) & 0x1u;
 880                                 }
 881
 882                                 result [i] = word;
 883                         }
 884
 885                         for (i = result.Length - 1; i >= 0 && result [i] == 0; --i) ;
 886                         if (i == -1)
 887                                 return new BigInteger (0, ZERO);
 888
 889                         if (i < result.Length - 1)
 890                                 result = Resize (result, i + 1);
 891
 892                         return new BigInteger (neg_res ? (short)-1 : (short)1, result);
 893                 }
 894
 895                 public static BigInteger operator| (BigInteger left, BigInteger right)
 896                 {
 897                         if (left.sign == 0)
 898                                 return right;
 899
 900                         if (right.sign == 0)
 901                                 return left;
 902
 903                         uint[] a = left.data;
 904                         uint[] b = right.data;
 905                         int ls = left.sign;
 906                         int rs = right.sign;
 907
 908                         bool neg_res = (ls == -1) || (rs == -1);
 909
 910                         uint[] result = new uint [Math.Max (a.Length, b.Length)];
 911
 912                         ulong ac = 1, bc = 1, borrow = 1;
 913
 914                         int i;
 915                         for (i = 0; i < result.Length; ++i) {
 916                                 uint va = 0;
 917                                 if (i < a.Length)
 918                                         va = a [i];
 919                                 if (ls == -1) {
 920                                         ac = ~va + ac;
 921                                         va = (uint)ac;
 922                                         ac = (uint)(ac >> 32);
 923                                 }
 924
 925                                 uint vb = 0;
 926                                 if (i < b.Length)
 927                                         vb = b [i];
 928                                 if (rs == -1) {
 929                                         bc = ~vb + bc;
 930                                         vb = (uint)bc;
 931                                         bc = (uint)(bc >> 32);
 932                                 }
 933
 934                                 uint word = va | vb;
 935
 936                                 if (neg_res) {
 937                                         borrow = word - borrow;
 938                                         word = ~(uint)borrow;
 939                                         borrow = (uint)(borrow >> 32) & 0x1u;
 940                                 }
 941
 942                                 result [i] = word;
 943                         }
 944
 945                         for (i = result.Length - 1; i >= 0 && result [i] == 0; --i) ;
 946                         if (i == -1)
 947                                 return new BigInteger (0, ZERO);
 948
 949                         if (i < result.Length - 1)
 950                                 result = Resize (result, i + 1);
 951
 952                         return new BigInteger (neg_res ? (short)-1 : (short)1, result);
 953                 }
 954
 955                 public static BigInteger operator^ (BigInteger left, BigInteger right)
 956                 {
 957                         if (left.sign == 0)
 958                                 return right;
 959
 960                         if (right.sign == 0)
 961                                 return left;
 962
 963                         uint[] a = left.data;
 964                         uint[] b = right.data;
 965                         int ls = left.sign;
 966                         int rs = right.sign;
 967
 968                         bool neg_res = (ls == -1) ^ (rs == -1);
 969
 970                         uint[] result = new uint [Math.Max (a.Length, b.Length)];
 971
 972                         ulong ac = 1, bc = 1, borrow = 1;
 973
 974                         int i;
 975                         for (i = 0; i < result.Length; ++i) {
 976                                 uint va = 0;
 977                                 if (i < a.Length)
 978                                         va = a [i];
 979                                 if (ls == -1) {
 980                                         ac = ~va + ac;
 981                                         va = (uint)ac;
 982                                         ac = (uint)(ac >> 32);
 983                                 }
 984
 985                                 uint vb = 0;
 986                                 if (i < b.Length)
 987                                         vb = b [i];
 988                                 if (rs == -1) {
 989                                         bc = ~vb + bc;
 990                                         vb = (uint)bc;
 991                                         bc = (uint)(bc >> 32);
 992                                 }
 993
 994                                 uint word = va ^ vb;
 995
 996                                 if (neg_res) {
 997                                         borrow = word - borrow;
 998                                         word = ~(uint)borrow;
 999                                         borrow = (uint)(borrow >> 32) & 0x1u;
1000                                 }
1001
1002                                 result [i] = word;
1003                         }
1004
1005                         for (i = result.Length - 1; i >= 0 && result [i] == 0; --i) ;
1006                         if (i == -1)
1007                                 return new BigInteger (0, ZERO);
1008
1009                         if (i < result.Length - 1)
1010                                 result = Resize (result, i + 1);
1011
1012                         return new BigInteger (neg_res ? (short)-1 : (short)1, result);
1013                 }
1014
1015                 public static BigInteger operator~ (BigInteger value)
1016                 {
1017                         if (value.sign == 0)
1018                                 return new BigInteger (-1, ONE);
1019
1020                         uint[] data = value.data;
1021                         int sign = value.sign;
1022
1023                         bool neg_res = sign == 1;
1024
1025                         uint[] result = new uint [data.Length];
1026
1027                         ulong carry = 1, borrow = 1;
1028
1029                         int i;
1030                         for (i = 0; i < result.Length; ++i) {
1031                                 uint word = data [i];
1032                                 if (sign == -1) {
1033                                         carry = ~word + carry;
1034                                         word = (uint)carry;
1035                                         carry = (uint)(carry >> 32);
1036                                 }
1037
1038                                 word = ~word;
1039
1040                                 if (neg_res) {
1041                                         borrow = word - borrow;
1042                                         word = ~(uint)borrow;
1043                                         borrow = (uint)(borrow >> 32) & 0x1u;
1044                                 }
1045
1046                                 result [i] = word;
1047                         }
1048
1049                         for (i = result.Length - 1; i >= 0 && result [i] == 0; --i) ;
1050                         if (i == -1)
1051                                 return new BigInteger (0, ZERO);
1052
1053                         if (i < result.Length - 1)
1054                                 result = Resize (result, i + 1);
1055
1056                         return new BigInteger (neg_res ? (short)-1 : (short)1, result);
1057                 }
1058
1059                 //returns the 0-based index of the most significant set bit
1060                 //returns 0 if no bit is set, so extra care when using it
1061                 static int BitScanBackward (uint word)
1062                 {
1063                         for (int i = 31; i >= 0; --i) {
1064                                 uint mask = 1u << i;
1065                                 if ((word & mask) == mask)
1066                                         return i;
1067                         }
1068                         return 0;
1069                 }
1070
1071                 public static BigInteger operator<< (BigInteger value, int shift)
1072                 {
1073                         if (shift == 0 || value.sign == 0)
1074                                 return value;
1075                         if (shift < 0)
1076                                 return value >> -shift;
1077
1078                         uint[] data = value.data;
1079                         int sign = value.sign;
1080
1081                         int topMostIdx = BitScanBackward (data [data.Length - 1]);
1082                         int bits = shift - (31 - topMostIdx);
1083                         int extra_words = (bits >> 5) + ((bits & 0x1F) != 0 ? 1 : 0);
1084
1085                         uint[] res = new uint [data.Length + extra_words];
1086
1087                         int idx_shift = shift >> 5;
1088                         int bit_shift = shift & 0x1F;
1089                         int carry_shift = 32 - bit_shift;
1090
1091                         if (carry_shift == 32) {
1092                                 for (int i = 0; i < data.Length; ++i) {
1093                                         uint word = data [i];
1094                                         res [i + idx_shift] |= word << bit_shift;
1095                                 }
1096                         } else {
1097                                 for (int i = 0; i < data.Length; ++i) {
1098                                         uint word = data [i];
1099                                         res [i + idx_shift] |= word << bit_shift;
1100                                         if (i + idx_shift + 1 < res.Length)
1101                                                 res [i + idx_shift + 1] = word >> carry_shift;
1102                                 }
1103                         }
1104
1105                         return new BigInteger ((short)sign, res);
1106                 }
1107
1108                 public static BigInteger operator>> (BigInteger value, int shift)
1109                 {
1110                         if (shift == 0 || value.sign == 0)
1111                                 return value;
1112                         if (shift < 0)
1113                                 return value << -shift;
1114
1115                         uint[] data = value.data;
1116                         int sign = value.sign;
1117
1118                         int topMostIdx = BitScanBackward (data [data.Length - 1]);
1119                         int idx_shift = shift >> 5;
1120                         int bit_shift = shift & 0x1F;
1121
1122                         int extra_words = idx_shift;
1123                         if (bit_shift > topMostIdx)
1124                                 ++extra_words;
1125                         int size = data.Length - extra_words;
1126
1127                         if (size <= 0) {
1128                                 if (sign == 1)
1129                                         return new BigInteger (0, ZERO);
1130                                 return new BigInteger (-1, ONE);
1131                         }
1132
1133                         uint[] res = new uint [size];
1134                         int carry_shift = 32 - bit_shift;
1135
1136                         if (carry_shift == 32) {
1137                                 for (int i = data.Length - 1; i >= idx_shift; --i) {
1138                                         uint word = data [i];
1139
1140                                         if (i - idx_shift < res.Length)
1141                                                 res [i - idx_shift] |= word >> bit_shift;
1142                                 }
1143                         } else {
1144                                 for (int i = data.Length - 1; i >= idx_shift; --i) {
1145                                         uint word = data [i];
1146
1147                                         if (i - idx_shift < res.Length)
1148                                                 res [i - idx_shift] |= word >> bit_shift;
1149                                         if (i - idx_shift - 1 >= 0)
1150                                                 res [i - idx_shift - 1] = word << carry_shift;
1151                                 }
1152
1153                         }
1154
1155                         //Round down instead of toward zero
1156                         if (sign == -1) {
1157                                 for (int i = 0; i < idx_shift; i++) {
1158                                         if (data [i] != 0u) {
1159                                                 var tmp = new BigInteger ((short)sign, res);
1160                                                 --tmp;
1161                                                 return tmp;
1162                                         }
1163                                 }
1164                                 if (bit_shift > 0 && (data [idx_shift] << carry_shift) != 0u) {
1165                                         var tmp = new BigInteger ((short)sign, res);
1166                                         --tmp;
1167                                         return tmp;
1168                                 }
1169                         }
1170                         return new BigInteger ((short)sign, res);
1171                 }
1172
1173                 public static bool operator< (BigInteger left, BigInteger right)
1174                 {
1175                         return Compare (left, right) < 0;
1176                 }
1177
1178                 public static bool operator< (BigInteger left, long right)
1179                 {
1180                         return left.CompareTo (right) < 0;
1181                 }
1182
1183
1184                 public static bool operator< (long left, BigInteger right)
1185                 {
1186                         return right.CompareTo (left) > 0;
1187                 }
1188
1189
1190                 [CLSCompliantAttribute (false)]
1191                 public static bool operator< (BigInteger left, ulong right)
1192                 {
1193                         return left.CompareTo (right) < 0;
1194                 }
1195
1196                 [CLSCompliantAttribute (false)]
1197                 public static bool operator< (ulong left, BigInteger right)
1198                 {
1199                         return right.CompareTo (left) > 0;
1200                 }
1201
1202                 public static bool operator<= (BigInteger left, BigInteger right)
1203                 {
1204                         return Compare (left, right) <= 0;
1205                 }
1206
1207                 public static bool operator<= (BigInteger left, long right)
1208                 {
1209                         return left.CompareTo (right) <= 0;
1210                 }
1211
1212                 public static bool operator<= (long left, BigInteger right)
1213                 {
1214                         return right.CompareTo (left) >= 0;
1215                 }
1216
1217                 [CLSCompliantAttribute (false)]
1218                 public static bool operator<= (BigInteger left, ulong right)
1219                 {
1220                         return left.CompareTo (right) <= 0;
1221                 }
1222
1223                 [CLSCompliantAttribute (false)]
1224                 public static bool operator<= (ulong left, BigInteger right)
1225                 {
1226                         return right.CompareTo (left) >= 0;
1227                 }
1228
1229                 public static bool operator> (BigInteger left, BigInteger right)
1230                 {
1231                         return Compare (left, right) > 0;
1232                 }
1233
1234                 public static bool operator> (BigInteger left, long right)
1235                 {
1236                         return left.CompareTo (right) > 0;
1237                 }
1238
1239                 public static bool operator> (long left, BigInteger right)
1240                 {
1241                         return right.CompareTo (left) < 0;
1242                 }
1243
1244                 [CLSCompliantAttribute (false)]
1245                 public static bool operator> (BigInteger left, ulong right)
1246                 {
1247                         return left.CompareTo (right) > 0;
1248                 }
1249
1250                 [CLSCompliantAttribute (false)]
1251                 public static bool operator> (ulong left, BigInteger right)
1252                 {
1253                         return right.CompareTo (left) < 0;
1254                 }
1255
1256                 public static bool operator>= (BigInteger left, BigInteger right)
1257                 {
1258                         return Compare (left, right) >= 0;
1259                 }
1260
1261                 public static bool operator>= (BigInteger left, long right)
1262                 {
1263                         return left.CompareTo (right) >= 0;
1264                 }
1265
1266                 public static bool operator>= (long left, BigInteger right)
1267                 {
1268                         return right.CompareTo (left) <= 0;
1269                 }
1270
1271                 [CLSCompliantAttribute (false)]
1272                 public static bool operator>= (BigInteger left, ulong right)
1273                 {
1274                         return left.CompareTo (right) >= 0;
1275                 }
1276
1277                 [CLSCompliantAttribute (false)]
1278                 public static bool operator>= (ulong left, BigInteger right)
1279                 {
1280                         return right.CompareTo (left) <= 0;
1281                 }
1282
1283                 public static bool operator== (BigInteger left, BigInteger right)
1284                 {
1285                         return Compare (left, right) == 0;
1286                 }
1287
1288                 public static bool operator== (BigInteger left, long right)
1289                 {
1290                         return left.CompareTo (right) == 0;
1291                 }
1292
1293                 public static bool operator== (long left, BigInteger right)
1294                 {
1295                         return right.CompareTo (left) == 0;
1296                 }
1297
1298                 [CLSCompliantAttribute (false)]
1299                 public static bool operator== (BigInteger left, ulong right)
1300                 {
1301                         return left.CompareTo (right) == 0;
1302                 }
1303
1304                 [CLSCompliantAttribute (false)]
1305                 public static bool operator== (ulong left, BigInteger right)
1306                 {
1307                         return right.CompareTo (left) == 0;
1308                 }
1309
1310                 public static bool operator!= (BigInteger left, BigInteger right)
1311                 {
1312                         return Compare (left, right) != 0;
1313                 }
1314
1315                 public static bool operator!= (BigInteger left, long right)
1316                 {
1317                         return left.CompareTo (right) != 0;
1318                 }
1319
1320                 public static bool operator!= (long left, BigInteger right)
1321                 {
1322                         return right.CompareTo (left) != 0;
1323                 }
1324
1325                 [CLSCompliantAttribute (false)]
1326                 public static bool operator!= (BigInteger left, ulong right)
1327                 {
1328                         return left.CompareTo (right) != 0;
1329                 }
1330
1331                 [CLSCompliantAttribute (false)]
1332                 public static bool operator!= (ulong left, BigInteger right)
1333                 {
1334                         return right.CompareTo (left) != 0;
1335                 }
1336
1337                 public override bool Equals (object obj)
1338                 {
1339                         if (!(obj is BigInteger))
1340                                 return false;
1341                         return Equals ((BigInteger)obj);
1342                 }
1343
1344                 public bool Equals (BigInteger other)
1345                 {
1346                         if (sign != other.sign)
1347                                 return false;
1348
1349                         int alen = data != null ? data.Length : 0;
1350                         int blen = other.data != null ? other.data.Length : 0;
1351
1352                         if (alen != blen)
1353                                 return false;
1354                         for (int i = 0; i < alen; ++i) {
1355                                 if (data [i] != other.data [i])
1356                                         return false;
1357                         }
1358                         return true;
1359                 }
1360
1361                 public bool Equals (long other)
1362                 {
1363                         return CompareTo (other) == 0;
1364                 }
1365
1366                 public override string ToString ()
1367                 {
1368                         return ToString (10, null);
1369                 }
1370
1371                 string ToStringWithPadding (string format, uint radix, IFormatProvider provider)
1372                 {
1373                         if (format.Length > 1) {
1374                                 int precision = Convert.ToInt32(format.Substring (1), CultureInfo.InvariantCulture.NumberFormat);
1375                                 string baseStr = ToString (radix, provider);
1376                                 if (baseStr.Length < precision) {
1377                                         string additional = new String ('0', precision - baseStr.Length);
1378                                         if (baseStr[0] != '-') {
1379                                                 return additional + baseStr;
1380                                         } else {
1381                                                         return "-" + additional + baseStr.Substring (1);
1382                                         }
1383                                 }
1384                                 return baseStr;
1385                         }
1386                         return ToString (radix, provider);
1387                 }
1388
1389                 public string ToString (string format)
1390                 {
1391                         return ToString (format, null);
1392                 }
1393
1394                 public string ToString (IFormatProvider provider)
1395                 {
1396                         return ToString (null, provider);
1397                 }
1398
1399
1400                 public string ToString (string format, IFormatProvider provider)
1401                 {
1402                         if (format == null || format == "")
1403                                 return ToString (10, provider);
1404
1405                         switch (format[0]) {
1406                         case 'd':
1407                         case 'D':
1408                         case 'g':
1409                         case 'G':
1410                         case 'r':
1411                         case 'R':
1412                                 return ToStringWithPadding (format, 10, provider);
1413                         case 'x':
1414                         case 'X':
1415                                 return ToStringWithPadding (format, 16, null);
1416                         default:
1417                                 throw new FormatException (string.Format ("format '{0}' not implemented", format));
1418                         }
1419                 }
1420
1421                 static uint[] MakeTwoComplement (uint[] v)
1422                 {
1423                         uint[] res = new uint [v.Length];
1424
1425                         ulong carry = 1;
1426                         for (int i = 0; i < v.Length; ++i) {
1427                                 uint word = v [i];
1428                                 carry = (ulong)~word + carry;
1429                                 word = (uint)carry;
1430                                 carry = (uint)(carry >> 32);
1431                                 res [i] = word;
1432                         }
1433
1434                         uint last = res [res.Length - 1];
1435                         int idx = FirstNonFFByte (last);
1436                         uint mask = 0xFF;
1437                         for (int i = 1; i < idx; ++i)
1438                                 mask = (mask << 8) | 0xFF;
1439
1440                         res [res.Length - 1] = last & mask;
1441                         return res;
1442                 }
1443
1444                 string ToString (uint radix, IFormatProvider provider)
1445                 {
1446                         const string characterSet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
1447
1448                         if (characterSet.Length < radix)
1449                                 throw new ArgumentException ("charSet length less than radix", "characterSet");
1450                         if (radix == 1)
1451                                 throw new ArgumentException ("There is no such thing as radix one notation", "radix");
1452
1453                         if (sign == 0)
1454                                 return "0";
1455                         if (data.Length == 1 && data [0] == 1)
1456                                 return sign == 1 ? "1" : "-1";
1457
1458                         List<char> digits = new List<char> (1 + data.Length * 3 / 10);
1459
1460                         BigInteger a;
1461                         if (sign == 1)
1462                                 a = this;
1463                         else {
1464                                 uint[] dt = data;
1465                                 if (radix > 10)
1466                                         dt = MakeTwoComplement (dt);
1467                                 a = new BigInteger (1, dt);
1468                         }
1469
1470                         while (a != 0) {
1471                                 BigInteger rem;
1472                                 a = DivRem (a, radix, out rem);
1473                                 digits.Add (characterSet [(int) rem]);
1474                         }
1475
1476                         if (sign == -1 && radix == 10) {
1477                                 NumberFormatInfo info = null;
1478                                 if (provider != null)
1479                                         info = provider.GetFormat (typeof (NumberFormatInfo)) as NumberFormatInfo;
1480                                 if (info != null) {
1481                                         string str = info.NegativeSign;
1482                                         for (int i = str.Length - 1; i >= 0; --i)
1483                                                 digits.Add (str [i]);
1484                                 } else {
1485                                         digits.Add ('-');
1486                                 }
1487                         }
1488
1489                         char last = digits [digits.Count - 1];
1490                         if (sign == 1 && radix > 10 && (last < '0' || last > '9'))
1491                                 digits.Add ('0');
1492
1493                         digits.Reverse ();
1494
1495                         return new String (digits.ToArray ());
1496                 }
1497
1498                 public static BigInteger Parse (string value)
1499                 {
1500                         Exception ex;
1501                         BigInteger result;
1502
1503                         if (!Parse (value, false, out result, out ex))
1504                                 throw ex;
1505                         return result;
1506                 }
1507
1508                 public static bool TryParse (string value, out BigInteger result)
1509                 {
1510                         Exception ex;
1511                         return Parse (value, true, out result, out ex);
1512                 }
1513
1514                 public static BigInteger Parse (string value, NumberStyles style)
1515                 {
1516                         return Parse (value, style, null);
1517                 }
1518
1519                 public static BigInteger Parse (string value, IFormatProvider provider)
1520                 {
1521                         return Parse (value, NumberStyles.Integer, provider);
1522                 }
1523
1524                 public static BigInteger Parse (
1525                         string value, NumberStyles style, IFormatProvider provider)
1526                 {
1527                         Exception exc;
1528                         BigInteger res;
1529
1530                         if (!Parse (value, style, provider, false, out res, out exc))
1531                                 throw exc;
1532
1533                         return res;
1534                 }
1535
1536                 public static bool TryParse (
1537                         string value, NumberStyles style, IFormatProvider provider,
1538                         out BigInteger result)
1539                 {
1540                         Exception exc;
1541                         if (!Parse (value, style, provider, true, out result, out exc)) {
1542                                 result = Zero;
1543                                 return false;
1544                         }
1545
1546                         return true;
1547                 }
1548
1549                 internal static bool Parse (string s, NumberStyles style, IFormatProvider fp, bool tryParse, out BigInteger result, out Exception exc)
1550                 {
1551                         result = Zero;
1552                         exc = null;
1553
1554                         if (s == null) {
1555                                 if (!tryParse)
1556                                         exc = new ArgumentNullException ("s");
1557                                 return false;
1558                         }
1559
1560                         if (s.Length == 0) {
1561                                 if (!tryParse)
1562                                         exc = GetFormatException ();
1563                                 return false;
1564                         }
1565
1566                         NumberFormatInfo nfi = null;
1567                         if (fp != null) {
1568                                 Type typeNFI = typeof(System.Globalization.NumberFormatInfo);
1569                                 nfi = (NumberFormatInfo)fp.GetFormat (typeNFI);
1570                         }
1571                         if (nfi == null)
1572                                 nfi = Thread.CurrentThread.CurrentCulture.NumberFormat;
1573
1574                         if (!CheckStyle (style, tryParse, ref exc))
1575                                 return false;
1576
1577                         bool AllowCurrencySymbol = (style & NumberStyles.AllowCurrencySymbol) != 0;
1578                         bool AllowHexSpecifier = (style & NumberStyles.AllowHexSpecifier) != 0;
1579                         bool AllowThousands = (style & NumberStyles.AllowThousands) != 0;
1580                         bool AllowDecimalPoint = (style & NumberStyles.AllowDecimalPoint) != 0;
1581                         bool AllowParentheses = (style & NumberStyles.AllowParentheses) != 0;
1582                         bool AllowTrailingSign = (style & NumberStyles.AllowTrailingSign) != 0;
1583                         bool AllowLeadingSign = (style & NumberStyles.AllowLeadingSign) != 0;
1584                         bool AllowTrailingWhite = (style & NumberStyles.AllowTrailingWhite) != 0;
1585                         bool AllowLeadingWhite = (style & NumberStyles.AllowLeadingWhite) != 0;
1586                         bool AllowExponent = (style & NumberStyles.AllowExponent) != 0;
1587
1588                         int pos = 0;
1589
1590                         if (AllowLeadingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1591                                 return false;
1592
1593                         bool foundOpenParentheses = false;
1594                         bool negative = false;
1595                         bool foundSign = false;
1596                         bool foundCurrency = false;
1597
1598                         // Pre-number stuff
1599                         if (AllowParentheses && s [pos] == '(') {
1600                                 foundOpenParentheses = true;
1601                                 foundSign = true;
1602                                 negative = true; // MS always make the number negative when there parentheses
1603                                 // even when NumberFormatInfo.NumberNegativePattern != 0!!!
1604                                 pos++;
1605                                 if (AllowLeadingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1606                                         return false;
1607
1608                                 if (s.Substring (pos, nfi.NegativeSign.Length) == nfi.NegativeSign) {
1609                                         if (!tryParse)
1610                                                 exc = GetFormatException ();
1611                                         return false;
1612                                 }
1613
1614                                 if (s.Substring (pos, nfi.PositiveSign.Length) == nfi.PositiveSign) {
1615                                         if (!tryParse)
1616                                                 exc = GetFormatException ();
1617                                         return false;
1618                                 }
1619                         }
1620
1621                         if (AllowLeadingSign && !foundSign) {
1622                                 // Sign + Currency
1623                                 FindSign (ref pos, s, nfi, ref foundSign, ref negative);
1624                                 if (foundSign) {
1625                                         if (AllowLeadingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1626                                                 return false;
1627                                         if (AllowCurrencySymbol) {
1628                                                 FindCurrency (ref pos, s, nfi,
1629                                                               ref foundCurrency);
1630                                                 if (foundCurrency && AllowLeadingWhite &&
1631                                                         !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1632                                                         return false;
1633                                         }
1634                                 }
1635                         }
1636
1637                         if (AllowCurrencySymbol && !foundCurrency) {
1638                                 // Currency + sign
1639                                 FindCurrency (ref pos, s, nfi, ref foundCurrency);
1640                                 if (foundCurrency) {
1641                                         if (AllowLeadingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1642                                                 return false;
1643                                         if (foundCurrency) {
1644                                                 if (!foundSign && AllowLeadingSign) {
1645                                                         FindSign (ref pos, s, nfi, ref foundSign,
1646                                                                   ref negative);
1647                                                         if (foundSign && AllowLeadingWhite &&
1648                                                                 !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1649                                                                 return false;
1650                                                 }
1651                                         }
1652                                 }
1653                         }
1654
1655                         BigInteger number = Zero;
1656                         int nDigits = 0;
1657                         int decimalPointPos = -1;
1658                         byte digitValue;
1659                         char hexDigit;
1660                         bool firstHexDigit = true;
1661
1662                         // Number stuff
1663                         while (pos < s.Length) {
1664
1665                                 if (!ValidDigit (s [pos], AllowHexSpecifier)) {
1666                                         if (AllowThousands &&
1667                                                 (FindOther (ref pos, s, nfi.NumberGroupSeparator)
1668                                                 || FindOther (ref pos, s, nfi.CurrencyGroupSeparator)))
1669                                                 continue;
1670
1671                                         if (AllowDecimalPoint && decimalPointPos < 0 &&
1672                                                 (FindOther (ref pos, s, nfi.NumberDecimalSeparator)
1673                                                 || FindOther (ref pos, s, nfi.CurrencyDecimalSeparator))) {
1674                                                 decimalPointPos = nDigits;
1675                                                 continue;
1676                                         }
1677
1678                                         break;
1679                                 }
1680
1681                                 nDigits++;
1682
1683                                 if (AllowHexSpecifier) {
1684                                         hexDigit = s [pos++];
1685                                         if (Char.IsDigit (hexDigit))
1686                                                 digitValue = (byte)(hexDigit - '0');
1687                                         else if (Char.IsLower (hexDigit))
1688                                                 digitValue = (byte)(hexDigit - 'a' + 10);
1689                                         else
1690                                                 digitValue = (byte)(hexDigit - 'A' + 10);
1691
1692                                         if (firstHexDigit && (byte)digitValue >= 8)
1693                                                 negative = true;
1694
1695                                         number = number * 16 + digitValue;
1696                                         firstHexDigit = false;
1697                                         continue;
1698                                 }
1699
1700                                 number = number * 10 + (byte)(s [pos++] - '0');
1701                         }
1702
1703                         // Post number stuff
1704                         if (nDigits == 0) {
1705                                 if (!tryParse)
1706                                         exc = GetFormatException ();
1707                                 return false;
1708                         }
1709
1710                         //Signed hex value (Two's Complement)
1711                         if (AllowHexSpecifier && negative) {
1712                                 BigInteger mask = BigInteger.Pow(16, nDigits) - 1;
1713                                 number = (number ^ mask) + 1;
1714                         }
1715
1716                         int exponent = 0;
1717                         if (AllowExponent)
1718                                 if (FindExponent (ref pos, s, ref exponent, tryParse, ref exc) && exc != null)
1719                                         return false;
1720
1721                         if (AllowTrailingSign && !foundSign) {
1722                                 // Sign + Currency
1723                                 FindSign (ref pos, s, nfi, ref foundSign, ref negative);
1724                                 if (foundSign && pos < s.Length) {
1725                                         if (AllowTrailingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1726                                                 return false;
1727                                 }
1728                         }
1729
1730                         if (AllowCurrencySymbol && !foundCurrency) {
1731                                 if (AllowTrailingWhite && pos < s.Length && !JumpOverWhite (ref pos, s, false, tryParse, ref exc))
1732                                         return false;
1733
1734                                 // Currency + sign
1735                                 FindCurrency (ref pos, s, nfi, ref foundCurrency);
1736                                 if (foundCurrency  && pos < s.Length) {
1737                                         if (AllowTrailingWhite  && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1738                                                 return false;
1739                                         if (!foundSign && AllowTrailingSign)
1740                                                 FindSign (ref pos, s, nfi, ref foundSign,
1741                                                           ref negative);
1742                                 }
1743                         }
1744
1745                         if (AllowTrailingWhite && pos < s.Length && !JumpOverWhite (ref pos, s, false, tryParse, ref exc))
1746                                 return false;
1747
1748                         if (foundOpenParentheses) {
1749                                 if (pos >= s.Length || s [pos++] != ')') {
1750                                         if (!tryParse)
1751                                                 exc = GetFormatException ();
1752                                         return false;
1753                                 }
1754                                 if (AllowTrailingWhite && pos < s.Length && !JumpOverWhite (ref pos, s, false, tryParse, ref exc))
1755                                         return false;
1756                         }
1757
1758                         if (pos < s.Length && s [pos] != '\u0000') {
1759                                 if (!tryParse)
1760                                         exc = GetFormatException ();
1761                                 return false;
1762                         }
1763
1764                         if (decimalPointPos >= 0)
1765                                 exponent = exponent - nDigits + decimalPointPos;
1766
1767                         if (exponent < 0) {
1768                                 //
1769                                 // Any non-zero values after decimal point are not allowed
1770                                 //
1771                                 BigInteger remainder;
1772                                 number = BigInteger.DivRem(number, BigInteger.Pow(10, -exponent), out remainder);
1773
1774                                 if (!remainder.IsZero) {
1775                                         if (!tryParse)
1776                                                 exc = new OverflowException ("Value too large or too small. exp="+exponent+" rem = " + remainder + " pow = " + BigInteger.Pow(10, -exponent));
1777                                         return false;
1778                                 }
1779                         } else if (exponent > 0) {
1780                                 number = BigInteger.Pow(10, exponent) * number;
1781                         }
1782
1783                         if (number.sign == 0)
1784                                 result = number;
1785                         else if (negative)
1786                                 result = new BigInteger (-1, number.data);
1787                         else
1788                                 result = new BigInteger (1, number.data);
1789
1790                         return true;
1791                 }
1792
1793                 internal static bool CheckStyle (NumberStyles style, bool tryParse, ref Exception exc)
1794                 {
1795                         if ((style & NumberStyles.AllowHexSpecifier) != 0) {
1796                                 NumberStyles ne = style ^ NumberStyles.AllowHexSpecifier;
1797                                 if ((ne & NumberStyles.AllowLeadingWhite) != 0)
1798                                         ne ^= NumberStyles.AllowLeadingWhite;
1799                                 if ((ne & NumberStyles.AllowTrailingWhite) != 0)
1800                                         ne ^= NumberStyles.AllowTrailingWhite;
1801                                 if (ne != 0) {
1802                                         if (!tryParse)
1803                                                 exc = new ArgumentException (
1804                                                         "With AllowHexSpecifier only " +
1805                                                         "AllowLeadingWhite and AllowTrailingWhite " +
1806                                                         "are permitted.");
1807                                         return false;
1808                                 }
1809                         } else if ((uint) style > (uint) NumberStyles.Any){
1810                                 if (!tryParse)
1811                                         exc = new ArgumentException ("Not a valid number style");
1812                                 return false;
1813                         }
1814
1815                         return true;
1816                 }
1817
1818                 internal static bool JumpOverWhite (ref int pos, string s, bool reportError, bool tryParse, ref Exception exc)
1819                 {
1820                         while (pos < s.Length && Char.IsWhiteSpace (s [pos]))
1821                                 pos++;
1822
1823                         if (reportError && pos >= s.Length) {
1824                                 if (!tryParse)
1825                                         exc = GetFormatException ();
1826                                 return false;
1827                         }
1828
1829                         return true;
1830                 }
1831
1832                 internal static void FindSign (ref int pos, string s, NumberFormatInfo nfi,
1833                                       ref bool foundSign, ref bool negative)
1834                 {
1835                         if ((pos + nfi.NegativeSign.Length) <= s.Length &&
1836                             string.CompareOrdinal(s, pos, nfi.NegativeSign, 0, nfi.NegativeSign.Length) == 0) {
1837                                 negative = true;
1838                                 foundSign = true;
1839                                 pos += nfi.NegativeSign.Length;
1840                         } else if ((pos + nfi.PositiveSign.Length) <= s.Length &&
1841                             string.CompareOrdinal(s, pos, nfi.PositiveSign, 0, nfi.PositiveSign.Length) == 0) {
1842                                 negative = false;
1843                                 pos += nfi.PositiveSign.Length;
1844                                 foundSign = true;
1845                         }
1846                 }
1847
1848                 internal static void FindCurrency (ref int pos,
1849                                                  string s,
1850                                                  NumberFormatInfo nfi,
1851                                                  ref bool foundCurrency)
1852                 {
1853                         if ((pos + nfi.CurrencySymbol.Length) <= s.Length &&
1854                              s.Substring (pos, nfi.CurrencySymbol.Length) == nfi.CurrencySymbol) {
1855                                 foundCurrency = true;
1856                                 pos += nfi.CurrencySymbol.Length;
1857                         }
1858                 }
1859
1860                 internal static bool FindExponent (ref int pos, string s, ref int exponent, bool tryParse, ref Exception exc)
1861                 {
1862                         exponent = 0;
1863
1864                         if (pos >= s.Length || (s [pos] != 'e' && s[pos] != 'E')) {
1865                                 exc = null;
1866                                 return false;
1867                         }
1868
1869                         var i = pos + 1;
1870                         if (i == s.Length) {
1871                                 exc = tryParse ? null : GetFormatException ();
1872                                 return true;
1873                         }
1874
1875                         bool negative = false;
1876                         if (s [i] == '-') {
1877                                 negative = true;
1878                                 if(++i == s.Length){
1879                                         exc = tryParse ? null : GetFormatException ();
1880                                         return true;
1881                                 }
1882                         }
1883
1884                         if (s [i] == '+' && ++i == s.Length) {
1885                                 exc = tryParse ? null : GetFormatException ();
1886                                 return true;
1887                         }
1888
1889                         long exp = 0; // temp long value
1890                         for (; i < s.Length; i++) {
1891                                 if (!Char.IsDigit (s [i]))  {
1892                                         exc = tryParse ? null : GetFormatException ();
1893                                         return true;
1894                                 }
1895
1896                                 // Reduce the risk of throwing an overflow exc
1897                                 exp = checked (exp * 10 - (int) (s [i] - '0'));
1898                                 if (exp < Int32.MinValue || exp > Int32.MaxValue) {
1899                                         exc = tryParse ? null : new OverflowException ("Value too large or too small.");
1900                                         return true;
1901                                 }
1902                         }
1903
1904                         // exp value saved as negative
1905                         if(!negative)
1906                                 exp = -exp;
1907
1908                         exc = null;
1909                         exponent = (int)exp;
1910                         pos = i;
1911                         return true;
1912                 }
1913
1914                 internal static bool FindOther (ref int pos, string s, string other)
1915                 {
1916                         if ((pos + other.Length) <= s.Length &&
1917                              s.Substring (pos, other.Length) == other) {
1918                                 pos += other.Length;
1919                                 return true;
1920                         }
1921
1922                         return false;
1923                 }
1924
1925                 internal static bool ValidDigit (char e, bool allowHex)
1926                 {
1927                         if (allowHex)
1928                                 return Char.IsDigit (e) || (e >= 'A' && e <= 'F') || (e >= 'a' && e <= 'f');
1929
1930                         return Char.IsDigit (e);
1931                 }
1932
1933                 static Exception GetFormatException ()
1934                 {
1935                         return new FormatException ("Input string was not in the correct format");
1936                 }
1937
1938                 static bool ProcessTrailingWhitespace (bool tryParse, string s, int position, ref Exception exc)
1939                 {
1940                         int len = s.Length;
1941
1942                         for (int i = position; i < len; i++){
1943                                 char c = s [i];
1944
1945                                 if (c != 0 && !Char.IsWhiteSpace (c)){
1946                                         if (!tryParse)
1947                                                 exc = GetFormatException ();
1948                                         return false;
1949                                 }
1950                         }
1951                         return true;
1952                 }
1953
1954                 static bool Parse (string s, bool tryParse, out BigInteger result, out Exception exc)
1955                 {
1956                         int len;
1957                         int i, sign = 1;
1958                         bool digits_seen = false;
1959
1960                         result = Zero;
1961                         exc = null;
1962
1963                         if (s == null) {
1964                                 if (!tryParse)
1965                                         exc = new ArgumentNullException ("value");
1966                                 return false;
1967                         }
1968
1969                         len = s.Length;
1970
1971                         char c;
1972                         for (i = 0; i < len; i++){
1973                                 c = s [i];
1974                                 if (!Char.IsWhiteSpace (c))
1975                                         break;
1976                         }
1977
1978                         if (i == len) {
1979                                 if (!tryParse)
1980                                         exc = GetFormatException ();
1981                                 return false;
1982                         }
1983
1984                         var info = Thread.CurrentThread.CurrentCulture.NumberFormat;
1985
1986                         string negative = info.NegativeSign;
1987                         string positive = info.PositiveSign;
1988
1989                         if (string.CompareOrdinal (s, i, positive, 0, positive.Length) == 0)
1990                                 i += positive.Length;
1991                         else if (string.CompareOrdinal (s, i, negative, 0, negative.Length) == 0) {
1992                                 sign = -1;
1993                                 i += negative.Length;
1994                         }
1995
1996                         BigInteger val = Zero;
1997                         for (; i < len; i++){
1998                                 c = s [i];
1999
2000                                 if (c == '\0') {
2001                                         i = len;
2002                                         continue;
2003                                 }
2004
2005                                 if (c >= '0' && c <= '9'){
2006                                         byte d = (byte) (c - '0');
2007
2008                                         val = val * 10 + d;
2009
2010                                         digits_seen = true;
2011                                 } else if (!ProcessTrailingWhitespace (tryParse, s, i, ref exc))
2012                                         return false;
2013                         }
2014
2015                         if (!digits_seen) {
2016                                 if (!tryParse)
2017                                         exc = GetFormatException ();
2018                                 return false;
2019                         }
2020
2021                         if (val.sign == 0)
2022                                 result = val;
2023                         else if (sign == -1)
2024                                 result = new BigInteger (-1, val.data);
2025                         else
2026                                 result = new BigInteger (1, val.data);
2027
2028                         return true;
2029                 }
2030
2031                 public static BigInteger Min (BigInteger left, BigInteger right)
2032                 {
2033                         int ls = left.sign;
2034                         int rs = right.sign;
2035
2036                         if (ls < rs)
2037                                 return left;
2038                         if (rs < ls)
2039                                 return right;
2040
2041                         int r = CoreCompare (left.data, right.data);
2042                         if (ls == -1)
2043                                 r = -r;
2044
2045                         if (r <= 0)
2046                                 return left;
2047                         return right;
2048                 }
2049
2050
2051                 public static BigInteger Max (BigInteger left, BigInteger right)
2052                 {
2053                         int ls = left.sign;
2054                         int rs = right.sign;
2055
2056                         if (ls > rs)
2057                                 return left;
2058                         if (rs > ls)
2059                                 return right;
2060
2061                         int r = CoreCompare (left.data, right.data);
2062                         if (ls == -1)
2063                                 r = -r;
2064
2065                         if (r >= 0)
2066                                 return left;
2067                         return right;
2068                 }
2069
2070                 public static BigInteger Abs (BigInteger value)
2071                 {
2072                         return new BigInteger ((short)Math.Abs (value.sign), value.data);
2073                 }
2074
2075
2076                 public static BigInteger DivRem (BigInteger dividend, BigInteger divisor, out BigInteger remainder)
2077                 {
2078                         if (divisor.sign == 0)
2079                                 throw new DivideByZeroException ();
2080
2081                         if (dividend.sign == 0) {
2082                                 remainder = dividend;
2083                                 return dividend;
2084                         }
2085
2086                         uint[] quotient;
2087                         uint[] remainder_value;
2088
2089                         DivModUnsigned (dividend.data, divisor.data, out quotient, out remainder_value);
2090
2091                         int i;
2092                         for (i = remainder_value.Length - 1; i >= 0 && remainder_value [i] == 0; --i) ;
2093                         if (i == -1) {
2094                                 remainder = new BigInteger (0, ZERO);
2095                         } else {
2096                                 if (i < remainder_value.Length - 1)
2097                                         remainder_value = Resize (remainder_value, i + 1);
2098                                 remainder = new BigInteger (dividend.sign, remainder_value);
2099                         }
2100
2101                         for (i = quotient.Length - 1; i >= 0 && quotient [i] == 0; --i) ;
2102                         if (i == -1)
2103                                 return new BigInteger (0, ZERO);
2104                         if (i < quotient.Length - 1)
2105                                 quotient = Resize (quotient, i + 1);
2106
2107                         return new BigInteger ((short)(dividend.sign * divisor.sign), quotient);
2108                 }
2109
2110         public static BigInteger Pow (BigInteger value, int exponent)
2111                 {
2112                         if (exponent < 0)
2113                                 throw new ArgumentOutOfRangeException("exponent", "exp must be >= 0");
2114                         if (exponent == 0)
2115                                 return One;
2116                         if (exponent == 1)
2117                                 return value;
2118
2119                         BigInteger result = One;
2120                         while (exponent != 0) {
2121                                 if ((exponent & 1) != 0)
2122                                         result = result * value;
2123                                 if (exponent == 1)
2124                                         break;
2125
2126                                 value = value * value;
2127                                 exponent >>= 1;
2128                         }
2129                         return result;
2130         }
2131
2132                 public static BigInteger ModPow (BigInteger value, BigInteger exponent, BigInteger modulus) {
2133                         if (exponent.sign == -1)
2134                                 throw new ArgumentOutOfRangeException("exponent", "power must be >= 0");
2135                         if (modulus.sign == 0)
2136                                 throw new DivideByZeroException ();
2137
2138                         BigInteger result = One % modulus;
2139                         while (exponent.sign != 0) {
2140                                 if (!exponent.IsEven) {
2141                                         result = result * value;
2142                                         result = result % modulus;
2143                                 }
2144                                 if (exponent.IsOne)
2145                                         break;
2146                                 value = value * value;
2147                                 value = value % modulus;
2148                                 exponent >>= 1;
2149                         }
2150                         return result;
2151                 }
2152
2153                 public static BigInteger GreatestCommonDivisor (BigInteger left, BigInteger right)
2154                 {
2155                         if (left.sign != 0 && left.data.Length == 1 && left.data [0] == 1)
2156                                 return new BigInteger (1, ONE);
2157                         if (right.sign != 0 && right.data.Length == 1 && right.data [0] == 1)
2158                                 return new BigInteger (1, ONE);
2159                         if (left.IsZero)
2160                                 return Abs(right);
2161                         if (right.IsZero)
2162                                 return Abs(left);
2163
2164                         BigInteger x = new BigInteger (1, left.data);
2165                         BigInteger y = new BigInteger (1, right.data);
2166
2167                         BigInteger g = y;
2168
2169                         while (x.data.Length > 1) {
2170                                 g = x;
2171                                 x = y % x;
2172                                 y = g;
2173
2174                         }
2175                         if (x.IsZero) return g;
2176
2177                         // TODO: should we have something here if we can convert to long?
2178
2179                         //
2180                         // Now we can just do it with single precision. I am using the binary gcd method,
2181                         // as it should be faster.
2182                         //
2183
2184                         uint yy = x.data [0];
2185                         uint xx = (uint)(y % yy);
2186
2187                         int t = 0;
2188
2189                         while (((xx | yy) & 1) == 0) {
2190                                 xx >>= 1; yy >>= 1; t++;
2191                         }
2192                         while (xx != 0) {
2193                                 while ((xx & 1) == 0) xx >>= 1;
2194                                 while ((yy & 1) == 0) yy >>= 1;
2195                                 if (xx >= yy)
2196                                         xx = (xx - yy) >> 1;
2197                                 else
2198                                         yy = (yy - xx) >> 1;
2199                         }
2200
2201                         return yy << t;
2202                 }
2203
2204                 /*LAMESPEC Log doesn't specify to how many ulp is has to be precise
2205                 We are equilavent to MS with about 2 ULP
2206                 */
2207                 public static double Log (BigInteger value, Double baseValue)
2208                 {
2209                         if (value.sign == -1 || baseValue == 1.0d || baseValue == -1.0d ||
2210                                         baseValue == Double.NegativeInfinity || double.IsNaN (baseValue))
2211                                 return double.NaN;
2212
2213                         if (baseValue == 0.0d || baseValue == Double.PositiveInfinity)
2214                                 return value.IsOne ? 0 : double.NaN;
2215
2216                         if (value.sign == 0)
2217                                 return double.NegativeInfinity;
2218
2219                         int length = value.data.Length - 1;
2220                         int bitCount = -1;
2221                         for (int curBit = 31; curBit >= 0; curBit--) {
2222                                 if ((value.data [length] & (1 << curBit)) != 0) {
2223                                         bitCount = curBit + length * 32;
2224                                         break;
2225                                 }
2226                         }
2227
2228                         long bitlen = bitCount;
2229                         Double c = 0, d = 1;
2230
2231                         BigInteger testBit = One;
2232                         long tempBitlen = bitlen;
2233                         while (tempBitlen > Int32.MaxValue) {
2234                                 testBit = testBit << Int32.MaxValue;
2235                                 tempBitlen -= Int32.MaxValue;
2236                         }
2237                         testBit = testBit << (int)tempBitlen;
2238
2239                         for (long curbit = bitlen; curbit >= 0; --curbit) {
2240                                 if ((value & testBit).sign != 0)
2241                                         c += d;
2242                                 d *= 0.5;
2243                                 testBit = testBit >> 1;
2244                         }
2245                         return (System.Math.Log (c) + System.Math.Log (2) * bitlen) / System.Math.Log (baseValue);
2246                 }
2247
2248
2249         public static double Log (BigInteger value)
2250                 {
2251             return Log (value, Math.E);
2252         }
2253
2254
2255         public static double Log10 (BigInteger value)
2256                 {
2257             return Log (value, 10);
2258         }
2259
2260                 [CLSCompliantAttribute (false)]
2261                 public bool Equals (ulong other)
2262                 {
2263                         return CompareTo (other) == 0;
2264                 }
2265
2266                 public override int GetHashCode ()
2267                 {
2268                         uint hash = (uint)(sign * 0x01010101u);
2269                         int len = data != null ? data.Length : 0;
2270
2271                         for (int i = 0; i < len; ++i)
2272                                 hash ^= data [i];
2273                         return (int)hash;
2274                 }
2275
2276                 public static BigInteger Add (BigInteger left, BigInteger right)
2277                 {
2278                         return left + right;
2279                 }
2280
2281                 public static BigInteger Subtract (BigInteger left, BigInteger right)
2282                 {
2283                         return left - right;
2284                 }
2285
2286                 public static BigInteger Multiply (BigInteger left, BigInteger right)
2287                 {
2288                         return left * right;
2289                 }
2290
2291                 public static BigInteger Divide (BigInteger dividend, BigInteger divisor)
2292                 {
2293                         return dividend / divisor;
2294                 }
2295
2296                 public static BigInteger Remainder (BigInteger dividend, BigInteger divisor)
2297                 {
2298                         return dividend % divisor;
2299                 }
2300
2301                 public static BigInteger Negate (BigInteger value)
2302                 {
2303                         return - value;
2304                 }
2305
2306                 public int CompareTo (object obj)
2307                 {
2308                         if (obj == null)
2309                                 return 1;
2310
2311                         if (!(obj is BigInteger))
2312                                 return -1;
2313
2314                         return Compare (this, (BigInteger)obj);
2315                 }
2316
2317                 public int CompareTo (BigInteger other)
2318                 {
2319                         return Compare (this, other);
2320                 }
2321
2322                 [CLSCompliantAttribute (false)]
2323                 public int CompareTo (ulong other)
2324                 {
2325                         if (sign < 0)
2326                                 return -1;
2327                         if (sign == 0)
2328                                 return other == 0 ? 0 : -1;
2329
2330                         if (data.Length > 2)
2331                                 return 1;
2332
2333                         uint high = (uint)(other >> 32);
2334                         uint low = (uint)other;
2335
2336                         return LongCompare (low, high);
2337                 }
2338
2339                 int LongCompare (uint low, uint high)
2340                 {
2341                         uint h = 0;
2342                         if (data.Length > 1)
2343                                 h = data [1];
2344
2345                         if (h > high)
2346                                 return 1;
2347                         if (h < high)
2348                                 return -1;
2349
2350                         uint l = data [0];
2351
2352                         if (l > low)
2353                                 return 1;
2354                         if (l < low)
2355                                 return -1;
2356
2357                         return 0;
2358                 }
2359
2360                 public int CompareTo (long other)
2361                 {
2362                         int ls = sign;
2363                         int rs = Math.Sign (other);
2364
2365                         if (ls != rs)
2366                                 return ls > rs ? 1 : -1;
2367
2368                         if (ls == 0)
2369                                 return 0;
2370
2371                         if (data.Length > 2)
2372                                 return sign;
2373
2374                         if (other < 0)
2375                                 other = -other;
2376                         uint low = (uint)other;
2377                         uint high = (uint)((ulong)other >> 32);
2378
2379                         int r = LongCompare (low, high);
2380                         if (ls == -1)
2381                                 r = -r;
2382
2383                         return r;
2384                 }
2385
2386                 public static int Compare (BigInteger left, BigInteger right)
2387                 {
2388                         int ls = left.sign;
2389                         int rs = right.sign;
2390
2391                         if (ls != rs)
2392                                 return ls > rs ? 1 : -1;
2393
2394                         int r = CoreCompare (left.data, right.data);
2395                         if (ls < 0)
2396                                 r = -r;
2397                         return r;
2398                 }
2399
2400
2401                 static int TopByte (uint x)
2402                 {
2403                         if ((x & 0xFFFF0000u) != 0) {
2404                                 if ((x & 0xFF000000u) != 0)
2405                                         return 4;
2406                                 return 3;
2407                         }
2408                         if ((x & 0xFF00u) != 0)
2409                                 return 2;
2410                         return 1;
2411                 }
2412
2413                 static int FirstNonFFByte (uint word)
2414                 {
2415                         if ((word & 0xFF000000u) != 0xFF000000u)
2416                                 return 4;
2417                         else if ((word & 0xFF0000u) != 0xFF0000u)
2418                                 return 3;
2419                         else if ((word & 0xFF00u) != 0xFF00u)
2420                                 return 2;
2421                         return 1;
2422                 }
2423
2424                 public byte[] ToByteArray ()
2425                 {
2426                         if (sign == 0)
2427                                 return new byte [1];
2428
2429                         //number of bytes not counting upper word
2430                         int bytes = (data.Length - 1) * 4;
2431                         bool needExtraZero = false;
2432
2433                         uint topWord = data [data.Length - 1];
2434                         int extra;
2435
2436                         //if the topmost bit is set we need an extra
2437                         if (sign == 1) {
2438                                 extra = TopByte (topWord);
2439                                 uint mask = 0x80u << ((extra - 1) * 8);
2440                                 if ((topWord & mask) != 0) {
2441                                         needExtraZero = true;
2442                                 }
2443                         } else {
2444                                 extra = TopByte (topWord);
2445                         }
2446
2447                         byte[] res = new byte [bytes + extra + (needExtraZero ? 1 : 0) ];
2448                         if (sign == 1) {
2449                                 int j = 0;
2450                                 int end = data.Length - 1;
2451                                 for (int i = 0; i < end; ++i) {
2452                                         uint word = data [i];
2453
2454                                         res [j++] = (byte)word;
2455                                         res [j++] = (byte)(word >> 8);
2456                                         res [j++] = (byte)(word >> 16);
2457                                         res [j++] = (byte)(word >> 24);
2458                                 }
2459                                 while (extra-- > 0) {
2460                                         res [j++] = (byte)topWord;
2461                                         topWord >>= 8;
2462                                 }
2463                         } else {
2464                                 int j = 0;
2465                                 int end = data.Length - 1;
2466
2467                                 uint carry = 1, word;
2468                                 ulong add;
2469                                 for (int i = 0; i < end; ++i) {
2470                                         word = data [i];
2471                                         add = (ulong)~word + carry;
2472                                         word = (uint)add;
2473                                         carry = (uint)(add >> 32);
2474
2475                                         res [j++] = (byte)word;
2476                                         res [j++] = (byte)(word >> 8);
2477                                         res [j++] = (byte)(word >> 16);
2478                                         res [j++] = (byte)(word >> 24);
2479                                 }
2480
2481                                 add = (ulong)~topWord + (carry);
2482                                 word = (uint)add;
2483                                 carry = (uint)(add >> 32);
2484                                 if (carry == 0) {
2485                                         int ex = FirstNonFFByte (word);
2486                                         bool needExtra = (word & (1 << (ex * 8 - 1))) == 0;
2487                                         int to = ex + (needExtra ? 1 : 0);
2488
2489                                         if (to != extra)
2490                                                 res = Resize (res, bytes + to);
2491
2492                                         while (ex-- > 0) {
2493                                                 res [j++] = (byte)word;
2494                                                 word >>= 8;
2495                                         }
2496                                         if (needExtra)
2497                                                 res [j++] = 0xFF;
2498                                 } else {
2499                                         res = Resize (res, bytes + 5);
2500                                         res [j++] = (byte)word;
2501                                         res [j++] = (byte)(word >> 8);
2502                                         res [j++] = (byte)(word >> 16);
2503                                         res [j++] = (byte)(word >> 24);
2504                                         res [j++] = 0xFF;
2505                                 }
2506                         }
2507
2508                         return res;
2509                 }
2510
2511                 static byte[] Resize (byte[] v, int len)
2512                 {
2513                         byte[] res = new byte [len];
2514                         Array.Copy (v, res, Math.Min (v.Length, len));
2515                         return res;
2516                 }
2517
2518                 static uint[] Resize (uint[] v, int len)
2519                 {
2520                         uint[] res = new uint [len];
2521                         Array.Copy (v, res, Math.Min (v.Length, len));
2522                         return res;
2523                 }
2524
2525                 static uint[] CoreAdd (uint[] a, uint[] b)
2526                 {
2527                         if (a.Length < b.Length) {
2528                                 uint[] tmp = a;
2529                                 a = b;
2530                                 b = tmp;
2531                         }
2532
2533                         int bl = a.Length;
2534                         int sl = b.Length;
2535
2536                         uint[] res = new uint [bl];
2537
2538                         ulong sum = 0;
2539
2540                         int i = 0;
2541                         for (; i < sl; i++) {
2542                                 sum = sum + a [i] + b [i];
2543                                 res [i] = (uint)sum;
2544                                 sum >>= 32;
2545                         }
2546
2547                         for (; i < bl; i++) {
2548                                 sum = sum + a [i];
2549                                 res [i] = (uint)sum;
2550                                 sum >>= 32;
2551                         }
2552
2553                         if (sum != 0) {
2554                                 res = Resize (res, bl + 1);
2555                                 res [i] = (uint)sum;
2556                         }
2557
2558                         return res;
2559                 }
2560
2561                 /*invariant a > b*/
2562                 static uint[] CoreSub (uint[] a, uint[] b)
2563                 {
2564                         int bl = a.Length;
2565                         int sl = b.Length;
2566
2567                         uint[] res = new uint [bl];
2568
2569                         ulong borrow = 0;
2570                         int i;
2571                         for (i = 0; i < sl; ++i) {
2572                                 borrow = (ulong)a [i] - b [i] - borrow;
2573
2574                                 res [i] = (uint)borrow;
2575                                 borrow = (borrow >> 32) & 0x1;
2576                         }
2577
2578                         for (; i < bl; i++) {
2579                                 borrow = (ulong)a [i] - borrow;
2580                                 res [i] = (uint)borrow;
2581                                 borrow = (borrow >> 32) & 0x1;
2582                         }
2583
2584                         //remove extra zeroes
2585                         for (i = bl - 1; i >= 0 && res [i] == 0; --i) ;
2586                         if (i < bl - 1)
2587                                 res = Resize (res, i + 1);
2588
2589             return res;
2590                 }
2591
2592
2593                 static uint[] CoreAdd (uint[] a, uint b)
2594                 {
2595                         int len = a.Length;
2596                         uint[] res = new uint [len];
2597
2598                         ulong sum = b;
2599                         int i;
2600                         for (i = 0; i < len; i++) {
2601                                 sum = sum + a [i];
2602                                 res [i] = (uint)sum;
2603                                 sum >>= 32;
2604                         }
2605
2606                         if (sum != 0) {
2607                                 res = Resize (res, len + 1);
2608                                 res [i] = (uint)sum;
2609                         }
2610
2611                         return res;
2612                 }
2613
2614                 static uint[] CoreSub (uint[] a, uint b)
2615                 {
2616                         int len = a.Length;
2617                         uint[] res = new uint [len];
2618
2619                         ulong borrow = b;
2620                         int i;
2621                         for (i = 0; i < len; i++) {
2622                                 borrow = (ulong)a [i] - borrow;
2623                                 res [i] = (uint)borrow;
2624                                 borrow = (borrow >> 32) & 0x1;
2625                         }
2626
2627                         //remove extra zeroes
2628                         for (i = len - 1; i >= 0 && res [i] == 0; --i) ;
2629                         if (i < len - 1)
2630                                 res = Resize (res, i + 1);
2631
2632             return res;
2633                 }
2634
2635                 static int CoreCompare (uint[] a, uint[] b)
2636                 {
2637                         int al = a != null ? a.Length : 0;
2638                         int bl = b != null ? b.Length : 0;
2639
2640                         if (al > bl)
2641                                 return 1;
2642                         if (bl > al)
2643                                 return -1;
2644
2645                         for (int i = al - 1; i >= 0; --i) {
2646                                 uint ai = a [i];
2647                                 uint bi = b [i];
2648                                 if (ai > bi)
2649                                         return 1;
2650                                 if (ai < bi)
2651                                         return -1;
2652                         }
2653                         return 0;
2654                 }
2655
2656                 static int GetNormalizeShift(uint value) {
2657                         int shift = 0;
2658
2659                         if ((value & 0xFFFF0000) == 0) { value <<= 16; shift += 16; }
2660                         if ((value & 0xFF000000) == 0) { value <<= 8; shift += 8; }
2661                         if ((value & 0xF0000000) == 0) { value <<= 4; shift += 4; }
2662                         if ((value & 0xC0000000) == 0) { value <<= 2; shift += 2; }
2663                         if ((value & 0x80000000) == 0) { value <<= 1; shift += 1; }
2664
2665                         return shift;
2666                 }
2667
2668                 static void Normalize (uint[] u, int l, uint[] un, int shift)
2669                 {
2670                         uint carry = 0;
2671                         int i;
2672                         if (shift > 0) {
2673                                 int rshift = 32 - shift;
2674                                 for (i = 0; i < l; i++) {
2675                                         uint ui = u [i];
2676                                         un [i] = (ui << shift) | carry;
2677                                         carry = ui >> rshift;
2678                                 }
2679                         } else {
2680                                 for (i = 0; i < l; i++) {
2681                                         un [i] = u [i];
2682                                 }
2683                         }
2684
2685                         while (i < un.Length) {
2686                                 un [i++] = 0;
2687                         }
2688
2689                         if (carry != 0) {
2690                                 un [l] = carry;
2691                         }
2692                 }
2693
2694                 static void Unnormalize (uint[] un, out uint[] r, int shift)
2695                 {
2696                         int length = un.Length;
2697                         r = new uint [length];
2698
2699                         if (shift > 0) {
2700                                 int lshift = 32 - shift;
2701                                 uint carry = 0;
2702                                 for (int i = length - 1; i >= 0; i--) {
2703                                         uint uni = un [i];
2704                                         r [i] = (uni >> shift) | carry;
2705                                         carry = (uni << lshift);
2706                                 }
2707                         } else {
2708                                 for (int i = 0; i < length; i++) {
2709                                         r [i] = un [i];
2710                                 }
2711                         }
2712                 }
2713
2714                 const ulong Base = 0x100000000;
2715                 static void DivModUnsigned (uint[] u, uint[] v, out uint[] q, out uint[] r)
2716                 {
2717                         int m = u.Length;
2718                         int n = v.Length;
2719
2720                         if (n <= 1) {
2721                                 //  Divide by single digit
2722                                 //
2723                                 ulong rem = 0;
2724                                 uint v0 = v [0];
2725                                 q = new uint[m];
2726                                 r = new uint [1];
2727
2728                                 for (int j = m - 1; j >= 0; j--) {
2729                                         rem *= Base;
2730                                         rem += u[j];
2731
2732                                         ulong div = rem / v0;
2733                                         rem -= div * v0;
2734                                         q[j] = (uint)div;
2735                                 }
2736                                 r [0] = (uint)rem;
2737                         } else if (m >= n) {
2738                                 int shift = GetNormalizeShift (v [n - 1]);
2739
2740                                 uint[] un = new uint [m + 1];
2741                                 uint[] vn = new uint [n];
2742
2743                                 Normalize (u, m, un, shift);
2744                                 Normalize (v, n, vn, shift);
2745
2746                                 q = new uint [m - n + 1];
2747                                 r = null;
2748
2749                                 //  Main division loop
2750                                 //
2751                                 for (int j = m - n; j >= 0; j--) {
2752                                         ulong rr, qq;
2753                                         int i;
2754
2755                                         rr = Base * un [j + n] + un [j + n - 1];
2756                                         qq = rr / vn [n - 1];
2757                                         rr -= qq * vn [n - 1];
2758
2759                                         for (; ; ) {
2760                                                 // Estimate too big ?
2761                                                 //
2762                                                 if ((qq >= Base) || (qq * vn [n - 2] > (rr * Base + un [j + n - 2]))) {
2763                                                         qq--;
2764                                                         rr += (ulong)vn [n - 1];
2765                                                         if (rr < Base)
2766                                                                 continue;
2767                                                 }
2768                                                 break;
2769                                         }
2770
2771
2772                                         //  Multiply and subtract
2773                                         //
2774                                         long b = 0;
2775                                         long t = 0;
2776                                         for (i = 0; i < n; i++) {
2777                                                 ulong p = vn [i] * qq;
2778                                                 t = (long)un [i + j] - (long)(uint)p - b;
2779                                                 un [i + j] = (uint)t;
2780                                                 p >>= 32;
2781                                                 t >>= 32;
2782                                                 b = (long)p - t;
2783                                         }
2784                                         t = (long)un [j + n] - b;
2785                                         un [j + n] = (uint)t;
2786
2787                                         //  Store the calculated value
2788                                         //
2789                                         q [j] = (uint)qq;
2790
2791                                         //  Add back vn[0..n] to un[j..j+n]
2792                                         //
2793                                         if (t < 0) {
2794                                                 q [j]--;
2795                                                 ulong c = 0;
2796                                                 for (i = 0; i < n; i++) {
2797                                                         c = (ulong)vn [i] + un [j + i] + c;
2798                                                         un [j + i] = (uint)c;
2799                                                         c >>= 32;
2800                                                 }
2801                                                 c += (ulong)un [j + n];
2802                                                 un [j + n] = (uint)c;
2803                                         }
2804                                 }
2805
2806                                 Unnormalize (un, out r, shift);
2807                         } else {
2808                                 q = new uint [] { 0 };
2809                                 r = u;
2810                         }
2811                 }
2812         }
2813 }