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