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 // The Multiply and Div 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;\r
  47 using System.Collections.Generic;\r
  48 using System.Diagnostics;\r
  49 using System.Diagnostics.CodeAnalysis;\r
  50 using System.Globalization;\r
  51 using System.Text;\r
  52
  53 /*
  54 Optimization
  55         Have proper popcount function for IsPowerOfTwo
  56         Use unsafe ops to avoid bounds check
  57         CoreAdd could avoid some resizes by checking for equal sized array that top overflow
  58         For bitwise operators, hoist the conditionals out of their main loop
  59         Optimize BitScanBackward
  60         Use a carry variable to make shift opts do half the number of array ops.
  61         Schoolbook multiply is O(n^2), use Karatsuba /Toom-3 for large numbers
  62 */\r
  63 namespace System.Numerics {\r
  64         public struct BigInteger : IComparable, IComparable<BigInteger>, IEquatable<BigInteger>
  65         {
  66                 //LSB on [0]
  67                 readonly uint[] data;
  68                 readonly short sign;
  69
  70                 static readonly uint[] ZERO = new uint [1];
  71                 static readonly uint[] ONE = new uint [1] { 1 };
  72
  73                 BigInteger (short sign, uint[] data)
  74                 {
  75                         this.sign = sign;
  76                         this.data = data;
  77                 }
  78
  79                 public BigInteger (int value)
  80                 {
  81                         if (value == 0) {
  82                                 sign = 0;
  83                                 data = ZERO;
  84                         } else if (value > 0) {
  85                                 sign = 1;
  86                                 data = new uint[] { (uint) value };
  87                         } else {
  88                                 sign = -1;
  89                                 data = new uint[1] { (uint)-value };
  90                         }
  91                 }
  92
  93                 [CLSCompliantAttribute (false)]
  94                 public BigInteger (uint value)
  95                 {
  96                         if (value == 0) {
  97                                 sign = 0;
  98                                 data = ZERO;
  99                         } else {
 100                                 sign = 1;
 101                                 data = new uint [1] { value };
 102                         }
 103                 }
 104
 105                 public BigInteger (long value)
 106                 {
 107                         if (value == 0) {
 108                                 sign = 0;
 109                                 data = ZERO;
 110                         } else if (value > 0) {
 111                                 sign = 1;
 112                                 uint low = (uint)value;
 113                                 uint high = (uint)(value >> 32);
 114
 115                                 data = new uint [high != 0 ? 2 : 1];
 116                                 data [0] = low;
 117                                 if (high != 0)
 118                                         data [1] = high;
 119                         } else {
 120                                 sign = -1;
 121                                 value = -value;
 122                                 uint low = (uint)value;
 123                                 uint high = (uint)((ulong)value >> 32);
 124
 125                                 data = new uint [high != 0 ? 2 : 1];
 126                                 data [0] = low;
 127                                 if (high != 0)
 128                                         data [1] = high;
 129                         }
 130                 }
 131
 132                 [CLSCompliantAttribute (false)]
 133                 public BigInteger (ulong value)
 134                 {
 135                         if (value == 0) {
 136                                 sign = 0;
 137                                 data = ZERO;
 138                         } else {
 139                                 sign = 1;
 140                                 uint low = (uint)value;
 141                                 uint high = (uint)(value >> 32);
 142
 143                                 data = new uint [high != 0 ? 2 : 1];
 144                                 data [0] = low;
 145                                 if (high != 0)
 146                                         data [1] = high;
 147                         }
 148                 }
 149
 150                 [CLSCompliantAttribute (false)]
 151                 public BigInteger (byte[] value)
 152                 {
 153                         if (value == null)
 154                                 throw new ArgumentNullException ("value");
 155
 156                         int len = value.Length;
 157
 158                         if (len == 0 || (len == 1 && value [0] == 0)) {
 159                                 sign = 0;
 160                                 data = ZERO;
 161                                 return;
 162                         }
 163
 164                         if ((value [len - 1] & 0x80) != 0)
 165                                 sign = -1;
 166                         else
 167                                 sign = 1;
 168
 169                         if (sign == 1) {
 170                                 while (value [len - 1] == 0)
 171                                         --len;
 172
 173                                 int full_words, size;
 174                                 full_words = size = len / 4;
 175                                 if ((len & 0x3) != 0)
 176                                         ++size;
 177
 178                                 data = new uint [size];
 179                                 int j = 0;
 180                                 for (int i = 0; i < full_words; ++i) {
 181                                         data [i] =      (uint)value [j++] |
 182                                                                 (uint)(value [j++] << 8) |
 183                                                                 (uint)(value [j++] << 16) |
 184                                                                 (uint)(value [j++] << 24);
 185                                 }
 186                                 size = len & 0x3;
 187                                 if (size > 0) {
 188                                         int idx = data.Length - 1;
 189                                         for (int i = 0; i < size; ++i)
 190                                                 data [idx] |= (uint)(value [j++] << (i * 8));
 191                                 }
 192                         } else {
 193                                 int full_words, size;
 194                                 full_words = size = len / 4;
 195                                 if ((len & 0x3) != 0)
 196                                         ++size;
 197
 198                                 data = new uint [size];
 199
 200                                 uint word, borrow = 1;
 201                                 ulong sub = 0;
 202                                 int j = 0;
 203
 204                                 for (int i = 0; i < full_words; ++i) {
 205                                         word =  (uint)value [j++] |
 206                                                         (uint)(value [j++] << 8) |
 207                                                         (uint)(value [j++] << 16) |
 208                                                         (uint)(value [j++] << 24);
 209
 210                                         sub = (ulong)word - borrow;
 211                                         word = (uint)sub;
 212                                         borrow = (uint)(sub >> 32) & 0x1u;
 213                                         data [i] = ~word;
 214                                 }
 215                                 size = len & 0x3;
 216
 217                                 if (size > 0) {
 218                                         word = 0;
 219                                         uint store_mask = 0;
 220                                         for (int i = 0; i < size; ++i) {
 221                                                 word |= (uint)(value [j++] << (i * 8));
 222                                                 store_mask = (store_mask << 8) | 0xFF;
 223                                         }
 224
 225                                         sub = word - borrow;
 226                                         word = (uint)sub;
 227                                         borrow = (uint)(sub >> 32) & 0x1u;
 228
 229                                         data [data.Length - 1] = ~word & store_mask;
 230                                 }
 231                                 if (borrow != 0) //FIXME I believe this can't happen, can someone write a test for it?
 232                                         throw new Exception ("non zero final carry");
 233                         }
 234
 235                 }
 236
 237                 public bool IsEven {
 238                         get { return (data [0] & 0x1) == 0; }
 239                 }
 240
 241                 public bool IsOne {
 242                         get { return sign == 1 && data.Length == 1 && data [0] == 1; }
 243                 }
 244
 245
 246                 //Gem from Hacker's Delight
 247                 //Returns the number of bits set in @x
 248                 static int PopulationCount (uint x)
 249                 {
 250                         x = x - ((x >> 1) & 0x55555555);
 251                         x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
 252                         x = (x + (x >> 4)) & 0x0F0F0F0F;
 253                         x = x + (x >> 8);
 254                         x = x + (x >> 16);
 255                         return (int)(x & 0x0000003F);
 256                 }
 257
 258                 public bool IsPowerOfTwo {
 259                         get {
 260                                 bool foundBit = false;
 261                                 if (sign != 1)
 262                                         return false;
 263                                 //This function is pop count == 1 for positive numbers
 264                                 for (int i = 0; i < data.Length; ++i) {
 265                                         int p = PopulationCount (data [i]);
 266                                         if (p > 0) {
 267                                                 if (p > 1 || foundBit)
 268                                                         return false;
 269                                                 foundBit = true;
 270                                         }
 271                                 }
 272                                 return foundBit;
 273                         }
 274                 }
 275
 276                 public bool IsZero {
 277                         get { return sign == 0; }
 278                 }
 279
 280                 public int Sign {
 281                         get { return sign; }
 282                 }
 283
 284                 public static BigInteger MinusOne {
 285                         get { return new BigInteger (-1, ONE); }
 286                 }
 287
 288                 public static BigInteger One {
 289                         get { return new BigInteger (1, ONE); }
 290                 }
 291
 292                 public static BigInteger Zero {
 293                         get { return new BigInteger (0, ZERO); }
 294                 }
 295
 296                 public static explicit operator int (BigInteger value)
 297                 {
 298                         if (value.data.Length > 1)
 299                                 throw new OverflowException ();
 300                         uint data = value.data [0];
 301
 302                         if (value.sign == 1) {
 303                                 if (data > (uint)int.MaxValue)
 304                                         throw new OverflowException ();
 305                                 return (int)data;
 306                         } else if (value.sign == -1) {
 307                                 if (data > 0x80000000u)
 308                                         throw new OverflowException ();
 309                                 return -(int)data;
 310                         }
 311
 312                         return 0;
 313                 }
 314
 315                 [CLSCompliantAttribute (false)]
 316                 public static explicit operator uint (BigInteger value)
 317                 {
 318                         if (value.data.Length > 1 || value.sign == -1)
 319                                 throw new OverflowException ();
 320                         return value.data [0];
 321                 }
 322
 323                 public static explicit operator short (BigInteger value)
 324                 {
 325                         int val = (int)value;
 326                         if (val < short.MinValue || val > short.MaxValue)
 327                                 throw new OverflowException ();
 328                         return (short)val;
 329                 }
 330
 331                 [CLSCompliantAttribute (false)]
 332                 public static explicit operator ushort (BigInteger value)
 333                 {
 334                         uint val = (uint)value;
 335                         if (val > ushort.MaxValue)
 336                                 throw new OverflowException ();
 337                         return (ushort)val;
 338                 }
 339
 340                 public static explicit operator byte (BigInteger value)
 341                 {
 342                         uint val = (uint)value;
 343                         if (val > byte.MaxValue)
 344                                 throw new OverflowException ();
 345                         return (byte)val;
 346                 }
 347
 348                 [CLSCompliantAttribute (false)]
 349                 public static explicit operator sbyte (BigInteger value)
 350                 {
 351                         int val = (int)value;
 352                         if (val < sbyte.MinValue || val > sbyte.MaxValue)
 353                                 throw new OverflowException ();
 354                         return (sbyte)val;
 355                 }
 356
 357
 358                 public static explicit operator long (BigInteger value)
 359                 {
 360                         if (value.sign == 0)
 361                                 return 0;
 362
 363                         if (value.data.Length > 2)
 364                                 throw new OverflowException ();
 365
 366                         uint low = value.data [0];
 367
 368                         if (value.data.Length == 1) {
 369                                 if (value.sign == 1)
 370                                         return (long)low;
 371                                 long res = (long)low;
 372                                 return -res;
 373                         }
 374
 375                         uint high = value.data [1];
 376
 377                         if (value.sign == 1) {
 378                                 if (high >= 0x80000000u)
 379                                         throw new OverflowException ();
 380                                 return (((long)high) << 32) | low;
 381                         }
 382
 383                         if (high > 0x80000000u)
 384                                 throw new OverflowException ();
 385
 386                         return - ((((long)high) << 32) | (long)low);
 387                 }
 388
 389                 [CLSCompliantAttribute (false)]
 390                 public static explicit operator ulong (BigInteger value)
 391                 {
 392                         if (value.data.Length > 2 || value.sign == -1)
 393                                 throw new OverflowException ();
 394
 395                         uint low = value.data [0];
 396                         if (value.data.Length == 1)
 397                                 return low;
 398
 399                         uint high = value.data [1];
 400                         return (((ulong)high) << 32) | low;
 401                 }
 402
 403
 404                 public static implicit operator BigInteger (int value)
 405                 {
 406                         return new BigInteger (value);
 407                 }
 408
 409                 [CLSCompliantAttribute (false)]
 410                 public static implicit operator BigInteger (uint value)
 411                 {
 412                         return new BigInteger (value);
 413                 }
 414
 415                 public static implicit operator BigInteger (short value)
 416                 {
 417                         return new BigInteger (value);
 418                 }
 419
 420                 [CLSCompliantAttribute (false)]
 421                 public static implicit operator BigInteger (ushort value)
 422                 {
 423                         return new BigInteger (value);
 424                 }
 425
 426                 public static implicit operator BigInteger (byte value)
 427                 {
 428                         return new BigInteger (value);
 429                 }
 430
 431                 [CLSCompliantAttribute (false)]
 432                 public static implicit operator BigInteger (sbyte value)
 433                 {
 434                         return new BigInteger (value);
 435                 }
 436
 437                 public static implicit operator BigInteger (long value)
 438                 {
 439                         return new BigInteger (value);
 440                 }
 441
 442                 [CLSCompliantAttribute (false)]
 443                 public static implicit operator BigInteger (ulong value)
 444                 {
 445                         return new BigInteger (value);
 446                 }
 447
 448                 public static BigInteger operator+ (BigInteger left, BigInteger right)
 449                 {
 450                         if (left.sign == 0)
 451                                 return right;
 452                         if (right.sign == 0)
 453                                 return left;
 454
 455                         if (left.sign == right.sign)
 456                                 return new BigInteger (left.sign, CoreAdd (left.data, right.data));
 457
 458                         int r = CoreCompare (left.data, right.data);
 459
 460                         if (r == 0)
 461                                 return new BigInteger (0, ZERO);
 462
 463                         if (r > 0) //left > right
 464                                 return new BigInteger (left.sign, CoreSub (left.data, right.data));
 465
 466                         return new BigInteger (right.sign, CoreSub (right.data, left.data));
 467                 }
 468
 469                 public static BigInteger operator- (BigInteger left, BigInteger right)
 470                 {
 471                         if (right.sign == 0)
 472                                 return left;
 473                         if (left.sign == 0)
 474                                 return new BigInteger ((short)-right.sign, right.data);
 475
 476                         if (left.sign == right.sign) {
 477                                 int r = CoreCompare (left.data, right.data);
 478
 479                                 if (r == 0)
 480                                         return new BigInteger (0, ZERO);
 481
 482                                 if (r > 0) //left > right
 483                                         return new BigInteger (left.sign, CoreSub (left.data, right.data));
 484
 485                                 return new BigInteger ((short)-right.sign, CoreSub (right.data, left.data));
 486                         }
 487
 488                         return new BigInteger (left.sign, CoreAdd (left.data, right.data));
 489                 }
 490
 491                 public static BigInteger operator* (BigInteger left, BigInteger right)
 492                 {
 493                         if (left.sign == 0 || right.sign == 0)
 494                                 return new BigInteger (0, ZERO);
 495
 496                         if (left.data [0] == 1 && left.data.Length == 1) {
 497                                 if (left.sign == 1)
 498                                         return right;
 499                                 return new BigInteger ((short)-right.sign, right.data);
 500                         }
 501
 502                         if (right.data [0] == 1 && right.data.Length == 1) {
 503                                 if (right.sign == 1)
 504                                         return left;
 505                                 return new BigInteger ((short)-left.sign, left.data);
 506                         }
 507
 508                         uint[] a = left.data;
 509                         uint[] b = right.data;
 510
 511                         uint[] res = new uint [a.Length + b.Length];
 512
 513             for (int i = 0; i < a.Length; ++i) {
 514                 uint ai = a [i];
 515                 int k = i;
 516
 517                 ulong carry = 0;
 518                 for (int j = 0; j < b.Length; ++j) {
 519                     carry = carry + ((ulong)ai) * b [j] + res [k];
 520                     res[k++] = (uint)carry;
 521                     carry >>= 32;
 522                 }
 523
 524                 while (carry != 0) {
 525                     carry += res [k];
 526                     res[k++] = (uint)carry;
 527                     carry >>= 32;
 528                 }
 529             }
 530
 531                         int m;
 532                         for (m = res.Length - 1; m >= 0 && res [m] == 0; --m) ;
 533                         if (m < res.Length - 1)
 534                                 res = Resize (res, m + 1);
 535
 536                         return new BigInteger ((short)(left.sign * right.sign), res);
 537                 }
 538
 539
 540                 public static BigInteger operator- (BigInteger value)
 541                 {
 542                         if (value.sign == 0)
 543                                 return value;
 544                         return new BigInteger ((short)-value.sign, value.data);
 545                 }
 546
 547                 public static BigInteger operator+ (BigInteger value)
 548                 {
 549                         return value;
 550                 }
 551
 552                 public static BigInteger operator++ (BigInteger value)
 553                 {
 554                         short sign = value.sign;
 555                         uint[] data = value.data;
 556                         if (data.Length == 1) {
 557                                 if (sign == -1 && data [0] == 1)
 558                                         return new BigInteger (0, ZERO);
 559                                 if (sign == 0)
 560                                         return new BigInteger (1, ONE);
 561                         }
 562
 563                         if (sign == -1)
 564                                 data = CoreSub (data, 1);
 565                         else
 566                                 data = CoreAdd (data, 1);
 567
 568                         return new BigInteger (sign, data);
 569                 }
 570
 571                 public static BigInteger operator-- (BigInteger value)
 572                 {
 573                         short sign = value.sign;
 574                         uint[] data = value.data;
 575                         if (data.Length == 1) {
 576                                 if (sign == 1 && data [0] == 1)
 577                                         return new BigInteger (0, ZERO);
 578                                 if (sign == 0)
 579                                         return new BigInteger (-1, ONE);
 580                         }
 581
 582                         if (sign == -1)
 583                                 data = CoreAdd (data, 1);
 584                         else
 585                                 data = CoreSub (data, 1);
 586
 587                         return new BigInteger (sign, data);
 588                 }
 589
 590                 public static BigInteger operator& (BigInteger left, BigInteger right)
 591                 {
 592                         if (left.sign == 0)
 593                                 return left;
 594
 595                         if (right.sign == 0)
 596                                 return right;
 597
 598                         uint[] a = left.data;
 599                         uint[] b = right.data;
 600                         int ls = left.sign;
 601                         int rs = right.sign;
 602
 603                         bool neg_res = (ls == rs) && (ls == -1);
 604
 605                         uint[] result = new uint [Math.Max (a.Length, b.Length)];
 606
 607                         ulong ac = 1, bc = 1, borrow = 1;
 608
 609                         int i;
 610                         for (i = 0; i < result.Length; ++i) {
 611                                 uint va = 0;
 612                                 if (i < a.Length)
 613                                         va = a [i];
 614                                 if (ls == -1) {
 615                                         ac = ~va + ac;
 616                                         va = (uint)ac;
 617                                         ac = (uint)(ac >> 32);
 618                                 }
 619
 620                                 uint vb = 0;
 621                                 if (i < b.Length)
 622                                         vb = b [i];
 623                                 if (rs == -1) {
 624                                         bc = ~vb + bc;
 625                                         vb = (uint)bc;
 626                                         bc = (uint)(bc >> 32);
 627                                 }
 628
 629                                 uint word = va & vb;
 630
 631                                 if (neg_res) {
 632                                         borrow = word - borrow;
 633                                         word = ~(uint)borrow;
 634                                         borrow = (uint)(borrow >> 32) & 0x1u;
 635                                 }
 636
 637                                 result [i] = word;
 638                         }
 639
 640                         for (i = result.Length - 1; i >= 0 && result [i] == 0; --i) ;
 641                         if (i == -1)
 642                                 return new BigInteger (0, ZERO);
 643
 644                         if (i < result.Length - 1)
 645                                 result = Resize (result, i + 1);
 646
 647                         return new BigInteger (neg_res ? (short)-1 : (short)1, result);
 648                 }
 649
 650                 public static BigInteger operator| (BigInteger left, BigInteger right)
 651                 {
 652                         if (left.sign == 0)
 653                                 return right;
 654
 655                         if (right.sign == 0)
 656                                 return left;
 657
 658                         uint[] a = left.data;
 659                         uint[] b = right.data;
 660                         int ls = left.sign;
 661                         int rs = right.sign;
 662
 663                         bool neg_res = (ls == -1) || (rs == -1);
 664
 665                         uint[] result = new uint [Math.Max (a.Length, b.Length)];
 666
 667                         ulong ac = 1, bc = 1, borrow = 1;
 668
 669                         int i;
 670                         for (i = 0; i < result.Length; ++i) {
 671                                 uint va = 0;
 672                                 if (i < a.Length)
 673                                         va = a [i];
 674                                 if (ls == -1) {
 675                                         ac = ~va + ac;
 676                                         va = (uint)ac;
 677                                         ac = (uint)(ac >> 32);
 678                                 }
 679
 680                                 uint vb = 0;
 681                                 if (i < b.Length)
 682                                         vb = b [i];
 683                                 if (rs == -1) {
 684                                         bc = ~vb + bc;
 685                                         vb = (uint)bc;
 686                                         bc = (uint)(bc >> 32);
 687                                 }
 688
 689                                 uint word = va | vb;
 690
 691                                 if (neg_res) {
 692                                         borrow = word - borrow;
 693                                         word = ~(uint)borrow;
 694                                         borrow = (uint)(borrow >> 32) & 0x1u;
 695                                 }
 696
 697                                 result [i] = word;
 698                         }
 699
 700                         for (i = result.Length - 1; i >= 0 && result [i] == 0; --i) ;
 701                         if (i == -1)
 702                                 return new BigInteger (0, ZERO);
 703
 704                         if (i < result.Length - 1)
 705                                 result = Resize (result, i + 1);
 706
 707                         return new BigInteger (neg_res ? (short)-1 : (short)1, result);
 708                 }
 709
 710                 public static BigInteger operator^ (BigInteger left, BigInteger right)
 711                 {
 712                         if (left.sign == 0)
 713                                 return right;
 714
 715                         if (right.sign == 0)
 716                                 return left;
 717
 718                         uint[] a = left.data;
 719                         uint[] b = right.data;
 720                         int ls = left.sign;
 721                         int rs = right.sign;
 722
 723                         bool neg_res = (ls == -1) ^ (rs == -1);
 724
 725                         uint[] result = new uint [Math.Max (a.Length, b.Length)];
 726
 727                         ulong ac = 1, bc = 1, borrow = 1;
 728
 729                         int i;
 730                         for (i = 0; i < result.Length; ++i) {
 731                                 uint va = 0;
 732                                 if (i < a.Length)
 733                                         va = a [i];
 734                                 if (ls == -1) {
 735                                         ac = ~va + ac;
 736                                         va = (uint)ac;
 737                                         ac = (uint)(ac >> 32);
 738                                 }
 739
 740                                 uint vb = 0;
 741                                 if (i < b.Length)
 742                                         vb = b [i];
 743                                 if (rs == -1) {
 744                                         bc = ~vb + bc;
 745                                         vb = (uint)bc;
 746                                         bc = (uint)(bc >> 32);
 747                                 }
 748
 749                                 uint word = va ^ vb;
 750
 751                                 if (neg_res) {
 752                                         borrow = word - borrow;
 753                                         word = ~(uint)borrow;
 754                                         borrow = (uint)(borrow >> 32) & 0x1u;
 755                                 }
 756
 757                                 result [i] = word;
 758                         }
 759
 760                         for (i = result.Length - 1; i >= 0 && result [i] == 0; --i) ;
 761                         if (i == -1)
 762                                 return new BigInteger (0, ZERO);
 763
 764                         if (i < result.Length - 1)
 765                                 result = Resize (result, i + 1);
 766
 767                         return new BigInteger (neg_res ? (short)-1 : (short)1, result);
 768                 }
 769
 770                 public static BigInteger operator~ (BigInteger value)
 771                 {
 772                         if (value.sign == 0)
 773                                 return new BigInteger (-1, ONE);
 774
 775                         uint[] data = value.data;
 776                         int sign = value.sign;
 777
 778                         bool neg_res = sign == 1;
 779
 780                         uint[] result = new uint [data.Length];
 781
 782                         ulong carry = 1, borrow = 1;
 783
 784                         int i;
 785                         for (i = 0; i < result.Length; ++i) {
 786                                 uint word = data [i];
 787                                 if (sign == -1) {
 788                                         carry = ~word + carry;
 789                                         word = (uint)carry;
 790                                         carry = (uint)(carry >> 32);
 791                                 }
 792
 793                                 word = ~word;
 794
 795                                 if (neg_res) {
 796                                         borrow = word - borrow;
 797                                         word = ~(uint)borrow;
 798                                         borrow = (uint)(borrow >> 32) & 0x1u;
 799                                 }
 800
 801                                 result [i] = word;
 802                         }
 803
 804                         for (i = result.Length - 1; i >= 0 && result [i] == 0; --i) ;
 805                         if (i == -1)
 806                                 return new BigInteger (0, ZERO);
 807
 808                         if (i < result.Length - 1)
 809                                 result = Resize (result, i + 1);
 810
 811                         return new BigInteger (neg_res ? (short)-1 : (short)1, result);
 812                 }
 813
 814                 //returns the 0-based index of the most significant set bit
 815                 //returns 0 if no bit is set, so extra care when using it
 816                 static int BitScanBackward (uint word)
 817                 {
 818                         for (int i = 31; i >= 0; --i) {
 819                                 uint mask = 1u << i;
 820                                 if ((word & mask) == mask)
 821                                         return i;
 822                         }
 823                         return 0;
 824                 }
 825
 826                 public static BigInteger operator<< (BigInteger value, int shift)
 827                 {
 828                         if (shift == 0 || value.sign == 0)
 829                                 return value;
 830                         if (shift < 0)
 831                                 return value >> -shift;
 832
 833                         uint[] data = value.data;
 834                         int sign = value.sign;
 835
 836                         int topMostIdx = BitScanBackward (data [data.Length - 1]);
 837                         int bits = shift - (31 - topMostIdx);
 838                         int extra_words = (bits >> 5) + ((bits & 0x1F) != 0 ? 1 : 0);
 839
 840                         uint[] res = new uint [data.Length + extra_words];
 841
 842                         int idx_shift = shift >> 5;
 843                         int bit_shift = shift & 0x1F;
 844                         int carry_shift = 32 - bit_shift;
 845
 846                         for (int i = 0; i < data.Length; ++i) {
 847                                 uint word = data [i];
 848                                 res [i + idx_shift] |= word << bit_shift;
 849                                 if (i + idx_shift + 1 < res.Length)
 850                                         res [i + idx_shift + 1] = word >> carry_shift;
 851                         }
 852
 853                         return new BigInteger ((short)sign, res);
 854                 }
 855
 856                 public static BigInteger operator>> (BigInteger value, int shift)
 857                 {
 858                         if (shift == 0 || value.sign == 0)
 859                                 return value;
 860                         if (shift < 0)
 861                                 return value << -shift;
 862
 863                         uint[] data = value.data;
 864                         int sign = value.sign;
 865
 866                         int topMostIdx = BitScanBackward (data [data.Length - 1]);
 867                         int idx_shift = shift >> 5;
 868                         int bit_shift = shift & 0x1F;
 869
 870                         int extra_words = idx_shift;
 871                         if (bit_shift > topMostIdx)
 872                                 ++extra_words;
 873                         int size = data.Length - extra_words;
 874
 875                         if (size <= 0) {
 876                                 if (sign == 1)
 877                                         return new BigInteger (0, ZERO);
 878                                 return new BigInteger (-1, ONE);
 879                         }
 880
 881                         uint[] res = new uint [size];
 882                         int carry_shift = 32 - bit_shift;
 883
 884                         for (int i = data.Length - 1; i >= idx_shift; --i) {
 885                                 uint word = data [i];
 886
 887                                 if (i - idx_shift < res.Length)
 888                                         res [i - idx_shift] |= word >> bit_shift;
 889                                 if (i - idx_shift - 1 >= 0)
 890                                         res [i - idx_shift - 1] = word << carry_shift;
 891                         }
 892
 893                         //Round down instead of toward zero
 894                         if (sign == -1) {
 895                                 for (int i = 0; i < idx_shift; i++) {
 896                                         if (data [i] != 0u) {
 897                                                 var tmp = new BigInteger ((short)sign, res);
 898                                                 --tmp;
 899                                                 return tmp;
 900                                         }
 901                                 }
 902                                 if (bit_shift > 0 && (data [idx_shift] << carry_shift) != 0u) {
 903                                         var tmp = new BigInteger ((short)sign, res);
 904                                         --tmp;
 905                                         return tmp;
 906                                 }
 907                         }
 908                         return new BigInteger ((short)sign, res);
 909                 }
 910
 911                 public static bool operator< (BigInteger left, BigInteger right)
 912                 {
 913                         return Compare (left, right) < 0;
 914                 }
 915
 916                 public static bool operator< (BigInteger left, long right)
 917                 {
 918                         return left.CompareTo (right) < 0;
 919                 }
 920
 921
 922                 public static bool operator< (long left, BigInteger right)
 923                 {
 924                         return right.CompareTo (left) > 0;
 925                 }
 926
 927
 928                 [CLSCompliantAttribute (false)]
 929                 public static bool operator< (BigInteger left, ulong right)
 930                 {
 931                         return left.CompareTo (right) < 0;
 932                 }
 933
 934                 [CLSCompliantAttribute (false)]
 935                 public static bool operator< (ulong left, BigInteger right)
 936                 {
 937                         return right.CompareTo (left) > 0;
 938                 }
 939
 940                 public static bool operator<= (BigInteger left, BigInteger right)
 941                 {
 942                         return Compare (left, right) <= 0;
 943                 }
 944
 945                 public static bool operator<= (BigInteger left, long right)
 946                 {
 947                         return left.CompareTo (right) <= 0;
 948                 }
 949
 950                 public static bool operator<= (long left, BigInteger right)
 951                 {
 952                         return right.CompareTo (left) >= 0;
 953                 }
 954
 955                 [CLSCompliantAttribute (false)]
 956                 public static bool operator<= (BigInteger left, ulong right)
 957                 {
 958                         return left.CompareTo (right) <= 0;
 959                 }
 960
 961                 [CLSCompliantAttribute (false)]
 962                 public static bool operator<= (ulong left, BigInteger right)
 963                 {
 964                         return right.CompareTo (left) >= 0;
 965                 }
 966
 967                 public static bool operator> (BigInteger left, BigInteger right)
 968                 {
 969                         return Compare (left, right) > 0;
 970                 }
 971
 972                 public static bool operator> (BigInteger left, long right)
 973                 {
 974                         return left.CompareTo (right) > 0;
 975                 }
 976
 977                 public static bool operator> (long left, BigInteger right)
 978                 {
 979                         return right.CompareTo (left) < 0;
 980                 }
 981
 982                 [CLSCompliantAttribute (false)]
 983                 public static bool operator> (BigInteger left, ulong right)
 984                 {
 985                         return left.CompareTo (right) > 0;
 986                 }
 987
 988                 [CLSCompliantAttribute (false)]
 989                 public static bool operator> (ulong left, BigInteger right)
 990                 {
 991                         return right.CompareTo (left) < 0;
 992                 }
 993
 994                 public static bool operator>= (BigInteger left, BigInteger right)
 995                 {
 996                         return Compare (left, right) >= 0;
 997                 }
 998
 999                 public static bool operator>= (BigInteger left, long right)
1000                 {
1001                         return left.CompareTo (right) >= 0;
1002                 }
1003
1004                 public static bool operator>= (long left, BigInteger right)
1005                 {
1006                         return right.CompareTo (left) <= 0;
1007                 }
1008
1009                 [CLSCompliantAttribute (false)]
1010                 public static bool operator>= (BigInteger left, ulong right)
1011                 {
1012                         return left.CompareTo (right) >= 0;
1013                 }
1014
1015                 [CLSCompliantAttribute (false)]
1016                 public static bool operator>= (ulong left, BigInteger right)
1017                 {
1018                         return right.CompareTo (left) <= 0;
1019                 }
1020
1021                 public static bool operator== (BigInteger left, BigInteger right)
1022                 {
1023                         return Compare (left, right) == 0;
1024                 }
1025
1026                 public static bool operator== (BigInteger left, long right)
1027                 {
1028                         return left.CompareTo (right) == 0;
1029                 }
1030
1031                 public static bool operator== (long left, BigInteger right)
1032                 {
1033                         return right.CompareTo (left) == 0;
1034                 }
1035
1036                 [CLSCompliantAttribute (false)]
1037                 public static bool operator== (BigInteger left, ulong right)
1038                 {
1039                         return left.CompareTo (right) == 0;
1040                 }
1041
1042                 [CLSCompliantAttribute (false)]
1043                 public static bool operator== (ulong left, BigInteger right)
1044                 {
1045                         return right.CompareTo (left) == 0;
1046                 }
1047
1048                 public static bool operator!= (BigInteger left, BigInteger right)
1049                 {
1050                         return Compare (left, right) != 0;
1051                 }
1052
1053                 public static bool operator!= (BigInteger left, long right)
1054                 {
1055                         return left.CompareTo (right) != 0;
1056                 }
1057
1058                 public static bool operator!= (long left, BigInteger right)
1059                 {
1060                         return right.CompareTo (left) != 0;
1061                 }
1062
1063                 [CLSCompliantAttribute (false)]
1064                 public static bool operator!= (BigInteger left, ulong right)
1065                 {
1066                         return left.CompareTo (right) != 0;
1067                 }
1068
1069                 [CLSCompliantAttribute (false)]
1070                 public static bool operator!= (ulong left, BigInteger right)
1071                 {
1072                         return right.CompareTo (left) != 0;
1073                 }
1074
1075                 public override bool Equals (object obj)
1076                 {
1077                         if (!(obj is BigInteger))
1078                                 return false;
1079                         return Equals ((BigInteger)obj);
1080                 }
1081
1082                 public bool Equals (BigInteger other)
1083                 {
1084                         if (sign != other.sign)
1085                                 return false;
1086                         if (data.Length != other.data.Length)
1087                                 return false;
1088                         for (int i = 0; i < data.Length; ++i) {
1089                                 if (data [i] != other.data [i])
1090                                         return false;
1091                         }
1092                         return true;
1093                 }
1094
1095                 public bool Equals (long other)
1096                 {
1097                         return CompareTo (other) == 0;
1098                 }
1099
1100                 public static BigInteger Min (BigInteger left, BigInteger right)
1101                 {
1102                         int ls = left.sign;
1103                         int rs = right.sign;
1104
1105                         if (ls < rs)
1106                                 return left;
1107                         if (rs < ls)
1108                                 return right;
1109
1110                         int r = CoreCompare (left.data, right.data);
1111                         if (ls == -1)
1112                                 r = -r;
1113
1114                         if (r <= 0)
1115                                 return left;
1116                         return right;
1117                 }
1118
1119
1120                 public static BigInteger Max (BigInteger left, BigInteger right)
1121                 {
1122                         int ls = left.sign;
1123                         int rs = right.sign;
1124
1125                         if (ls > rs)
1126                                 return left;
1127                         if (rs > ls)
1128                                 return right;
1129
1130                         int r = CoreCompare (left.data, right.data);
1131                         if (ls == -1)
1132                                 r = -r;
1133
1134                         if (r >= 0)
1135                                 return left;
1136                         return right;
1137                 }
1138
1139                 public static BigInteger Abs (BigInteger value)
1140                 {
1141                         return new BigInteger ((short)Math.Abs (value.sign), value.data);
1142                 }
1143
1144
1145                 public static BigInteger DivRem (BigInteger dividend, BigInteger divisor, out BigInteger remainder)
1146                 {
1147                         if (divisor.sign == 0)
1148                                 throw new DivideByZeroException ();
1149
1150                         if (dividend.sign == 0) {
1151                                 remainder = dividend;
1152                                 return dividend;
1153                         }
1154
1155                         uint[] quotient;
1156                         uint[] remainder_value;
1157
1158                         DivModUnsigned (dividend.data, divisor.data, out quotient, out remainder_value);
1159
1160                         int i;
1161                         for (i = remainder_value.Length - 1; i >= 0 && remainder_value [i] == 0; --i) ;
1162                         if (i == -1) {
1163                                 remainder = new BigInteger (0, ZERO);
1164                         } else {
1165                                 if (i < remainder_value.Length - 1)
1166                                         remainder_value = Resize (remainder_value, i + 1);
1167                                 remainder = new BigInteger (dividend.sign, remainder_value);
1168                         }
1169
1170                         for (i = quotient.Length - 1; i >= 0 && quotient [i] == 0; --i) ;
1171                         if (i == -1)
1172                                 return new BigInteger (0, ZERO);
1173                         if (i < quotient.Length - 1)
1174                                 quotient = Resize (quotient, i + 1);
1175
1176                         return new BigInteger ((short)(dividend.sign * divisor.sign), quotient);
1177                 }
1178
1179                 [CLSCompliantAttribute (false)]
1180                 public bool Equals (ulong other)
1181                 {
1182                         return CompareTo (other) == 0;
1183                 }
1184
1185                 public override int GetHashCode ()
1186                 {
1187                         uint hash = (uint)(sign * 0x01010101u);
1188
1189                         for (int i = 0; i < data.Length; ++i)
1190                                 hash ^= data [i];
1191                         return (int)hash;
1192                 }
1193
1194                 public static BigInteger Add (BigInteger left, BigInteger right)
1195                 {
1196                         return left + right;
1197                 }
1198
1199                 public static BigInteger Subtract (BigInteger left, BigInteger right)
1200                 {
1201                         return left - right;
1202                 }
1203
1204                 public static BigInteger Multiply (BigInteger left, BigInteger right)
1205                 {
1206                         return left * right;
1207                 }
1208
1209                 public static BigInteger Negate (BigInteger value)
1210                 {
1211                         return - value;
1212                 }
1213
1214                 public int CompareTo (object obj)
1215                 {
1216                         if (obj == null)
1217                                 return 1;
1218
1219                         if (!(obj is BigInteger))
1220                                 return -1;
1221
1222                         return Compare (this, (BigInteger)obj);
1223                 }
1224
1225                 public int CompareTo (BigInteger other)
1226                 {
1227                         return Compare (this, other);
1228                 }
1229
1230                 [CLSCompliantAttribute (false)]
1231                 public int CompareTo (ulong other)
1232                 {
1233                         if (sign < 0)
1234                                 return -1;
1235                         if (sign == 0)
1236                                 return other == 0 ? 0 : -1;
1237
1238                         if (data.Length > 2)
1239                                 return 1;
1240
1241                         uint high = (uint)(other >> 32);
1242                         uint low = (uint)other;
1243
1244                         return LongCompare (low, high);
1245                 }
1246
1247                 int LongCompare (uint low, uint high)
1248                 {
1249                         uint h = 0;
1250                         if (data.Length > 1)
1251                                 h = data [1];
1252
1253                         if (h > high)
1254                                 return 1;
1255                         if (h < high)
1256                                 return -1;
1257
1258                         uint l = data [0];
1259
1260                         if (l > low)
1261                                 return 1;
1262                         if (l < low)
1263                                 return -1;
1264
1265                         return 0;
1266                 }
1267
1268                 public int CompareTo (long other)
1269                 {
1270                         int ls = sign;
1271                         int rs = Math.Sign (other);
1272
1273                         if (ls != rs)
1274                                 return ls > rs ? 1 : -1;
1275
1276                         if (ls == 0)
1277                                 return 0;
1278
1279                         if (data.Length > 2)
1280                                 return -sign;
1281
1282                         if (other < 0)
1283                                 other = -other;
1284                         uint low = (uint)other;
1285                         uint high = (uint)((ulong)other >> 32);
1286
1287                         int r = LongCompare (low, high);
1288                         if (ls == -1)
1289                                 r = -r;
1290
1291                         return r;
1292                 }
1293
1294                 public static int Compare (BigInteger left, BigInteger right)
1295                 {
1296                         int ls = left.sign;
1297                         int rs = right.sign;
1298
1299                         if (ls != rs)
1300                                 return ls > rs ? 1 : -1;
1301
1302                         int r = CoreCompare (left.data, right.data);
1303                         if (ls < 0)
1304                                 r = -r;
1305                         return r;
1306                 }
1307
1308
1309                 static int TopByte (uint x)
1310                 {
1311                         if ((x & 0xFFFF0000u) != 0) {
1312                                 if ((x & 0xFF000000u) != 0)
1313                                         return 4;
1314                                 return 3;
1315                         }
1316                         if ((x & 0xFF00u) != 0)
1317                                 return 2;
1318                         return 1;
1319                 }
1320
1321                 static int FirstNonFFByte (uint word)
1322                 {
1323                         if ((word & 0xFF000000u) != 0xFF000000u)
1324                                 return 4;
1325                         else if ((word & 0xFF0000u) != 0xFF0000u)
1326                                 return 3;
1327                         else if ((word & 0xFF00u) != 0xFF00u)
1328                                 return 2;
1329                         return 1;
1330                 }
1331
1332                 public byte[] ToByteArray ()
1333                 {
1334                         if (sign == 0)
1335                                 return new byte [1];
1336
1337                         //number of bytes not counting upper word
1338                         int bytes = (data.Length - 1) * 4;
1339                         bool needExtraZero = false;
1340
1341                         uint topWord = data [data.Length - 1];
1342                         int extra;
1343
1344                         //if the topmost bit is set we need an extra
1345                         if (sign == 1) {
1346                                 extra = TopByte (topWord);
1347                                 uint mask = 0x80u << ((extra - 1) * 8);
1348                                 if ((topWord & mask) != 0) {
1349                                         needExtraZero = true;
1350                                 }
1351                         } else {
1352                                 extra = TopByte (topWord);
1353                         }
1354
1355                         byte[] res = new byte [bytes + extra + (needExtraZero ? 1 : 0) ];
1356                         if (sign == 1) {
1357                                 int j = 0;
1358                                 int end = data.Length - 1;
1359                                 for (int i = 0; i < end; ++i) {
1360                                         uint word = data [i];
1361
1362                                         res [j++] = (byte)word;
1363                                         res [j++] = (byte)(word >> 8);
1364                                         res [j++] = (byte)(word >> 16);
1365                                         res [j++] = (byte)(word >> 24);
1366                                 }
1367                                 while (extra-- > 0) {
1368                                         res [j++] = (byte)topWord;
1369                                         topWord >>= 8;
1370                                 }
1371                         } else {
1372                                 int j = 0;
1373                                 int end = data.Length - 1;
1374
1375                                 uint carry = 1, word;
1376                                 ulong add;
1377                                 for (int i = 0; i < end; ++i) {
1378                                         word = data [i];
1379                                         add = (ulong)~word + carry;
1380                                         word = (uint)add;
1381                                         carry = (uint)(add >> 32);
1382
1383                                         res [j++] = (byte)word;
1384                                         res [j++] = (byte)(word >> 8);
1385                                         res [j++] = (byte)(word >> 16);
1386                                         res [j++] = (byte)(word >> 24);
1387                                 }
1388
1389                                 add = (ulong)~topWord + (carry);
1390                                 word = (uint)add;
1391                                 carry = (uint)(add >> 32);
1392                                 if (carry == 0) {
1393                                         int ex = FirstNonFFByte (word);
1394                                         bool needExtra = (word & (1 << (ex * 8 - 1))) == 0;
1395                                         int to = ex + (needExtra ? 1 : 0);
1396
1397                                         if (to != extra)
1398                                                 res = Resize (res, bytes + to);
1399
1400                                         while (ex-- > 0) {
1401                                                 res [j++] = (byte)word;
1402                                                 word >>= 8;
1403                                         }
1404                                         if (needExtra)
1405                                                 res [j++] = 0xFF;
1406                                 } else {
1407                                         res = Resize (res, bytes + 5);
1408                                         res [j++] = (byte)word;
1409                                         res [j++] = (byte)(word >> 8);
1410                                         res [j++] = (byte)(word >> 16);
1411                                         res [j++] = (byte)(word >> 24);
1412                                         res [j++] = 0xFF;
1413                                 }
1414                         }
1415
1416                         return res;
1417                 }
1418
1419                 static byte[] Resize (byte[] v, int len)
1420                 {\r
1421                         byte[] res = new byte [len];\r
1422                         Array.Copy (v, res, Math.Min (v.Length, len));\r
1423                         return res;\r
1424                 }
1425
1426                 static uint[] Resize (uint[] v, int len)
1427                 {
1428                         uint[] res = new uint [len];\r
1429                         Array.Copy (v, res, Math.Min (v.Length, len));\r
1430                         return res;\r
1431                 }
1432
1433                 static uint[] CoreAdd (uint[] a, uint[] b)
1434                 {
1435                         if (a.Length < b.Length) {
1436                                 uint[] tmp = a;
1437                                 a = b;
1438                                 b = tmp;
1439                         }
1440
1441                         int bl = a.Length;
1442                         int sl = b.Length;
1443
1444                         uint[] res = new uint [bl];
1445
1446                         ulong sum = 0;
1447
1448                         int i = 0;
1449                         for (; i < sl; i++) {
1450                                 sum = sum + a [i] + b [i];
1451                                 res [i] = (uint)sum;
1452                                 sum >>= 32;
1453                         }
1454
1455                         for (; i < bl; i++) {
1456                                 sum = sum + a [i];
1457                                 res [i] = (uint)sum;
1458                                 sum >>= 32;
1459                         }
1460
1461                         if (sum != 0) {
1462                                 res = Resize (res, bl + 1);
1463                                 res [i] = (uint)sum;
1464                         }
1465
1466                         return res;
1467                 }
1468
1469                 /*invariant a > b*/
1470                 static uint[] CoreSub (uint[] a, uint[] b)
1471                 {
1472                         int bl = a.Length;
1473                         int sl = b.Length;
1474
1475                         uint[] res = new uint [bl];
1476
1477                         ulong borrow = 0;
1478                         int i;
1479                         for (i = 0; i < sl; ++i) {
1480                                 borrow = (ulong)a [i] - b [i] - borrow;
1481
1482                                 res [i] = (uint)borrow;
1483                                 borrow = (borrow >> 32) & 0x1;
1484                         }
1485
1486                         for (; i < bl; i++) {
1487                                 borrow = (ulong)a [i] - borrow;
1488                                 res [i] = (uint)borrow;
1489                                 borrow = (borrow >> 32) & 0x1;
1490                         }
1491
1492                         //remove extra zeroes
1493                         for (i = bl - 1; i >= 0 && res [i] == 0; --i) ;
1494                         if (i < bl - 1)
1495                                 res = Resize (res, i + 1);
1496
1497             return res;
1498                 }
1499
1500
1501                 static uint[] CoreAdd (uint[] a, uint b)
1502                 {
1503                         int len = a.Length;
1504                         uint[] res = new uint [len];
1505
1506                         ulong sum = b;
1507                         int i;
1508                         for (i = 0; i < len; i++) {
1509                                 sum = sum + a [i];
1510                                 res [i] = (uint)sum;
1511                                 sum >>= 32;
1512                         }
1513
1514                         if (sum != 0) {
1515                                 res = Resize (res, len + 1);
1516                                 res [i] = (uint)sum;
1517                         }
1518
1519                         return res;
1520                 }
1521
1522                 static uint[] CoreSub (uint[] a, uint b)
1523                 {
1524                         int len = a.Length;
1525                         uint[] res = new uint [len];
1526
1527                         ulong borrow = b;
1528                         int i;
1529                         for (i = 0; i < len; i++) {
1530                                 borrow = (ulong)a [i] - borrow;
1531                                 res [i] = (uint)borrow;
1532                                 borrow = (borrow >> 32) & 0x1;
1533                         }
1534
1535                         //remove extra zeroes
1536                         for (i = len - 1; i >= 0 && res [i] == 0; --i) ;
1537                         if (i < len - 1)
1538                                 res = Resize (res, i + 1);
1539
1540             return res;
1541                 }
1542
1543                 static int CoreCompare (uint[] a, uint[] b)
1544                 {
1545                         int     al = a.Length;
1546                         int bl = b.Length;
1547
1548                         if (al > bl)
1549                                 return 1;
1550                         if (bl > al)
1551                                 return -1;
1552
1553                         for (int i = al - 1; i >= 0; --i) {
1554                                 uint ai = a [i];
1555                                 uint bi = b [i];
1556                                 if (ai > bi)
1557                                         return 1;
1558                                 if (ai < bi)
1559                                         return -1;
1560                         }
1561                         return 0;
1562                 }
1563
1564                 static int GetNormalizeShift(uint value) {
1565                         int shift = 0;
1566
1567                         if ((value & 0xFFFF0000) == 0) { value <<= 16; shift += 16; }
1568                         if ((value & 0xFF000000) == 0) { value <<= 8; shift += 8; }
1569                         if ((value & 0xF0000000) == 0) { value <<= 4; shift += 4; }
1570                         if ((value & 0xC0000000) == 0) { value <<= 2; shift += 2; }
1571                         if ((value & 0x80000000) == 0) { value <<= 1; shift += 1; }
1572
1573                         return shift;
1574                 }
1575
1576                 static void Normalize (uint[] u, int l, uint[] un, int shift)
1577                 {
1578                         uint carry = 0;
1579                         int i;
1580                         if (shift > 0) {
1581                                 int rshift = 32 - shift;
1582                                 for (i = 0; i < l; i++) {
1583                                         uint ui = u [i];
1584                                         un [i] = (ui << shift) | carry;
1585                                         carry = ui >> rshift;
1586                                 }
1587                         } else {
1588                                 for (i = 0; i < l; i++) {
1589                                         un [i] = u [i];
1590                                 }
1591                         }
1592
1593                         while (i < un.Length) {
1594                                 un [i++] = 0;
1595                         }
1596
1597                         if (carry != 0) {
1598                                 un [l] = carry;
1599                         }
1600                 }
1601
1602                 static void Unnormalize (uint[] un, out uint[] r, int shift)
1603                 {
1604                         int length = un.Length;
1605                         r = new uint [length];
1606
1607                         if (shift > 0) {
1608                                 int lshift = 32 - shift;
1609                                 uint carry = 0;
1610                                 for (int i = length - 1; i >= 0; i--) {
1611                                         uint uni = un [i];
1612                                         r [i] = (uni >> shift) | carry;
1613                                         carry = (uni << lshift);
1614                                 }
1615                         } else {
1616                                 for (int i = 0; i < length; i++) {
1617                                         r [i] = un [i];
1618                                 }
1619                         }
1620                 }
1621
1622                 const ulong Base = 0x100000000;
1623                 static void DivModUnsigned (uint[] u, uint[] v, out uint[] q, out uint[] r)
1624                 {
1625                         int m = u.Length;
1626                         int n = v.Length;
1627
1628                         if (n <= 1) {
1629                                 //  Divide by single digit
1630                                 //
1631                                 ulong rem = 0;
1632                                 uint v0 = v [0];
1633                                 q = new uint[m];
1634                                 r = new uint [1];
1635
1636                                 for (int j = m - 1; j >= 0; j--) {
1637                                         rem *= Base;
1638                                         rem += u[j];
1639
1640                                         ulong div = rem / v0;
1641                                         rem -= div * v0;
1642                                         q[j] = (uint)div;
1643                                 }
1644                                 r [0] = (uint)rem;
1645                         } else if (m >= n) {
1646                                 int shift = GetNormalizeShift (v [n - 1]);
1647
1648                                 uint[] un = new uint [m + 1];
1649                                 uint[] vn = new uint [n];
1650
1651                                 Normalize (u, m, un, shift);
1652                                 Normalize (v, n, vn, shift);
1653
1654                                 q = new uint [m - n + 1];
1655                                 r = null;
1656
1657                                 //  Main division loop
1658                                 //
1659                                 for (int j = m - n; j >= 0; j--) {
1660                                         ulong rr, qq;
1661                                         int i;
1662
1663                                         rr = Base * un [j + n] + un [j + n - 1];
1664                                         qq = rr / vn [n - 1];
1665                                         rr -= qq * vn [n - 1];
1666
1667                                         for (; ; ) {
1668                                                 // Estimate too big ?
1669                                                 //
1670                                                 if ((qq >= Base) || (qq * vn [n - 2] > (rr * Base + un [j + n - 2]))) {
1671                                                         qq--;
1672                                                         rr += (ulong)vn [n - 1];
1673                                                         if (rr < Base)
1674                                                                 continue;
1675                                                 }
1676                                                 break;
1677                                         }
1678
1679
1680                                         //  Multiply and subtract
1681                                         //
1682                                         long b = 0;
1683                                         long t = 0;
1684                                         for (i = 0; i < n; i++) {
1685                                                 ulong p = vn [i] * qq;
1686                                                 t = (long)un [i + j] - (long)(uint)p - b;
1687                                                 un [i + j] = (uint)t;
1688                                                 p >>= 32;
1689                                                 t >>= 32;
1690                                                 b = (long)p - t;
1691                                         }
1692                                         t = (long)un [j + n] - b;
1693                                         un [j + n] = (uint)t;
1694
1695                                         //  Store the calculated value
1696                                         //
1697                                         q [j] = (uint)qq;
1698
1699                                         //  Add back vn[0..n] to un[j..j+n]
1700                                         //
1701                                         if (t < 0) {
1702                                                 q [j]--;
1703                                                 ulong c = 0;
1704                                                 for (i = 0; i < n; i++) {
1705                                                         c = (ulong)vn [i] + un [j + i] + c;
1706                                                         un [j + i] = (uint)c;
1707                                                         c >>= 32;
1708                                                 }
1709                                                 c += (ulong)un [j + n];
1710                                                 un [j + n] = (uint)c;
1711                                         }
1712                                 }
1713
1714                                 Unnormalize (un, out r, shift);
1715                         } else {
1716                                 q = new uint [] { 0 };
1717                                 r = u;
1718                         }
1719                 }
1720         }
1721 }\r