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

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