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