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
1678                         if (AllowHexSpecifier && negative) {
1679                                 //number = 123456;
1680                                 BigInteger mask = BigInteger.Pow(16, nDigits) - 1;
1681                                 number = (number ^ mask) + 1;
1682                         }
1683
1684                         int exponent = 0;
1685                         if (AllowExponent)
1686                                 if (FindExponent (ref pos, s, ref exponent, tryParse, ref exc) && exc != null)
1687                                         return false;
1688
1689                         if (AllowTrailingSign && !foundSign) {
1690                                 // Sign + Currency
1691                                 FindSign (ref pos, s, nfi, ref foundSign, ref negative);
1692                                 if (foundSign && pos < s.Length) {
1693                                         if (AllowTrailingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1694                                                 return false;
1695                                 }
1696                         }
1697
1698                         if (AllowCurrencySymbol && !foundCurrency) {
1699                                 if (AllowTrailingWhite && pos < s.Length && !JumpOverWhite (ref pos, s, false, tryParse, ref exc))
1700                                         return false;
1701
1702                                 // Currency + sign
1703                                 FindCurrency (ref pos, s, nfi, ref foundCurrency);
1704                                 if (foundCurrency  && pos < s.Length) {
1705                                         if (AllowTrailingWhite  && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1706                                                 return false;
1707                                         if (!foundSign && AllowTrailingSign)
1708                                                 FindSign (ref pos, s, nfi, ref foundSign,
1709                                                           ref negative);
1710                                 }
1711                         }
1712
1713                         if (AllowTrailingWhite && pos < s.Length && !JumpOverWhite (ref pos, s, false, tryParse, ref exc))
1714                                 return false;
1715
1716                         if (foundOpenParentheses) {
1717                                 if (pos >= s.Length || s [pos++] != ')') {
1718                                         if (!tryParse)
1719                                                 exc = GetFormatException ();
1720                                         return false;
1721                                 }
1722                                 if (AllowTrailingWhite && pos < s.Length && !JumpOverWhite (ref pos, s, false, tryParse, ref exc))
1723                                         return false;
1724                         }
1725
1726                         if (pos < s.Length && s [pos] != '\u0000') {
1727                                 if (!tryParse)
1728                                         exc = GetFormatException ();
1729                                 return false;
1730                         }
1731
1732                         if (decimalPointPos >= 0)
1733                                 exponent = exponent - nDigits + decimalPointPos;
1734
1735                         if (exponent < 0) {
1736                                 //
1737                                 // Any non-zero values after decimal point are not allowed
1738                                 //
1739                                 BigInteger remainder;
1740                                 number = BigInteger.DivRem(number, BigInteger.Pow(10, -exponent), out remainder);
1741
1742                                 if (!remainder.IsZero) {
1743                                         if (!tryParse)
1744                                                 exc = new OverflowException ("Value too large or too small. exp="+exponent+" rem = " + remainder + " pow = " + BigInteger.Pow(10, -exponent));
1745                                         return false;
1746                                 }
1747                         } else if (exponent > 0) {
1748                                 number = BigInteger.Pow(10, exponent) * number;
1749                         }
1750
1751                         if (number.sign == 0)
1752                                 result = number;
1753                         else if (negative)
1754                                 result = new BigInteger (-1, number.data);
1755                         else
1756                                 result = new BigInteger (1, number.data);
1757
1758                         return true;
1759                 }
1760
1761                 internal static bool CheckStyle (NumberStyles style, bool tryParse, ref Exception exc)
1762                 {
1763                         if ((style & NumberStyles.AllowHexSpecifier) != 0) {
1764                                 NumberStyles ne = style ^ NumberStyles.AllowHexSpecifier;
1765                                 if ((ne & NumberStyles.AllowLeadingWhite) != 0)
1766                                         ne ^= NumberStyles.AllowLeadingWhite;
1767                                 if ((ne & NumberStyles.AllowTrailingWhite) != 0)
1768                                         ne ^= NumberStyles.AllowTrailingWhite;
1769                                 if (ne != 0) {
1770                                         if (!tryParse)
1771                                                 exc = new ArgumentException (
1772                                                         "With AllowHexSpecifier only " +
1773                                                         "AllowLeadingWhite and AllowTrailingWhite " +
1774                                                         "are permitted.");
1775                                         return false;
1776                                 }
1777                         } else if ((uint) style > (uint) NumberStyles.Any){
1778                                 if (!tryParse)
1779                                         exc = new ArgumentException ("Not a valid number style");
1780                                 return false;
1781                         }
1782
1783                         return true;
1784                 }
1785
1786                 internal static bool JumpOverWhite (ref int pos, string s, bool reportError, bool tryParse, ref Exception exc)
1787                 {
1788                         while (pos < s.Length && Char.IsWhiteSpace (s [pos]))
1789                                 pos++;
1790
1791                         if (reportError && pos >= s.Length) {
1792                                 if (!tryParse)
1793                                         exc = GetFormatException ();
1794                                 return false;
1795                         }
1796
1797                         return true;
1798                 }
1799
1800                 internal static void FindSign (ref int pos, string s, NumberFormatInfo nfi,
1801                                       ref bool foundSign, ref bool negative)
1802                 {
1803                         if ((pos + nfi.NegativeSign.Length) <= s.Length &&
1804                             string.CompareOrdinal(s, pos, nfi.NegativeSign, 0, nfi.NegativeSign.Length) == 0) {
1805                                 negative = true;
1806                                 foundSign = true;
1807                                 pos += nfi.NegativeSign.Length;
1808                         } else if ((pos + nfi.PositiveSign.Length) <= s.Length &&
1809                             string.CompareOrdinal(s, pos, nfi.PositiveSign, 0, nfi.PositiveSign.Length) == 0) {
1810                                 negative = false;
1811                                 pos += nfi.PositiveSign.Length;
1812                                 foundSign = true;
1813                         }
1814                 }
1815
1816                 internal static void FindCurrency (ref int pos,
1817                                                  string s,
1818                                                  NumberFormatInfo nfi,
1819                                                  ref bool foundCurrency)
1820                 {
1821                         if ((pos + nfi.CurrencySymbol.Length) <= s.Length &&
1822                              s.Substring (pos, nfi.CurrencySymbol.Length) == nfi.CurrencySymbol) {
1823                                 foundCurrency = true;
1824                                 pos += nfi.CurrencySymbol.Length;
1825                         }
1826                 }
1827
1828                 internal static bool FindExponent (ref int pos, string s, ref int exponent, bool tryParse, ref Exception exc)
1829                 {
1830                         exponent = 0;
1831
1832                         if (pos >= s.Length || (s [pos] != 'e' && s[pos] != 'E')) {
1833                                 exc = null;
1834                                 return false;
1835                         }
1836
1837                         var i = pos + 1;
1838                         if (i == s.Length) {
1839                                 exc = tryParse ? null : GetFormatException ();
1840                                 return true;
1841                         }
1842
1843                         bool negative = false;
1844                         if (s [i] == '-') {
1845                                 negative = true;
1846                                 if(++i == s.Length){
1847                                         exc = tryParse ? null : GetFormatException ();
1848                                         return true;
1849                                 }
1850                         }
1851
1852                         if (s [i] == '+' && ++i == s.Length) {
1853                                 exc = tryParse ? null : GetFormatException ();
1854                                 return true;
1855                         }
1856
1857                         long exp = 0; // temp long value
1858                         for (; i < s.Length; i++) {
1859                                 if (!Char.IsDigit (s [i]))  {
1860                                         exc = tryParse ? null : GetFormatException ();
1861                                         return true;
1862                                 }
1863
1864                                 // Reduce the risk of throwing an overflow exc
1865                                 exp = checked (exp * 10 - (int) (s [i] - '0'));
1866                                 if (exp < Int32.MinValue || exp > Int32.MaxValue) {
1867                                         exc = tryParse ? null : new OverflowException ("Value too large or too small.");
1868                                         return true;
1869                                 }
1870                         }
1871
1872                         // exp value saved as negative
1873                         if(!negative)
1874                                 exp = -exp;
1875
1876                         exc = null;
1877                         exponent = (int)exp;
1878                         pos = i;
1879                         return true;
1880                 }
1881
1882                 internal static bool FindOther (ref int pos, string s, string other)
1883                 {
1884                         if ((pos + other.Length) <= s.Length &&
1885                              s.Substring (pos, other.Length) == other) {
1886                                 pos += other.Length;
1887                                 return true;
1888                         }
1889
1890                         return false;
1891                 }
1892
1893                 internal static bool ValidDigit (char e, bool allowHex)
1894                 {
1895                         if (allowHex)
1896                                 return Char.IsDigit (e) || (e >= 'A' && e <= 'F') || (e >= 'a' && e <= 'f');
1897
1898                         return Char.IsDigit (e);
1899                 }
1900
1901                 static Exception GetFormatException ()
1902                 {
1903                         return new FormatException ("Input string was not in the correct format");
1904                 }
1905
1906                 static bool ProcessTrailingWhitespace (bool tryParse, string s, int position, ref Exception exc)
1907                 {
1908                         int len = s.Length;
1909
1910                         for (int i = position; i < len; i++){
1911                                 char c = s [i];
1912
1913                                 if (c != 0 && !Char.IsWhiteSpace (c)){
1914                                         if (!tryParse)
1915                                                 exc = GetFormatException ();
1916                                         return false;
1917                                 }
1918                         }
1919                         return true;
1920                 }
1921
1922                 static bool Parse (string s, bool tryParse, out BigInteger result, out Exception exc)
1923                 {
1924                         int len;
1925                         int i, sign = 1;
1926                         bool digits_seen = false;
1927
1928                         result = Zero;
1929                         exc = null;
1930
1931                         if (s == null) {
1932                                 if (!tryParse)
1933                                         exc = new ArgumentNullException ("value");
1934                                 return false;
1935                         }
1936
1937                         len = s.Length;
1938
1939                         char c;
1940                         for (i = 0; i < len; i++){
1941                                 c = s [i];
1942                                 if (!Char.IsWhiteSpace (c))
1943                                         break;
1944                         }
1945
1946                         if (i == len) {
1947                                 if (!tryParse)
1948                                         exc = GetFormatException ();
1949                                 return false;
1950                         }
1951
1952                         var info = Thread.CurrentThread.CurrentCulture.NumberFormat;
1953
1954                         string negative = info.NegativeSign;
1955                         string positive = info.PositiveSign;
1956
1957                         if (string.CompareOrdinal (s, i, positive, 0, positive.Length) == 0)
1958                                 i += positive.Length;
1959                         else if (string.CompareOrdinal (s, i, negative, 0, negative.Length) == 0) {
1960                                 sign = -1;
1961                                 i += negative.Length;
1962                         }
1963
1964                         BigInteger val = Zero;
1965                         for (; i < len; i++){
1966                                 c = s [i];
1967
1968                                 if (c == '\0') {
1969                                         i = len;
1970                                         continue;
1971                                 }
1972
1973                                 if (c >= '0' && c <= '9'){
1974                                         byte d = (byte) (c - '0');
1975
1976                                         val = val * 10 + d;
1977
1978                                         digits_seen = true;
1979                                 } else if (!ProcessTrailingWhitespace (tryParse, s, i, ref exc))
1980                                         return false;
1981                         }
1982
1983                         if (!digits_seen) {
1984                                 if (!tryParse)
1985                                         exc = GetFormatException ();
1986                                 return false;
1987                         }
1988
1989                         if (val.sign == 0)
1990                                 result = val;
1991                         else if (sign == -1)
1992                                 result = new BigInteger (-1, val.data);
1993                         else
1994                                 result = new BigInteger (1, val.data);
1995
1996                         return true;
1997                 }
1998
1999                 public static BigInteger Min (BigInteger left, BigInteger right)
2000                 {
2001                         int ls = left.sign;
2002                         int rs = right.sign;
2003
2004                         if (ls < rs)
2005                                 return left;
2006                         if (rs < ls)
2007                                 return right;
2008
2009                         int r = CoreCompare (left.data, right.data);
2010                         if (ls == -1)
2011                                 r = -r;
2012
2013                         if (r <= 0)
2014                                 return left;
2015                         return right;
2016                 }
2017
2018
2019                 public static BigInteger Max (BigInteger left, BigInteger right)
2020                 {
2021                         int ls = left.sign;
2022                         int rs = right.sign;
2023
2024                         if (ls > rs)
2025                                 return left;
2026                         if (rs > ls)
2027                                 return right;
2028
2029                         int r = CoreCompare (left.data, right.data);
2030                         if (ls == -1)
2031                                 r = -r;
2032
2033                         if (r >= 0)
2034                                 return left;
2035                         return right;
2036                 }
2037
2038                 public static BigInteger Abs (BigInteger value)
2039                 {
2040                         return new BigInteger ((short)Math.Abs (value.sign), value.data);
2041                 }
2042
2043
2044                 public static BigInteger DivRem (BigInteger dividend, BigInteger divisor, out BigInteger remainder)
2045                 {
2046                         if (divisor.sign == 0)
2047                                 throw new DivideByZeroException ();
2048
2049                         if (dividend.sign == 0) {
2050                                 remainder = dividend;
2051                                 return dividend;
2052                         }
2053
2054                         uint[] quotient;
2055                         uint[] remainder_value;
2056
2057                         DivModUnsigned (dividend.data, divisor.data, out quotient, out remainder_value);
2058
2059                         int i;
2060                         for (i = remainder_value.Length - 1; i >= 0 && remainder_value [i] == 0; --i) ;
2061                         if (i == -1) {
2062                                 remainder = new BigInteger (0, ZERO);
2063                         } else {
2064                                 if (i < remainder_value.Length - 1)
2065                                         remainder_value = Resize (remainder_value, i + 1);
2066                                 remainder = new BigInteger (dividend.sign, remainder_value);
2067                         }
2068
2069                         for (i = quotient.Length - 1; i >= 0 && quotient [i] == 0; --i) ;
2070                         if (i == -1)
2071                                 return new BigInteger (0, ZERO);
2072                         if (i < quotient.Length - 1)
2073                                 quotient = Resize (quotient, i + 1);
2074
2075                         return new BigInteger ((short)(dividend.sign * divisor.sign), quotient);
2076                 }
2077
2078         public static BigInteger Pow (BigInteger value, int exponent)
2079                 {
2080                         if (exponent < 0)
2081                                 throw new ArgumentOutOfRangeException("exponent", "exp must be >= 0");
2082                         if (exponent == 0)
2083                                 return One;
2084                         if (exponent == 1)
2085                                 return value;
2086
2087                         BigInteger result = One;
2088                         while (exponent != 0) {
2089                                 if ((exponent & 1) != 0)
2090                                         result = result * value;
2091                                 if (exponent == 1)
2092                                         break;
2093
2094                                 value = value * value;
2095                                 exponent >>= 1;
2096                         }
2097                         return result;
2098         }
2099
2100                 public static BigInteger ModPow (BigInteger value, BigInteger exponent, BigInteger modulus) {
2101                         if (exponent.sign == -1)
2102                                 throw new ArgumentOutOfRangeException("exponent", "power must be >= 0");
2103                         if (modulus.sign == 0)
2104                                 throw new DivideByZeroException ();
2105
2106                         BigInteger result = One % modulus;
2107                         while (exponent.sign != 0) {
2108                                 if (!exponent.IsEven) {
2109                                         result = result * value;
2110                                         result = result % modulus;
2111                                 }
2112                                 if (exponent.IsOne)
2113                                         break;
2114                                 value = value * value;
2115                                 value = value % modulus;
2116                                 exponent >>= 1;
2117                         }
2118                         return result;
2119                 }
2120
2121                 public static BigInteger GreatestCommonDivisor (BigInteger left, BigInteger right)
2122                 {
2123                         if (left.sign != 0 && left.data.Length == 1 && left.data [0] == 1)
2124                                 return new BigInteger (1, ONE);
2125                         if (right.sign != 0 && right.data.Length == 1 && right.data [0] == 1)
2126                                 return new BigInteger (1, ONE);
2127                         if (left.IsZero)
2128                                 return Abs(right);
2129                         if (right.IsZero)
2130                                 return Abs(left);
2131
2132                         BigInteger x = new BigInteger (1, left.data);
2133                         BigInteger y = new BigInteger (1, right.data);
2134
2135                         BigInteger g = y;
2136
2137                         while (x.data.Length > 1) {
2138                                 g = x;
2139                                 x = y % x;
2140                                 y = g;
2141
2142                         }
2143                         if (x.IsZero) return g;
2144
2145                         // TODO: should we have something here if we can convert to long?
2146
2147                         //
2148                         // Now we can just do it with single precision. I am using the binary gcd method,
2149                         // as it should be faster.
2150                         //
2151
2152                         uint yy = x.data [0];
2153                         uint xx = (uint)(y % yy);
2154
2155                         int t = 0;
2156
2157                         while (((xx | yy) & 1) == 0) {
2158                                 xx >>= 1; yy >>= 1; t++;
2159                         }
2160                         while (xx != 0) {
2161                                 while ((xx & 1) == 0) xx >>= 1;
2162                                 while ((yy & 1) == 0) yy >>= 1;
2163                                 if (xx >= yy)
2164                                         xx = (xx - yy) >> 1;
2165                                 else
2166                                         yy = (yy - xx) >> 1;
2167                         }
2168
2169                         return yy << t;
2170                 }
2171
2172                 /*LAMESPEC Log doesn't specify to how many ulp is has to be precise
2173                 We are equilavent to MS with about 2 ULP
2174                 */
2175                 public static double Log (BigInteger value, Double baseValue)
2176                 {
2177                         if (value.sign == -1 || baseValue == 1.0d || baseValue == -1.0d ||
2178                                         baseValue == Double.NegativeInfinity || double.IsNaN (baseValue))
2179                                 return double.NaN;
2180
2181                         if (baseValue == 0.0d || baseValue == Double.PositiveInfinity)
2182                                 return value.IsOne ? 0 : double.NaN;
2183
2184                         if (value.sign == 0)
2185                                 return double.NegativeInfinity;
2186
2187                         int length = value.data.Length - 1;
2188                         int bitCount = -1;
2189                         for (int curBit = 31; curBit >= 0; curBit--) {
2190                                 if ((value.data [length] & (1 << curBit)) != 0) {
2191                                         bitCount = curBit + length * 32;
2192                                         break;
2193                                 }
2194                         }
2195
2196                         long bitlen = bitCount;
2197                         Double c = 0, d = 1;
2198
2199                         BigInteger testBit = One;
2200                         long tempBitlen = bitlen;
2201                         while (tempBitlen > Int32.MaxValue) {
2202                                 testBit = testBit << Int32.MaxValue;
2203                                 tempBitlen -= Int32.MaxValue;
2204                         }
2205                         testBit = testBit << (int)tempBitlen;
2206
2207                         for (long curbit = bitlen; curbit >= 0; --curbit) {
2208                                 if ((value & testBit).sign != 0)
2209                                         c += d;
2210                                 d *= 0.5;
2211                                 testBit = testBit >> 1;
2212                         }
2213                         return (System.Math.Log (c) + System.Math.Log (2) * bitlen) / System.Math.Log (baseValue);
2214                 }
2215
2216
2217         public static double Log (BigInteger value)
2218                 {
2219             return Log (value, Math.E);
2220         }
2221
2222
2223         public static double Log10 (BigInteger value)
2224                 {
2225             return Log (value, 10);
2226         }
2227
2228                 [CLSCompliantAttribute (false)]
2229                 public bool Equals (ulong other)
2230                 {
2231                         return CompareTo (other) == 0;
2232                 }
2233
2234                 public override int GetHashCode ()
2235                 {
2236                         uint hash = (uint)(sign * 0x01010101u);
2237                         int len = data != null ? data.Length : 0;
2238
2239                         for (int i = 0; i < len; ++i)
2240                                 hash ^= data [i];
2241                         return (int)hash;
2242                 }
2243
2244                 public static BigInteger Add (BigInteger left, BigInteger right)
2245                 {
2246                         return left + right;
2247                 }
2248
2249                 public static BigInteger Subtract (BigInteger left, BigInteger right)
2250                 {
2251                         return left - right;
2252                 }
2253
2254                 public static BigInteger Multiply (BigInteger left, BigInteger right)
2255                 {
2256                         return left * right;
2257                 }
2258
2259                 public static BigInteger Divide (BigInteger dividend, BigInteger divisor)
2260                 {
2261                         return dividend / divisor;
2262                 }
2263
2264                 public static BigInteger Remainder (BigInteger dividend, BigInteger divisor)
2265                 {
2266                         return dividend % divisor;
2267                 }
2268
2269                 public static BigInteger Negate (BigInteger value)
2270                 {
2271                         return - value;
2272                 }
2273
2274                 public int CompareTo (object obj)
2275                 {
2276                         if (obj == null)
2277                                 return 1;
2278
2279                         if (!(obj is BigInteger))
2280                                 return -1;
2281
2282                         return Compare (this, (BigInteger)obj);
2283                 }
2284
2285                 public int CompareTo (BigInteger other)
2286                 {
2287                         return Compare (this, other);
2288                 }
2289
2290                 [CLSCompliantAttribute (false)]
2291                 public int CompareTo (ulong other)
2292                 {
2293                         if (sign < 0)
2294                                 return -1;
2295                         if (sign == 0)
2296                                 return other == 0 ? 0 : -1;
2297
2298                         if (data.Length > 2)
2299                                 return 1;
2300
2301                         uint high = (uint)(other >> 32);
2302                         uint low = (uint)other;
2303
2304                         return LongCompare (low, high);
2305                 }
2306
2307                 int LongCompare (uint low, uint high)
2308                 {
2309                         uint h = 0;
2310                         if (data.Length > 1)
2311                                 h = data [1];
2312
2313                         if (h > high)
2314                                 return 1;
2315                         if (h < high)
2316                                 return -1;
2317
2318                         uint l = data [0];
2319
2320                         if (l > low)
2321                                 return 1;
2322                         if (l < low)
2323                                 return -1;
2324
2325                         return 0;
2326                 }
2327
2328                 public int CompareTo (long other)
2329                 {
2330                         int ls = sign;
2331                         int rs = Math.Sign (other);
2332
2333                         if (ls != rs)
2334                                 return ls > rs ? 1 : -1;
2335
2336                         if (ls == 0)
2337                                 return 0;
2338
2339                         if (data.Length > 2)
2340                                 return sign;
2341
2342                         if (other < 0)
2343                                 other = -other;
2344                         uint low = (uint)other;
2345                         uint high = (uint)((ulong)other >> 32);
2346
2347                         int r = LongCompare (low, high);
2348                         if (ls == -1)
2349                                 r = -r;
2350
2351                         return r;
2352                 }
2353
2354                 public static int Compare (BigInteger left, BigInteger right)
2355                 {
2356                         int ls = left.sign;
2357                         int rs = right.sign;
2358
2359                         if (ls != rs)
2360                                 return ls > rs ? 1 : -1;
2361
2362                         int r = CoreCompare (left.data, right.data);
2363                         if (ls < 0)
2364                                 r = -r;
2365                         return r;
2366                 }
2367
2368
2369                 static int TopByte (uint x)
2370                 {
2371                         if ((x & 0xFFFF0000u) != 0) {
2372                                 if ((x & 0xFF000000u) != 0)
2373                                         return 4;
2374                                 return 3;
2375                         }
2376                         if ((x & 0xFF00u) != 0)
2377                                 return 2;
2378                         return 1;
2379                 }
2380
2381                 static int FirstNonFFByte (uint word)
2382                 {
2383                         if ((word & 0xFF000000u) != 0xFF000000u)
2384                                 return 4;
2385                         else if ((word & 0xFF0000u) != 0xFF0000u)
2386                                 return 3;
2387                         else if ((word & 0xFF00u) != 0xFF00u)
2388                                 return 2;
2389                         return 1;
2390                 }
2391
2392                 public byte[] ToByteArray ()
2393                 {
2394                         if (sign == 0)
2395                                 return new byte [1];
2396
2397                         //number of bytes not counting upper word
2398                         int bytes = (data.Length - 1) * 4;
2399                         bool needExtraZero = false;
2400
2401                         uint topWord = data [data.Length - 1];
2402                         int extra;
2403
2404                         //if the topmost bit is set we need an extra
2405                         if (sign == 1) {
2406                                 extra = TopByte (topWord);
2407                                 uint mask = 0x80u << ((extra - 1) * 8);
2408                                 if ((topWord & mask) != 0) {
2409                                         needExtraZero = true;
2410                                 }
2411                         } else {
2412                                 extra = TopByte (topWord);
2413                         }
2414
2415                         byte[] res = new byte [bytes + extra + (needExtraZero ? 1 : 0) ];
2416                         if (sign == 1) {
2417                                 int j = 0;
2418                                 int end = data.Length - 1;
2419                                 for (int i = 0; i < end; ++i) {
2420                                         uint word = data [i];
2421
2422                                         res [j++] = (byte)word;
2423                                         res [j++] = (byte)(word >> 8);
2424                                         res [j++] = (byte)(word >> 16);
2425                                         res [j++] = (byte)(word >> 24);
2426                                 }
2427                                 while (extra-- > 0) {
2428                                         res [j++] = (byte)topWord;
2429                                         topWord >>= 8;
2430                                 }
2431                         } else {
2432                                 int j = 0;
2433                                 int end = data.Length - 1;
2434
2435                                 uint carry = 1, word;
2436                                 ulong add;
2437                                 for (int i = 0; i < end; ++i) {
2438                                         word = data [i];
2439                                         add = (ulong)~word + carry;
2440                                         word = (uint)add;
2441                                         carry = (uint)(add >> 32);
2442
2443                                         res [j++] = (byte)word;
2444                                         res [j++] = (byte)(word >> 8);
2445                                         res [j++] = (byte)(word >> 16);
2446                                         res [j++] = (byte)(word >> 24);
2447                                 }
2448
2449                                 add = (ulong)~topWord + (carry);
2450                                 word = (uint)add;
2451                                 carry = (uint)(add >> 32);
2452                                 if (carry == 0) {
2453                                         int ex = FirstNonFFByte (word);
2454                                         bool needExtra = (word & (1 << (ex * 8 - 1))) == 0;
2455                                         int to = ex + (needExtra ? 1 : 0);
2456
2457                                         if (to != extra)
2458                                                 res = Resize (res, bytes + to);
2459
2460                                         while (ex-- > 0) {
2461                                                 res [j++] = (byte)word;
2462                                                 word >>= 8;
2463                                         }
2464                                         if (needExtra)
2465                                                 res [j++] = 0xFF;
2466                                 } else {
2467                                         res = Resize (res, bytes + 5);
2468                                         res [j++] = (byte)word;
2469                                         res [j++] = (byte)(word >> 8);
2470                                         res [j++] = (byte)(word >> 16);
2471                                         res [j++] = (byte)(word >> 24);
2472                                         res [j++] = 0xFF;
2473                                 }
2474                         }
2475
2476                         return res;
2477                 }
2478
2479                 static byte[] Resize (byte[] v, int len)
2480                 {
2481                         byte[] res = new byte [len];
2482                         Array.Copy (v, res, Math.Min (v.Length, len));
2483                         return res;
2484                 }
2485
2486                 static uint[] Resize (uint[] v, int len)
2487                 {
2488                         uint[] res = new uint [len];
2489                         Array.Copy (v, res, Math.Min (v.Length, len));
2490                         return res;
2491                 }
2492
2493                 static uint[] CoreAdd (uint[] a, uint[] b)
2494                 {
2495                         if (a.Length < b.Length) {
2496                                 uint[] tmp = a;
2497                                 a = b;
2498                                 b = tmp;
2499                         }
2500
2501                         int bl = a.Length;
2502                         int sl = b.Length;
2503
2504                         uint[] res = new uint [bl];
2505
2506                         ulong sum = 0;
2507
2508                         int i = 0;
2509                         for (; i < sl; i++) {
2510                                 sum = sum + a [i] + b [i];
2511                                 res [i] = (uint)sum;
2512                                 sum >>= 32;
2513                         }
2514
2515                         for (; i < bl; i++) {
2516                                 sum = sum + a [i];
2517                                 res [i] = (uint)sum;
2518                                 sum >>= 32;
2519                         }
2520
2521                         if (sum != 0) {
2522                                 res = Resize (res, bl + 1);
2523                                 res [i] = (uint)sum;
2524                         }
2525
2526                         return res;
2527                 }
2528
2529                 /*invariant a > b*/
2530                 static uint[] CoreSub (uint[] a, uint[] b)
2531                 {
2532                         int bl = a.Length;
2533                         int sl = b.Length;
2534
2535                         uint[] res = new uint [bl];
2536
2537                         ulong borrow = 0;
2538                         int i;
2539                         for (i = 0; i < sl; ++i) {
2540                                 borrow = (ulong)a [i] - b [i] - borrow;
2541
2542                                 res [i] = (uint)borrow;
2543                                 borrow = (borrow >> 32) & 0x1;
2544                         }
2545
2546                         for (; i < bl; i++) {
2547                                 borrow = (ulong)a [i] - borrow;
2548                                 res [i] = (uint)borrow;
2549                                 borrow = (borrow >> 32) & 0x1;
2550                         }
2551
2552                         //remove extra zeroes
2553                         for (i = bl - 1; i >= 0 && res [i] == 0; --i) ;
2554                         if (i < bl - 1)
2555                                 res = Resize (res, i + 1);
2556
2557             return res;
2558                 }
2559
2560
2561                 static uint[] CoreAdd (uint[] a, uint b)
2562                 {
2563                         int len = a.Length;
2564                         uint[] res = new uint [len];
2565
2566                         ulong sum = b;
2567                         int i;
2568                         for (i = 0; i < len; i++) {
2569                                 sum = sum + a [i];
2570                                 res [i] = (uint)sum;
2571                                 sum >>= 32;
2572                         }
2573
2574                         if (sum != 0) {
2575                                 res = Resize (res, len + 1);
2576                                 res [i] = (uint)sum;
2577                         }
2578
2579                         return res;
2580                 }
2581
2582                 static uint[] CoreSub (uint[] a, uint b)
2583                 {
2584                         int len = a.Length;
2585                         uint[] res = new uint [len];
2586
2587                         ulong borrow = b;
2588                         int i;
2589                         for (i = 0; i < len; i++) {
2590                                 borrow = (ulong)a [i] - borrow;
2591                                 res [i] = (uint)borrow;
2592                                 borrow = (borrow >> 32) & 0x1;
2593                         }
2594
2595                         //remove extra zeroes
2596                         for (i = len - 1; i >= 0 && res [i] == 0; --i) ;
2597                         if (i < len - 1)
2598                                 res = Resize (res, i + 1);
2599
2600             return res;
2601                 }
2602
2603                 static int CoreCompare (uint[] a, uint[] b)
2604                 {
2605                         int al = a != null ? a.Length : 0;
2606                         int bl = b != null ? b.Length : 0;
2607
2608                         if (al > bl)
2609                                 return 1;
2610                         if (bl > al)
2611                                 return -1;
2612
2613                         for (int i = al - 1; i >= 0; --i) {
2614                                 uint ai = a [i];
2615                                 uint bi = b [i];
2616                                 if (ai > bi)
2617                                         return 1;
2618                                 if (ai < bi)
2619                                         return -1;
2620                         }
2621                         return 0;
2622                 }
2623
2624                 static int GetNormalizeShift(uint value) {
2625                         int shift = 0;
2626
2627                         if ((value & 0xFFFF0000) == 0) { value <<= 16; shift += 16; }
2628                         if ((value & 0xFF000000) == 0) { value <<= 8; shift += 8; }
2629                         if ((value & 0xF0000000) == 0) { value <<= 4; shift += 4; }
2630                         if ((value & 0xC0000000) == 0) { value <<= 2; shift += 2; }
2631                         if ((value & 0x80000000) == 0) { value <<= 1; shift += 1; }
2632
2633                         return shift;
2634                 }
2635
2636                 static void Normalize (uint[] u, int l, uint[] un, int shift)
2637                 {
2638                         uint carry = 0;
2639                         int i;
2640                         if (shift > 0) {
2641                                 int rshift = 32 - shift;
2642                                 for (i = 0; i < l; i++) {
2643                                         uint ui = u [i];
2644                                         un [i] = (ui << shift) | carry;
2645                                         carry = ui >> rshift;
2646                                 }
2647                         } else {
2648                                 for (i = 0; i < l; i++) {
2649                                         un [i] = u [i];
2650                                 }
2651                         }
2652
2653                         while (i < un.Length) {
2654                                 un [i++] = 0;
2655                         }
2656
2657                         if (carry != 0) {
2658                                 un [l] = carry;
2659                         }
2660                 }
2661
2662                 static void Unnormalize (uint[] un, out uint[] r, int shift)
2663                 {
2664                         int length = un.Length;
2665                         r = new uint [length];
2666
2667                         if (shift > 0) {
2668                                 int lshift = 32 - shift;
2669                                 uint carry = 0;
2670                                 for (int i = length - 1; i >= 0; i--) {
2671                                         uint uni = un [i];
2672                                         r [i] = (uni >> shift) | carry;
2673                                         carry = (uni << lshift);
2674                                 }
2675                         } else {
2676                                 for (int i = 0; i < length; i++) {
2677                                         r [i] = un [i];
2678                                 }
2679                         }
2680                 }
2681
2682                 const ulong Base = 0x100000000;
2683                 static void DivModUnsigned (uint[] u, uint[] v, out uint[] q, out uint[] r)
2684                 {
2685                         int m = u.Length;
2686                         int n = v.Length;
2687
2688                         if (n <= 1) {
2689                                 //  Divide by single digit
2690                                 //
2691                                 ulong rem = 0;
2692                                 uint v0 = v [0];
2693                                 q = new uint[m];
2694                                 r = new uint [1];
2695
2696                                 for (int j = m - 1; j >= 0; j--) {
2697                                         rem *= Base;
2698                                         rem += u[j];
2699
2700                                         ulong div = rem / v0;
2701                                         rem -= div * v0;
2702                                         q[j] = (uint)div;
2703                                 }
2704                                 r [0] = (uint)rem;
2705                         } else if (m >= n) {
2706                                 int shift = GetNormalizeShift (v [n - 1]);
2707
2708                                 uint[] un = new uint [m + 1];
2709                                 uint[] vn = new uint [n];
2710
2711                                 Normalize (u, m, un, shift);
2712                                 Normalize (v, n, vn, shift);
2713
2714                                 q = new uint [m - n + 1];
2715                                 r = null;
2716
2717                                 //  Main division loop
2718                                 //
2719                                 for (int j = m - n; j >= 0; j--) {
2720                                         ulong rr, qq;
2721                                         int i;
2722
2723                                         rr = Base * un [j + n] + un [j + n - 1];
2724                                         qq = rr / vn [n - 1];
2725                                         rr -= qq * vn [n - 1];
2726
2727                                         for (; ; ) {
2728                                                 // Estimate too big ?
2729                                                 //
2730                                                 if ((qq >= Base) || (qq * vn [n - 2] > (rr * Base + un [j + n - 2]))) {
2731                                                         qq--;
2732                                                         rr += (ulong)vn [n - 1];
2733                                                         if (rr < Base)
2734                                                                 continue;
2735                                                 }
2736                                                 break;
2737                                         }
2738
2739
2740                                         //  Multiply and subtract
2741                                         //
2742                                         long b = 0;
2743                                         long t = 0;
2744                                         for (i = 0; i < n; i++) {
2745                                                 ulong p = vn [i] * qq;
2746                                                 t = (long)un [i + j] - (long)(uint)p - b;
2747                                                 un [i + j] = (uint)t;
2748                                                 p >>= 32;
2749                                                 t >>= 32;
2750                                                 b = (long)p - t;
2751                                         }
2752                                         t = (long)un [j + n] - b;
2753                                         un [j + n] = (uint)t;
2754
2755                                         //  Store the calculated value
2756                                         //
2757                                         q [j] = (uint)qq;
2758
2759                                         //  Add back vn[0..n] to un[j..j+n]
2760                                         //
2761                                         if (t < 0) {
2762                                                 q [j]--;
2763                                                 ulong c = 0;
2764                                                 for (i = 0; i < n; i++) {
2765                                                         c = (ulong)vn [i] + un [j + i] + c;
2766                                                         un [j + i] = (uint)c;
2767                                                         c >>= 32;
2768                                                 }
2769                                                 c += (ulong)un [j + n];
2770                                                 un [j + n] = (uint)c;
2771                                         }
2772                                 }
2773
2774                                 Unnormalize (un, out r, shift);
2775                         } else {
2776                                 q = new uint [] { 0 };
2777                                 r = u;
2778                         }
2779                 }
2780         }
2781 }