ghc/lib/std/BigInteger.cs

   1 // Big Integer class for .NET
   2 // (c) The GHC Team 2001
   3
   4 // TODO:
   5 // Constructors from Single, Double, Currency, String
   6 //
   7
   8 using System;
   9 using System.Diagnostics;
  10
  11 public class BigInteger : IComparable, IConvertible, IFormattable {
  12
  13  int sign;
  14  int size;
  15  int used;
  16  byte[] body;
  17
  18  const int B_BASE = 256;
  19  const double B_BASE_FLT = 256.0;
  20
  21
  22  // Constructors
  23
  24  public BigInteger() {
  25 #if BIGINTEGER_DEBUG
  26    Debug.Assert(this.sane());
  27 #endif
  28  }
  29
  30  public BigInteger(Int32 n) {
  31    this.size = 4;
  32    this.body = new byte[this.size];
  33    this.sign = this.used = 0;
  34    if (n == 0) {
  35 #if BIGINTEGER_DEBUG
  36      Debug.Assert(this.sane());
  37 #endif
  38      return;
  39    }
  40    if (n < 0) {
  41      this.sign = -1;
  42    }
  43    else {
  44      this.sign = 1;
  45    }
  46    if (n < 0) {
  47      n = -n;
  48    }
  49    while (n != 0) {
  50      this.body[this.used] = (byte)(n % B_BASE);
  51      n /= B_BASE;
  52      this.used++;
  53    }
  54 #if BIGINTEGER_DEBUG
  55    Debug.Assert(this.sane());
  56 #endif
  57  }
  58
  59  public BigInteger(UInt32 n) {
  60    this.size = 4;
  61    this.body = new byte[this.size];
  62    this.sign = this.used = 0;
  63    if (n == 0) {
  64 #if BIGINTEGER_DEBUG
  65      Debug.Assert(this.sane());
  66 #endif
  67      return;
  68    }
  69    this.sign = 1;
  70    while (n != 0) {
  71      this.body[this.used] = (byte)(n % B_BASE);
  72      n /= B_BASE;
  73      this.used++;
  74    }
  75 #if BIGINTEGER_DEBUG
  76    Debug.Assert(this.sane());
  77 #endif
  78  }
  79
  80  public BigInteger(Int64 n) {
  81    this.size = 8;
  82    this.body = new byte[this.size];
  83    this.sign = this.used = 0;
  84    if (n == 0) {
  85 #if BIGINTEGER_DEBUG
  86      Debug.Assert(this.sane());
  87 #endif
  88      return;
  89    }
  90    if (n < 0) {
  91      this.sign = -1;
  92    }
  93    else {
  94      this.sign = 1;
  95    }
  96    if (n < 0) {
  97      n = -n;
  98    }
  99    while (n != 0) {
 100      this.body[this.used] = (byte)(n % B_BASE);
 101      n /= B_BASE;
 102      this.used++;
 103    }
 104 #if BIGINTEGER_DEBUG
 105    Debug.Assert(this.sane());
 106 #endif
 107  }
 108
 109  public BigInteger(UInt64 n) {
 110    this.size = 8;
 111    this.body = new byte[this.size];
 112    this.sign = this.used = 0;
 113    if (n == 0) {
 114 #if BIGINTEGER_DEBUG
 115      Debug.Assert(this.sane());
 116 #endif
 117      return;
 118    }
 119    this.sign = 1;
 120    while (n != 0) {
 121      this.body[this.used] = (byte)(n % B_BASE);
 122      n /= B_BASE;
 123      this.used++;
 124    }
 125 #if BIGINTEGER_DEBUG
 126    Debug.Assert(this.sane());
 127 #endif
 128  }
 129
 130  // NOTE: This only works currectly if B_BASE >= 10
 131  // TODO: Turn this into a Parse method taking a String
 132  public BigInteger (char [] str) {
 133    int sign, d, t, i, j, carry;
 134
 135    for (i = 0; str[i] != 0; i++) {
 136    }
 137    this.size = i;
 138    this.body = new byte[this.size];
 139    this.sign = this.used = 0;
 140    sign = 1;
 141    i = 0;
 142    if (str[0] == '-') {
 143      i++;
 144      sign = -1;
 145    }
 146
 147    while (Char.IsDigit(str[i])) {
 148
 149      // multiply this by 10
 150      carry = 0;
 151      for (j = 0; j < this.used; j++) {
 152        t = 10 * this.body[j] + carry;
 153        this.body[j] = (byte)(t % B_BASE);
 154        carry = t / B_BASE;
 155      }
 156 #if BIGINTEGER_DEBUG
 157      Debug.Assert(carry < B_BASE);
 158 #endif
 159      if (carry > 0) {
 160        this.body[this.used++] = (byte)carry;
 161      }
 162      // add a digit on
 163      d = str[i] - '0';
 164      i++;
 165
 166      carry = d;
 167      for (j = 0; j < this.used; j++) {
 168        carry += this.body[j];
 169        this.body[j] = (byte)(carry % B_BASE);
 170        carry /= B_BASE;
 171        if (carry == 0) {
 172          break;
 173        }
 174      }
 175      if (carry > 0) {
 176        this.body[this.used++] = (byte)carry;
 177      }
 178    }
 179
 180    this.sign = sign;
 181 #if BIGINTEGER_DEBUG
 182    Debug.Assert(this.sane());
 183 #endif
 184  }
 185
 186
 187  // Constants
 188  static readonly BigInteger Zero = new BigInteger(0);
 189  static readonly BigInteger One = new BigInteger(1);
 190  static readonly BigInteger MinusOne = new BigInteger(-1);
 191
 192
 193  // Conversions
 194
 195  // Implicit
 196  public static implicit operator BigInteger(SByte n) {
 197    return new BigInteger((Int32)n);
 198  }
 199
 200  public static implicit operator BigInteger(Byte n) {
 201    return new BigInteger((UInt32)n);
 202  }
 203
 204  public static implicit operator BigInteger(Int16 n) {
 205    return new BigInteger((Int32)n);
 206  }
 207
 208  public static implicit operator BigInteger(UInt16 n) {
 209    return new BigInteger((UInt32)n);
 210  }
 211
 212  public static implicit operator BigInteger(Char n) {
 213    return new BigInteger((Int32)n);
 214  }
 215
 216  public static implicit operator BigInteger(Int32 n) {
 217    return new BigInteger(n);
 218  }
 219
 220  public static implicit operator BigInteger(UInt32 n) {
 221    return new BigInteger(n);
 222  }
 223
 224  public static implicit operator BigInteger(Int64 n) {
 225    return new BigInteger(n);
 226  }
 227
 228  public static implicit operator BigInteger(UInt64 n) {
 229    return new BigInteger(n);
 230  }
 231
 232  // Explicit
 233
 234  public static Boolean ToBoolean(BigInteger n) {
 235    throw new InvalidCastException();
 236  }
 237
 238  public static explicit operator Boolean(BigInteger n) {
 239    return ToBoolean(n);
 240  }
 241
 242  Boolean IConvertible.ToBoolean(IFormatProvider p) {
 243    return ToBoolean(this);
 244  }
 245
 246  public static DateTime ToDateTime(BigInteger n) {
 247    throw new InvalidCastException();
 248  }
 249
 250  DateTime IConvertible.ToDateTime(IFormatProvider p) {
 251    return ToDateTime(this);
 252  }
 253
 254  public static explicit operator DateTime(BigInteger n) {
 255    return ToDateTime(n);
 256  }
 257
 258  public static SByte ToSByte(BigInteger n) {
 259    SByte res;
 260    if (n.sign == 0) {
 261      return 0;
 262    }
 263    res = 0;
 264    if (n.used > 0) {
 265      res = (SByte)n.body[0];
 266    }
 267    if (n.sign < 0) {
 268      res = (SByte)(-res);
 269    }
 270    return res;
 271  }
 272
 273  SByte IConvertible.ToSByte(IFormatProvider p) {
 274    return ToSByte(this);
 275  }
 276
 277  public static explicit operator SByte(BigInteger n) {
 278    return ToSByte(n);
 279  }
 280
 281  public static Byte ToByte(BigInteger n) {
 282    Byte res;
 283    if (n.sign == 0) {
 284      return 0;
 285    }
 286    res = 0;
 287    if (n.used > 0) {
 288      res = (Byte)n.body[0];
 289    }
 290    return res;
 291  }
 292
 293  Byte IConvertible.ToByte(IFormatProvider p) {
 294    return ToByte(this);
 295  }
 296
 297  public static explicit operator Byte(BigInteger n) {
 298    return ToByte(n);
 299  }
 300
 301  public static Int16 ToInt16(BigInteger n) {
 302    int i, d;
 303    Int16 res;
 304    if (n.sign == 0) {
 305      return 0;
 306    }
 307    res = 0;
 308    for (i = n.used-1; i >= 0; i--) {
 309      d = n.body[i];
 310      res = (Int16)(res * B_BASE + d);
 311    }
 312    if (n.sign < 0) {
 313      res = (Int16)(-res);
 314    }
 315    return res;
 316  }
 317
 318  Int16 IConvertible.ToInt16(IFormatProvider p) {
 319    return ToInt16(this);
 320  }
 321
 322  public static explicit operator Int16(BigInteger n) {
 323    return ToInt16(n);
 324  }
 325
 326  public static UInt16 ToUInt16(BigInteger n) {
 327    int i, d;
 328    UInt16 res;
 329    if (n.sign == 0) {
 330      return 0;
 331    }
 332    res = 0;
 333    for (i = n.used-1; i >= 0; i--) {
 334      d = n.body[i];
 335      res = (UInt16)(res * B_BASE + d);
 336    }
 337    return res;
 338  }
 339
 340  UInt16 IConvertible.ToUInt16(IFormatProvider p) {
 341    return ToUInt16(this);
 342  }
 343
 344  public static explicit operator UInt16(BigInteger n) {
 345    return ToUInt16(n);
 346  }
 347
 348  public static Char ToChar(BigInteger n) {
 349    throw new InvalidCastException();
 350  }
 351
 352  Char IConvertible.ToChar(IFormatProvider p) {
 353    return ToChar(this);
 354  }
 355
 356  public static explicit operator Char(BigInteger n) {
 357    return ToChar(n);
 358  }
 359
 360  public static Int32 ToInt32(BigInteger n) {
 361    int i, d;
 362    Int32 res;
 363    if (n.sign == 0) {
 364      return 0;
 365    }
 366    res = 0;
 367    for (i = n.used-1; i >= 0; i--) {
 368      d = n.body[i];
 369      res = res * B_BASE + d;
 370    }
 371    if (n.sign < 0) {
 372      res = -res;
 373    }
 374    return res;
 375  }
 376
 377  Int32 IConvertible.ToInt32(IFormatProvider p) {
 378    return ToInt32(this);
 379  }
 380
 381  public static explicit operator Int32(BigInteger n) {
 382    return ToInt32(n);
 383  }
 384
 385  public static UInt32 ToUInt32(BigInteger n) {
 386    int i, d;
 387    UInt32 res;
 388    if (n.sign == 0) {
 389      return 0;
 390    }
 391    res = 0;
 392    for (i = n.used-1; i >= 0; i--) {
 393      d = n.body[i];
 394      res = res * B_BASE + (UInt32)d;
 395    }
 396    return res;
 397  }
 398
 399  UInt32 IConvertible.ToUInt32(IFormatProvider p) {
 400    return ToUInt32(this);
 401  }
 402
 403  public static explicit operator UInt32(BigInteger n) {
 404    return ToUInt32(n);
 405  }
 406
 407  public static Int64 ToInt64(BigInteger n) {
 408    int i, d;
 409    Int64 res;
 410    if (n.sign == 0) {
 411      return 0;
 412    }
 413    res = 0;
 414    for (i = n.used-1; i >= 0; i--) {
 415      d = n.body[i];
 416      res = res * B_BASE + d;
 417    }
 418    if (n.sign < 0) {
 419      res = -res;
 420    }
 421    return res;
 422  }
 423
 424  Int64 IConvertible.ToInt64(IFormatProvider p) {
 425    return ToInt64(this);
 426  }
 427
 428  public static explicit operator Int64(BigInteger n) {
 429    return ToInt64(n);
 430  }
 431
 432  public static UInt64 ToUInt64(BigInteger n) {
 433    int i, d;
 434    UInt64 res;
 435    if (n.sign == 0) {
 436      return 0;
 437    }
 438    res = 0;
 439    for (i = n.used-1; i >= 0; i--) {
 440      d = n.body[i];
 441      res = res * B_BASE + (UInt64)d;
 442    }
 443    return res;
 444  }
 445
 446  UInt64 IConvertible.ToUInt64(IFormatProvider p) {
 447    return ToUInt64(this);
 448  }
 449
 450  public static explicit operator UInt64(BigInteger n) {
 451    return ToUInt64(n);
 452  }
 453
 454  public static Decimal ToDecimal(BigInteger n) {
 455    int i, d;
 456    Decimal res;
 457    if (n.sign == 0) {
 458      return 0;
 459    }
 460    res = 0;
 461    for (i = n.used-1; i >= 0; i--) {
 462      d = n.body[i];
 463      res = res * B_BASE + (Decimal)d;
 464    }
 465    return res;
 466  }
 467
 468  Decimal IConvertible.ToDecimal(IFormatProvider p) {
 469    return ToDecimal(this);
 470  }
 471
 472  public static explicit operator Decimal(BigInteger n) {
 473    return ToDecimal(n);
 474  }
 475
 476  public static Single ToSingle(BigInteger n) {
 477    int i, d;
 478    Single res;
 479    if (n.sign == 0) {
 480      return 0.0F;
 481    }
 482    res = 0.0F;
 483    for (i = n.used-1; i >= 0; i--) {
 484      d = n.body[i];
 485      res = res * (Single)B_BASE_FLT + d;
 486    }
 487    if (n.sign < 0) {
 488      res = -res;
 489    }
 490    return res;
 491  }
 492
 493  Single IConvertible.ToSingle(IFormatProvider p) {
 494    return ToSingle(this);
 495  }
 496
 497  public static explicit operator Single(BigInteger n) {
 498    return ToSingle(n);
 499  }
 500
 501  public static Double ToDouble(BigInteger n) {
 502    int i, d;
 503    Double res;
 504    if (n.sign == 0) {
 505      return 0.0;
 506    }
 507    res = 0.0;
 508    for (i = n.used-1; i >= 0; i--) {
 509      d = n.body[i];
 510      res = res * B_BASE_FLT + d;
 511    }
 512    if (n.sign < 0) {
 513      res = -res;
 514    }
 515    return res;
 516  }
 517
 518  Double IConvertible.ToDouble(IFormatProvider p) {
 519    return ToDouble(this);
 520  }
 521
 522  public static explicit operator Double(BigInteger n) {
 523    return ToDouble(n);
 524  }
 525
 526  override public String ToString() {
 527    int i;
 528    Console.Write ( "sign={0}  used={1}  size={2}   ", this.sign, this.used, this.size );
 529    for (i = this.used-1; i >= 0; i--) {
 530      Console.Write ( "{0} ", (int)(this.body[i]) );
 531    }
 532    Console.Write ( "\n" );
 533    return "(some number or other)";
 534  }
 535
 536  public String ToString(IFormatProvider p) {
 537    return ToString(null, p);
 538  }
 539
 540  public String ToString(String fmt) {
 541    return this.ToString();
 542  }
 543
 544  public String ToString(String fmt, IFormatProvider p) {
 545    throw new InvalidCastException();
 546  }
 547
 548  public Object ToType(Type ty, IFormatProvider n) {
 549    throw new InvalidCastException();
 550  }
 551
 552  // public object GetFormat(Type
 553
 554  public TypeCode GetTypeCode() {
 555    return TypeCode.Int64;
 556  }
 557
 558  // Basics
 559
 560  bool sane() {
 561    if (this.sign == 0 && this.used != 0) {
 562      return false;
 563    }
 564    if (this.sign != -1 && this.sign != 0 && this.sign != 1) {
 565      return false;
 566    }
 567    if (this.used < 0) {
 568      return false;
 569    }
 570    if (this.size < 0) {
 571      return false;
 572    }
 573    if (this.used > this.size) {
 574      return false;
 575    }
 576    if (this.used == 0) {
 577      return true;
 578    }
 579    if (this.body[this.used-1] == 0) {
 580      return false;
 581    }
 582    return true;
 583  }
 584
 585  void u_renormalise() {
 586    while (this.used > 0 && this.body[this.used-1] == 0) {
 587      this.used--;
 588    }
 589    if (this.used == 0) {
 590      this.sign = 0;
 591    }
 592    else {
 593      this.sign = 1;
 594    }
 595  }
 596
 597
 598  public void renormalise() {
 599    while (this.used > 0 && this.body[this.used-1] == 0) {
 600      this.used--;
 601    }
 602    if (this.used == 0) {
 603      this.sign = 0;
 604    }
 605  }
 606
 607
 608  // Size of things
 609
 610  static int maxused_addsub ( BigInteger x, BigInteger y ) {
 611 #if BIGINTEGER_DEBUG
 612    Debug.Assert(x.sane());
 613    Debug.Assert(y.sane());
 614 #endif
 615    return 1 + (x.used > y.used ? x.used : y.used);
 616  }
 617
 618  static int maxused_mul ( BigInteger x, BigInteger y ) {
 619 #if BIGINTEGER_DEBUG
 620    Debug.Assert(x.sane());
 621    Debug.Assert(y.sane());
 622 #endif
 623    return x.used + y.used;
 624  }
 625
 626  static int maxused_qrm ( BigInteger x, BigInteger y ) {
 627 #if BIGINTEGER_DEBUG
 628    Debug.Assert(x.sane());
 629    Debug.Assert(y.sane());
 630 #endif
 631    return (x.used > y.used ? x.used : y.used);
 632  }
 633
 634  int maxused_neg() {
 635 #if BIGINTEGER_DEBUG
 636    Debug.Assert(this.sane());
 637 #endif
 638    return this.used;
 639  }
 640
 641
 642  // Signed ops
 643
 644  // A helper for signed + and -.  sdiff(x,y) ignores the signs of x and y
 645  // sets p to the signed value abs(x)-abs(y).
 646  static void sdiff(BigInteger x, BigInteger y, BigInteger res) {
 647    int t;
 648 #if BIGINTEGER_DEBUG
 649    Debug.Assert(x.sane());
 650    Debug.Assert(y.sane());
 651    Debug.Assert(res.size == maxused_addsub(x,y));
 652 #endif
 653    t = ucmp(x,y);
 654    if (t == 0) {
 655      res.sign = res.used = 0;
 656      return;
 657    }
 658    if (t == -1) {
 659      // x < y
 660      usub(y,x,res);
 661      res.sign = -1;
 662    }
 663    else {
 664      // x > y
 665      usub(x,y,res);
 666      res.sign = 1;
 667    }
 668 #if BIGINTEGER_DEBUG
 669    Debug.Assert(res.sane());
 670 #endif
 671  }
 672
 673  public BigInteger Negate() {
 674 #if BIGINTEGER_DEBUG
 675    Debug.Assert(this.sane());
 676 #endif
 677    BigInteger res = new BigInteger();
 678    res.size = this.used;
 679    res.body = new byte[res.used];
 680    res.used = this.used;
 681    for (int i = 0; i < this.used; i++) {
 682      res.body[i] = this.body[i];
 683    }
 684    res.sign = -(this.sign);
 685    return res;
 686  }
 687
 688  public static BigInteger Add(BigInteger x, BigInteger y) {
 689 #if BIGINTEGER_DEBUG
 690    Debug.Assert(x.sane());
 691    Debug.Assert(y.sane());
 692 #endif
 693    BigInteger res = new BigInteger();
 694    res.size = maxused_addsub(x, y);
 695    res.used = res.sign = 0;
 696
 697    if ( (x.sign >= 0 && y.sign >= 0) ||
 698         (x.sign < 0  && y.sign < 0)) {
 699      // same sign; add magnitude and clone sign
 700      uadd(x,y,res);
 701      if (x.sign < 0 && res.sign != 0) {
 702        res.sign = -1;
 703      }
 704    }
 705    else {
 706      // signs differ; use sdiff
 707      if (x.sign >= 0 && y.sign < 0) {
 708        sdiff(x,y,res);
 709      }
 710      else {
 711 #if BIGINTEGER_DEBUG
 712        Debug.Assert(x.sign < 0 && y.sign >= 0);
 713 #endif
 714        sdiff(y,x,res);
 715      }
 716    }
 717 #if BIGINTEGER_DEBUG
 718    Debug.Assert(res.sane());
 719 #endif
 720    return res;
 721  }
 722
 723  public BigInteger Increment() {
 724    return this + 1;
 725  }
 726
 727  public static BigInteger Sub(BigInteger x, BigInteger y) {
 728 #if BIGINTEGER_DEBUG
 729    Debug.Assert(x.sane());
 730    Debug.Assert(y.sane());
 731 #endif
 732    BigInteger res = new BigInteger();
 733    res.size = maxused_addsub(x, y);
 734    res.used = res.sign = 0;
 735
 736    if ( (x.sign >= 0 && y.sign < 0) ||
 737         (x.sign < 0  && y.sign >= 0)) {
 738      // opposite signs; add magnitudes and clone sign of x
 739      uadd(x,y,res);
 740 #if BIGINTEGER_DEBUG
 741      Debug.Assert(res.sign != 0);
 742 #endif
 743      if (x.sign < 0) {
 744        res.sign = -1;
 745      }
 746    }
 747    else
 748      // signs are the same; use sdiff
 749      if (x.sign >= 0 && y.sign >= 0) {
 750        sdiff(x,y,res);
 751      }
 752      else {
 753 #if BIGINTEGER_DEBUG
 754        Debug.Assert(x.sign < 0 && y.sign < 0);
 755 #endif
 756        sdiff(y,x,res);
 757      }
 758 #if BIGINTEGER_DEBUG
 759    Debug.Assert(res.sane());
 760 #endif
 761    return res;
 762  }
 763
 764  public BigInteger Decrement() {
 765    return this - 1;
 766  }
 767
 768  public static BigInteger Multiply(BigInteger x, BigInteger y) {
 769 #if BIGINTEGER_DEBUG
 770    Debug.Assert(x.sane());
 771    Debug.Assert(y.sane());
 772 #endif
 773    BigInteger res = new BigInteger();
 774    res.size = maxused_mul(x, y);
 775    res.body = new byte[res.size];
 776    res.used = res.sign = 0;
 777
 778    if (x.sign == 0 || y.sign == 0) {
 779      res.sign = res.used = 0;
 780 #if BIGINTEGER_DEBUG
 781      Debug.Assert(res.sane());
 782 #endif
 783      return res;
 784    }
 785    umul(x,y,res);
 786    if (x.sign != y.sign) {
 787      res.sign = -1;
 788    }
 789 #if BIGINTEGER_DEBUG
 790    Debug.Assert(res.sane());
 791 #endif
 792    return res;
 793  }
 794
 795  public static BigInteger Divide(BigInteger x, BigInteger y) {
 796    BigInteger q, r;
 797    QuotientRemainder(x, y, out q, out r);
 798    return q;
 799  }
 800
 801  public static BigInteger Remainder(BigInteger x, BigInteger y) {
 802    BigInteger q, r;
 803    QuotientRemainder(x, y, out q, out r);
 804    return r;
 805  }
 806
 807  public static Int32 Compare(BigInteger x, BigInteger y) {
 808 #if BIGINTEGER_DEBUG
 809    Debug.Assert(x.sane());
 810    Debug.Assert(y.sane());
 811 #endif
 812    if (x.sign < y.sign) {
 813      return -1;
 814    }
 815    if (x.sign > y.sign) {
 816      return 1;
 817    }
 818 #if BIGINTEGER_DEBUG
 819    Debug.Assert(x.sign == y.sign);
 820 #endif
 821    if (x.sign == 0) {
 822      return 0;
 823    }
 824    if (x.sign == 1) {
 825      return ucmp(x,y);
 826    }
 827    else {
 828      return ucmp(y,x);
 829    }
 830  }
 831
 832  public Int32 CompareTo(Object o) {
 833    return Compare(this, (BigInteger)o);
 834  }
 835
 836  public static Boolean Equals(BigInteger x, BigInteger y) {
 837    return Compare(x, y) == 0;
 838  }
 839
 840  override public Boolean Equals(Object o) {
 841    return this == (BigInteger)o;
 842  }
 843
 844  override public Int32 GetHashCode() {
 845    int i;
 846    UInt32 h = 0;
 847    for (i = 0; i < this.used; i++) {
 848      h = (h << 4) + this.body[i];
 849      UInt32 g = h & 0xf0000000;
 850      if (g != 0) {
 851        h ^= g >> 24;
 852        h ^= g;
 853      }
 854    }
 855    return (Int32)h;
 856  }
 857
 858  // Overloaded operators
 859
 860  public static BigInteger operator +(BigInteger x) {
 861    return x;
 862  }
 863
 864  public static BigInteger operator -(BigInteger x) {
 865    return x.Negate();
 866  }
 867
 868  public static BigInteger operator +(BigInteger x, BigInteger y) {
 869    return Add(x, y);
 870  }
 871
 872  public static BigInteger operator -(BigInteger x, BigInteger y) {
 873    return Sub(x, y);
 874  }
 875
 876  public static BigInteger operator ++(BigInteger x) {
 877    return x + 1;
 878  }
 879
 880  public static BigInteger operator --(BigInteger x) {
 881    return x - 1;
 882  }
 883
 884  public static BigInteger operator *(BigInteger x, BigInteger y) {
 885    return Multiply(x, y);
 886  }
 887
 888  public static BigInteger operator /(BigInteger x, BigInteger y) {
 889    return Divide(x, y);
 890  }
 891
 892  public static BigInteger operator %(BigInteger x, BigInteger y) {
 893    return Remainder(x, y);
 894  }
 895
 896  public static Boolean operator ==(BigInteger x, BigInteger y) {
 897    return Equals(x, y);
 898  }
 899
 900  public static Boolean operator !=(BigInteger x, BigInteger y) {
 901    return !Equals(x, y);
 902  }
 903  public static Boolean operator <(BigInteger x, BigInteger y) {
 904    return Compare(x, y) == -1;
 905  }
 906
 907  public static Boolean operator <=(BigInteger x, BigInteger y) {
 908    return Compare(x, y) < 1;
 909  }
 910
 911  public static Boolean operator >(BigInteger x, BigInteger y) {
 912    return Compare(x, y) == 1;
 913  }
 914
 915  public static Boolean operator >=(BigInteger x, BigInteger y) {
 916    return Compare(x, y) > 0;
 917  }
 918
 919
 920  // Quotient and remainder (private)
 921
 922  public static void QuotientRemainder(BigInteger x, BigInteger y, out BigInteger q, out BigInteger r) {
 923 #if BIGINTEGER_DEBUG
 924    Debug.Assert(x.sane());
 925    Debug.Assert(y.sane());
 926 #endif
 927
 928    if (y.sign == 0) {
 929      throw(new System.DivideByZeroException());
 930    }
 931
 932    if (x.sign == 0) {
 933      q = new BigInteger();
 934      r = new BigInteger();
 935      q.used = r.used = q.sign = r.sign = 0;
 936 #if BIGINTEGER_DEBUG
 937      Debug.Assert(q.sane());
 938      Debug.Assert(r.sane());
 939 #endif
 940      return;
 941    }
 942
 943    uqrm(x, y, out q, out r);
 944    if (x.sign != y.sign && q.sign != 0) {
 945      q.sign = -1;
 946    }
 947    if (x.sign == -1 && r.sign != 0) {
 948      r.sign = -1;
 949    }
 950
 951 #if BIGINTEGER_DEBUG
 952    Debug.Assert(q.sane());
 953    Debug.Assert(r.sane());
 954 #endif
 955  }
 956
 957
 958  // Unsigned ops (private)
 959
 960  static int ucmp(BigInteger x, BigInteger y) {
 961    int i;
 962 #if BIGINTEGER_DEBUG
 963    Debug.Assert(x.sane());
 964    Debug.Assert(y.sane());
 965 #endif
 966    if (x.used < y.used) {
 967      return -1;
 968    }
 969    if (x.used > y.used) {
 970      return 1;
 971    }
 972    for (i = x.used-1; i >= 0; i--) {
 973      if (x.body[i] < y.body[i]) {
 974        return -1;
 975      }
 976      if (x.body[i] > y.body[i]) {
 977        return 1;
 978      }
 979    }
 980    return 0;
 981  }
 982
 983  static void uadd ( BigInteger x, BigInteger y, BigInteger res ) {
 984    int c, i, t, n;
 985    BigInteger longer;
 986
 987 #if BIGINTEGER_DEBUG
 988    Debug.Assert(x.sane());
 989    Debug.Assert(y.sane());
 990    Debug.Assert (res.size == maxused_addsub(x,y));
 991 #endif
 992    res.used = res.size;
 993    res.body[res.used-1] = 0;
 994
 995    if (x.used > y.used) {
 996      n = y.used;
 997      longer = x;
 998    }
 999    else {
1000      n = x.used;
1001      longer = y;
1002    }
1003
1004    c = 0;
1005    for (i = 0; i < n; i++) {
1006      t = x.body[i] + y.body[i] + c;
1007      if (t >= B_BASE) {
1008        res.body[i] = (byte)(t-B_BASE);
1009        c = 1;
1010      }
1011      else {
1012        res.body[i] = (byte)t;
1013        c = 0;
1014      }
1015    }
1016
1017    for (i = n; i < longer.used; i++) {
1018      t = longer.body[i] + c;
1019      if (t >= B_BASE) {
1020        res.body[i] = (byte)(t-B_BASE);
1021      }
1022      else {
1023        res.body[i] = (byte)t;
1024        c = 0;
1025      }
1026    }
1027    if (c > 0) {
1028 #if BIGINTEGER_DEBUG
1029      Debug.Assert(res.used == longer.used+1);
1030 #endif
1031      res.body[longer.used] = (byte)c;
1032    }
1033
1034    res.u_renormalise();
1035 #if BIGINTEGER_DEBUG
1036    Debug.Assert(res.sane());
1037 #endif
1038  }
1039
1040  static void usub(BigInteger x, BigInteger y, BigInteger res) {
1041 #if BIGINTEGER_DEBUG
1042    Debug.Assert(x.sane());
1043    Debug.Assert(y.sane());
1044    Debug.Assert(x.used >= y.used);
1045    Debug.Assert(res.size == maxused_addsub(x,y));
1046 #endif
1047
1048    int b, i, t;
1049
1050    b = 0;
1051    for (i = 0; i < y.used; i++) {
1052      t = x.body[i] - y.body[i] - b;
1053      if (t < 0) {
1054        res.body[i] = (byte)(t + B_BASE);
1055        b = 1;
1056      }
1057      else {
1058        res.body[i] = (byte)t;
1059        b = 0;
1060      }
1061    }
1062
1063    for (i = y.used; i < x.used; i++) {
1064      t = x.body[i] - b;
1065      if (t < 0) {
1066        res.body[i] = (byte)(t + B_BASE);
1067      }
1068      else {
1069        res.body[i] = (byte)t;
1070        b = 0;
1071      }
1072    }
1073 #if BIGINTEGER_DEBUG
1074    Debug.Assert (b == 0);
1075 #endif
1076
1077    res.used = x.used;
1078    res.u_renormalise();
1079 #if BIGINTEGER_DEBUG
1080    Debug.Assert(res.sane());
1081 #endif
1082  }
1083
1084  static void umul(BigInteger x, BigInteger y, BigInteger res) {
1085    int i, j, carry;
1086
1087 #if BIGINTEGER_DEBUG
1088    Debug.Assert(x.sane());
1089    Debug.Assert(y.sane());
1090    Debug.Assert(res.size == maxused_mul(x,y));
1091 #endif
1092
1093    for (j = 0; j < y.used; j++) {
1094      res.body[j] = 0;
1095    }
1096
1097    for (i = 0; i < x.used; i++) {
1098      carry = 0;
1099      for (j = 0; j < y.used; j++) {
1100        carry += res.body[i+j] + x.body[i]*y.body[j];
1101        res.body[i+j] = (byte)(carry % B_BASE);
1102        carry /= B_BASE;
1103 #if BIGINTEGER_DEBUG
1104        Debug.Assert (carry < B_BASE);
1105 #endif
1106      }
1107      res.body[i+y.used] = (byte)carry;
1108    }
1109
1110    res.used = x.used+y.used;
1111    res.u_renormalise();
1112 #if BIGINTEGER_DEBUG
1113    Debug.Assert(res.sane());
1114 #endif
1115  }
1116
1117  static void uqrm(BigInteger dend, BigInteger isor, out BigInteger dres, out BigInteger mres) {
1118    int i, j, t, vh, delta, carry, scaleup;
1119    byte [] dend_body, isor_body, tmp;
1120    bool toolarge;
1121
1122 #if BIGINTEGER_DEBUG
1123    Debug.Assert(isor.sane());
1124    Debug.Assert(dend.sane());
1125    Debug.Assert(isor.used > 0);  // against division by zero
1126 #endif
1127    dres = new BigInteger();
1128    mres = new BigInteger();
1129    mres.size = dres.size = maxused_qrm(isor, dend);
1130    dres.body = new byte[dres.size];
1131    mres.body = new byte[mres.size];
1132
1133    if (dend.used < isor.used) {
1134      // Result of division must be zero, since dividend has
1135      // fewer digits than the divisor.  Remainder is the
1136      // original dividend.
1137      dres.used = 0;
1138      mres.used = dend.used;
1139      for (j = 0; j < mres.used; j++) {
1140        mres.body[j] = dend.body[j];
1141      }
1142      dres.u_renormalise();
1143      mres.u_renormalise();
1144 #if BIGINTEGER_DEBUG
1145      Debug.Assert(dres.sane());
1146      Debug.Assert(mres.sane());
1147 #endif
1148      return;
1149    }
1150
1151    if (isor.used == 1) {
1152
1153      // Simple case; divisor is a single digit
1154      carry = 0;
1155      for (j = dend.used-1; j >= 0; j--) {
1156        carry += dend.body[j];
1157        dres.body[j] = (byte)(carry/isor.body[0]);
1158        carry = B_BASE*(carry%isor.body[0]);
1159      }
1160      carry /= B_BASE;
1161      dres.used = dend.used;
1162      dres.u_renormalise();
1163
1164      // Remainder is the final carry value
1165      mres.used = 0;
1166      if (carry > 0) {
1167        mres.used = 1;
1168        mres.body[0] = (byte)carry;
1169      }
1170      dres.u_renormalise();
1171      mres.u_renormalise();
1172 #if BIGINTEGER_DEBUG
1173      Debug.Assert(dres.sane());
1174      Debug.Assert(mres.sane());
1175 #endif
1176      return;
1177
1178    }
1179    else {
1180
1181      // Complex case: both dividend and divisor have two or more digits.
1182 #if BIGINTEGER_DEBUG
1183      Debug.Assert(isor.used >= 2);
1184      Debug.Assert(dend.used >= 2);
1185 #endif
1186
1187      // Allocate space for a copy of both dividend and divisor, since we
1188      // need to mess with them.  Also allocate tmp as a place to hold
1189      // values of the form   quotient_digit * divisor.
1190      dend_body = new byte[dend.used+1];
1191      isor_body = new byte[isor.used];
1192      tmp       = new byte[isor.used+1];
1193
1194      // Calculate a scaling-up factor, and multiply both divisor and
1195      // dividend by it.  Doing this reduces the number of corrections
1196      // needed to the quotient-digit-estimates made in the loop below,
1197      // and thus speeds up division, but is not actually needed to
1198      // get the correct results.  The scaleup factor should not increase
1199      // the number of digits needed to represent either the divisor
1200      // (since the factor is derived from it) or the dividend (since
1201      // we already gave it a new leading zero).
1202      scaleup = B_BASE / (1 + isor.body[isor.used-1]);
1203 #if BIGINTEGER_DEBUG
1204      Debug.Assert (1 <= scaleup && scaleup <= B_BASE/2);
1205 #endif
1206
1207      if (scaleup == 1) {
1208        // Don't bother to multiply; just copy.
1209        for (j = 0; j < dend.used; j++) {
1210          dend_body[j] = dend.body[j];
1211        }
1212        for (j = 0; j < isor.used; j++) {
1213          isor_body[j] = isor.body[j];
1214        }
1215
1216        // Extend dividend with leading zero.
1217        dend_body[dend.used] = tmp[isor.used] = 0;
1218
1219      }
1220      else {
1221        carry = 0;
1222        for (j = 0; j < isor.used; j++) {
1223          t = scaleup * isor.body[j] + carry;
1224          isor_body[j] = (byte)(t % B_BASE);
1225          carry = t / B_BASE;
1226        }
1227 #if BIGINTEGER_DEBUG
1228        Debug.Assert (carry == 0);
1229 #endif
1230
1231        carry = 0;
1232        for (j = 0; j < dend.used; j++) {
1233          t = scaleup * dend.body[j] + carry;
1234          dend_body[j] = (byte)(t % B_BASE);
1235          carry = t / B_BASE;
1236        }
1237        dend_body[dend.used] = (byte)carry;
1238        tmp[isor.used] = 0;
1239      }
1240
1241      // For each quotient digit ...
1242      for (i = dend.used; i >= isor.used; i--) {
1243 #if BIGINTEGER_DEBUG
1244        Debug.Assert (i-2 >= 0);
1245        Debug.Assert (i <= dend.used);
1246        Debug.Assert (isor.used >= 2);
1247 #endif
1248
1249 #if BIGINTEGER_DEBUG
1250        Console.WriteLine("\n---------\nqdigit {0}", i );
1251        Console.Write("dend_body is ");
1252        for (j = dend.used; j>= 0; j--) {
1253          Console.Write("{0} ",dend_body[j]);
1254        }
1255        Console.Write("\n");
1256 #endif
1257        // Make a guess vh of the quotient digit
1258        vh = (B_BASE*B_BASE*dend_body[i] + B_BASE*dend_body[i-1] + dend_body[i-2])
1259        /
1260        (B_BASE*isor_body[isor.used-1] + isor_body[isor.used-2]);
1261        if (vh > B_BASE-1) {
1262          vh = B_BASE-1;
1263        }
1264 #if BIGINTEGER_DEBUG
1265        Console.WriteLine("guess formed from {0} {1} {2}   {3} {4}",
1266               dend_body[i], dend_body[i-1] , dend_body[i-2],
1267               isor_body[isor.used-1], isor_body[isor.used-2]);
1268        Console.WriteLine("guess is {0}", vh );
1269 #endif
1270        // Check if vh is too large (by 1).  Calculate vh * isor into tmp
1271        // and see if it exceeds the same length prefix of dend.  If so,
1272        // vh needs to be decremented.
1273        carry = 0;
1274        for (j = 0; j < isor.used; j++) {
1275          t = vh * isor_body[j] + carry;
1276          tmp[j] = (byte)(t % B_BASE);
1277          carry = t / B_BASE;
1278        }
1279        tmp[isor.used] = (byte)carry;
1280        delta = i - isor.used;
1281 #if BIGINTEGER_DEBUG
1282        Console.WriteLine("final carry is {0}", carry);
1283        Console.Write("vh * isor is " );
1284        for (j = isor.used; j >=0; j--) {
1285          Console.Write("{0} ",tmp[j]);Console.Write("\n");
1286        }
1287        Console.WriteLine("delta = {0}", delta );
1288 #endif
1289        toolarge = false;
1290        for (j = isor.used; j >= 0; j--) {
1291 #if BIGINTEGER_DEBUG
1292          Console.Write ( "({0},{1})  ", (int)(tmp[j]), (int)(dend_body[j+delta]) );
1293 #endif
1294          if (tmp[j] > dend_body[j+delta]) {
1295            toolarge=true;
1296            break;
1297          }
1298          if (tmp[j] < dend_body[j+delta]) {
1299            break;
1300          }
1301        }
1302
1303        // If we did guess too large, decrement vh and subtract a copy of
1304        // isor from tmp.  This had better not go negative!
1305        if (toolarge) {
1306 #if BIGINTEGER_DEBUG
1307          Console.WriteLine ( "guess too large" );
1308 #endif
1309          vh--;
1310          carry = 0;
1311          for (j = 0; j < isor.used; j++) {
1312            if (carry + isor_body[j] > tmp[j]) {
1313              tmp[j] = (byte)((B_BASE + tmp[j]) - isor_body[j] - carry);
1314              carry = 1;
1315            }
1316            else {
1317              tmp[j] = (byte)(tmp[j] - isor_body[j] - carry);
1318              carry = 0;
1319            }
1320          }
1321          //if (carry > 0) {pp(isor);pp(dend);};
1322          //Debug.Assert(carry == 0);
1323          if (carry > 0) {
1324            Debug.Assert(tmp[isor.used] > 0);
1325            tmp[isor.used]--;
1326          }
1327 #if BIGINTEGER_DEBUG
1328          Console.Write("after adjustment of tmp ");
1329          for (j = isor.used; j >=0; j--) {
1330            Console.Write("{0} ",tmp[j]);
1331          }
1332          Console.Write("\n");
1333 #endif
1334        }
1335
1336        // Now vh really is the i'th quotient digit.
1337        // Subtract (tmp << delta) from
1338        // the dividend.
1339        carry = 0;
1340        for (j = 0; j <= isor.used; j++) {
1341          if (carry + tmp[j] > dend_body[j+delta]) {
1342            dend_body[j+delta] = (byte)((B_BASE+dend_body[j+delta]) - tmp[j]
1343                                        - carry);
1344            carry = 1;
1345          }
1346          else {
1347            dend_body[j+delta] = (byte)(dend_body[j+delta] - tmp[j] - carry);
1348            carry = 0;
1349          }
1350        }
1351 #if BIGINTEGER_DEBUG
1352        Debug.Assert(carry==0);
1353 #endif
1354
1355 #if BIGINTEGER_DEBUG
1356        Console.Write("after final sub ");
1357        for(j=dend.used; j>=0; j--) Console.Write("{0} ", dend_body[j]);
1358        Console.Write("\n");
1359 #endif
1360
1361        // park vh in the result array
1362 #if DEBUG_SAINTEGER_UDIV
1363        Console.WriteLine("[{0}] <- {1}", i-isor.used, vh );
1364 #endif
1365        dres.body[i-isor.used] = (byte)vh;
1366      }
1367    }
1368
1369    // Now we've got all the quotient digits.  Zap leading zeroes.
1370    dres.used = dend.used - isor.used + 1;
1371    dres.u_renormalise();
1372 #if BIGINTEGER_DEBUG
1373    Debug.Assert(dres.sane());
1374 #endif
1375
1376    // The remainder is in dend_body.  Copy, divide by the original scaling
1377    // factor, and zap leading zeroes.
1378    mres.used = dend.used;
1379    for (j = 0; j < dend.used; j++) {
1380      mres.body[j] = dend_body[j];
1381    }
1382    mres.u_renormalise();
1383 #if BIGINTEGER_DEBUG
1384    Debug.Assert(mres.sane());
1385 #endif
1386
1387    if (scaleup > 1) {
1388      carry = 0;
1389      for (j = mres.used-1; j >= 0; j--) {
1390        carry += mres.body[j];
1391        mres.body[j] = (byte)(carry/scaleup);
1392        carry = B_BASE*(carry%scaleup);
1393      }
1394 #if BIGINTEGER_DEBUG
1395      Debug.Assert (carry == 0);
1396 #endif
1397      mres.u_renormalise();
1398 #if BIGINTEGER_DEBUG
1399      Debug.Assert(mres.sane());
1400 #endif
1401    }
1402
1403  }
1404
1405
1406  // Test framework
1407
1408 #if BIGINTEGER_DEBUG
1409  public static void Test ( ) {
1410    int i, j, t, k, m;
1411    BigInteger bi, bj, bk, bm;
1412
1413    BigInteger a, b;
1414    a = new BigInteger(1);
1415    for (int n = 1; n <= 10; n++) {
1416      b = new BigInteger(n);
1417      a *= n;
1418    }
1419    Console.WriteLine("{0}", (double)a);
1420
1421    for (i = -10007; i <= 10007; i++) {
1422      Console.WriteLine ( "i = {0}", i );
1423
1424      bi = new BigInteger(i);
1425      t = (int)bi;
1426      Debug.Assert(i == t);
1427
1428      for (j = -10007; j <= 10007; j++) {
1429        bj = new BigInteger(j);
1430        t = (int)bj;
1431        Debug.Assert(j == t);
1432        bk = bi + bj;
1433        k = (int)bk;
1434        if (i+j != k) {
1435          bi.ToString();
1436          bj.ToString();
1437          bk.ToString();
1438          Debug.Assert(i + j == k);
1439        }
1440
1441        bk = bi - bj;
1442        k = (int)bk;
1443        if (i-j != k) {
1444          bi.ToString();
1445          bj.ToString();
1446          bk.ToString();
1447          Debug.Assert(i - j == k);
1448        }
1449
1450        bk = bi * bj;
1451        k = (int)bk;
1452        if (i*j != k) {
1453          bi.ToString();
1454          bj.ToString();
1455          bk.ToString();
1456          Debug.Assert(i * j == k);
1457        }
1458
1459        if (j != 0) {
1460          QuotientRemainder(bi, bj, out bk, out bm);
1461          k = (int)bk;
1462          m = (int)bm;
1463          Debug.Assert(k == i / j);
1464          Debug.Assert(m == i % j);
1465        }
1466      }
1467    }
1468    Console.WriteLine("done");
1469  }
1470 #endif
1471
1472 }