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

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