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                         if (high > 0x80000000u)
 477                                 throw new OverflowException ();
 478
 479                         return - ((((long)high) << 32) | (long)low);
 480                 }
 481
 482                 [CLSCompliantAttribute (false)]
 483                 public static explicit operator ulong (BigInteger value)
 484                 {
 485                         if (value.sign == 0)
 486                                 return 0;
 487                         if (value.data.Length > 2 || value.sign == -1)
 488                                 throw new OverflowException ();
 489
 490                         uint low = value.data [0];
 491                         if (value.data.Length == 1)
 492                                 return low;
 493
 494                         uint high = value.data [1];
 495                         return (((ulong)high) << 32) | low;
 496                 }
 497
 498                 public static explicit operator double (BigInteger value)
 499                 {
 500                         //FIXME
 501                         try {
 502                     return double.Parse (value.ToString (),
 503                     System.Globalization.CultureInfo.InvariantCulture.NumberFormat);
 504                         } catch (OverflowException) {
 505                                 return value.sign == -1 ? double.NegativeInfinity : double.PositiveInfinity;
 506                         }
 507         }
 508
 509                 public static explicit operator float (BigInteger value)
 510                 {
 511                         //FIXME
 512                         try {
 513                                 return float.Parse (value.ToString (),
 514                                 System.Globalization.CultureInfo.InvariantCulture.NumberFormat);
 515                         } catch (OverflowException) {
 516                                 return value.sign == -1 ? float.NegativeInfinity : float.PositiveInfinity;
 517                         }
 518                 }
 519
 520                 public static explicit operator decimal (BigInteger value)
 521                 {
 522                         if (value.sign == 0)
 523                         return Decimal.Zero;
 524
 525                         uint[] data = value.data;
 526                         if (data.Length > 3)
 527                                 throw new OverflowException ();
 528
 529                         int lo = 0, mi = 0, hi = 0;
 530                         if (data.Length > 2)
 531                                 hi = (Int32)data [2];
 532                         if (data.Length > 1)
 533                                 mi = (Int32)data [1];
 534                         if (data.Length > 0)
 535                                 lo = (Int32)data [0];
 536
 537                         return new Decimal(lo, mi, hi, value.sign < 0, 0);
 538                 }
 539
 540                 public static implicit operator BigInteger (int value)
 541                 {
 542                         return new BigInteger (value);
 543                 }
 544
 545                 [CLSCompliantAttribute (false)]
 546                 public static implicit operator BigInteger (uint value)
 547                 {
 548                         return new BigInteger (value);
 549                 }
 550
 551                 public static implicit operator BigInteger (short value)
 552                 {
 553                         return new BigInteger (value);
 554                 }
 555
 556                 [CLSCompliantAttribute (false)]
 557                 public static implicit operator BigInteger (ushort value)
 558                 {
 559                         return new BigInteger (value);
 560                 }
 561
 562                 public static implicit operator BigInteger (byte value)
 563                 {
 564                         return new BigInteger (value);
 565                 }
 566
 567                 [CLSCompliantAttribute (false)]
 568                 public static implicit operator BigInteger (sbyte value)
 569                 {
 570                         return new BigInteger (value);
 571                 }
 572
 573                 public static implicit operator BigInteger (long value)
 574                 {
 575                         return new BigInteger (value);
 576                 }
 577
 578                 [CLSCompliantAttribute (false)]
 579                 public static implicit operator BigInteger (ulong value)
 580                 {
 581                         return new BigInteger (value);
 582                 }
 583
 584                 public static explicit operator BigInteger (double value)
 585                 {
 586                         return new BigInteger (value);
 587                 }
 588
 589                 public static explicit operator BigInteger (float value)
 590                 {
 591                         return new BigInteger (value);
 592                 }
 593
 594                 public static explicit operator BigInteger (decimal value)
 595                 {
 596                         return new BigInteger (value);
 597                 }
 598
 599                 public static BigInteger operator+ (BigInteger left, BigInteger right)
 600                 {
 601                         if (left.sign == 0)
 602                                 return right;
 603                         if (right.sign == 0)
 604                                 return left;
 605
 606                         if (left.sign == right.sign)
 607                                 return new BigInteger (left.sign, CoreAdd (left.data, right.data));
 608
 609                         int r = CoreCompare (left.data, right.data);
 610
 611                         if (r == 0)
 612                                 return new BigInteger (0, ZERO);
 613
 614                         if (r > 0) //left > right
 615                                 return new BigInteger (left.sign, CoreSub (left.data, right.data));
 616
 617                         return new BigInteger (right.sign, CoreSub (right.data, left.data));
 618                 }
 619
 620                 public static BigInteger operator- (BigInteger left, BigInteger right)
 621                 {
 622                         if (right.sign == 0)
 623                                 return left;
 624                         if (left.sign == 0)
 625                                 return new BigInteger ((short)-right.sign, right.data);
 626
 627                         if (left.sign == right.sign) {
 628                                 int r = CoreCompare (left.data, right.data);
 629
 630                                 if (r == 0)
 631                                         return new BigInteger (0, ZERO);
 632
 633                                 if (r > 0) //left > right
 634                                         return new BigInteger (left.sign, CoreSub (left.data, right.data));
 635
 636                                 return new BigInteger ((short)-right.sign, CoreSub (right.data, left.data));
 637                         }
 638
 639                         return new BigInteger (left.sign, CoreAdd (left.data, right.data));
 640                 }
 641
 642                 public static BigInteger operator* (BigInteger left, BigInteger right)
 643                 {
 644                         if (left.sign == 0 || right.sign == 0)
 645                                 return new BigInteger (0, ZERO);
 646
 647                         if (left.data [0] == 1 && left.data.Length == 1) {
 648                                 if (left.sign == 1)
 649                                         return right;
 650                                 return new BigInteger ((short)-right.sign, right.data);
 651                         }
 652
 653                         if (right.data [0] == 1 && right.data.Length == 1) {
 654                                 if (right.sign == 1)
 655                                         return left;
 656                                 return new BigInteger ((short)-left.sign, left.data);
 657                         }
 658
 659                         uint[] a = left.data;
 660                         uint[] b = right.data;
 661
 662                         uint[] res = new uint [a.Length + b.Length];
 663
 664             for (int i = 0; i < a.Length; ++i) {
 665                 uint ai = a [i];
 666                 int k = i;
 667
 668                 ulong carry = 0;
 669                 for (int j = 0; j < b.Length; ++j) {
 670                     carry = carry + ((ulong)ai) * b [j] + res [k];
 671                     res[k++] = (uint)carry;
 672                     carry >>= 32;
 673                 }
 674
 675                 while (carry != 0) {
 676                     carry += res [k];
 677                     res[k++] = (uint)carry;
 678                     carry >>= 32;
 679                 }
 680             }
 681
 682                         int m;
 683                         for (m = res.Length - 1; m >= 0 && res [m] == 0; --m) ;
 684                         if (m < res.Length - 1)
 685                                 res = Resize (res, m + 1);
 686
 687                         return new BigInteger ((short)(left.sign * right.sign), res);
 688                 }
 689
 690                 public static BigInteger operator/ (BigInteger dividend, BigInteger divisor)
 691                 {
 692                         if (divisor.sign == 0)
 693                                 throw new DivideByZeroException ();
 694
 695                         if (dividend.sign == 0)
 696                                 return dividend;
 697
 698                         uint[] quotient;
 699                         uint[] remainder_value;
 700
 701                         DivModUnsigned (dividend.data, divisor.data, out quotient, out remainder_value);
 702
 703                         int i;
 704                         for (i = quotient.Length - 1; i >= 0 && quotient [i] == 0; --i) ;
 705                         if (i == -1)
 706                                 return new BigInteger (0, ZERO);
 707                         if (i < quotient.Length - 1)
 708                                 quotient = Resize (quotient, i + 1);
 709
 710                         return new BigInteger ((short)(dividend.sign * divisor.sign), quotient);
 711                 }
 712
 713                 public static BigInteger operator% (BigInteger dividend, BigInteger divisor)
 714                 {
 715                         if (divisor.sign == 0)
 716                                 throw new DivideByZeroException ();
 717
 718                         if (dividend.sign == 0)
 719                                 return dividend;
 720
 721                         uint[] quotient;
 722                         uint[] remainder_value;
 723
 724                         DivModUnsigned (dividend.data, divisor.data, out quotient, out remainder_value);
 725
 726                         int i;
 727                         for (i = remainder_value.Length - 1; i >= 0 && remainder_value [i] == 0; --i) ;
 728                         if (i == -1)
 729                                 return new BigInteger (0, ZERO);
 730
 731                         if (i < remainder_value.Length - 1)
 732                                 remainder_value = Resize (remainder_value, i + 1);
 733                         return new BigInteger (dividend.sign, remainder_value);
 734                 }
 735
 736                 public static BigInteger operator- (BigInteger value)
 737                 {
 738                         if (value.sign == 0)
 739                                 return value;
 740                         return new BigInteger ((short)-value.sign, value.data);
 741                 }
 742
 743                 public static BigInteger operator+ (BigInteger value)
 744                 {
 745                         return value;
 746                 }
 747
 748                 public static BigInteger operator++ (BigInteger value)
 749                 {
 750                         if (value.sign == 0)
 751                                 return One;
 752
 753                         short sign = value.sign;
 754                         uint[] data = value.data;
 755                         if (data.Length == 1) {
 756                                 if (sign == -1 && data [0] == 1)
 757                                         return new BigInteger (0, ZERO);
 758                                 if (sign == 0)
 759                                         return new BigInteger (1, ONE);
 760                         }
 761
 762                         if (sign == -1)
 763                                 data = CoreSub (data, 1);
 764                         else
 765                                 data = CoreAdd (data, 1);
 766
 767                         return new BigInteger (sign, data);
 768                 }
 769
 770                 public static BigInteger operator-- (BigInteger value)
 771                 {
 772                         if (value.sign == 0)
 773                                 return MinusOne;
 774
 775                         short sign = value.sign;
 776                         uint[] data = value.data;
 777                         if (data.Length == 1) {
 778                                 if (sign == 1 && data [0] == 1)
 779                                         return new BigInteger (0, ZERO);
 780                                 if (sign == 0)
 781                                         return new BigInteger (-1, ONE);
 782                         }
 783
 784                         if (sign == -1)
 785                                 data = CoreAdd (data, 1);
 786                         else
 787                                 data = CoreSub (data, 1);
 788
 789                         return new BigInteger (sign, data);
 790                 }
 791
 792                 public static BigInteger operator& (BigInteger left, BigInteger right)
 793                 {
 794                         if (left.sign == 0)
 795                                 return left;
 796
 797                         if (right.sign == 0)
 798                                 return right;
 799
 800                         uint[] a = left.data;
 801                         uint[] b = right.data;
 802                         int ls = left.sign;
 803                         int rs = right.sign;
 804
 805                         bool neg_res = (ls == rs) && (ls == -1);
 806
 807                         uint[] result = new uint [Math.Max (a.Length, b.Length)];
 808
 809                         ulong ac = 1, bc = 1, borrow = 1;
 810
 811                         int i;
 812                         for (i = 0; i < result.Length; ++i) {
 813                                 uint va = 0;
 814                                 if (i < a.Length)
 815                                         va = a [i];
 816                                 if (ls == -1) {
 817                                         ac = ~va + ac;
 818                                         va = (uint)ac;
 819                                         ac = (uint)(ac >> 32);
 820                                 }
 821
 822                                 uint vb = 0;
 823                                 if (i < b.Length)
 824                                         vb = b [i];
 825                                 if (rs == -1) {
 826                                         bc = ~vb + bc;
 827                                         vb = (uint)bc;
 828                                         bc = (uint)(bc >> 32);
 829                                 }
 830
 831                                 uint word = va & vb;
 832
 833                                 if (neg_res) {
 834                                         borrow = word - borrow;
 835                                         word = ~(uint)borrow;
 836                                         borrow = (uint)(borrow >> 32) & 0x1u;
 837                                 }
 838
 839                                 result [i] = word;
 840                         }
 841
 842                         for (i = result.Length - 1; i >= 0 && result [i] == 0; --i) ;
 843                         if (i == -1)
 844                                 return new BigInteger (0, ZERO);
 845
 846                         if (i < result.Length - 1)
 847                                 result = Resize (result, i + 1);
 848
 849                         return new BigInteger (neg_res ? (short)-1 : (short)1, result);
 850                 }
 851
 852                 public static BigInteger operator| (BigInteger left, BigInteger right)
 853                 {
 854                         if (left.sign == 0)
 855                                 return right;
 856
 857                         if (right.sign == 0)
 858                                 return left;
 859
 860                         uint[] a = left.data;
 861                         uint[] b = right.data;
 862                         int ls = left.sign;
 863                         int rs = right.sign;
 864
 865                         bool neg_res = (ls == -1) || (rs == -1);
 866
 867                         uint[] result = new uint [Math.Max (a.Length, b.Length)];
 868
 869                         ulong ac = 1, bc = 1, borrow = 1;
 870
 871                         int i;
 872                         for (i = 0; i < result.Length; ++i) {
 873                                 uint va = 0;
 874                                 if (i < a.Length)
 875                                         va = a [i];
 876                                 if (ls == -1) {
 877                                         ac = ~va + ac;
 878                                         va = (uint)ac;
 879                                         ac = (uint)(ac >> 32);
 880                                 }
 881
 882                                 uint vb = 0;
 883                                 if (i < b.Length)
 884                                         vb = b [i];
 885                                 if (rs == -1) {
 886                                         bc = ~vb + bc;
 887                                         vb = (uint)bc;
 888                                         bc = (uint)(bc >> 32);
 889                                 }
 890
 891                                 uint word = va | vb;
 892
 893                                 if (neg_res) {
 894                                         borrow = word - borrow;
 895                                         word = ~(uint)borrow;
 896                                         borrow = (uint)(borrow >> 32) & 0x1u;
 897                                 }
 898
 899                                 result [i] = word;
 900                         }
 901
 902                         for (i = result.Length - 1; i >= 0 && result [i] == 0; --i) ;
 903                         if (i == -1)
 904                                 return new BigInteger (0, ZERO);
 905
 906                         if (i < result.Length - 1)
 907                                 result = Resize (result, i + 1);
 908
 909                         return new BigInteger (neg_res ? (short)-1 : (short)1, result);
 910                 }
 911
 912                 public static BigInteger operator^ (BigInteger left, BigInteger right)
 913                 {
 914                         if (left.sign == 0)
 915                                 return right;
 916
 917                         if (right.sign == 0)
 918                                 return left;
 919
 920                         uint[] a = left.data;
 921                         uint[] b = right.data;
 922                         int ls = left.sign;
 923                         int rs = right.sign;
 924
 925                         bool neg_res = (ls == -1) ^ (rs == -1);
 926
 927                         uint[] result = new uint [Math.Max (a.Length, b.Length)];
 928
 929                         ulong ac = 1, bc = 1, borrow = 1;
 930
 931                         int i;
 932                         for (i = 0; i < result.Length; ++i) {
 933                                 uint va = 0;
 934                                 if (i < a.Length)
 935                                         va = a [i];
 936                                 if (ls == -1) {
 937                                         ac = ~va + ac;
 938                                         va = (uint)ac;
 939                                         ac = (uint)(ac >> 32);
 940                                 }
 941
 942                                 uint vb = 0;
 943                                 if (i < b.Length)
 944                                         vb = b [i];
 945                                 if (rs == -1) {
 946                                         bc = ~vb + bc;
 947                                         vb = (uint)bc;
 948                                         bc = (uint)(bc >> 32);
 949                                 }
 950
 951                                 uint word = va ^ vb;
 952
 953                                 if (neg_res) {
 954                                         borrow = word - borrow;
 955                                         word = ~(uint)borrow;
 956                                         borrow = (uint)(borrow >> 32) & 0x1u;
 957                                 }
 958
 959                                 result [i] = word;
 960                         }
 961
 962                         for (i = result.Length - 1; i >= 0 && result [i] == 0; --i) ;
 963                         if (i == -1)
 964                                 return new BigInteger (0, ZERO);
 965
 966                         if (i < result.Length - 1)
 967                                 result = Resize (result, i + 1);
 968
 969                         return new BigInteger (neg_res ? (short)-1 : (short)1, result);
 970                 }
 971
 972                 public static BigInteger operator~ (BigInteger value)
 973                 {
 974                         if (value.sign == 0)
 975                                 return new BigInteger (-1, ONE);
 976
 977                         uint[] data = value.data;
 978                         int sign = value.sign;
 979
 980                         bool neg_res = sign == 1;
 981
 982                         uint[] result = new uint [data.Length];
 983
 984                         ulong carry = 1, borrow = 1;
 985
 986                         int i;
 987                         for (i = 0; i < result.Length; ++i) {
 988                                 uint word = data [i];
 989                                 if (sign == -1) {
 990                                         carry = ~word + carry;
 991                                         word = (uint)carry;
 992                                         carry = (uint)(carry >> 32);
 993                                 }
 994
 995                                 word = ~word;
 996
 997                                 if (neg_res) {
 998                                         borrow = word - borrow;
 999                                         word = ~(uint)borrow;
1000                                         borrow = (uint)(borrow >> 32) & 0x1u;
1001                                 }
1002
1003                                 result [i] = word;
1004                         }
1005
1006                         for (i = result.Length - 1; i >= 0 && result [i] == 0; --i) ;
1007                         if (i == -1)
1008                                 return new BigInteger (0, ZERO);
1009
1010                         if (i < result.Length - 1)
1011                                 result = Resize (result, i + 1);
1012
1013                         return new BigInteger (neg_res ? (short)-1 : (short)1, result);
1014                 }
1015
1016                 //returns the 0-based index of the most significant set bit
1017                 //returns 0 if no bit is set, so extra care when using it
1018                 static int BitScanBackward (uint word)
1019                 {
1020                         for (int i = 31; i >= 0; --i) {
1021                                 uint mask = 1u << i;
1022                                 if ((word & mask) == mask)
1023                                         return i;
1024                         }
1025                         return 0;
1026                 }
1027
1028                 public static BigInteger operator<< (BigInteger value, int shift)
1029                 {
1030                         if (shift == 0 || value.sign == 0)
1031                                 return value;
1032                         if (shift < 0)
1033                                 return value >> -shift;
1034
1035                         uint[] data = value.data;
1036                         int sign = value.sign;
1037
1038                         int topMostIdx = BitScanBackward (data [data.Length - 1]);
1039                         int bits = shift - (31 - topMostIdx);
1040                         int extra_words = (bits >> 5) + ((bits & 0x1F) != 0 ? 1 : 0);
1041
1042                         uint[] res = new uint [data.Length + extra_words];
1043
1044                         int idx_shift = shift >> 5;
1045                         int bit_shift = shift & 0x1F;
1046                         int carry_shift = 32 - bit_shift;
1047
1048                         if (carry_shift == 32) {
1049                                 for (int i = 0; i < data.Length; ++i) {
1050                                         uint word = data [i];
1051                                         res [i + idx_shift] |= word << bit_shift;
1052                                 }
1053                         } else {
1054                                 for (int i = 0; i < data.Length; ++i) {
1055                                         uint word = data [i];
1056                                         res [i + idx_shift] |= word << bit_shift;
1057                                         if (i + idx_shift + 1 < res.Length)
1058                                                 res [i + idx_shift + 1] = word >> carry_shift;
1059                                 }
1060                         }
1061
1062                         return new BigInteger ((short)sign, res);
1063                 }
1064
1065                 public static BigInteger operator>> (BigInteger value, int shift)
1066                 {
1067                         if (shift == 0 || value.sign == 0)
1068                                 return value;
1069                         if (shift < 0)
1070                                 return value << -shift;
1071
1072                         uint[] data = value.data;
1073                         int sign = value.sign;
1074
1075                         int topMostIdx = BitScanBackward (data [data.Length - 1]);
1076                         int idx_shift = shift >> 5;
1077                         int bit_shift = shift & 0x1F;
1078
1079                         int extra_words = idx_shift;
1080                         if (bit_shift > topMostIdx)
1081                                 ++extra_words;
1082                         int size = data.Length - extra_words;
1083
1084                         if (size <= 0) {
1085                                 if (sign == 1)
1086                                         return new BigInteger (0, ZERO);
1087                                 return new BigInteger (-1, ONE);
1088                         }
1089
1090                         uint[] res = new uint [size];
1091                         int carry_shift = 32 - bit_shift;
1092
1093                         if (carry_shift == 32) {
1094                                 for (int i = data.Length - 1; i >= idx_shift; --i) {
1095                                         uint word = data [i];
1096
1097                                         if (i - idx_shift < res.Length)
1098                                                 res [i - idx_shift] |= word >> bit_shift;
1099                                 }
1100                         } else {
1101                                 for (int i = data.Length - 1; i >= idx_shift; --i) {
1102                                         uint word = data [i];
1103
1104                                         if (i - idx_shift < res.Length)
1105                                                 res [i - idx_shift] |= word >> bit_shift;
1106                                         if (i - idx_shift - 1 >= 0)
1107                                                 res [i - idx_shift - 1] = word << carry_shift;
1108                                 }
1109
1110                         }
1111
1112                         //Round down instead of toward zero
1113                         if (sign == -1) {
1114                                 for (int i = 0; i < idx_shift; i++) {
1115                                         if (data [i] != 0u) {
1116                                                 var tmp = new BigInteger ((short)sign, res);
1117                                                 --tmp;
1118                                                 return tmp;
1119                                         }
1120                                 }
1121                                 if (bit_shift > 0 && (data [idx_shift] << carry_shift) != 0u) {
1122                                         var tmp = new BigInteger ((short)sign, res);
1123                                         --tmp;
1124                                         return tmp;
1125                                 }
1126                         }
1127                         return new BigInteger ((short)sign, res);
1128                 }
1129
1130                 public static bool operator< (BigInteger left, BigInteger right)
1131                 {
1132                         return Compare (left, right) < 0;
1133                 }
1134
1135                 public static bool operator< (BigInteger left, long right)
1136                 {
1137                         return left.CompareTo (right) < 0;
1138                 }
1139
1140
1141                 public static bool operator< (long left, BigInteger right)
1142                 {
1143                         return right.CompareTo (left) > 0;
1144                 }
1145
1146
1147                 [CLSCompliantAttribute (false)]
1148                 public static bool operator< (BigInteger left, ulong right)
1149                 {
1150                         return left.CompareTo (right) < 0;
1151                 }
1152
1153                 [CLSCompliantAttribute (false)]
1154                 public static bool operator< (ulong left, BigInteger right)
1155                 {
1156                         return right.CompareTo (left) > 0;
1157                 }
1158
1159                 public static bool operator<= (BigInteger left, BigInteger right)
1160                 {
1161                         return Compare (left, right) <= 0;
1162                 }
1163
1164                 public static bool operator<= (BigInteger left, long right)
1165                 {
1166                         return left.CompareTo (right) <= 0;
1167                 }
1168
1169                 public static bool operator<= (long left, BigInteger right)
1170                 {
1171                         return right.CompareTo (left) >= 0;
1172                 }
1173
1174                 [CLSCompliantAttribute (false)]
1175                 public static bool operator<= (BigInteger left, ulong right)
1176                 {
1177                         return left.CompareTo (right) <= 0;
1178                 }
1179
1180                 [CLSCompliantAttribute (false)]
1181                 public static bool operator<= (ulong left, BigInteger right)
1182                 {
1183                         return right.CompareTo (left) >= 0;
1184                 }
1185
1186                 public static bool operator> (BigInteger left, BigInteger right)
1187                 {
1188                         return Compare (left, right) > 0;
1189                 }
1190
1191                 public static bool operator> (BigInteger left, long right)
1192                 {
1193                         return left.CompareTo (right) > 0;
1194                 }
1195
1196                 public static bool operator> (long left, BigInteger right)
1197                 {
1198                         return right.CompareTo (left) < 0;
1199                 }
1200
1201                 [CLSCompliantAttribute (false)]
1202                 public static bool operator> (BigInteger left, ulong right)
1203                 {
1204                         return left.CompareTo (right) > 0;
1205                 }
1206
1207                 [CLSCompliantAttribute (false)]
1208                 public static bool operator> (ulong left, BigInteger right)
1209                 {
1210                         return right.CompareTo (left) < 0;
1211                 }
1212
1213                 public static bool operator>= (BigInteger left, BigInteger right)
1214                 {
1215                         return Compare (left, right) >= 0;
1216                 }
1217
1218                 public static bool operator>= (BigInteger left, long right)
1219                 {
1220                         return left.CompareTo (right) >= 0;
1221                 }
1222
1223                 public static bool operator>= (long left, BigInteger right)
1224                 {
1225                         return right.CompareTo (left) <= 0;
1226                 }
1227
1228                 [CLSCompliantAttribute (false)]
1229                 public static bool operator>= (BigInteger left, ulong right)
1230                 {
1231                         return left.CompareTo (right) >= 0;
1232                 }
1233
1234                 [CLSCompliantAttribute (false)]
1235                 public static bool operator>= (ulong left, BigInteger right)
1236                 {
1237                         return right.CompareTo (left) <= 0;
1238                 }
1239
1240                 public static bool operator== (BigInteger left, BigInteger right)
1241                 {
1242                         return Compare (left, right) == 0;
1243                 }
1244
1245                 public static bool operator== (BigInteger left, long right)
1246                 {
1247                         return left.CompareTo (right) == 0;
1248                 }
1249
1250                 public static bool operator== (long left, BigInteger right)
1251                 {
1252                         return right.CompareTo (left) == 0;
1253                 }
1254
1255                 [CLSCompliantAttribute (false)]
1256                 public static bool operator== (BigInteger left, ulong right)
1257                 {
1258                         return left.CompareTo (right) == 0;
1259                 }
1260
1261                 [CLSCompliantAttribute (false)]
1262                 public static bool operator== (ulong left, BigInteger right)
1263                 {
1264                         return right.CompareTo (left) == 0;
1265                 }
1266
1267                 public static bool operator!= (BigInteger left, BigInteger right)
1268                 {
1269                         return Compare (left, right) != 0;
1270                 }
1271
1272                 public static bool operator!= (BigInteger left, long right)
1273                 {
1274                         return left.CompareTo (right) != 0;
1275                 }
1276
1277                 public static bool operator!= (long left, BigInteger right)
1278                 {
1279                         return right.CompareTo (left) != 0;
1280                 }
1281
1282                 [CLSCompliantAttribute (false)]
1283                 public static bool operator!= (BigInteger left, ulong right)
1284                 {
1285                         return left.CompareTo (right) != 0;
1286                 }
1287
1288                 [CLSCompliantAttribute (false)]
1289                 public static bool operator!= (ulong left, BigInteger right)
1290                 {
1291                         return right.CompareTo (left) != 0;
1292                 }
1293
1294                 public override bool Equals (object obj)
1295                 {
1296                         if (!(obj is BigInteger))
1297                                 return false;
1298                         return Equals ((BigInteger)obj);
1299                 }
1300
1301                 public bool Equals (BigInteger other)
1302                 {
1303                         if (sign != other.sign)
1304                                 return false;
1305
1306                         int alen = data != null ? data.Length : 0;
1307                         int blen = other.data != null ? other.data.Length : 0;
1308
1309                         if (alen != blen)
1310                                 return false;
1311                         for (int i = 0; i < alen; ++i) {
1312                                 if (data [i] != other.data [i])
1313                                         return false;
1314                         }
1315                         return true;
1316                 }
1317
1318                 public bool Equals (long other)
1319                 {
1320                         return CompareTo (other) == 0;
1321                 }
1322
1323                 public override string ToString ()
1324                 {
1325                         return ToString (10, null);
1326                 }
1327
1328                 string ToStringWithPadding (string format, uint radix, IFormatProvider provider)
1329                 {
1330                         if (format.Length > 1) {
1331                                 int precision = Convert.ToInt32(format.Substring (1), CultureInfo.InvariantCulture.NumberFormat);
1332                                 string baseStr = ToString (radix, provider);
1333                                 if (baseStr.Length < precision) {
1334                                         string additional = new String ('0', precision - baseStr.Length);
1335                                         if (baseStr[0] != '-') {
1336                                                 return additional + baseStr;
1337                                         } else {
1338                                                         return "-" + additional + baseStr.Substring (1);
1339                                         }
1340                                 }
1341                                 return baseStr;
1342                         }
1343                         return ToString (radix, provider);
1344                 }
1345
1346                 public string ToString (string format)
1347                 {
1348                         return ToString (format, null);
1349                 }
1350
1351                 public string ToString (IFormatProvider provider)
1352                 {
1353                         return ToString (null, provider);
1354                 }
1355
1356
1357                 public string ToString (string format, IFormatProvider provider)
1358                 {
1359                         if (format == null || format == "")
1360                                 return ToString (10, provider);
1361
1362                         switch (format[0]) {
1363                         case 'd':
1364                         case 'D':
1365                         case 'g':
1366                         case 'G':
1367                         case 'r':
1368                         case 'R':
1369                                 return ToStringWithPadding (format, 10, provider);
1370                         case 'x':
1371                         case 'X':
1372                                 return ToStringWithPadding (format, 16, null);
1373                         default:
1374                                 throw new FormatException (string.Format ("format '{0}' not implemented", format));
1375                         }
1376                 }
1377
1378                 static uint[] MakeTwoComplement (uint[] v)
1379                 {
1380                         uint[] res = new uint [v.Length];
1381
1382                         ulong carry = 1;
1383                         for (int i = 0; i < v.Length; ++i) {
1384                                 uint word = v [i];
1385                                 carry = (ulong)~word + carry;
1386                                 word = (uint)carry;
1387                                 carry = (uint)(carry >> 32);
1388                                 res [i] = word;
1389                         }
1390
1391                         uint last = res [res.Length - 1];
1392                         int idx = FirstNonFFByte (last);
1393                         uint mask = 0xFF;
1394                         for (int i = 1; i < idx; ++i)
1395                                 mask = (mask << 8) | 0xFF;
1396
1397                         res [res.Length - 1] = last & mask;
1398                         return res;
1399                 }
1400
1401                 string ToString (uint radix, IFormatProvider provider)
1402                 {
1403                         const string characterSet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
1404
1405                         if (characterSet.Length < radix)
1406                                 throw new ArgumentException ("charSet length less than radix", "characterSet");
1407                         if (radix == 1)
1408                                 throw new ArgumentException ("There is no such thing as radix one notation", "radix");
1409
1410                         if (sign == 0)
1411                                 return "0";
1412                         if (data.Length == 1 && data [0] == 1)
1413                                 return sign == 1 ? "1" : "-1";
1414
1415                         List<char> digits = new List<char> (1 + data.Length * 3 / 10);
1416
1417                         BigInteger a;
1418                         if (sign == 1)
1419                                 a = this;
1420                         else {
1421                                 uint[] dt = data;
1422                                 if (radix > 10)
1423                                         dt = MakeTwoComplement (dt);
1424                                 a = new BigInteger (1, dt);
1425                         }
1426
1427                         while (a != 0) {
1428                                 BigInteger rem;
1429                                 a = DivRem (a, radix, out rem);
1430                                 digits.Add (characterSet [(int) rem]);
1431                         }
1432
1433                         if (sign == -1 && radix == 10) {
1434                                 NumberFormatInfo info = null;
1435                                 if (provider != null)
1436                                         info = provider.GetFormat (typeof (NumberFormatInfo)) as NumberFormatInfo;
1437                                 if (info != null) {
1438                                         string str = info.NegativeSign;
1439                                         for (int i = str.Length - 1; i >= 0; --i)
1440                                                 digits.Add (str [i]);
1441                                 } else {
1442                                         digits.Add ('-');
1443                                 }
1444                         }
1445
1446                         char last = digits [digits.Count - 1];
1447                         if (sign == 1 && radix > 10 && (last < '0' || last > '9'))
1448                                 digits.Add ('0');
1449
1450                         digits.Reverse ();
1451
1452                         return new String (digits.ToArray ());
1453                 }
1454
1455                 public static BigInteger Parse (string value)
1456                 {
1457                         Exception ex;
1458                         BigInteger result;
1459
1460                         if (!Parse (value, false, out result, out ex))
1461                                 throw ex;
1462                         return result;
1463                 }
1464
1465                 public static bool TryParse (string value, out BigInteger result)
1466                 {
1467                         Exception ex;
1468                         return Parse (value, true, out result, out ex);
1469                 }
1470
1471                 public static BigInteger Parse (string value, NumberStyles style)
1472                 {
1473                         return Parse (value, style, null);
1474                 }
1475
1476                 public static BigInteger Parse (string value, IFormatProvider provider)
1477                 {
1478                         return Parse (value, NumberStyles.Integer, provider);
1479                 }
1480
1481                 public static BigInteger Parse (
1482                         string value, NumberStyles style, IFormatProvider provider)
1483                 {
1484                         Exception exc;
1485                         BigInteger res;
1486
1487                         if (!Parse (value, style, provider, false, out res, out exc))
1488                                 throw exc;
1489
1490                         return res;
1491                 }
1492
1493                 public static bool TryParse (
1494                         string value, NumberStyles style, IFormatProvider provider,
1495                         out BigInteger result)
1496                 {
1497                         Exception exc;
1498                         if (!Parse (value, style, provider, true, out result, out exc)) {
1499                                 result = Zero;
1500                                 return false;
1501                         }
1502
1503                         return true;
1504                 }
1505
1506                 internal static bool Parse (string s, NumberStyles style, IFormatProvider fp, bool tryParse, out BigInteger result, out Exception exc)
1507                 {
1508                         result = Zero;
1509                         exc = null;
1510
1511                         if (s == null) {
1512                                 if (!tryParse)
1513                                         exc = new ArgumentNullException ("s");
1514                                 return false;
1515                         }
1516
1517                         if (s.Length == 0) {
1518                                 if (!tryParse)
1519                                         exc = GetFormatException ();
1520                                 return false;
1521                         }
1522
1523                         NumberFormatInfo nfi = null;
1524                         if (fp != null) {
1525                                 Type typeNFI = typeof(System.Globalization.NumberFormatInfo);
1526                                 nfi = (NumberFormatInfo)fp.GetFormat (typeNFI);
1527                         }
1528                         if (nfi == null)
1529                                 nfi = Thread.CurrentThread.CurrentCulture.NumberFormat;
1530
1531                         if (!CheckStyle (style, tryParse, ref exc))
1532                                 return false;
1533
1534                         bool AllowCurrencySymbol = (style & NumberStyles.AllowCurrencySymbol) != 0;
1535                         bool AllowHexSpecifier = (style & NumberStyles.AllowHexSpecifier) != 0;
1536                         bool AllowThousands = (style & NumberStyles.AllowThousands) != 0;
1537                         bool AllowDecimalPoint = (style & NumberStyles.AllowDecimalPoint) != 0;
1538                         bool AllowParentheses = (style & NumberStyles.AllowParentheses) != 0;
1539                         bool AllowTrailingSign = (style & NumberStyles.AllowTrailingSign) != 0;
1540                         bool AllowLeadingSign = (style & NumberStyles.AllowLeadingSign) != 0;
1541                         bool AllowTrailingWhite = (style & NumberStyles.AllowTrailingWhite) != 0;
1542                         bool AllowLeadingWhite = (style & NumberStyles.AllowLeadingWhite) != 0;
1543                         bool AllowExponent = (style & NumberStyles.AllowExponent) != 0;
1544
1545                         int pos = 0;
1546
1547                         if (AllowLeadingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1548                                 return false;
1549
1550                         bool foundOpenParentheses = false;
1551                         bool negative = false;
1552                         bool foundSign = false;
1553                         bool foundCurrency = false;
1554
1555                         // Pre-number stuff
1556                         if (AllowParentheses && s [pos] == '(') {
1557                                 foundOpenParentheses = true;
1558                                 foundSign = true;
1559                                 negative = true; // MS always make the number negative when there parentheses
1560                                 // even when NumberFormatInfo.NumberNegativePattern != 0!!!
1561                                 pos++;
1562                                 if (AllowLeadingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1563                                         return false;
1564
1565                                 if (s.Substring (pos, nfi.NegativeSign.Length) == nfi.NegativeSign) {
1566                                         if (!tryParse)
1567                                                 exc = GetFormatException ();
1568                                         return false;
1569                                 }
1570
1571                                 if (s.Substring (pos, nfi.PositiveSign.Length) == nfi.PositiveSign) {
1572                                         if (!tryParse)
1573                                                 exc = GetFormatException ();
1574                                         return false;
1575                                 }
1576                         }
1577
1578                         if (AllowLeadingSign && !foundSign) {
1579                                 // Sign + Currency
1580                                 FindSign (ref pos, s, nfi, ref foundSign, ref negative);
1581                                 if (foundSign) {
1582                                         if (AllowLeadingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1583                                                 return false;
1584                                         if (AllowCurrencySymbol) {
1585                                                 FindCurrency (ref pos, s, nfi,
1586                                                               ref foundCurrency);
1587                                                 if (foundCurrency && AllowLeadingWhite &&
1588                                                         !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1589                                                         return false;
1590                                         }
1591                                 }
1592                         }
1593
1594                         if (AllowCurrencySymbol && !foundCurrency) {
1595                                 // Currency + sign
1596                                 FindCurrency (ref pos, s, nfi, ref foundCurrency);
1597                                 if (foundCurrency) {
1598                                         if (AllowLeadingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1599                                                 return false;
1600                                         if (foundCurrency) {
1601                                                 if (!foundSign && AllowLeadingSign) {
1602                                                         FindSign (ref pos, s, nfi, ref foundSign,
1603                                                                   ref negative);
1604                                                         if (foundSign && AllowLeadingWhite &&
1605                                                                 !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1606                                                                 return false;
1607                                                 }
1608                                         }
1609                                 }
1610                         }
1611
1612                         BigInteger number = Zero;
1613                         int nDigits = 0;
1614                         int decimalPointPos = -1;
1615                         byte digitValue;
1616                         char hexDigit;
1617                         bool firstHexDigit = true;
1618
1619                         // Number stuff
1620                         while (pos < s.Length) {
1621
1622                                 if (!ValidDigit (s [pos], AllowHexSpecifier)) {
1623                                         if (AllowThousands &&
1624                                                 (FindOther (ref pos, s, nfi.NumberGroupSeparator)
1625                                                 || FindOther (ref pos, s, nfi.CurrencyGroupSeparator)))
1626                                                 continue;
1627
1628                                         if (AllowDecimalPoint && decimalPointPos < 0 &&
1629                                                 (FindOther (ref pos, s, nfi.NumberDecimalSeparator)
1630                                                 || FindOther (ref pos, s, nfi.CurrencyDecimalSeparator))) {
1631                                                 decimalPointPos = nDigits;
1632                                                 continue;
1633                                         }
1634
1635                                         break;
1636                                 }
1637
1638                                 nDigits++;
1639
1640                                 if (AllowHexSpecifier) {
1641                                         hexDigit = s [pos++];
1642                                         if (Char.IsDigit (hexDigit))
1643                                                 digitValue = (byte)(hexDigit - '0');
1644                                         else if (Char.IsLower (hexDigit))
1645                                                 digitValue = (byte)(hexDigit - 'a' + 10);
1646                                         else
1647                                                 digitValue = (byte)(hexDigit - 'A' + 10);
1648
1649                                         if (firstHexDigit && (byte)digitValue >= 8)
1650                                                 negative = true;
1651
1652                                         number = number * 16 + digitValue;
1653                                         firstHexDigit = false;
1654                                         continue;
1655                                 }
1656
1657                                 number = number * 10 + (byte)(s [pos++] - '0');
1658                         }
1659
1660                         // Post number stuff
1661                         if (nDigits == 0) {
1662                                 if (!tryParse)
1663                                         exc = GetFormatException ();
1664                                 return false;
1665                         }
1666
1667                         //signed hex value
1668                         if (AllowHexSpecifier && negative) {
1669                                 //number = 123456;
1670                                 BigInteger mask = BigInteger.Pow(16, nDigits) - 1;
1671                                 number = (number ^ mask) + 1;
1672                         }
1673
1674                         int exponent = 0;
1675                         if (AllowExponent)
1676                                 if (FindExponent (ref pos, s, ref exponent, tryParse, ref exc) && exc != null)
1677                                         return false;
1678
1679                         if (AllowTrailingSign && !foundSign) {
1680                                 // Sign + Currency
1681                                 FindSign (ref pos, s, nfi, ref foundSign, ref negative);
1682                                 if (foundSign && pos < s.Length) {
1683                                         if (AllowTrailingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1684                                                 return false;
1685                                 }
1686                         }
1687
1688                         if (AllowCurrencySymbol && !foundCurrency) {
1689                                 if (AllowTrailingWhite && pos < s.Length && !JumpOverWhite (ref pos, s, false, tryParse, ref exc))
1690                                         return false;
1691
1692                                 // Currency + sign
1693                                 FindCurrency (ref pos, s, nfi, ref foundCurrency);
1694                                 if (foundCurrency  && pos < s.Length) {
1695                                         if (AllowTrailingWhite  && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
1696                                                 return false;
1697                                         if (!foundSign && AllowTrailingSign)
1698                                                 FindSign (ref pos, s, nfi, ref foundSign,
1699                                                           ref negative);
1700                                 }
1701                         }
1702
1703                         if (AllowTrailingWhite && pos < s.Length && !JumpOverWhite (ref pos, s, false, tryParse, ref exc))
1704                                 return false;
1705
1706                         if (foundOpenParentheses) {
1707                                 if (pos >= s.Length || s [pos++] != ')') {
1708                                         if (!tryParse)
1709                                                 exc = GetFormatException ();
1710                                         return false;
1711                                 }
1712                                 if (AllowTrailingWhite && pos < s.Length && !JumpOverWhite (ref pos, s, false, tryParse, ref exc))
1713                                         return false;
1714                         }
1715
1716                         if (pos < s.Length && s [pos] != '\u0000') {
1717                                 if (!tryParse)
1718                                         exc = GetFormatException ();
1719                                 return false;
1720                         }
1721
1722                         if (decimalPointPos >= 0)
1723                                 exponent = exponent - nDigits + decimalPointPos;
1724
1725                         if (exponent < 0) {
1726                                 //
1727                                 // Any non-zero values after decimal point are not allowed
1728                                 //
1729                                 BigInteger remainder;
1730                                 number = BigInteger.DivRem(number, BigInteger.Pow(10, -exponent), out remainder);
1731
1732                                 if (!remainder.IsZero) {
1733                                         if (!tryParse)
1734                                                 exc = new OverflowException ("Value too large or too small. exp="+exponent+" rem = " + remainder + " pow = " + BigInteger.Pow(10, -exponent));
1735                                         return false;
1736                                 }
1737                         } else if (exponent > 0) {
1738                                 number = BigInteger.Pow(10, exponent) * number;
1739                         }
1740
1741                         if (number.sign == 0)
1742                                 result = number;
1743                         else if (negative)
1744                                 result = new BigInteger (-1, number.data);
1745                         else
1746                                 result = new BigInteger (1, number.data);
1747
1748                         return true;
1749                 }
1750
1751                 internal static bool CheckStyle (NumberStyles style, bool tryParse, ref Exception exc)
1752                 {
1753                         if ((style & NumberStyles.AllowHexSpecifier) != 0) {
1754                                 NumberStyles ne = style ^ NumberStyles.AllowHexSpecifier;
1755                                 if ((ne & NumberStyles.AllowLeadingWhite) != 0)
1756                                         ne ^= NumberStyles.AllowLeadingWhite;
1757                                 if ((ne & NumberStyles.AllowTrailingWhite) != 0)
1758                                         ne ^= NumberStyles.AllowTrailingWhite;
1759                                 if (ne != 0) {
1760                                         if (!tryParse)
1761                                                 exc = new ArgumentException (
1762                                                         "With AllowHexSpecifier only " +
1763                                                         "AllowLeadingWhite and AllowTrailingWhite " +
1764                                                         "are permitted.");
1765                                         return false;
1766                                 }
1767                         } else if ((uint) style > (uint) NumberStyles.Any){
1768                                 if (!tryParse)
1769                                         exc = new ArgumentException ("Not a valid number style");
1770                                 return false;
1771                         }
1772
1773                         return true;
1774                 }
1775
1776                 internal static bool JumpOverWhite (ref int pos, string s, bool reportError, bool tryParse, ref Exception exc)
1777                 {
1778                         while (pos < s.Length && Char.IsWhiteSpace (s [pos]))
1779                                 pos++;
1780
1781                         if (reportError && pos >= s.Length) {
1782                                 if (!tryParse)
1783                                         exc = GetFormatException ();
1784                                 return false;
1785                         }
1786
1787                         return true;
1788                 }
1789
1790                 internal static void FindSign (ref int pos, string s, NumberFormatInfo nfi,
1791                                       ref bool foundSign, ref bool negative)
1792                 {
1793                         if ((pos + nfi.NegativeSign.Length) <= s.Length &&
1794                             string.CompareOrdinal(s, pos, nfi.NegativeSign, 0, nfi.NegativeSign.Length) == 0) {
1795                                 negative = true;
1796                                 foundSign = true;
1797                                 pos += nfi.NegativeSign.Length;
1798                         } else if ((pos + nfi.PositiveSign.Length) <= s.Length &&
1799                             string.CompareOrdinal(s, pos, nfi.PositiveSign, 0, nfi.PositiveSign.Length) == 0) {
1800                                 negative = false;
1801                                 pos += nfi.PositiveSign.Length;
1802                                 foundSign = true;
1803                         }
1804                 }
1805
1806                 internal static void FindCurrency (ref int pos,
1807                                                  string s,
1808                                                  NumberFormatInfo nfi,
1809                                                  ref bool foundCurrency)
1810                 {
1811                         if ((pos + nfi.CurrencySymbol.Length) <= s.Length &&
1812                              s.Substring (pos, nfi.CurrencySymbol.Length) == nfi.CurrencySymbol) {
1813                                 foundCurrency = true;
1814                                 pos += nfi.CurrencySymbol.Length;
1815                         }
1816                 }
1817
1818                 internal static bool FindExponent (ref int pos, string s, ref int exponent, bool tryParse, ref Exception exc)
1819                 {
1820                         exponent = 0;
1821
1822                         if (pos >= s.Length || (s [pos] != 'e' && s[pos] != 'E')) {
1823                                 exc = null;
1824                                 return false;
1825                         }
1826
1827                         var i = pos + 1;
1828                         if (i == s.Length) {
1829                                 exc = tryParse ? null : GetFormatException ();
1830                                 return true;
1831                         }
1832
1833                         bool negative = false;
1834                         if (s [i] == '-') {
1835                                 negative = true;
1836                                 if(++i == s.Length){
1837                                         exc = tryParse ? null : GetFormatException ();
1838                                         return true;
1839                                 }
1840                         }
1841
1842                         if (s [i] == '+' && ++i == s.Length) {
1843                                 exc = tryParse ? null : GetFormatException ();
1844                                 return true;
1845                         }
1846
1847                         long exp = 0; // temp long value
1848                         for (; i < s.Length; i++) {
1849                                 if (!Char.IsDigit (s [i]))  {
1850                                         exc = tryParse ? null : GetFormatException ();
1851                                         return true;
1852                                 }
1853
1854                                 // Reduce the risk of throwing an overflow exc
1855                                 exp = checked (exp * 10 - (int) (s [i] - '0'));
1856                                 if (exp < Int32.MinValue || exp > Int32.MaxValue) {
1857                                         exc = tryParse ? null : new OverflowException ("Value too large or too small.");
1858                                         return true;
1859                                 }
1860                         }
1861
1862                         // exp value saved as negative
1863                         if(!negative)
1864                                 exp = -exp;
1865
1866                         exc = null;
1867                         exponent = (int)exp;
1868                         pos = i;
1869                         return true;
1870                 }
1871
1872                 internal static bool FindOther (ref int pos, string s, string other)
1873                 {
1874                         if ((pos + other.Length) <= s.Length &&
1875                              s.Substring (pos, other.Length) == other) {
1876                                 pos += other.Length;
1877                                 return true;
1878                         }
1879
1880                         return false;
1881                 }
1882
1883                 internal static bool ValidDigit (char e, bool allowHex)
1884                 {
1885                         if (allowHex)
1886                                 return Char.IsDigit (e) || (e >= 'A' && e <= 'F') || (e >= 'a' && e <= 'f');
1887
1888                         return Char.IsDigit (e);
1889                 }
1890
1891                 static Exception GetFormatException ()
1892                 {
1893                         return new FormatException ("Input string was not in the correct format");
1894                 }
1895
1896                 static bool ProcessTrailingWhitespace (bool tryParse, string s, int position, ref Exception exc)
1897                 {
1898                         int len = s.Length;
1899
1900                         for (int i = position; i < len; i++){
1901                                 char c = s [i];
1902
1903                                 if (c != 0 && !Char.IsWhiteSpace (c)){
1904                                         if (!tryParse)
1905                                                 exc = GetFormatException ();
1906                                         return false;
1907                                 }
1908                         }
1909                         return true;
1910                 }
1911
1912                 static bool Parse (string s, bool tryParse, out BigInteger result, out Exception exc)
1913                 {
1914                         int len;
1915                         int i, sign = 1;
1916                         bool digits_seen = false;
1917
1918                         result = Zero;
1919                         exc = null;
1920
1921                         if (s == null) {
1922                                 if (!tryParse)
1923                                         exc = new ArgumentNullException ("value");
1924                                 return false;
1925                         }
1926
1927                         len = s.Length;
1928
1929                         char c;
1930                         for (i = 0; i < len; i++){
1931                                 c = s [i];
1932                                 if (!Char.IsWhiteSpace (c))
1933                                         break;
1934                         }
1935
1936                         if (i == len) {
1937                                 if (!tryParse)
1938                                         exc = GetFormatException ();
1939                                 return false;
1940                         }
1941
1942                         var info = Thread.CurrentThread.CurrentCulture.NumberFormat;
1943
1944                         string negative = info.NegativeSign;
1945                         string positive = info.PositiveSign;
1946
1947                         if (string.CompareOrdinal (s, i, positive, 0, positive.Length) == 0)
1948                                 i += positive.Length;
1949                         else if (string.CompareOrdinal (s, i, negative, 0, negative.Length) == 0) {
1950                                 sign = -1;
1951                                 i += negative.Length;
1952                         }
1953
1954                         BigInteger val = Zero;
1955                         for (; i < len; i++){
1956                                 c = s [i];
1957
1958                                 if (c == '\0') {
1959                                         i = len;
1960                                         continue;
1961                                 }
1962
1963                                 if (c >= '0' && c <= '9'){
1964                                         byte d = (byte) (c - '0');
1965
1966                                         val = val * 10 + d;
1967
1968                                         digits_seen = true;
1969                                 } else if (!ProcessTrailingWhitespace (tryParse, s, i, ref exc))
1970                                         return false;
1971                         }
1972
1973                         if (!digits_seen) {
1974                                 if (!tryParse)
1975                                         exc = GetFormatException ();
1976                                 return false;
1977                         }
1978
1979                         if (val.sign == 0)
1980                                 result = val;
1981                         else if (sign == -1)
1982                                 result = new BigInteger (-1, val.data);
1983                         else
1984                                 result = new BigInteger (1, val.data);
1985
1986                         return true;
1987                 }
1988
1989                 public static BigInteger Min (BigInteger left, BigInteger right)
1990                 {
1991                         int ls = left.sign;
1992                         int rs = right.sign;
1993
1994                         if (ls < rs)
1995                                 return left;
1996                         if (rs < ls)
1997                                 return right;
1998
1999                         int r = CoreCompare (left.data, right.data);
2000                         if (ls == -1)
2001                                 r = -r;
2002
2003                         if (r <= 0)
2004                                 return left;
2005                         return right;
2006                 }
2007
2008
2009                 public static BigInteger Max (BigInteger left, BigInteger right)
2010                 {
2011                         int ls = left.sign;
2012                         int rs = right.sign;
2013
2014                         if (ls > rs)
2015                                 return left;
2016                         if (rs > ls)
2017                                 return right;
2018
2019                         int r = CoreCompare (left.data, right.data);
2020                         if (ls == -1)
2021                                 r = -r;
2022
2023                         if (r >= 0)
2024                                 return left;
2025                         return right;
2026                 }
2027
2028                 public static BigInteger Abs (BigInteger value)
2029                 {
2030                         return new BigInteger ((short)Math.Abs (value.sign), value.data);
2031                 }
2032
2033
2034                 public static BigInteger DivRem (BigInteger dividend, BigInteger divisor, out BigInteger remainder)
2035                 {
2036                         if (divisor.sign == 0)
2037                                 throw new DivideByZeroException ();
2038
2039                         if (dividend.sign == 0) {
2040                                 remainder = dividend;
2041                                 return dividend;
2042                         }
2043
2044                         uint[] quotient;
2045                         uint[] remainder_value;
2046
2047                         DivModUnsigned (dividend.data, divisor.data, out quotient, out remainder_value);
2048
2049                         int i;
2050                         for (i = remainder_value.Length - 1; i >= 0 && remainder_value [i] == 0; --i) ;
2051                         if (i == -1) {
2052                                 remainder = new BigInteger (0, ZERO);
2053                         } else {
2054                                 if (i < remainder_value.Length - 1)
2055                                         remainder_value = Resize (remainder_value, i + 1);
2056                                 remainder = new BigInteger (dividend.sign, remainder_value);
2057                         }
2058
2059                         for (i = quotient.Length - 1; i >= 0 && quotient [i] == 0; --i) ;
2060                         if (i == -1)
2061                                 return new BigInteger (0, ZERO);
2062                         if (i < quotient.Length - 1)
2063                                 quotient = Resize (quotient, i + 1);
2064
2065                         return new BigInteger ((short)(dividend.sign * divisor.sign), quotient);
2066                 }
2067
2068         public static BigInteger Pow (BigInteger value, int exponent)
2069                 {
2070                         if (exponent < 0)
2071                                 throw new ArgumentOutOfRangeException("exponent", "exp must be >= 0");
2072                         if (exponent == 0)
2073                                 return One;
2074                         if (exponent == 1)
2075                                 return value;
2076
2077                         BigInteger result = One;
2078                         while (exponent != 0) {
2079                                 if ((exponent & 1) != 0)
2080                                         result = result * value;
2081                                 if (exponent == 1)
2082                                         break;
2083
2084                                 value = value * value;
2085                                 exponent >>= 1;
2086                         }
2087                         return result;
2088         }
2089
2090                 public static BigInteger ModPow (BigInteger value, BigInteger exponent, BigInteger modulus) {
2091                         if (exponent.sign == -1)
2092                                 throw new ArgumentOutOfRangeException("exponent", "power must be >= 0");
2093                         if (modulus.sign == 0)
2094                                 throw new DivideByZeroException ();
2095
2096                         BigInteger result = One % modulus;
2097                         while (exponent.sign != 0) {
2098                                 if (!exponent.IsEven) {
2099                                         result = result * value;
2100                                         result = result % modulus;
2101                                 }
2102                                 if (exponent.IsOne)
2103                                         break;
2104                                 value = value * value;
2105                                 value = value % modulus;
2106                                 exponent >>= 1;
2107                         }
2108                         return result;
2109                 }
2110
2111                 public static BigInteger GreatestCommonDivisor (BigInteger left, BigInteger right)
2112                 {
2113                         if (left.sign != 0 && left.data.Length == 1 && left.data [0] == 1)
2114                                 return new BigInteger (1, ONE);
2115                         if (right.sign != 0 && right.data.Length == 1 && right.data [0] == 1)
2116                                 return new BigInteger (1, ONE);
2117                         if (left.IsZero)
2118                                 return Abs(right);
2119                         if (right.IsZero)
2120                                 return Abs(left);
2121
2122                         BigInteger x = new BigInteger (1, left.data);
2123                         BigInteger y = new BigInteger (1, right.data);
2124
2125                         BigInteger g = y;
2126
2127                         while (x.data.Length > 1) {
2128                                 g = x;
2129                                 x = y % x;
2130                                 y = g;
2131
2132                         }
2133                         if (x.IsZero) return g;
2134
2135                         // TODO: should we have something here if we can convert to long?
2136
2137                         //
2138                         // Now we can just do it with single precision. I am using the binary gcd method,
2139                         // as it should be faster.
2140                         //
2141
2142                         uint yy = x.data [0];
2143                         uint xx = (uint)(y % yy);
2144
2145                         int t = 0;
2146
2147                         while (((xx | yy) & 1) == 0) {
2148                                 xx >>= 1; yy >>= 1; t++;
2149                         }
2150                         while (xx != 0) {
2151                                 while ((xx & 1) == 0) xx >>= 1;
2152                                 while ((yy & 1) == 0) yy >>= 1;
2153                                 if (xx >= yy)
2154                                         xx = (xx - yy) >> 1;
2155                                 else
2156                                         yy = (yy - xx) >> 1;
2157                         }
2158
2159                         return yy << t;
2160                 }
2161
2162                 /*LAMESPEC Log doesn't specify to how many ulp is has to be precise
2163                 We are equilavent to MS with about 2 ULP
2164                 */
2165                 public static double Log (BigInteger value, Double baseValue)
2166                 {
2167                         if (value.sign == -1 || baseValue == 1.0d || baseValue == -1.0d ||
2168                                         baseValue == Double.NegativeInfinity || double.IsNaN (baseValue))
2169                                 return double.NaN;
2170
2171                         if (baseValue == 0.0d || baseValue == Double.PositiveInfinity)
2172                                 return value.IsOne ? 0 : double.NaN;
2173
2174                         if (value.sign == 0)
2175                                 return double.NegativeInfinity;
2176
2177                         int length = value.data.Length - 1;
2178                         int bitCount = -1;
2179                         for (int curBit = 31; curBit >= 0; curBit--) {
2180                                 if ((value.data [length] & (1 << curBit)) != 0) {
2181                                         bitCount = curBit + length * 32;
2182                                         break;
2183                                 }
2184                         }
2185
2186                         long bitlen = bitCount;
2187                         Double c = 0, d = 1;
2188
2189                         BigInteger testBit = One;
2190                         long tempBitlen = bitlen;
2191                         while (tempBitlen > Int32.MaxValue) {
2192                                 testBit = testBit << Int32.MaxValue;
2193                                 tempBitlen -= Int32.MaxValue;
2194                         }
2195                         testBit = testBit << (int)tempBitlen;
2196
2197                         for (long curbit = bitlen; curbit >= 0; --curbit) {
2198                                 if ((value & testBit).sign != 0)
2199                                         c += d;
2200                                 d *= 0.5;
2201                                 testBit = testBit >> 1;
2202                         }
2203                         return (System.Math.Log (c) + System.Math.Log (2) * bitlen) / System.Math.Log (baseValue);
2204                 }
2205
2206
2207         public static double Log (BigInteger value)
2208                 {
2209             return Log (value, Math.E);
2210         }
2211
2212
2213         public static double Log10 (BigInteger value)
2214                 {
2215             return Log (value, 10);
2216         }
2217
2218                 [CLSCompliantAttribute (false)]
2219                 public bool Equals (ulong other)
2220                 {
2221                         return CompareTo (other) == 0;
2222                 }
2223
2224                 public override int GetHashCode ()
2225                 {
2226                         uint hash = (uint)(sign * 0x01010101u);
2227                         int len = data != null ? data.Length : 0;
2228
2229                         for (int i = 0; i < len; ++i)
2230                                 hash ^= data [i];
2231                         return (int)hash;
2232                 }
2233
2234                 public static BigInteger Add (BigInteger left, BigInteger right)
2235                 {
2236                         return left + right;
2237                 }
2238
2239                 public static BigInteger Subtract (BigInteger left, BigInteger right)
2240                 {
2241                         return left - right;
2242                 }
2243
2244                 public static BigInteger Multiply (BigInteger left, BigInteger right)
2245                 {
2246                         return left * right;
2247                 }
2248
2249                 public static BigInteger Divide (BigInteger dividend, BigInteger divisor)
2250                 {
2251                         return dividend / divisor;
2252                 }
2253
2254                 public static BigInteger Remainder (BigInteger dividend, BigInteger divisor)
2255                 {
2256                         return dividend % divisor;
2257                 }
2258
2259                 public static BigInteger Negate (BigInteger value)
2260                 {
2261                         return - value;
2262                 }
2263
2264                 public int CompareTo (object obj)
2265                 {
2266                         if (obj == null)
2267                                 return 1;
2268
2269                         if (!(obj is BigInteger))
2270                                 return -1;
2271
2272                         return Compare (this, (BigInteger)obj);
2273                 }
2274
2275                 public int CompareTo (BigInteger other)
2276                 {
2277                         return Compare (this, other);
2278                 }
2279
2280                 [CLSCompliantAttribute (false)]
2281                 public int CompareTo (ulong other)
2282                 {
2283                         if (sign < 0)
2284                                 return -1;
2285                         if (sign == 0)
2286                                 return other == 0 ? 0 : -1;
2287
2288                         if (data.Length > 2)
2289                                 return 1;
2290
2291                         uint high = (uint)(other >> 32);
2292                         uint low = (uint)other;
2293
2294                         return LongCompare (low, high);
2295                 }
2296
2297                 int LongCompare (uint low, uint high)
2298                 {
2299                         uint h = 0;
2300                         if (data.Length > 1)
2301                                 h = data [1];
2302
2303                         if (h > high)
2304                                 return 1;
2305                         if (h < high)
2306                                 return -1;
2307
2308                         uint l = data [0];
2309
2310                         if (l > low)
2311                                 return 1;
2312                         if (l < low)
2313                                 return -1;
2314
2315                         return 0;
2316                 }
2317
2318                 public int CompareTo (long other)
2319                 {
2320                         int ls = sign;
2321                         int rs = Math.Sign (other);
2322
2323                         if (ls != rs)
2324                                 return ls > rs ? 1 : -1;
2325
2326                         if (ls == 0)
2327                                 return 0;
2328
2329                         if (data.Length > 2)
2330                                 return sign;
2331
2332                         if (other < 0)
2333                                 other = -other;
2334                         uint low = (uint)other;
2335                         uint high = (uint)((ulong)other >> 32);
2336
2337                         int r = LongCompare (low, high);
2338                         if (ls == -1)
2339                                 r = -r;
2340
2341                         return r;
2342                 }
2343
2344                 public static int Compare (BigInteger left, BigInteger right)
2345                 {
2346                         int ls = left.sign;
2347                         int rs = right.sign;
2348
2349                         if (ls != rs)
2350                                 return ls > rs ? 1 : -1;
2351
2352                         int r = CoreCompare (left.data, right.data);
2353                         if (ls < 0)
2354                                 r = -r;
2355                         return r;
2356                 }
2357
2358
2359                 static int TopByte (uint x)
2360                 {
2361                         if ((x & 0xFFFF0000u) != 0) {
2362                                 if ((x & 0xFF000000u) != 0)
2363                                         return 4;
2364                                 return 3;
2365                         }
2366                         if ((x & 0xFF00u) != 0)
2367                                 return 2;
2368                         return 1;
2369                 }
2370
2371                 static int FirstNonFFByte (uint word)
2372                 {
2373                         if ((word & 0xFF000000u) != 0xFF000000u)
2374                                 return 4;
2375                         else if ((word & 0xFF0000u) != 0xFF0000u)
2376                                 return 3;
2377                         else if ((word & 0xFF00u) != 0xFF00u)
2378                                 return 2;
2379                         return 1;
2380                 }
2381
2382                 public byte[] ToByteArray ()
2383                 {
2384                         if (sign == 0)
2385                                 return new byte [1];
2386
2387                         //number of bytes not counting upper word
2388                         int bytes = (data.Length - 1) * 4;
2389                         bool needExtraZero = false;
2390
2391                         uint topWord = data [data.Length - 1];
2392                         int extra;
2393
2394                         //if the topmost bit is set we need an extra
2395                         if (sign == 1) {
2396                                 extra = TopByte (topWord);
2397                                 uint mask = 0x80u << ((extra - 1) * 8);
2398                                 if ((topWord & mask) != 0) {
2399                                         needExtraZero = true;
2400                                 }
2401                         } else {
2402                                 extra = TopByte (topWord);
2403                         }
2404
2405                         byte[] res = new byte [bytes + extra + (needExtraZero ? 1 : 0) ];
2406                         if (sign == 1) {
2407                                 int j = 0;
2408                                 int end = data.Length - 1;
2409                                 for (int i = 0; i < end; ++i) {
2410                                         uint word = data [i];
2411
2412                                         res [j++] = (byte)word;
2413                                         res [j++] = (byte)(word >> 8);
2414                                         res [j++] = (byte)(word >> 16);
2415                                         res [j++] = (byte)(word >> 24);
2416                                 }
2417                                 while (extra-- > 0) {
2418                                         res [j++] = (byte)topWord;
2419                                         topWord >>= 8;
2420                                 }
2421                         } else {
2422                                 int j = 0;
2423                                 int end = data.Length - 1;
2424
2425                                 uint carry = 1, word;
2426                                 ulong add;
2427                                 for (int i = 0; i < end; ++i) {
2428                                         word = data [i];
2429                                         add = (ulong)~word + carry;
2430                                         word = (uint)add;
2431                                         carry = (uint)(add >> 32);
2432
2433                                         res [j++] = (byte)word;
2434                                         res [j++] = (byte)(word >> 8);
2435                                         res [j++] = (byte)(word >> 16);
2436                                         res [j++] = (byte)(word >> 24);
2437                                 }
2438
2439                                 add = (ulong)~topWord + (carry);
2440                                 word = (uint)add;
2441                                 carry = (uint)(add >> 32);
2442                                 if (carry == 0) {
2443                                         int ex = FirstNonFFByte (word);
2444                                         bool needExtra = (word & (1 << (ex * 8 - 1))) == 0;
2445                                         int to = ex + (needExtra ? 1 : 0);
2446
2447                                         if (to != extra)
2448                                                 res = Resize (res, bytes + to);
2449
2450                                         while (ex-- > 0) {
2451                                                 res [j++] = (byte)word;
2452                                                 word >>= 8;
2453                                         }
2454                                         if (needExtra)
2455                                                 res [j++] = 0xFF;
2456                                 } else {
2457                                         res = Resize (res, bytes + 5);
2458                                         res [j++] = (byte)word;
2459                                         res [j++] = (byte)(word >> 8);
2460                                         res [j++] = (byte)(word >> 16);
2461                                         res [j++] = (byte)(word >> 24);
2462                                         res [j++] = 0xFF;
2463                                 }
2464                         }
2465
2466                         return res;
2467                 }
2468
2469                 static byte[] Resize (byte[] v, int len)
2470                 {
2471                         byte[] res = new byte [len];
2472                         Array.Copy (v, res, Math.Min (v.Length, len));
2473                         return res;
2474                 }
2475
2476                 static uint[] Resize (uint[] v, int len)
2477                 {
2478                         uint[] res = new uint [len];
2479                         Array.Copy (v, res, Math.Min (v.Length, len));
2480                         return res;
2481                 }
2482
2483                 static uint[] CoreAdd (uint[] a, uint[] b)
2484                 {
2485                         if (a.Length < b.Length) {
2486                                 uint[] tmp = a;
2487                                 a = b;
2488                                 b = tmp;
2489                         }
2490
2491                         int bl = a.Length;
2492                         int sl = b.Length;
2493
2494                         uint[] res = new uint [bl];
2495
2496                         ulong sum = 0;
2497
2498                         int i = 0;
2499                         for (; i < sl; i++) {
2500                                 sum = sum + a [i] + b [i];
2501                                 res [i] = (uint)sum;
2502                                 sum >>= 32;
2503                         }
2504
2505                         for (; i < bl; i++) {
2506                                 sum = sum + a [i];
2507                                 res [i] = (uint)sum;
2508                                 sum >>= 32;
2509                         }
2510
2511                         if (sum != 0) {
2512                                 res = Resize (res, bl + 1);
2513                                 res [i] = (uint)sum;
2514                         }
2515
2516                         return res;
2517                 }
2518
2519                 /*invariant a > b*/
2520                 static uint[] CoreSub (uint[] a, uint[] b)
2521                 {
2522                         int bl = a.Length;
2523                         int sl = b.Length;
2524
2525                         uint[] res = new uint [bl];
2526
2527                         ulong borrow = 0;
2528                         int i;
2529                         for (i = 0; i < sl; ++i) {
2530                                 borrow = (ulong)a [i] - b [i] - borrow;
2531
2532                                 res [i] = (uint)borrow;
2533                                 borrow = (borrow >> 32) & 0x1;
2534                         }
2535
2536                         for (; i < bl; i++) {
2537                                 borrow = (ulong)a [i] - borrow;
2538                                 res [i] = (uint)borrow;
2539                                 borrow = (borrow >> 32) & 0x1;
2540                         }
2541
2542                         //remove extra zeroes
2543                         for (i = bl - 1; i >= 0 && res [i] == 0; --i) ;
2544                         if (i < bl - 1)
2545                                 res = Resize (res, i + 1);
2546
2547             return res;
2548                 }
2549
2550
2551                 static uint[] CoreAdd (uint[] a, uint b)
2552                 {
2553                         int len = a.Length;
2554                         uint[] res = new uint [len];
2555
2556                         ulong sum = b;
2557                         int i;
2558                         for (i = 0; i < len; i++) {
2559                                 sum = sum + a [i];
2560                                 res [i] = (uint)sum;
2561                                 sum >>= 32;
2562                         }
2563
2564                         if (sum != 0) {
2565                                 res = Resize (res, len + 1);
2566                                 res [i] = (uint)sum;
2567                         }
2568
2569                         return res;
2570                 }
2571
2572                 static uint[] CoreSub (uint[] a, uint b)
2573                 {
2574                         int len = a.Length;
2575                         uint[] res = new uint [len];
2576
2577                         ulong borrow = b;
2578                         int i;
2579                         for (i = 0; i < len; i++) {
2580                                 borrow = (ulong)a [i] - borrow;
2581                                 res [i] = (uint)borrow;
2582                                 borrow = (borrow >> 32) & 0x1;
2583                         }
2584
2585                         //remove extra zeroes
2586                         for (i = len - 1; i >= 0 && res [i] == 0; --i) ;
2587                         if (i < len - 1)
2588                                 res = Resize (res, i + 1);
2589
2590             return res;
2591                 }
2592
2593                 static int CoreCompare (uint[] a, uint[] b)
2594                 {
2595                         int al = a != null ? a.Length : 0;
2596                         int bl = b != null ? b.Length : 0;
2597
2598                         if (al > bl)
2599                                 return 1;
2600                         if (bl > al)
2601                                 return -1;
2602
2603                         for (int i = al - 1; i >= 0; --i) {
2604                                 uint ai = a [i];
2605                                 uint bi = b [i];
2606                                 if (ai > bi)
2607                                         return 1;
2608                                 if (ai < bi)
2609                                         return -1;
2610                         }
2611                         return 0;
2612                 }
2613
2614                 static int GetNormalizeShift(uint value) {
2615                         int shift = 0;
2616
2617                         if ((value & 0xFFFF0000) == 0) { value <<= 16; shift += 16; }
2618                         if ((value & 0xFF000000) == 0) { value <<= 8; shift += 8; }
2619                         if ((value & 0xF0000000) == 0) { value <<= 4; shift += 4; }
2620                         if ((value & 0xC0000000) == 0) { value <<= 2; shift += 2; }
2621                         if ((value & 0x80000000) == 0) { value <<= 1; shift += 1; }
2622
2623                         return shift;
2624                 }
2625
2626                 static void Normalize (uint[] u, int l, uint[] un, int shift)
2627                 {
2628                         uint carry = 0;
2629                         int i;
2630                         if (shift > 0) {
2631                                 int rshift = 32 - shift;
2632                                 for (i = 0; i < l; i++) {
2633                                         uint ui = u [i];
2634                                         un [i] = (ui << shift) | carry;
2635                                         carry = ui >> rshift;
2636                                 }
2637                         } else {
2638                                 for (i = 0; i < l; i++) {
2639                                         un [i] = u [i];
2640                                 }
2641                         }
2642
2643                         while (i < un.Length) {
2644                                 un [i++] = 0;
2645                         }
2646
2647                         if (carry != 0) {
2648                                 un [l] = carry;
2649                         }
2650                 }
2651
2652                 static void Unnormalize (uint[] un, out uint[] r, int shift)
2653                 {
2654                         int length = un.Length;
2655                         r = new uint [length];
2656
2657                         if (shift > 0) {
2658                                 int lshift = 32 - shift;
2659                                 uint carry = 0;
2660                                 for (int i = length - 1; i >= 0; i--) {
2661                                         uint uni = un [i];
2662                                         r [i] = (uni >> shift) | carry;
2663                                         carry = (uni << lshift);
2664                                 }
2665                         } else {
2666                                 for (int i = 0; i < length; i++) {
2667                                         r [i] = un [i];
2668                                 }
2669                         }
2670                 }
2671
2672                 const ulong Base = 0x100000000;
2673                 static void DivModUnsigned (uint[] u, uint[] v, out uint[] q, out uint[] r)
2674                 {
2675                         int m = u.Length;
2676                         int n = v.Length;
2677
2678                         if (n <= 1) {
2679                                 //  Divide by single digit
2680                                 //
2681                                 ulong rem = 0;
2682                                 uint v0 = v [0];
2683                                 q = new uint[m];
2684                                 r = new uint [1];
2685
2686                                 for (int j = m - 1; j >= 0; j--) {
2687                                         rem *= Base;
2688                                         rem += u[j];
2689
2690                                         ulong div = rem / v0;
2691                                         rem -= div * v0;
2692                                         q[j] = (uint)div;
2693                                 }
2694                                 r [0] = (uint)rem;
2695                         } else if (m >= n) {
2696                                 int shift = GetNormalizeShift (v [n - 1]);
2697
2698                                 uint[] un = new uint [m + 1];
2699                                 uint[] vn = new uint [n];
2700
2701                                 Normalize (u, m, un, shift);
2702                                 Normalize (v, n, vn, shift);
2703
2704                                 q = new uint [m - n + 1];
2705                                 r = null;
2706
2707                                 //  Main division loop
2708                                 //
2709                                 for (int j = m - n; j >= 0; j--) {
2710                                         ulong rr, qq;
2711                                         int i;
2712
2713                                         rr = Base * un [j + n] + un [j + n - 1];
2714                                         qq = rr / vn [n - 1];
2715                                         rr -= qq * vn [n - 1];
2716
2717                                         for (; ; ) {
2718                                                 // Estimate too big ?
2719                                                 //
2720                                                 if ((qq >= Base) || (qq * vn [n - 2] > (rr * Base + un [j + n - 2]))) {
2721                                                         qq--;
2722                                                         rr += (ulong)vn [n - 1];
2723                                                         if (rr < Base)
2724                                                                 continue;
2725                                                 }
2726                                                 break;
2727                                         }
2728
2729
2730                                         //  Multiply and subtract
2731                                         //
2732                                         long b = 0;
2733                                         long t = 0;
2734                                         for (i = 0; i < n; i++) {
2735                                                 ulong p = vn [i] * qq;
2736                                                 t = (long)un [i + j] - (long)(uint)p - b;
2737                                                 un [i + j] = (uint)t;
2738                                                 p >>= 32;
2739                                                 t >>= 32;
2740                                                 b = (long)p - t;
2741                                         }
2742                                         t = (long)un [j + n] - b;
2743                                         un [j + n] = (uint)t;
2744
2745                                         //  Store the calculated value
2746                                         //
2747                                         q [j] = (uint)qq;
2748
2749                                         //  Add back vn[0..n] to un[j..j+n]
2750                                         //
2751                                         if (t < 0) {
2752                                                 q [j]--;
2753                                                 ulong c = 0;
2754                                                 for (i = 0; i < n; i++) {
2755                                                         c = (ulong)vn [i] + un [j + i] + c;
2756                                                         un [j + i] = (uint)c;
2757                                                         c >>= 32;
2758                                                 }
2759                                                 c += (ulong)un [j + n];
2760                                                 un [j + n] = (uint)c;
2761                                         }
2762                                 }
2763
2764                                 Unnormalize (un, out r, shift);
2765                         } else {
2766                                 q = new uint [] { 0 };
2767                                 r = u;
2768                         }
2769                 }
2770         }
2771 }