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 */\r
  41 namespace System.Numerics {\r
  42         public struct BigInteger : IComparable, IComparable<BigInteger>, IEquatable<BigInteger>
  43         {
  44                 //LSB on [0]
  45                 readonly uint[] data;
  46                 readonly short sign;
  47
  48                 static readonly uint[] ZERO = new uint [1];
  49                 static readonly uint[] ONE = new uint [1] { 1 };
  50
  51                 BigInteger (short sign, uint[] data)
  52                 {
  53                         this.sign = sign;
  54                         this.data = data;
  55                 }
  56
  57                 public BigInteger (int value)
  58                 {
  59                         if (value == 0) {
  60                                 sign = 0;
  61                                 data = ZERO;
  62                         } else if (value > 0) {
  63                                 sign = 1;
  64                                 data = new uint[] { (uint) value };
  65                         } else {
  66                                 sign = -1;
  67                                 data = new uint[1] { (uint)-value };
  68                         }
  69                 }
  70
  71                 [CLSCompliantAttribute (false)]
  72                 public BigInteger (uint value)
  73                 {
  74                         if (value == 0) {
  75                                 sign = 0;
  76                                 data = ZERO;
  77                         } else {
  78                                 sign = 1;
  79                                 data = new uint [1] { value };
  80                         }
  81                 }
  82
  83                 public BigInteger (long value)
  84                 {
  85                         if (value == 0) {
  86                                 sign = 0;
  87                                 data = ZERO;
  88                         } else if (value > 0) {
  89                                 sign = 1;
  90                                 uint low = (uint)value;
  91                                 uint high = (uint)(value >> 32);
  92
  93                                 data = new uint [high != 0 ? 2 : 1];
  94                                 data [0] = low;
  95                                 if (high != 0)
  96                                         data [1] = high;
  97                         } else {
  98                                 sign = -1;
  99                                 value = -value;
 100                                 uint low = (uint)value;
 101                                 uint high = (uint)((ulong)value >> 32);
 102
 103                                 data = new uint [high != 0 ? 2 : 1];
 104                                 data [0] = low;
 105                                 if (high != 0)
 106                                         data [1] = high;
 107                         }
 108                 }
 109
 110                 [CLSCompliantAttribute (false)]
 111                 public BigInteger (ulong value)
 112                 {
 113                         if (value == 0) {
 114                                 sign = 0;
 115                                 data = ZERO;
 116                         } else {
 117                                 sign = 1;
 118                                 uint low = (uint)value;
 119                                 uint high = (uint)(value >> 32);
 120
 121                                 data = new uint [high != 0 ? 2 : 1];
 122                                 data [0] = low;
 123                                 if (high != 0)
 124                                         data [1] = high;
 125                         }
 126                 }
 127
 128                 [CLSCompliantAttribute (false)]
 129                 public BigInteger (byte[] value)
 130                 {
 131                         if (value == null)
 132                                 throw new ArgumentNullException ("value");
 133
 134                         int len = value.Length;
 135
 136                         if (len == 0 || (len == 1 && value [0] == 0)) {
 137                                 sign = 0;
 138                                 data = ZERO;
 139                                 return;
 140                         }
 141
 142                         if ((value [len - 1] & 0x80) != 0)
 143                                 sign = -1;
 144                         else
 145                                 sign = 1;
 146
 147                         if (sign == 1) {
 148                                 while (value [len - 1] == 0)
 149                                         --len;
 150
 151                                 int full_words, size;
 152                                 full_words = size = len / 4;
 153                                 if ((len & 0x3) != 0)
 154                                         ++size;
 155
 156                                 data = new uint [size];
 157                                 int j = 0;
 158                                 for (int i = 0; i < full_words; ++i) {
 159                                         data [i] =      (uint)value [j++] |
 160                                                                 (uint)(value [j++] << 8) |
 161                                                                 (uint)(value [j++] << 16) |
 162                                                                 (uint)(value [j++] << 24);
 163                                 }
 164                                 size = len & 0x3;
 165                                 if (size > 0) {
 166                                         int idx = data.Length - 1;
 167                                         for (int i = 0; i < size; ++i)
 168                                                 data [idx] |= (uint)(value [j++] << (i * 8));
 169                                 }
 170                         } else {
 171                                 int full_words, size;
 172                                 full_words = size = len / 4;
 173                                 if ((len & 0x3) != 0)
 174                                         ++size;
 175
 176                                 data = new uint [size];
 177
 178                                 uint word, borrow = 1;
 179                                 ulong sub = 0;
 180                                 int j = 0;
 181
 182                                 for (int i = 0; i < full_words; ++i) {
 183                                         word =  (uint)value [j++] |
 184                                                         (uint)(value [j++] << 8) |
 185                                                         (uint)(value [j++] << 16) |
 186                                                         (uint)(value [j++] << 24);
 187
 188                                         sub = (ulong)word - borrow;
 189                                         word = (uint)sub;
 190                                         borrow = (uint)(sub >> 32) & 0x1u;
 191                                         data [i] = ~word;
 192                                 }
 193                                 size = len & 0x3;
 194
 195                                 if (size > 0) {
 196                                         word = 0;
 197                                         uint store_mask = 0;
 198                                         for (int i = 0; i < size; ++i) {
 199                                                 word |= (uint)(value [j++] << (i * 8));
 200                                                 store_mask = (store_mask << 8) | 0xFF;
 201                                         }
 202
 203                                         sub = word - borrow;
 204                                         word = (uint)sub;
 205                                         borrow = (uint)(sub >> 32) & 0x1u;
 206
 207                                         data [data.Length - 1] = ~word & store_mask;
 208                                 }
 209                                 if (borrow != 0) //FIXME I believe this can't happen, can someone write a test for it?
 210                                         throw new Exception ("non zero final carry");
 211                         }
 212
 213                 }
 214
 215                 public bool IsEven {
 216                         get { return (data [0] & 0x1) == 0; }
 217                 }
 218
 219                 public bool IsOne {
 220                         get { return sign == 1 && data.Length == 1 && data [0] == 1; }
 221                 }
 222
 223
 224                 //Gem from Hacker's Delight
 225                 //Returns the number of bits set in @x
 226                 static int PopulationCount (uint x)
 227                 {
 228                         x = x - ((x >> 1) & 0x55555555);
 229                         x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
 230                         x = (x + (x >> 4)) & 0x0F0F0F0F;
 231                         x = x + (x >> 8);
 232                         x = x + (x >> 16);
 233                         return (int)(x & 0x0000003F);
 234                 }
 235
 236                 public bool IsPowerOfTwo {
 237                         get {
 238                                 bool foundBit = false;
 239                                 if (sign != 1)
 240                                         return false;
 241                                 //This function is pop count == 1 for positive numbers
 242                                 for (int i = 0; i < data.Length; ++i) {
 243                                         int p = PopulationCount (data [i]);
 244                                         if (p > 0) {
 245                                                 if (p > 1 || foundBit)
 246                                                         return false;
 247                                                 foundBit = true;
 248                                         }
 249                                 }
 250                                 return foundBit;
 251                         }
 252                 }
 253
 254                 public bool IsZero {
 255                         get { return sign == 0; }
 256                 }
 257
 258                 public int Sign {
 259                         get { return sign; }
 260                 }
 261
 262                 public static BigInteger MinusOne {
 263                         get { return new BigInteger (-1, ONE); }
 264                 }
 265
 266                 public static BigInteger One {
 267                         get { return new BigInteger (1, ONE); }
 268                 }
 269
 270                 public static BigInteger Zero {
 271                         get { return new BigInteger (0, ZERO); }
 272                 }
 273
 274                 public static explicit operator int (BigInteger value)
 275                 {
 276                         if (value.data.Length > 1)
 277                                 throw new OverflowException ();
 278                         uint data = value.data [0];
 279
 280                         if (value.sign == 1) {
 281                                 if (data > (uint)int.MaxValue)
 282                                         throw new OverflowException ();
 283                                 return (int)data;
 284                         } else if (value.sign == -1) {
 285                                 if (data > 0x80000000u)
 286                                         throw new OverflowException ();
 287                                 return -(int)data;
 288                         }
 289
 290                         return 0;
 291                 }
 292
 293                 [CLSCompliantAttribute (false)]
 294                 public static explicit operator uint (BigInteger value)
 295                 {
 296                         if (value.data.Length > 1 || value.sign == -1)
 297                                 throw new OverflowException ();
 298                         return value.data [0];
 299                 }
 300
 301                 public static explicit operator long (BigInteger value)
 302                 {
 303                         if (value.sign == 0)
 304                                 return 0;
 305
 306                         if (value.data.Length > 2)
 307                                 throw new OverflowException ();
 308
 309                         uint low = value.data [0];
 310
 311                         if (value.data.Length == 1) {
 312                                 if (value.sign == 1)
 313                                         return (long)low;
 314                                 long res = (long)low;
 315                                 return -res;
 316                         }
 317
 318                         uint high = value.data [1];
 319
 320                         if (value.sign == 1) {
 321                                 if (high >= 0x80000000u)
 322                                         throw new OverflowException ();
 323                                 return (((long)high) << 32) | low;
 324                         }
 325
 326                         if (high > 0x80000000u)
 327                                 throw new OverflowException ();
 328
 329                         return - ((((long)high) << 32) | (long)low);
 330                 }
 331
 332                 [CLSCompliantAttribute (false)]
 333                 public static explicit operator ulong (BigInteger value)
 334                 {
 335                         if (value.data.Length > 2 || value.sign == -1)
 336                                 throw new OverflowException ();
 337
 338                         uint low = value.data [0];
 339                         if (value.data.Length == 1)
 340                                 return low;
 341
 342                         uint high = value.data [1];
 343                         return (((ulong)high) << 32) | low;
 344                 }
 345
 346
 347                 public static implicit operator BigInteger (int value)
 348                 {
 349                         return new BigInteger (value);
 350                 }
 351
 352                 [CLSCompliantAttribute (false)]
 353                 public static implicit operator BigInteger (uint value)
 354                 {
 355                         return new BigInteger (value);
 356                 }
 357
 358                 public static implicit operator BigInteger (long value)
 359                 {
 360                         return new BigInteger (value);
 361                 }
 362
 363                 [CLSCompliantAttribute (false)]
 364                 public static implicit operator BigInteger (ulong value)
 365                 {
 366                         return new BigInteger (value);
 367                 }
 368
 369                 public static BigInteger operator+ (BigInteger left, BigInteger right)
 370                 {
 371                         if (left.sign == 0)
 372                                 return right;
 373                         if (right.sign == 0)
 374                                 return left;
 375
 376                         if (left.sign == right.sign)
 377                                 return new BigInteger (left.sign, CoreAdd (left.data, right.data));
 378
 379                         int r = CoreCompare (left.data, right.data);
 380
 381                         if (r == 0)
 382                                 return new BigInteger (0, ZERO);
 383
 384                         if (r > 0) //left > right
 385                                 return new BigInteger (left.sign, CoreSub (left.data, right.data));
 386
 387                         return new BigInteger (right.sign, CoreSub (right.data, left.data));
 388                 }
 389
 390                 public static bool operator< (BigInteger left, BigInteger right)
 391                 {
 392                         return Compare (left, right) < 0;
 393                 }
 394
 395                 [CLSCompliantAttribute (false)]
 396                 public static bool operator< (BigInteger left, ulong right)
 397                 {
 398                         return left.CompareTo (right) < 0;
 399                 }
 400
 401                 [CLSCompliantAttribute (false)]
 402                 public static bool operator< (ulong left, BigInteger right)
 403                 {
 404                         return right.CompareTo (left) > 0;
 405                 }
 406
 407                 public static bool operator<= (BigInteger left, BigInteger right)
 408                 {
 409                         return Compare (left, right) <= 0;
 410                 }
 411
 412                 [CLSCompliantAttribute (false)]
 413                 public static bool operator<= (BigInteger left, ulong right)
 414                 {
 415                         return left.CompareTo (right) <= 0;
 416                 }
 417
 418                 [CLSCompliantAttribute (false)]
 419                 public static bool operator<= (ulong left, BigInteger right)
 420                 {
 421                         return right.CompareTo (left) >= 0;
 422                 }
 423
 424                 public static bool operator> (BigInteger left, BigInteger right)
 425                 {
 426                         return Compare (left, right) > 0;
 427                 }
 428
 429                 [CLSCompliantAttribute (false)]
 430                 public static bool operator> (BigInteger left, ulong right)
 431                 {
 432                         return left.CompareTo (right) > 0;
 433                 }
 434
 435                 [CLSCompliantAttribute (false)]
 436                 public static bool operator> (ulong left, BigInteger right)
 437                 {
 438                         return right.CompareTo (left) < 0;
 439                 }
 440
 441                 public static bool operator>= (BigInteger left, BigInteger right)
 442                 {
 443                         return Compare (left, right) >= 0;
 444                 }
 445
 446                 [CLSCompliantAttribute (false)]
 447                 public static bool operator>= (BigInteger left, ulong right)
 448                 {
 449                         return left.CompareTo (right) >= 0;
 450                 }
 451
 452                 [CLSCompliantAttribute (false)]
 453                 public static bool operator>= (ulong left, BigInteger right)
 454                 {
 455                         return right.CompareTo (left) <= 0;
 456                 }
 457
 458                 public static bool operator== (BigInteger left, BigInteger right)
 459                 {
 460                         return Compare (left, right) == 0;
 461                 }
 462
 463                 [CLSCompliantAttribute (false)]
 464                 public static bool operator== (BigInteger left, ulong right)
 465                 {
 466                         return left.CompareTo (right) == 0;
 467                 }
 468
 469                 [CLSCompliantAttribute (false)]
 470                 public static bool operator== (ulong left, BigInteger right)
 471                 {
 472                         return right.CompareTo (left) == 0;
 473                 }
 474
 475                 public static bool operator!= (BigInteger left, BigInteger right)
 476                 {
 477                         return Compare (left, right) != 0;
 478                 }
 479
 480                 [CLSCompliantAttribute (false)]
 481                 public static bool operator!= (BigInteger left, ulong right)
 482                 {
 483                         return left.CompareTo (right) != 0;
 484                 }
 485
 486                 [CLSCompliantAttribute (false)]
 487                 public static bool operator!= (ulong left, BigInteger right)
 488                 {
 489                         return right.CompareTo (left) != 0;
 490                 }
 491
 492                 public override bool Equals (object obj)
 493                 {
 494                         if (!(obj is BigInteger))
 495                                 return false;
 496                         return Equals ((BigInteger)obj);
 497                 }
 498
 499                 public bool Equals (BigInteger other)
 500                 {
 501                         if (sign != other.sign)
 502                                 return false;
 503                         if (data.Length != other.data.Length)
 504                                 return false;
 505                         for (int i = 0; i < data.Length; ++i) {
 506                                 if (data [i] != other.data [i])
 507                                         return false;
 508                         }
 509                         return true;
 510                 }
 511
 512                 [CLSCompliantAttribute (false)]
 513                 public bool Equals (ulong other)
 514                 {
 515                         return CompareTo (other) == 0;
 516                 }
 517
 518                 public override int GetHashCode ()
 519                 {
 520                         uint hash = (uint)(sign * 0x01010101u);
 521
 522                         for (int i = 0; i < data.Length; ++i)
 523                                 hash ^= data [i];
 524                         return (int)hash;
 525                 }
 526
 527                 public static BigInteger Add (BigInteger left, BigInteger right)
 528                 {
 529                         return left + right;
 530                 }
 531
 532                 public int CompareTo (object obj)
 533                 {
 534                         if (obj == null)
 535                                 return 1;
 536
 537                         if (!(obj is BigInteger))
 538                                 return -1;
 539
 540                         return Compare (this, (BigInteger)obj);
 541                 }
 542
 543                 public int CompareTo (BigInteger other)
 544                 {
 545                         return Compare (this, other);
 546                 }
 547
 548                 [CLSCompliantAttribute (false)]
 549                 public int CompareTo (ulong other)
 550                 {
 551                         if (sign < 0)
 552                                 return -1;
 553                         if (sign == 0)
 554                                 return other == 0 ? 0 : -1;
 555
 556                         if (data.Length > 2)
 557                                 return 1;
 558
 559                         uint high = (uint)(other >> 32);
 560                         uint low = (uint)other;
 561
 562                         return LongCompare (low, high);
 563                 }
 564
 565                 int LongCompare (uint low, uint high)
 566                 {
 567                         uint h = 0;
 568                         if (data.Length > 1)
 569                                 h = data [1];
 570
 571                         if (h > high)
 572                                 return 1;
 573                         if (h < high)
 574                                 return -1;
 575
 576                         uint l = data [0];
 577
 578                         if (l > low)
 579                                 return 1;
 580                         if (l < low)
 581                                 return -1;
 582
 583                         return 0;
 584                 }
 585
 586                 public int CompareTo (long other)
 587                 {
 588                         int ls = sign;
 589                         int rs = Math.Sign (other);
 590
 591                         if (ls != rs)
 592                                 return ls > rs ? 1 : -1;
 593
 594                         if (ls == 0)
 595                                 return 0;
 596
 597                         if (data.Length > 2)
 598                                 return -sign;
 599
 600                         if (other < 0)
 601                                 other = -other;
 602                         uint low = (uint)other;
 603                         uint high = (uint)((ulong)other >> 32);
 604
 605                         int r = LongCompare (low, high);
 606                         if (ls == -1)
 607                                 r = -r;
 608
 609                         return r;
 610                 }
 611
 612                 public static int Compare (BigInteger left, BigInteger right)
 613                 {
 614                         int ls = left.sign;
 615                         int rs = right.sign;
 616
 617                         if (ls != rs)
 618                                 return ls > rs ? 1 : -1;
 619
 620                         int r = CoreCompare (left.data, right.data);
 621                         if (ls < 0)
 622                                 r = -r;
 623                         return r;
 624                 }
 625
 626
 627                 static int TopByte (uint x)
 628                 {
 629                         if ((x & 0xFFFF0000u) != 0) {
 630                                 if ((x & 0xFF000000u) != 0)
 631                                         return 4;
 632                                 return 3;
 633                         }
 634                         if ((x & 0xFF00u) != 0)
 635                                 return 2;
 636                         return 1;
 637                 }
 638
 639                 static int FirstNonFFByte (uint word)
 640                 {
 641                         if ((word & 0xFF000000u) != 0xFF000000u)
 642                                 return 4;
 643                         else if ((word & 0xFF0000u) != 0xFF0000u)
 644                                 return 3;
 645                         else if ((word & 0xFF00u) != 0xFF00u)
 646                                 return 2;
 647                         return 1;
 648                 }
 649
 650                 public byte[] ToByteArray ()
 651                 {
 652                         if (sign == 0)
 653                                 return new byte [1];
 654
 655                         //number of bytes not counting upper word
 656                         int bytes = (data.Length - 1) * 4;
 657                         bool needExtraZero = false;
 658
 659                         uint topWord = data [data.Length - 1];
 660                         int extra;
 661
 662                         //if the topmost bit is set we need an extra
 663                         if (sign == 1) {
 664                                 extra = TopByte (topWord);
 665                                 uint mask = 0x80u << ((extra - 1) * 8);
 666                                 if ((topWord & mask) != 0) {
 667                                         needExtraZero = true;
 668                                 }
 669                         } else {
 670                                 extra = TopByte (topWord);
 671                         }
 672
 673                         byte[] res = new byte [bytes + extra + (needExtraZero ? 1 : 0) ];
 674                         if (sign == 1) {
 675                                 int j = 0;
 676                                 int end = data.Length - 1;
 677                                 for (int i = 0; i < end; ++i) {
 678                                         uint word = data [i];
 679
 680                                         res [j++] = (byte)word;
 681                                         res [j++] = (byte)(word >> 8);
 682                                         res [j++] = (byte)(word >> 16);
 683                                         res [j++] = (byte)(word >> 24);
 684                                 }
 685                                 while (extra-- > 0) {
 686                                         res [j++] = (byte)topWord;
 687                                         topWord >>= 8;
 688                                 }
 689                         } else {
 690                                 int j = 0;
 691                                 int end = data.Length - 1;
 692
 693                                 uint carry = 1, word;
 694                                 ulong add;
 695                                 for (int i = 0; i < end; ++i) {
 696                                         word = data [i];
 697                                         add = (ulong)~word + carry;
 698                                         word = (uint)add;
 699                                         carry = (uint)(add >> 32);
 700
 701                                         res [j++] = (byte)word;
 702                                         res [j++] = (byte)(word >> 8);
 703                                         res [j++] = (byte)(word >> 16);
 704                                         res [j++] = (byte)(word >> 24);
 705                                 }
 706
 707                                 add = (ulong)~topWord + (carry);
 708                                 word = (uint)add;
 709                                 carry = (uint)(add >> 32);
 710                                 if (carry == 0) {
 711                                         int ex = FirstNonFFByte (word);
 712                                         bool needExtra = (word & (1 << (ex * 8 - 1))) == 0;
 713                                         int to = ex + (needExtra ? 1 : 0);
 714
 715                                         if (to != extra)
 716                                                 res = Resize (res, bytes + to);
 717
 718                                         while (ex-- > 0) {
 719                                                 res [j++] = (byte)word;
 720                                                 word >>= 8;
 721                                         }
 722                                         if (needExtra)
 723                                                 res [j++] = 0xFF;
 724                                 } else {
 725                                         res = Resize (res, bytes + 5);
 726                                         res [j++] = (byte)word;
 727                                         res [j++] = (byte)(word >> 8);
 728                                         res [j++] = (byte)(word >> 16);
 729                                         res [j++] = (byte)(word >> 24);
 730                                         res [j++] = 0xFF;
 731                                 }
 732                         }
 733
 734                         return res;
 735                 }
 736
 737                 static byte[] Resize (byte[] v, int len)
 738                 {\r
 739                         byte[] res = new byte [len];\r
 740                         Array.Copy (v, res, Math.Min (v.Length, len));\r
 741                         return res;\r
 742                 }
 743
 744                 static uint[] Resize (uint[] v, int len)
 745                 {
 746                         uint[] res = new uint [len];\r
 747                         Array.Copy (v, res, Math.Min (v.Length, len));\r
 748                         return res;\r
 749                 }
 750
 751                 static uint[] CoreAdd (uint[] a, uint[] b)
 752                 {
 753                         if (a.Length < b.Length) {
 754                                 uint[] tmp = a;
 755                                 a = b;
 756                                 b = tmp;
 757                         }
 758
 759                         int bl = a.Length;
 760                         int sl = b.Length;
 761
 762                         uint[] res = new uint [bl];
 763
 764                         ulong sum = 0;
 765
 766                         int i = 0;
 767                         for (; i < sl; i++) {
 768                                 sum = sum + a [i] + b [i];
 769                                 res [i] = (uint)sum;
 770                                 sum >>= 32;
 771                         }
 772
 773                         for (; i < bl; i++) {
 774                                 sum = sum + a [i];
 775                                 res [i] = (uint)sum;
 776                                 sum >>= 32;
 777                         }
 778
 779                         if (sum != 0) {
 780                                 res = Resize (res, bl + 1);
 781                                 res [i] = (uint)sum;
 782                         }
 783
 784                         return res;
 785                 }
 786
 787                 /*invariant a > b*/
 788                 static uint[] CoreSub (uint[] a, uint[] b)
 789                 {
 790                         int bl = a.Length;
 791                         int sl = b.Length;
 792
 793                         Console.WriteLine ("bl {0} sl {1}", bl, sl);
 794
 795                         uint[] res = new uint [bl];
 796
 797                         ulong borrow = 0;
 798                         int i;
 799                         for (i = 0; i < sl; ++i) {
 800                                 borrow = (ulong)a [i] - b [i] - borrow;
 801
 802                                 Console.WriteLine ("a {0} b {1}", a[i], b [i]);
 803
 804                                 res [i] = (uint)borrow;
 805                                 borrow = (borrow >> 32) & 0x1;
 806                         }
 807
 808                         for (; i < bl; i++) {
 809                                 borrow = (ulong)a [i] - borrow;
 810                                 res [i] = (uint)borrow;
 811                                 borrow = (borrow >> 32) & 0x1;
 812                         }
 813
 814                         //remove extra zeroes
 815                         for (i = bl - 1; i >= 0 && res [i] == 0; --i) ;
 816                         if (i < bl - 1)
 817                                 res = Resize (res, i + 1);
 818
 819             return res;
 820                 }
 821
 822                 static int CoreCompare (uint[] a, uint[] b)
 823                 {
 824                         int     al = a.Length;
 825                         int bl = b.Length;
 826
 827                         if (al > bl)
 828                                 return 1;
 829                         if (bl > al)
 830                                 return -1;
 831
 832                         for (int i = al - 1; i >= 0; --i) {
 833                                 uint ai = a [i];
 834                                 uint bi = b [i];
 835                                 if (ai > bi)
 836                                         return 1;
 837                                 if (ai < bi)
 838                                         return -1;
 839                         }
 840                         return 0;
 841                 }
 842
 843         }
 844 }\r