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 #if NET_4_0
1472                 [MonoTODO]
1473                 public static BigInteger Parse (string value, NumberStyles style)
1474                 {
1475                         throw new NotImplementedException ();
1476                 }
1477
1478                 [MonoTODO]
1479                 public static BigInteger Parse (string value, IFormatProvider provider)
1480                 {
1481                         throw new NotImplementedException ();
1482                 }
1483
1484                 [MonoTODO]
1485                 public static BigInteger Parse (
1486                         string value, NumberStyles style, IFormatProvider provider)
1487                 {
1488                         throw new InvalidOperationException ();
1489                 }
1490
1491                 [MonoTODO]
1492                 public static bool TryParse (
1493                         string value, NumberStyles style, IFormatProvider provider,
1494                         out BigInteger result)
1495                 {
1496                         throw new NotImplementedException ();
1497                 }
1498 #endif
1499
1500
1501                 static Exception GetFormatException ()
1502                 {
1503                         return new FormatException ("Input string was not in the correct format");
1504                 }
1505
1506                 static bool ProcessTrailingWhitespace (bool tryParse, string s, int position, ref Exception exc)
1507                 {
1508                         int len = s.Length;
1509
1510                         for (int i = position; i < len; i++){
1511                                 char c = s [i];
1512
1513                                 if (c != 0 && !Char.IsWhiteSpace (c)){
1514                                         if (!tryParse)
1515                                                 exc = GetFormatException ();
1516                                         return false;
1517                                 }
1518                         }
1519                         return true;
1520                 }
1521
1522                 static bool Parse (string s, bool tryParse, out BigInteger result, out Exception exc)
1523                 {
1524                         int len;
1525                         int i, sign = 1;
1526                         bool digits_seen = false;
1527
1528                         result = Zero;
1529                         exc = null;
1530
1531                         if (s == null) {
1532                                 if (!tryParse)
1533                                         exc = new ArgumentNullException ("value");
1534                                 return false;
1535                         }
1536
1537                         len = s.Length;
1538
1539                         char c;
1540                         for (i = 0; i < len; i++){
1541                                 c = s [i];
1542                                 if (!Char.IsWhiteSpace (c))
1543                                         break;
1544                         }
1545
1546                         if (i == len) {
1547                                 if (!tryParse)
1548                                         exc = GetFormatException ();
1549                                 return false;
1550                         }
1551
1552                         var info = Thread.CurrentThread.CurrentCulture.NumberFormat;
1553
1554                         string negative = info.NegativeSign;
1555                         string positive = info.PositiveSign;
1556
1557                         if (string.CompareOrdinal (s, i, positive, 0, positive.Length) == 0)
1558                                 i += positive.Length;
1559                         else if (string.CompareOrdinal (s, i, negative, 0, negative.Length) == 0) {
1560                                 sign = -1;
1561                                 i += negative.Length;
1562                         }
1563
1564                         BigInteger val = Zero;
1565                         for (; i < len; i++){
1566                                 c = s [i];
1567
1568                                 if (c == '\0') {
1569                                         i = len;
1570                                         continue;
1571                                 }
1572
1573                                 if (c >= '0' && c <= '9'){
1574                                         byte d = (byte) (c - '0');
1575
1576                                         val = val * 10 + d;
1577
1578                                         digits_seen = true;
1579                                 } else if (!ProcessTrailingWhitespace (tryParse, s, i, ref exc))
1580                                         return false;
1581                         }
1582
1583                         if (!digits_seen) {
1584                                 if (!tryParse)
1585                                         exc = GetFormatException ();
1586                                 return false;
1587                         }
1588
1589                         if (val.sign == 0)
1590                                 result = val;
1591                         else if (sign == -1)
1592                                 result = new BigInteger (-1, val.data);
1593                         else
1594                                 result = new BigInteger (1, val.data);
1595
1596                         return true;
1597                 }
1598
1599                 public static BigInteger Min (BigInteger left, BigInteger right)
1600                 {
1601                         int ls = left.sign;
1602                         int rs = right.sign;
1603
1604                         if (ls < rs)
1605                                 return left;
1606                         if (rs < ls)
1607                                 return right;
1608
1609                         int r = CoreCompare (left.data, right.data);
1610                         if (ls == -1)
1611                                 r = -r;
1612
1613                         if (r <= 0)
1614                                 return left;
1615                         return right;
1616                 }
1617
1618
1619                 public static BigInteger Max (BigInteger left, BigInteger right)
1620                 {
1621                         int ls = left.sign;
1622                         int rs = right.sign;
1623
1624                         if (ls > rs)
1625                                 return left;
1626                         if (rs > ls)
1627                                 return right;
1628
1629                         int r = CoreCompare (left.data, right.data);
1630                         if (ls == -1)
1631                                 r = -r;
1632
1633                         if (r >= 0)
1634                                 return left;
1635                         return right;
1636                 }
1637
1638                 public static BigInteger Abs (BigInteger value)
1639                 {
1640                         return new BigInteger ((short)Math.Abs (value.sign), value.data);
1641                 }
1642
1643
1644                 public static BigInteger DivRem (BigInteger dividend, BigInteger divisor, out BigInteger remainder)
1645                 {
1646                         if (divisor.sign == 0)
1647                                 throw new DivideByZeroException ();
1648
1649                         if (dividend.sign == 0) {
1650                                 remainder = dividend;
1651                                 return dividend;
1652                         }
1653
1654                         uint[] quotient;
1655                         uint[] remainder_value;
1656
1657                         DivModUnsigned (dividend.data, divisor.data, out quotient, out remainder_value);
1658
1659                         int i;
1660                         for (i = remainder_value.Length - 1; i >= 0 && remainder_value [i] == 0; --i) ;
1661                         if (i == -1) {
1662                                 remainder = new BigInteger (0, ZERO);
1663                         } else {
1664                                 if (i < remainder_value.Length - 1)
1665                                         remainder_value = Resize (remainder_value, i + 1);
1666                                 remainder = new BigInteger (dividend.sign, remainder_value);
1667                         }
1668
1669                         for (i = quotient.Length - 1; i >= 0 && quotient [i] == 0; --i) ;
1670                         if (i == -1)
1671                                 return new BigInteger (0, ZERO);
1672                         if (i < quotient.Length - 1)
1673                                 quotient = Resize (quotient, i + 1);
1674
1675                         return new BigInteger ((short)(dividend.sign * divisor.sign), quotient);
1676                 }
1677
1678         public static BigInteger Pow (BigInteger value, int exponent)
1679                 {
1680                         if (exponent < 0)
1681                                 throw new ArgumentOutOfRangeException("exponent", "exp must be >= 0");
1682                         if (exponent == 0)
1683                                 return One;
1684                         if (exponent == 1)
1685                                 return value;
1686
1687                         BigInteger result = One;
1688                         while (exponent != 0) {
1689                                 if ((exponent & 1) != 0)
1690                                         result = result * value;
1691                                 if (exponent == 1)
1692                                         break;
1693
1694                                 value = value * value;
1695                                 exponent >>= 1;
1696                         }
1697                         return result;
1698         }
1699
1700                 public static BigInteger ModPow (BigInteger value, BigInteger exponent, BigInteger modulus) {
1701                         if (exponent.sign == -1)
1702                                 throw new ArgumentOutOfRangeException("exponent", "power must be >= 0");
1703                         if (modulus.sign == 0)
1704                                 throw new DivideByZeroException ();
1705
1706                         BigInteger result = One % modulus;
1707                         while (exponent.sign != 0) {
1708                                 if (!exponent.IsEven) {
1709                                         result = result * value;
1710                                         result = result % modulus;
1711                                 }
1712                                 if (exponent.IsOne)
1713                                         break;
1714                                 value = value * value;
1715                                 value = value % modulus;
1716                                 exponent >>= 1;
1717                         }
1718                         return result;
1719                 }
1720
1721                 public static BigInteger GreatestCommonDivisor (BigInteger left, BigInteger right)
1722                 {
1723                         if (left.sign != 0 && left.data.Length == 1 && left.data [0] == 1)
1724                                 return new BigInteger (1, ONE);
1725                         if (right.sign != 0 && right.data.Length == 1 && right.data [0] == 1)
1726                                 return new BigInteger (1, ONE);
1727                         if (left.IsZero)
1728                                 return Abs(right);
1729                         if (right.IsZero)
1730                                 return Abs(left);
1731
1732                         BigInteger x = new BigInteger (1, left.data);
1733                         BigInteger y = new BigInteger (1, right.data);
1734
1735                         BigInteger g = y;
1736
1737                         while (x.data.Length > 1) {
1738                                 g = x;
1739                                 x = y % x;
1740                                 y = g;
1741
1742                         }
1743                         if (x.IsZero) return g;
1744
1745                         // TODO: should we have something here if we can convert to long?
1746
1747                         //
1748                         // Now we can just do it with single precision. I am using the binary gcd method,
1749                         // as it should be faster.
1750                         //
1751
1752                         uint yy = x.data [0];
1753                         uint xx = (uint)(y % yy);
1754
1755                         int t = 0;
1756
1757                         while (((xx | yy) & 1) == 0) {
1758                                 xx >>= 1; yy >>= 1; t++;
1759                         }
1760                         while (xx != 0) {
1761                                 while ((xx & 1) == 0) xx >>= 1;
1762                                 while ((yy & 1) == 0) yy >>= 1;
1763                                 if (xx >= yy)
1764                                         xx = (xx - yy) >> 1;
1765                                 else
1766                                         yy = (yy - xx) >> 1;
1767                         }
1768
1769                         return yy << t;
1770                 }
1771
1772                 /*LAMESPEC Log doesn't specify to how many ulp is has to be precise
1773                 We are equilavent to MS with about 2 ULP
1774                 */
1775                 public static double Log (BigInteger value, Double baseValue)
1776                 {
1777                         if (value.sign == -1 || baseValue == 1.0d || baseValue == -1.0d ||
1778                                         baseValue == Double.NegativeInfinity || double.IsNaN (baseValue))
1779                                 return double.NaN;
1780
1781                         if (baseValue == 0.0d || baseValue == Double.PositiveInfinity)
1782                                 return value.IsOne ? 0 : double.NaN;
1783
1784                         if (value.sign == 0)
1785                                 return double.NegativeInfinity;
1786
1787                         int length = value.data.Length - 1;
1788                         int bitCount = -1;
1789                         for (int curBit = 31; curBit >= 0; curBit--) {
1790                                 if ((value.data [length] & (1 << curBit)) != 0) {
1791                                         bitCount = curBit + length * 32;
1792                                         break;
1793                                 }
1794                         }
1795
1796                         long bitlen = bitCount;
1797                         Double c = 0, d = 1;
1798
1799                         BigInteger testBit = One;
1800                         long tempBitlen = bitlen;
1801                         while (tempBitlen > Int32.MaxValue) {
1802                                 testBit = testBit << Int32.MaxValue;
1803                                 tempBitlen -= Int32.MaxValue;
1804                         }
1805                         testBit = testBit << (int)tempBitlen;
1806
1807                         for (long curbit = bitlen; curbit >= 0; --curbit) {
1808                                 if ((value & testBit).sign != 0)
1809                                         c += d;
1810                                 d *= 0.5;
1811                                 testBit = testBit >> 1;
1812                         }
1813                         return (System.Math.Log (c) + System.Math.Log (2) * bitlen) / System.Math.Log (baseValue);
1814                 }
1815
1816
1817         public static double Log (BigInteger value)
1818                 {
1819             return Log (value, Math.E);
1820         }
1821
1822
1823         public static double Log10 (BigInteger value)
1824                 {
1825             return Log (value, 10);
1826         }
1827
1828                 [CLSCompliantAttribute (false)]
1829                 public bool Equals (ulong other)
1830                 {
1831                         return CompareTo (other) == 0;
1832                 }
1833
1834                 public override int GetHashCode ()
1835                 {
1836                         uint hash = (uint)(sign * 0x01010101u);
1837                         int len = data != null ? data.Length : 0;
1838
1839                         for (int i = 0; i < len; ++i)
1840                                 hash ^= data [i];
1841                         return (int)hash;
1842                 }
1843
1844                 public static BigInteger Add (BigInteger left, BigInteger right)
1845                 {
1846                         return left + right;
1847                 }
1848
1849                 public static BigInteger Subtract (BigInteger left, BigInteger right)
1850                 {
1851                         return left - right;
1852                 }
1853
1854                 public static BigInteger Multiply (BigInteger left, BigInteger right)
1855                 {
1856                         return left * right;
1857                 }
1858
1859                 public static BigInteger Divide (BigInteger dividend, BigInteger divisor)
1860                 {
1861                         return dividend / divisor;
1862                 }
1863
1864                 public static BigInteger Remainder (BigInteger dividend, BigInteger divisor)
1865                 {
1866                         return dividend % divisor;
1867                 }
1868
1869                 public static BigInteger Negate (BigInteger value)
1870                 {
1871                         return - value;
1872                 }
1873
1874                 public int CompareTo (object obj)
1875                 {
1876                         if (obj == null)
1877                                 return 1;
1878
1879                         if (!(obj is BigInteger))
1880                                 return -1;
1881
1882                         return Compare (this, (BigInteger)obj);
1883                 }
1884
1885                 public int CompareTo (BigInteger other)
1886                 {
1887                         return Compare (this, other);
1888                 }
1889
1890                 [CLSCompliantAttribute (false)]
1891                 public int CompareTo (ulong other)
1892                 {
1893                         if (sign < 0)
1894                                 return -1;
1895                         if (sign == 0)
1896                                 return other == 0 ? 0 : -1;
1897
1898                         if (data.Length > 2)
1899                                 return 1;
1900
1901                         uint high = (uint)(other >> 32);
1902                         uint low = (uint)other;
1903
1904                         return LongCompare (low, high);
1905                 }
1906
1907                 int LongCompare (uint low, uint high)
1908                 {
1909                         uint h = 0;
1910                         if (data.Length > 1)
1911                                 h = data [1];
1912
1913                         if (h > high)
1914                                 return 1;
1915                         if (h < high)
1916                                 return -1;
1917
1918                         uint l = data [0];
1919
1920                         if (l > low)
1921                                 return 1;
1922                         if (l < low)
1923                                 return -1;
1924
1925                         return 0;
1926                 }
1927
1928                 public int CompareTo (long other)
1929                 {
1930                         int ls = sign;
1931                         int rs = Math.Sign (other);
1932
1933                         if (ls != rs)
1934                                 return ls > rs ? 1 : -1;
1935
1936                         if (ls == 0)
1937                                 return 0;
1938
1939                         if (data.Length > 2)
1940                                 return sign;
1941
1942                         if (other < 0)
1943                                 other = -other;
1944                         uint low = (uint)other;
1945                         uint high = (uint)((ulong)other >> 32);
1946
1947                         int r = LongCompare (low, high);
1948                         if (ls == -1)
1949                                 r = -r;
1950
1951                         return r;
1952                 }
1953
1954                 public static int Compare (BigInteger left, BigInteger right)
1955                 {
1956                         int ls = left.sign;
1957                         int rs = right.sign;
1958
1959                         if (ls != rs)
1960                                 return ls > rs ? 1 : -1;
1961
1962                         int r = CoreCompare (left.data, right.data);
1963                         if (ls < 0)
1964                                 r = -r;
1965                         return r;
1966                 }
1967
1968
1969                 static int TopByte (uint x)
1970                 {
1971                         if ((x & 0xFFFF0000u) != 0) {
1972                                 if ((x & 0xFF000000u) != 0)
1973                                         return 4;
1974                                 return 3;
1975                         }
1976                         if ((x & 0xFF00u) != 0)
1977                                 return 2;
1978                         return 1;
1979                 }
1980
1981                 static int FirstNonFFByte (uint word)
1982                 {
1983                         if ((word & 0xFF000000u) != 0xFF000000u)
1984                                 return 4;
1985                         else if ((word & 0xFF0000u) != 0xFF0000u)
1986                                 return 3;
1987                         else if ((word & 0xFF00u) != 0xFF00u)
1988                                 return 2;
1989                         return 1;
1990                 }
1991
1992                 public byte[] ToByteArray ()
1993                 {
1994                         if (sign == 0)
1995                                 return new byte [1];
1996
1997                         //number of bytes not counting upper word
1998                         int bytes = (data.Length - 1) * 4;
1999                         bool needExtraZero = false;
2000
2001                         uint topWord = data [data.Length - 1];
2002                         int extra;
2003
2004                         //if the topmost bit is set we need an extra
2005                         if (sign == 1) {
2006                                 extra = TopByte (topWord);
2007                                 uint mask = 0x80u << ((extra - 1) * 8);
2008                                 if ((topWord & mask) != 0) {
2009                                         needExtraZero = true;
2010                                 }
2011                         } else {
2012                                 extra = TopByte (topWord);
2013                         }
2014
2015                         byte[] res = new byte [bytes + extra + (needExtraZero ? 1 : 0) ];
2016                         if (sign == 1) {
2017                                 int j = 0;
2018                                 int end = data.Length - 1;
2019                                 for (int i = 0; i < end; ++i) {
2020                                         uint word = data [i];
2021
2022                                         res [j++] = (byte)word;
2023                                         res [j++] = (byte)(word >> 8);
2024                                         res [j++] = (byte)(word >> 16);
2025                                         res [j++] = (byte)(word >> 24);
2026                                 }
2027                                 while (extra-- > 0) {
2028                                         res [j++] = (byte)topWord;
2029                                         topWord >>= 8;
2030                                 }
2031                         } else {
2032                                 int j = 0;
2033                                 int end = data.Length - 1;
2034
2035                                 uint carry = 1, word;
2036                                 ulong add;
2037                                 for (int i = 0; i < end; ++i) {
2038                                         word = data [i];
2039                                         add = (ulong)~word + carry;
2040                                         word = (uint)add;
2041                                         carry = (uint)(add >> 32);
2042
2043                                         res [j++] = (byte)word;
2044                                         res [j++] = (byte)(word >> 8);
2045                                         res [j++] = (byte)(word >> 16);
2046                                         res [j++] = (byte)(word >> 24);
2047                                 }
2048
2049                                 add = (ulong)~topWord + (carry);
2050                                 word = (uint)add;
2051                                 carry = (uint)(add >> 32);
2052                                 if (carry == 0) {
2053                                         int ex = FirstNonFFByte (word);
2054                                         bool needExtra = (word & (1 << (ex * 8 - 1))) == 0;
2055                                         int to = ex + (needExtra ? 1 : 0);
2056
2057                                         if (to != extra)
2058                                                 res = Resize (res, bytes + to);
2059
2060                                         while (ex-- > 0) {
2061                                                 res [j++] = (byte)word;
2062                                                 word >>= 8;
2063                                         }
2064                                         if (needExtra)
2065                                                 res [j++] = 0xFF;
2066                                 } else {
2067                                         res = Resize (res, bytes + 5);
2068                                         res [j++] = (byte)word;
2069                                         res [j++] = (byte)(word >> 8);
2070                                         res [j++] = (byte)(word >> 16);
2071                                         res [j++] = (byte)(word >> 24);
2072                                         res [j++] = 0xFF;
2073                                 }
2074                         }
2075
2076                         return res;
2077                 }
2078
2079                 static byte[] Resize (byte[] v, int len)
2080                 {
2081                         byte[] res = new byte [len];
2082                         Array.Copy (v, res, Math.Min (v.Length, len));
2083                         return res;
2084                 }
2085
2086                 static uint[] Resize (uint[] v, int len)
2087                 {
2088                         uint[] res = new uint [len];
2089                         Array.Copy (v, res, Math.Min (v.Length, len));
2090                         return res;
2091                 }
2092
2093                 static uint[] CoreAdd (uint[] a, uint[] b)
2094                 {
2095                         if (a.Length < b.Length) {
2096                                 uint[] tmp = a;
2097                                 a = b;
2098                                 b = tmp;
2099                         }
2100
2101                         int bl = a.Length;
2102                         int sl = b.Length;
2103
2104                         uint[] res = new uint [bl];
2105
2106                         ulong sum = 0;
2107
2108                         int i = 0;
2109                         for (; i < sl; i++) {
2110                                 sum = sum + a [i] + b [i];
2111                                 res [i] = (uint)sum;
2112                                 sum >>= 32;
2113                         }
2114
2115                         for (; i < bl; i++) {
2116                                 sum = sum + a [i];
2117                                 res [i] = (uint)sum;
2118                                 sum >>= 32;
2119                         }
2120
2121                         if (sum != 0) {
2122                                 res = Resize (res, bl + 1);
2123                                 res [i] = (uint)sum;
2124                         }
2125
2126                         return res;
2127                 }
2128
2129                 /*invariant a > b*/
2130                 static uint[] CoreSub (uint[] a, uint[] b)
2131                 {
2132                         int bl = a.Length;
2133                         int sl = b.Length;
2134
2135                         uint[] res = new uint [bl];
2136
2137                         ulong borrow = 0;
2138                         int i;
2139                         for (i = 0; i < sl; ++i) {
2140                                 borrow = (ulong)a [i] - b [i] - borrow;
2141
2142                                 res [i] = (uint)borrow;
2143                                 borrow = (borrow >> 32) & 0x1;
2144                         }
2145
2146                         for (; i < bl; i++) {
2147                                 borrow = (ulong)a [i] - borrow;
2148                                 res [i] = (uint)borrow;
2149                                 borrow = (borrow >> 32) & 0x1;
2150                         }
2151
2152                         //remove extra zeroes
2153                         for (i = bl - 1; i >= 0 && res [i] == 0; --i) ;
2154                         if (i < bl - 1)
2155                                 res = Resize (res, i + 1);
2156
2157             return res;
2158                 }
2159
2160
2161                 static uint[] CoreAdd (uint[] a, uint b)
2162                 {
2163                         int len = a.Length;
2164                         uint[] res = new uint [len];
2165
2166                         ulong sum = b;
2167                         int i;
2168                         for (i = 0; i < len; i++) {
2169                                 sum = sum + a [i];
2170                                 res [i] = (uint)sum;
2171                                 sum >>= 32;
2172                         }
2173
2174                         if (sum != 0) {
2175                                 res = Resize (res, len + 1);
2176                                 res [i] = (uint)sum;
2177                         }
2178
2179                         return res;
2180                 }
2181
2182                 static uint[] CoreSub (uint[] a, uint b)
2183                 {
2184                         int len = a.Length;
2185                         uint[] res = new uint [len];
2186
2187                         ulong borrow = b;
2188                         int i;
2189                         for (i = 0; i < len; i++) {
2190                                 borrow = (ulong)a [i] - borrow;
2191                                 res [i] = (uint)borrow;
2192                                 borrow = (borrow >> 32) & 0x1;
2193                         }
2194
2195                         //remove extra zeroes
2196                         for (i = len - 1; i >= 0 && res [i] == 0; --i) ;
2197                         if (i < len - 1)
2198                                 res = Resize (res, i + 1);
2199
2200             return res;
2201                 }
2202
2203                 static int CoreCompare (uint[] a, uint[] b)
2204                 {
2205                         int al = a != null ? a.Length : 0;
2206                         int bl = b != null ? b.Length : 0;
2207
2208                         if (al > bl)
2209                                 return 1;
2210                         if (bl > al)
2211                                 return -1;
2212
2213                         for (int i = al - 1; i >= 0; --i) {
2214                                 uint ai = a [i];
2215                                 uint bi = b [i];
2216                                 if (ai > bi)
2217                                         return 1;
2218                                 if (ai < bi)
2219                                         return -1;
2220                         }
2221                         return 0;
2222                 }
2223
2224                 static int GetNormalizeShift(uint value) {
2225                         int shift = 0;
2226
2227                         if ((value & 0xFFFF0000) == 0) { value <<= 16; shift += 16; }
2228                         if ((value & 0xFF000000) == 0) { value <<= 8; shift += 8; }
2229                         if ((value & 0xF0000000) == 0) { value <<= 4; shift += 4; }
2230                         if ((value & 0xC0000000) == 0) { value <<= 2; shift += 2; }
2231                         if ((value & 0x80000000) == 0) { value <<= 1; shift += 1; }
2232
2233                         return shift;
2234                 }
2235
2236                 static void Normalize (uint[] u, int l, uint[] un, int shift)
2237                 {
2238                         uint carry = 0;
2239                         int i;
2240                         if (shift > 0) {
2241                                 int rshift = 32 - shift;
2242                                 for (i = 0; i < l; i++) {
2243                                         uint ui = u [i];
2244                                         un [i] = (ui << shift) | carry;
2245                                         carry = ui >> rshift;
2246                                 }
2247                         } else {
2248                                 for (i = 0; i < l; i++) {
2249                                         un [i] = u [i];
2250                                 }
2251                         }
2252
2253                         while (i < un.Length) {
2254                                 un [i++] = 0;
2255                         }
2256
2257                         if (carry != 0) {
2258                                 un [l] = carry;
2259                         }
2260                 }
2261
2262                 static void Unnormalize (uint[] un, out uint[] r, int shift)
2263                 {
2264                         int length = un.Length;
2265                         r = new uint [length];
2266
2267                         if (shift > 0) {
2268                                 int lshift = 32 - shift;
2269                                 uint carry = 0;
2270                                 for (int i = length - 1; i >= 0; i--) {
2271                                         uint uni = un [i];
2272                                         r [i] = (uni >> shift) | carry;
2273                                         carry = (uni << lshift);
2274                                 }
2275                         } else {
2276                                 for (int i = 0; i < length; i++) {
2277                                         r [i] = un [i];
2278                                 }
2279                         }
2280                 }
2281
2282                 const ulong Base = 0x100000000;
2283                 static void DivModUnsigned (uint[] u, uint[] v, out uint[] q, out uint[] r)
2284                 {
2285                         int m = u.Length;
2286                         int n = v.Length;
2287
2288                         if (n <= 1) {
2289                                 //  Divide by single digit
2290                                 //
2291                                 ulong rem = 0;
2292                                 uint v0 = v [0];
2293                                 q = new uint[m];
2294                                 r = new uint [1];
2295
2296                                 for (int j = m - 1; j >= 0; j--) {
2297                                         rem *= Base;
2298                                         rem += u[j];
2299
2300                                         ulong div = rem / v0;
2301                                         rem -= div * v0;
2302                                         q[j] = (uint)div;
2303                                 }
2304                                 r [0] = (uint)rem;
2305                         } else if (m >= n) {
2306                                 int shift = GetNormalizeShift (v [n - 1]);
2307
2308                                 uint[] un = new uint [m + 1];
2309                                 uint[] vn = new uint [n];
2310
2311                                 Normalize (u, m, un, shift);
2312                                 Normalize (v, n, vn, shift);
2313
2314                                 q = new uint [m - n + 1];
2315                                 r = null;
2316
2317                                 //  Main division loop
2318                                 //
2319                                 for (int j = m - n; j >= 0; j--) {
2320                                         ulong rr, qq;
2321                                         int i;
2322
2323                                         rr = Base * un [j + n] + un [j + n - 1];
2324                                         qq = rr / vn [n - 1];
2325                                         rr -= qq * vn [n - 1];
2326
2327                                         for (; ; ) {
2328                                                 // Estimate too big ?
2329                                                 //
2330                                                 if ((qq >= Base) || (qq * vn [n - 2] > (rr * Base + un [j + n - 2]))) {
2331                                                         qq--;
2332                                                         rr += (ulong)vn [n - 1];
2333                                                         if (rr < Base)
2334                                                                 continue;
2335                                                 }
2336                                                 break;
2337                                         }
2338
2339
2340                                         //  Multiply and subtract
2341                                         //
2342                                         long b = 0;
2343                                         long t = 0;
2344                                         for (i = 0; i < n; i++) {
2345                                                 ulong p = vn [i] * qq;
2346                                                 t = (long)un [i + j] - (long)(uint)p - b;
2347                                                 un [i + j] = (uint)t;
2348                                                 p >>= 32;
2349                                                 t >>= 32;
2350                                                 b = (long)p - t;
2351                                         }
2352                                         t = (long)un [j + n] - b;
2353                                         un [j + n] = (uint)t;
2354
2355                                         //  Store the calculated value
2356                                         //
2357                                         q [j] = (uint)qq;
2358
2359                                         //  Add back vn[0..n] to un[j..j+n]
2360                                         //
2361                                         if (t < 0) {
2362                                                 q [j]--;
2363                                                 ulong c = 0;
2364                                                 for (i = 0; i < n; i++) {
2365                                                         c = (ulong)vn [i] + un [j + i] + c;
2366                                                         un [j + i] = (uint)c;
2367                                                         c >>= 32;
2368                                                 }
2369                                                 c += (ulong)un [j + n];
2370                                                 un [j + n] = (uint)c;
2371                                         }
2372                                 }
2373
2374                                 Unnormalize (un, out r, shift);
2375                         } else {
2376                                 q = new uint [] { 0 };
2377                                 r = u;
2378                         }
2379                 }
2380         }
2381 }