--- /dev/null
+// Big Integer class for .NET
+// (c) The GHC Team 2001
+
+// TODO:
+// Constructors from Single, Double, Currency, String
+//
+
+using System;
+using System.Diagnostics;
+
+public class BigInteger : IComparable, IConvertible, IFormattable {
+
+ int sign;
+ int size;
+ int used;
+ byte[] body;
+
+ const int B_BASE = 256;
+ const double B_BASE_FLT = 256.0;
+
+
+ // Constructors
+
+ public BigInteger() {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(this.sane());
+#endif
+ }
+
+ public BigInteger(Int32 n) {
+ this.size = 4;
+ this.body = new byte[this.size];
+ this.sign = this.used = 0;
+ if (n == 0) {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(this.sane());
+#endif
+ return;
+ }
+ if (n < 0) {
+ this.sign = -1;
+ }
+ else {
+ this.sign = 1;
+ }
+ if (n < 0) {
+ n = -n;
+ }
+ while (n != 0) {
+ this.body[this.used] = (byte)(n % B_BASE);
+ n /= B_BASE;
+ this.used++;
+ }
+#if BIGINTEGER_DEBUG
+ Debug.Assert(this.sane());
+#endif
+ }
+
+ public BigInteger(UInt32 n) {
+ this.size = 4;
+ this.body = new byte[this.size];
+ this.sign = this.used = 0;
+ if (n == 0) {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(this.sane());
+#endif
+ return;
+ }
+ this.sign = 1;
+ while (n != 0) {
+ this.body[this.used] = (byte)(n % B_BASE);
+ n /= B_BASE;
+ this.used++;
+ }
+#if BIGINTEGER_DEBUG
+ Debug.Assert(this.sane());
+#endif
+ }
+
+ public BigInteger(Int64 n) {
+ this.size = 8;
+ this.body = new byte[this.size];
+ this.sign = this.used = 0;
+ if (n == 0) {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(this.sane());
+#endif
+ return;
+ }
+ if (n < 0) {
+ this.sign = -1;
+ }
+ else {
+ this.sign = 1;
+ }
+ if (n < 0) {
+ n = -n;
+ }
+ while (n != 0) {
+ this.body[this.used] = (byte)(n % B_BASE);
+ n /= B_BASE;
+ this.used++;
+ }
+#if BIGINTEGER_DEBUG
+ Debug.Assert(this.sane());
+#endif
+ }
+
+ public BigInteger(UInt64 n) {
+ this.size = 8;
+ this.body = new byte[this.size];
+ this.sign = this.used = 0;
+ if (n == 0) {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(this.sane());
+#endif
+ return;
+ }
+ this.sign = 1;
+ while (n != 0) {
+ this.body[this.used] = (byte)(n % B_BASE);
+ n /= B_BASE;
+ this.used++;
+ }
+#if BIGINTEGER_DEBUG
+ Debug.Assert(this.sane());
+#endif
+ }
+
+ // NOTE: This only works currectly if B_BASE >= 10
+ // TODO: Turn this into a Parse method taking a String
+ public BigInteger (char [] str) {
+ int sign, d, t, i, j, carry;
+
+ for (i = 0; str[i] != 0; i++) {
+ }
+ this.size = i;
+ this.body = new byte[this.size];
+ this.sign = this.used = 0;
+ sign = 1;
+ i = 0;
+ if (str[0] == '-') {
+ i++;
+ sign = -1;
+ }
+
+ while (Char.IsDigit(str[i])) {
+
+ // multiply this by 10
+ carry = 0;
+ for (j = 0; j < this.used; j++) {
+ t = 10 * this.body[j] + carry;
+ this.body[j] = (byte)(t % B_BASE);
+ carry = t / B_BASE;
+ }
+#if BIGINTEGER_DEBUG
+ Debug.Assert(carry < B_BASE);
+#endif
+ if (carry > 0) {
+ this.body[this.used++] = (byte)carry;
+ }
+ // add a digit on
+ d = str[i] - '0';
+ i++;
+
+ carry = d;
+ for (j = 0; j < this.used; j++) {
+ carry += this.body[j];
+ this.body[j] = (byte)(carry % B_BASE);
+ carry /= B_BASE;
+ if (carry == 0) {
+ break;
+ }
+ }
+ if (carry > 0) {
+ this.body[this.used++] = (byte)carry;
+ }
+ }
+
+ this.sign = sign;
+#if BIGINTEGER_DEBUG
+ Debug.Assert(this.sane());
+#endif
+ }
+
+
+ // Constants
+ static readonly BigInteger Zero = new BigInteger(0);
+ static readonly BigInteger One = new BigInteger(1);
+ static readonly BigInteger MinusOne = new BigInteger(-1);
+
+
+ // Conversions
+
+ // Implicit
+ public static implicit operator BigInteger(SByte n) {
+ return new BigInteger((Int32)n);
+ }
+
+ public static implicit operator BigInteger(Byte n) {
+ return new BigInteger((UInt32)n);
+ }
+
+ public static implicit operator BigInteger(Int16 n) {
+ return new BigInteger((Int32)n);
+ }
+
+ public static implicit operator BigInteger(UInt16 n) {
+ return new BigInteger((UInt32)n);
+ }
+
+ public static implicit operator BigInteger(Char n) {
+ return new BigInteger((Int32)n);
+ }
+
+ public static implicit operator BigInteger(Int32 n) {
+ return new BigInteger(n);
+ }
+
+ public static implicit operator BigInteger(UInt32 n) {
+ return new BigInteger(n);
+ }
+
+ public static implicit operator BigInteger(Int64 n) {
+ return new BigInteger(n);
+ }
+
+ public static implicit operator BigInteger(UInt64 n) {
+ return new BigInteger(n);
+ }
+
+ // Explicit
+
+ public static Boolean ToBoolean(BigInteger n) {
+ throw new InvalidCastException();
+ }
+
+ public static explicit operator Boolean(BigInteger n) {
+ return ToBoolean(n);
+ }
+
+ Boolean IConvertible.ToBoolean(IFormatProvider p) {
+ return ToBoolean(this);
+ }
+
+ public static DateTime ToDateTime(BigInteger n) {
+ throw new InvalidCastException();
+ }
+
+ DateTime IConvertible.ToDateTime(IFormatProvider p) {
+ return ToDateTime(this);
+ }
+
+ public static explicit operator DateTime(BigInteger n) {
+ return ToDateTime(n);
+ }
+
+ public static SByte ToSByte(BigInteger n) {
+ SByte res;
+ if (n.sign == 0) {
+ return 0;
+ }
+ res = 0;
+ if (n.used > 0) {
+ res = (SByte)n.body[0];
+ }
+ if (n.sign < 0) {
+ res = (SByte)(-res);
+ }
+ return res;
+ }
+
+ SByte IConvertible.ToSByte(IFormatProvider p) {
+ return ToSByte(this);
+ }
+
+ public static explicit operator SByte(BigInteger n) {
+ return ToSByte(n);
+ }
+
+ public static Byte ToByte(BigInteger n) {
+ Byte res;
+ if (n.sign == 0) {
+ return 0;
+ }
+ res = 0;
+ if (n.used > 0) {
+ res = (Byte)n.body[0];
+ }
+ return res;
+ }
+
+ Byte IConvertible.ToByte(IFormatProvider p) {
+ return ToByte(this);
+ }
+
+ public static explicit operator Byte(BigInteger n) {
+ return ToByte(n);
+ }
+
+ public static Int16 ToInt16(BigInteger n) {
+ int i, d;
+ Int16 res;
+ if (n.sign == 0) {
+ return 0;
+ }
+ res = 0;
+ for (i = n.used-1; i >= 0; i--) {
+ d = n.body[i];
+ res = (Int16)(res * B_BASE + d);
+ }
+ if (n.sign < 0) {
+ res = (Int16)(-res);
+ }
+ return res;
+ }
+
+ Int16 IConvertible.ToInt16(IFormatProvider p) {
+ return ToInt16(this);
+ }
+
+ public static explicit operator Int16(BigInteger n) {
+ return ToInt16(n);
+ }
+
+ public static UInt16 ToUInt16(BigInteger n) {
+ int i, d;
+ UInt16 res;
+ if (n.sign == 0) {
+ return 0;
+ }
+ res = 0;
+ for (i = n.used-1; i >= 0; i--) {
+ d = n.body[i];
+ res = (UInt16)(res * B_BASE + d);
+ }
+ return res;
+ }
+
+ UInt16 IConvertible.ToUInt16(IFormatProvider p) {
+ return ToUInt16(this);
+ }
+
+ public static explicit operator UInt16(BigInteger n) {
+ return ToUInt16(n);
+ }
+
+ public static Char ToChar(BigInteger n) {
+ throw new InvalidCastException();
+ }
+
+ Char IConvertible.ToChar(IFormatProvider p) {
+ return ToChar(this);
+ }
+
+ public static explicit operator Char(BigInteger n) {
+ return ToChar(n);
+ }
+
+ public static Int32 ToInt32(BigInteger n) {
+ int i, d;
+ Int32 res;
+ if (n.sign == 0) {
+ return 0;
+ }
+ res = 0;
+ for (i = n.used-1; i >= 0; i--) {
+ d = n.body[i];
+ res = res * B_BASE + d;
+ }
+ if (n.sign < 0) {
+ res = -res;
+ }
+ return res;
+ }
+
+ Int32 IConvertible.ToInt32(IFormatProvider p) {
+ return ToInt32(this);
+ }
+
+ public static explicit operator Int32(BigInteger n) {
+ return ToInt32(n);
+ }
+
+ public static UInt32 ToUInt32(BigInteger n) {
+ int i, d;
+ UInt32 res;
+ if (n.sign == 0) {
+ return 0;
+ }
+ res = 0;
+ for (i = n.used-1; i >= 0; i--) {
+ d = n.body[i];
+ res = res * B_BASE + (UInt32)d;
+ }
+ return res;
+ }
+
+ UInt32 IConvertible.ToUInt32(IFormatProvider p) {
+ return ToUInt32(this);
+ }
+
+ public static explicit operator UInt32(BigInteger n) {
+ return ToUInt32(n);
+ }
+
+ public static Int64 ToInt64(BigInteger n) {
+ int i, d;
+ Int64 res;
+ if (n.sign == 0) {
+ return 0;
+ }
+ res = 0;
+ for (i = n.used-1; i >= 0; i--) {
+ d = n.body[i];
+ res = res * B_BASE + d;
+ }
+ if (n.sign < 0) {
+ res = -res;
+ }
+ return res;
+ }
+
+ Int64 IConvertible.ToInt64(IFormatProvider p) {
+ return ToInt64(this);
+ }
+
+ public static explicit operator Int64(BigInteger n) {
+ return ToInt64(n);
+ }
+
+ public static UInt64 ToUInt64(BigInteger n) {
+ int i, d;
+ UInt64 res;
+ if (n.sign == 0) {
+ return 0;
+ }
+ res = 0;
+ for (i = n.used-1; i >= 0; i--) {
+ d = n.body[i];
+ res = res * B_BASE + (UInt64)d;
+ }
+ return res;
+ }
+
+ UInt64 IConvertible.ToUInt64(IFormatProvider p) {
+ return ToUInt64(this);
+ }
+
+ public static explicit operator UInt64(BigInteger n) {
+ return ToUInt64(n);
+ }
+
+ public static Decimal ToDecimal(BigInteger n) {
+ int i, d;
+ Decimal res;
+ if (n.sign == 0) {
+ return 0;
+ }
+ res = 0;
+ for (i = n.used-1; i >= 0; i--) {
+ d = n.body[i];
+ res = res * B_BASE + (Decimal)d;
+ }
+ return res;
+ }
+
+ Decimal IConvertible.ToDecimal(IFormatProvider p) {
+ return ToDecimal(this);
+ }
+
+ public static explicit operator Decimal(BigInteger n) {
+ return ToDecimal(n);
+ }
+
+ public static Single ToSingle(BigInteger n) {
+ int i, d;
+ Single res;
+ if (n.sign == 0) {
+ return 0.0F;
+ }
+ res = 0.0F;
+ for (i = n.used-1; i >= 0; i--) {
+ d = n.body[i];
+ res = res * (Single)B_BASE_FLT + d;
+ }
+ if (n.sign < 0) {
+ res = -res;
+ }
+ return res;
+ }
+
+ Single IConvertible.ToSingle(IFormatProvider p) {
+ return ToSingle(this);
+ }
+
+ public static explicit operator Single(BigInteger n) {
+ return ToSingle(n);
+ }
+
+ public static Double ToDouble(BigInteger n) {
+ int i, d;
+ Double res;
+ if (n.sign == 0) {
+ return 0.0;
+ }
+ res = 0.0;
+ for (i = n.used-1; i >= 0; i--) {
+ d = n.body[i];
+ res = res * B_BASE_FLT + d;
+ }
+ if (n.sign < 0) {
+ res = -res;
+ }
+ return res;
+ }
+
+ Double IConvertible.ToDouble(IFormatProvider p) {
+ return ToDouble(this);
+ }
+
+ public static explicit operator Double(BigInteger n) {
+ return ToDouble(n);
+ }
+
+ override public String ToString() {
+ int i;
+ Console.Write ( "sign={0} used={1} size={2} ", this.sign, this.used, this.size );
+ for (i = this.used-1; i >= 0; i--) {
+ Console.Write ( "{0} ", (int)(this.body[i]) );
+ }
+ Console.Write ( "\n" );
+ return "(some number or other)";
+ }
+
+ public String ToString(IFormatProvider p) {
+ return ToString(null, p);
+ }
+
+ public String ToString(String fmt) {
+ return this.ToString();
+ }
+
+ public String ToString(String fmt, IFormatProvider p) {
+ throw new InvalidCastException();
+ }
+
+ public Object ToType(Type ty, IFormatProvider n) {
+ throw new InvalidCastException();
+ }
+
+ // public object GetFormat(Type
+
+ public TypeCode GetTypeCode() {
+ return TypeCode.Int64;
+ }
+
+ // Basics
+
+ bool sane() {
+ if (this.sign == 0 && this.used != 0) {
+ return false;
+ }
+ if (this.sign != -1 && this.sign != 0 && this.sign != 1) {
+ return false;
+ }
+ if (this.used < 0) {
+ return false;
+ }
+ if (this.size < 0) {
+ return false;
+ }
+ if (this.used > this.size) {
+ return false;
+ }
+ if (this.used == 0) {
+ return true;
+ }
+ if (this.body[this.used-1] == 0) {
+ return false;
+ }
+ return true;
+ }
+
+ void u_renormalise() {
+ while (this.used > 0 && this.body[this.used-1] == 0) {
+ this.used--;
+ }
+ if (this.used == 0) {
+ this.sign = 0;
+ }
+ else {
+ this.sign = 1;
+ }
+ }
+
+
+ public void renormalise() {
+ while (this.used > 0 && this.body[this.used-1] == 0) {
+ this.used--;
+ }
+ if (this.used == 0) {
+ this.sign = 0;
+ }
+ }
+
+
+ // Size of things
+
+ static int maxused_addsub ( BigInteger x, BigInteger y ) {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(x.sane());
+ Debug.Assert(y.sane());
+#endif
+ return 1 + (x.used > y.used ? x.used : y.used);
+ }
+
+ static int maxused_mul ( BigInteger x, BigInteger y ) {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(x.sane());
+ Debug.Assert(y.sane());
+#endif
+ return x.used + y.used;
+ }
+
+ static int maxused_qrm ( BigInteger x, BigInteger y ) {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(x.sane());
+ Debug.Assert(y.sane());
+#endif
+ return (x.used > y.used ? x.used : y.used);
+ }
+
+ int maxused_neg() {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(this.sane());
+#endif
+ return this.used;
+ }
+
+
+ // Signed ops
+
+ // A helper for signed + and -. sdiff(x,y) ignores the signs of x and y
+ // sets p to the signed value abs(x)-abs(y).
+ static void sdiff(BigInteger x, BigInteger y, BigInteger res) {
+ int t;
+#if BIGINTEGER_DEBUG
+ Debug.Assert(x.sane());
+ Debug.Assert(y.sane());
+ Debug.Assert(res.size == maxused_addsub(x,y));
+#endif
+ t = ucmp(x,y);
+ if (t == 0) {
+ res.sign = res.used = 0;
+ return;
+ }
+ if (t == -1) {
+ // x < y
+ usub(y,x,res);
+ res.sign = -1;
+ }
+ else {
+ // x > y
+ usub(x,y,res);
+ res.sign = 1;
+ }
+#if BIGINTEGER_DEBUG
+ Debug.Assert(res.sane());
+#endif
+ }
+
+ public BigInteger Negate() {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(this.sane());
+#endif
+ BigInteger res = new BigInteger();
+ res.size = this.used;
+ res.body = new byte[res.used];
+ res.used = this.used;
+ for (int i = 0; i < this.used; i++) {
+ res.body[i] = this.body[i];
+ }
+ res.sign = -(this.sign);
+ return res;
+ }
+
+ public static BigInteger Add(BigInteger x, BigInteger y) {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(x.sane());
+ Debug.Assert(y.sane());
+#endif
+ BigInteger res = new BigInteger();
+ res.size = maxused_addsub(x, y);
+ res.used = res.sign = 0;
+
+ if ( (x.sign >= 0 && y.sign >= 0) ||
+ (x.sign < 0 && y.sign < 0)) {
+ // same sign; add magnitude and clone sign
+ uadd(x,y,res);
+ if (x.sign < 0 && res.sign != 0) {
+ res.sign = -1;
+ }
+ }
+ else {
+ // signs differ; use sdiff
+ if (x.sign >= 0 && y.sign < 0) {
+ sdiff(x,y,res);
+ }
+ else {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(x.sign < 0 && y.sign >= 0);
+#endif
+ sdiff(y,x,res);
+ }
+ }
+#if BIGINTEGER_DEBUG
+ Debug.Assert(res.sane());
+#endif
+ return res;
+ }
+
+ public BigInteger Increment() {
+ return this + 1;
+ }
+
+ public static BigInteger Sub(BigInteger x, BigInteger y) {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(x.sane());
+ Debug.Assert(y.sane());
+#endif
+ BigInteger res = new BigInteger();
+ res.size = maxused_addsub(x, y);
+ res.used = res.sign = 0;
+
+ if ( (x.sign >= 0 && y.sign < 0) ||
+ (x.sign < 0 && y.sign >= 0)) {
+ // opposite signs; add magnitudes and clone sign of x
+ uadd(x,y,res);
+#if BIGINTEGER_DEBUG
+ Debug.Assert(res.sign != 0);
+#endif
+ if (x.sign < 0) {
+ res.sign = -1;
+ }
+ }
+ else
+ // signs are the same; use sdiff
+ if (x.sign >= 0 && y.sign >= 0) {
+ sdiff(x,y,res);
+ }
+ else {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(x.sign < 0 && y.sign < 0);
+#endif
+ sdiff(y,x,res);
+ }
+#if BIGINTEGER_DEBUG
+ Debug.Assert(res.sane());
+#endif
+ return res;
+ }
+
+ public BigInteger Decrement() {
+ return this - 1;
+ }
+
+ public static BigInteger Multiply(BigInteger x, BigInteger y) {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(x.sane());
+ Debug.Assert(y.sane());
+#endif
+ BigInteger res = new BigInteger();
+ res.size = maxused_mul(x, y);
+ res.body = new byte[res.size];
+ res.used = res.sign = 0;
+
+ if (x.sign == 0 || y.sign == 0) {
+ res.sign = res.used = 0;
+#if BIGINTEGER_DEBUG
+ Debug.Assert(res.sane());
+#endif
+ return res;
+ }
+ umul(x,y,res);
+ if (x.sign != y.sign) {
+ res.sign = -1;
+ }
+#if BIGINTEGER_DEBUG
+ Debug.Assert(res.sane());
+#endif
+ return res;
+ }
+
+ public static BigInteger Divide(BigInteger x, BigInteger y) {
+ BigInteger q, r;
+ QuotientRemainder(x, y, out q, out r);
+ return q;
+ }
+
+ public static BigInteger Remainder(BigInteger x, BigInteger y) {
+ BigInteger q, r;
+ QuotientRemainder(x, y, out q, out r);
+ return r;
+ }
+
+ public static Int32 Compare(BigInteger x, BigInteger y) {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(x.sane());
+ Debug.Assert(y.sane());
+#endif
+ if (x.sign < y.sign) {
+ return -1;
+ }
+ if (x.sign > y.sign) {
+ return 1;
+ }
+#if BIGINTEGER_DEBUG
+ Debug.Assert(x.sign == y.sign);
+#endif
+ if (x.sign == 0) {
+ return 0;
+ }
+ if (x.sign == 1) {
+ return ucmp(x,y);
+ }
+ else {
+ return ucmp(y,x);
+ }
+ }
+
+ public Int32 CompareTo(Object o) {
+ return Compare(this, (BigInteger)o);
+ }
+
+ public static Boolean Equals(BigInteger x, BigInteger y) {
+ return Compare(x, y) == 0;
+ }
+
+ override public Boolean Equals(Object o) {
+ return this == (BigInteger)o;
+ }
+
+ override public Int32 GetHashCode() {
+ int i;
+ UInt32 h = 0;
+ for (i = 0; i < this.used; i++) {
+ h = (h << 4) + this.body[i];
+ UInt32 g = h & 0xf0000000;
+ if (g != 0) {
+ h ^= g >> 24;
+ h ^= g;
+ }
+ }
+ return (Int32)h;
+ }
+
+ // Overloaded operators
+
+ public static BigInteger operator +(BigInteger x) {
+ return x;
+ }
+
+ public static BigInteger operator -(BigInteger x) {
+ return x.Negate();
+ }
+
+ public static BigInteger operator +(BigInteger x, BigInteger y) {
+ return Add(x, y);
+ }
+
+ public static BigInteger operator -(BigInteger x, BigInteger y) {
+ return Sub(x, y);
+ }
+
+ public static BigInteger operator ++(BigInteger x) {
+ return x + 1;
+ }
+
+ public static BigInteger operator --(BigInteger x) {
+ return x - 1;
+ }
+
+ public static BigInteger operator *(BigInteger x, BigInteger y) {
+ return Multiply(x, y);
+ }
+
+ public static BigInteger operator /(BigInteger x, BigInteger y) {
+ return Divide(x, y);
+ }
+
+ public static BigInteger operator %(BigInteger x, BigInteger y) {
+ return Remainder(x, y);
+ }
+
+ public static Boolean operator ==(BigInteger x, BigInteger y) {
+ return Equals(x, y);
+ }
+
+ public static Boolean operator !=(BigInteger x, BigInteger y) {
+ return !Equals(x, y);
+ }
+ public static Boolean operator <(BigInteger x, BigInteger y) {
+ return Compare(x, y) == -1;
+ }
+
+ public static Boolean operator <=(BigInteger x, BigInteger y) {
+ return Compare(x, y) < 1;
+ }
+
+ public static Boolean operator >(BigInteger x, BigInteger y) {
+ return Compare(x, y) == 1;
+ }
+
+ public static Boolean operator >=(BigInteger x, BigInteger y) {
+ return Compare(x, y) > 0;
+ }
+
+
+ // Quotient and remainder (private)
+
+ public static void QuotientRemainder(BigInteger x, BigInteger y, out BigInteger q, out BigInteger r) {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(x.sane());
+ Debug.Assert(y.sane());
+#endif
+
+ if (y.sign == 0) {
+ throw(new System.DivideByZeroException());
+ }
+
+ if (x.sign == 0) {
+ q = new BigInteger();
+ r = new BigInteger();
+ q.used = r.used = q.sign = r.sign = 0;
+#if BIGINTEGER_DEBUG
+ Debug.Assert(q.sane());
+ Debug.Assert(r.sane());
+#endif
+ return;
+ }
+
+ uqrm(x, y, out q, out r);
+ if (x.sign != y.sign && q.sign != 0) {
+ q.sign = -1;
+ }
+ if (x.sign == -1 && r.sign != 0) {
+ r.sign = -1;
+ }
+
+#if BIGINTEGER_DEBUG
+ Debug.Assert(q.sane());
+ Debug.Assert(r.sane());
+#endif
+ }
+
+
+ // Unsigned ops (private)
+
+ static int ucmp(BigInteger x, BigInteger y) {
+ int i;
+#if BIGINTEGER_DEBUG
+ Debug.Assert(x.sane());
+ Debug.Assert(y.sane());
+#endif
+ if (x.used < y.used) {
+ return -1;
+ }
+ if (x.used > y.used) {
+ return 1;
+ }
+ for (i = x.used-1; i >= 0; i--) {
+ if (x.body[i] < y.body[i]) {
+ return -1;
+ }
+ if (x.body[i] > y.body[i]) {
+ return 1;
+ }
+ }
+ return 0;
+ }
+
+ static void uadd ( BigInteger x, BigInteger y, BigInteger res ) {
+ int c, i, t, n;
+ BigInteger longer;
+
+#if BIGINTEGER_DEBUG
+ Debug.Assert(x.sane());
+ Debug.Assert(y.sane());
+ Debug.Assert (res.size == maxused_addsub(x,y));
+#endif
+ res.used = res.size;
+ res.body[res.used-1] = 0;
+
+ if (x.used > y.used) {
+ n = y.used;
+ longer = x;
+ }
+ else {
+ n = x.used;
+ longer = y;
+ }
+
+ c = 0;
+ for (i = 0; i < n; i++) {
+ t = x.body[i] + y.body[i] + c;
+ if (t >= B_BASE) {
+ res.body[i] = (byte)(t-B_BASE);
+ c = 1;
+ }
+ else {
+ res.body[i] = (byte)t;
+ c = 0;
+ }
+ }
+
+ for (i = n; i < longer.used; i++) {
+ t = longer.body[i] + c;
+ if (t >= B_BASE) {
+ res.body[i] = (byte)(t-B_BASE);
+ }
+ else {
+ res.body[i] = (byte)t;
+ c = 0;
+ }
+ }
+ if (c > 0) {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(res.used == longer.used+1);
+#endif
+ res.body[longer.used] = (byte)c;
+ }
+
+ res.u_renormalise();
+#if BIGINTEGER_DEBUG
+ Debug.Assert(res.sane());
+#endif
+ }
+
+ static void usub(BigInteger x, BigInteger y, BigInteger res) {
+#if BIGINTEGER_DEBUG
+ Debug.Assert(x.sane());
+ Debug.Assert(y.sane());
+ Debug.Assert(x.used >= y.used);
+ Debug.Assert(res.size == maxused_addsub(x,y));
+#endif
+
+ int b, i, t;
+
+ b = 0;
+ for (i = 0; i < y.used; i++) {
+ t = x.body[i] - y.body[i] - b;
+ if (t < 0) {
+ res.body[i] = (byte)(t + B_BASE);
+ b = 1;
+ }
+ else {
+ res.body[i] = (byte)t;
+ b = 0;
+ }
+ }
+
+ for (i = y.used; i < x.used; i++) {
+ t = x.body[i] - b;
+ if (t < 0) {
+ res.body[i] = (byte)(t + B_BASE);
+ }
+ else {
+ res.body[i] = (byte)t;
+ b = 0;
+ }
+ }
+#if BIGINTEGER_DEBUG
+ Debug.Assert (b == 0);
+#endif
+
+ res.used = x.used;
+ res.u_renormalise();
+#if BIGINTEGER_DEBUG
+ Debug.Assert(res.sane());
+#endif
+ }
+
+ static void umul(BigInteger x, BigInteger y, BigInteger res) {
+ int i, j, carry;
+
+#if BIGINTEGER_DEBUG
+ Debug.Assert(x.sane());
+ Debug.Assert(y.sane());
+ Debug.Assert(res.size == maxused_mul(x,y));
+#endif
+
+ for (j = 0; j < y.used; j++) {
+ res.body[j] = 0;
+ }
+
+ for (i = 0; i < x.used; i++) {
+ carry = 0;
+ for (j = 0; j < y.used; j++) {
+ carry += res.body[i+j] + x.body[i]*y.body[j];
+ res.body[i+j] = (byte)(carry % B_BASE);
+ carry /= B_BASE;
+#if BIGINTEGER_DEBUG
+ Debug.Assert (carry < B_BASE);
+#endif
+ }
+ res.body[i+y.used] = (byte)carry;
+ }
+
+ res.used = x.used+y.used;
+ res.u_renormalise();
+#if BIGINTEGER_DEBUG
+ Debug.Assert(res.sane());
+#endif
+ }
+
+ static void uqrm(BigInteger dend, BigInteger isor, out BigInteger dres, out BigInteger mres) {
+ int i, j, t, vh, delta, carry, scaleup;
+ byte [] dend_body, isor_body, tmp;
+ bool toolarge;
+
+#if BIGINTEGER_DEBUG
+ Debug.Assert(isor.sane());
+ Debug.Assert(dend.sane());
+ Debug.Assert(isor.used > 0); // against division by zero
+#endif
+ dres = new BigInteger();
+ mres = new BigInteger();
+ mres.size = dres.size = maxused_qrm(isor, dend);
+ dres.body = new byte[dres.size];
+ mres.body = new byte[mres.size];
+
+ if (dend.used < isor.used) {
+ // Result of division must be zero, since dividend has
+ // fewer digits than the divisor. Remainder is the
+ // original dividend.
+ dres.used = 0;
+ mres.used = dend.used;
+ for (j = 0; j < mres.used; j++) {
+ mres.body[j] = dend.body[j];
+ }
+ dres.u_renormalise();
+ mres.u_renormalise();
+#if BIGINTEGER_DEBUG
+ Debug.Assert(dres.sane());
+ Debug.Assert(mres.sane());
+#endif
+ return;
+ }
+
+ if (isor.used == 1) {
+
+ // Simple case; divisor is a single digit
+ carry = 0;
+ for (j = dend.used-1; j >= 0; j--) {
+ carry += dend.body[j];
+ dres.body[j] = (byte)(carry/isor.body[0]);
+ carry = B_BASE*(carry%isor.body[0]);
+ }
+ carry /= B_BASE;
+ dres.used = dend.used;
+ dres.u_renormalise();
+
+ // Remainder is the final carry value
+ mres.used = 0;
+ if (carry > 0) {
+ mres.used = 1;
+ mres.body[0] = (byte)carry;
+ }
+ dres.u_renormalise();
+ mres.u_renormalise();
+#if BIGINTEGER_DEBUG
+ Debug.Assert(dres.sane());
+ Debug.Assert(mres.sane());
+#endif
+ return;
+
+ }
+ else {
+
+ // Complex case: both dividend and divisor have two or more digits.
+#if BIGINTEGER_DEBUG
+ Debug.Assert(isor.used >= 2);
+ Debug.Assert(dend.used >= 2);
+#endif
+
+ // Allocate space for a copy of both dividend and divisor, since we
+ // need to mess with them. Also allocate tmp as a place to hold
+ // values of the form quotient_digit * divisor.
+ dend_body = new byte[dend.used+1];
+ isor_body = new byte[isor.used];
+ tmp = new byte[isor.used+1];
+
+ // Calculate a scaling-up factor, and multiply both divisor and
+ // dividend by it. Doing this reduces the number of corrections
+ // needed to the quotient-digit-estimates made in the loop below,
+ // and thus speeds up division, but is not actually needed to
+ // get the correct results. The scaleup factor should not increase
+ // the number of digits needed to represent either the divisor
+ // (since the factor is derived from it) or the dividend (since
+ // we already gave it a new leading zero).
+ scaleup = B_BASE / (1 + isor.body[isor.used-1]);
+#if BIGINTEGER_DEBUG
+ Debug.Assert (1 <= scaleup && scaleup <= B_BASE/2);
+#endif
+
+ if (scaleup == 1) {
+ // Don't bother to multiply; just copy.
+ for (j = 0; j < dend.used; j++) {
+ dend_body[j] = dend.body[j];
+ }
+ for (j = 0; j < isor.used; j++) {
+ isor_body[j] = isor.body[j];
+ }
+
+ // Extend dividend with leading zero.
+ dend_body[dend.used] = tmp[isor.used] = 0;
+
+ }
+ else {
+ carry = 0;
+ for (j = 0; j < isor.used; j++) {
+ t = scaleup * isor.body[j] + carry;
+ isor_body[j] = (byte)(t % B_BASE);
+ carry = t / B_BASE;
+ }
+#if BIGINTEGER_DEBUG
+ Debug.Assert (carry == 0);
+#endif
+
+ carry = 0;
+ for (j = 0; j < dend.used; j++) {
+ t = scaleup * dend.body[j] + carry;
+ dend_body[j] = (byte)(t % B_BASE);
+ carry = t / B_BASE;
+ }
+ dend_body[dend.used] = (byte)carry;
+ tmp[isor.used] = 0;
+ }
+
+ // For each quotient digit ...
+ for (i = dend.used; i >= isor.used; i--) {
+#if BIGINTEGER_DEBUG
+ Debug.Assert (i-2 >= 0);
+ Debug.Assert (i <= dend.used);
+ Debug.Assert (isor.used >= 2);
+#endif
+
+#if BIGINTEGER_DEBUG
+ Console.WriteLine("\n---------\nqdigit {0}", i );
+ Console.Write("dend_body is ");
+ for (j = dend.used; j>= 0; j--) {
+ Console.Write("{0} ",dend_body[j]);
+ }
+ Console.Write("\n");
+#endif
+ // Make a guess vh of the quotient digit
+ vh = (B_BASE*B_BASE*dend_body[i] + B_BASE*dend_body[i-1] + dend_body[i-2])
+ /
+ (B_BASE*isor_body[isor.used-1] + isor_body[isor.used-2]);
+ if (vh > B_BASE-1) {
+ vh = B_BASE-1;
+ }
+#if BIGINTEGER_DEBUG
+ Console.WriteLine("guess formed from {0} {1} {2} {3} {4}",
+ dend_body[i], dend_body[i-1] , dend_body[i-2],
+ isor_body[isor.used-1], isor_body[isor.used-2]);
+ Console.WriteLine("guess is {0}", vh );
+#endif
+ // Check if vh is too large (by 1). Calculate vh * isor into tmp
+ // and see if it exceeds the same length prefix of dend. If so,
+ // vh needs to be decremented.
+ carry = 0;
+ for (j = 0; j < isor.used; j++) {
+ t = vh * isor_body[j] + carry;
+ tmp[j] = (byte)(t % B_BASE);
+ carry = t / B_BASE;
+ }
+ tmp[isor.used] = (byte)carry;
+ delta = i - isor.used;
+#if BIGINTEGER_DEBUG
+ Console.WriteLine("final carry is {0}", carry);
+ Console.Write("vh * isor is " );
+ for (j = isor.used; j >=0; j--) {
+ Console.Write("{0} ",tmp[j]);Console.Write("\n");
+ }
+ Console.WriteLine("delta = {0}", delta );
+#endif
+ toolarge = false;
+ for (j = isor.used; j >= 0; j--) {
+#if BIGINTEGER_DEBUG
+ Console.Write ( "({0},{1}) ", (int)(tmp[j]), (int)(dend_body[j+delta]) );
+#endif
+ if (tmp[j] > dend_body[j+delta]) {
+ toolarge=true;
+ break;
+ }
+ if (tmp[j] < dend_body[j+delta]) {
+ break;
+ }
+ }
+
+ // If we did guess too large, decrement vh and subtract a copy of
+ // isor from tmp. This had better not go negative!
+ if (toolarge) {
+#if BIGINTEGER_DEBUG
+ Console.WriteLine ( "guess too large" );
+#endif
+ vh--;
+ carry = 0;
+ for (j = 0; j < isor.used; j++) {
+ if (carry + isor_body[j] > tmp[j]) {
+ tmp[j] = (byte)((B_BASE + tmp[j]) - isor_body[j] - carry);
+ carry = 1;
+ }
+ else {
+ tmp[j] = (byte)(tmp[j] - isor_body[j] - carry);
+ carry = 0;
+ }
+ }
+ //if (carry > 0) {pp(isor);pp(dend);};
+ //Debug.Assert(carry == 0);
+ if (carry > 0) {
+ Debug.Assert(tmp[isor.used] > 0);
+ tmp[isor.used]--;
+ }
+#if BIGINTEGER_DEBUG
+ Console.Write("after adjustment of tmp ");
+ for (j = isor.used; j >=0; j--) {
+ Console.Write("{0} ",tmp[j]);
+ }
+ Console.Write("\n");
+#endif
+ }
+
+ // Now vh really is the i'th quotient digit.
+ // Subtract (tmp << delta) from
+ // the dividend.
+ carry = 0;
+ for (j = 0; j <= isor.used; j++) {
+ if (carry + tmp[j] > dend_body[j+delta]) {
+ dend_body[j+delta] = (byte)((B_BASE+dend_body[j+delta]) - tmp[j]
+ - carry);
+ carry = 1;
+ }
+ else {
+ dend_body[j+delta] = (byte)(dend_body[j+delta] - tmp[j] - carry);
+ carry = 0;
+ }
+ }
+#if BIGINTEGER_DEBUG
+ Debug.Assert(carry==0);
+#endif
+
+#if BIGINTEGER_DEBUG
+ Console.Write("after final sub ");
+ for(j=dend.used; j>=0; j--) Console.Write("{0} ", dend_body[j]);
+ Console.Write("\n");
+#endif
+
+ // park vh in the result array
+#if DEBUG_SAINTEGER_UDIV
+ Console.WriteLine("[{0}] <- {1}", i-isor.used, vh );
+#endif
+ dres.body[i-isor.used] = (byte)vh;
+ }
+ }
+
+ // Now we've got all the quotient digits. Zap leading zeroes.
+ dres.used = dend.used - isor.used + 1;
+ dres.u_renormalise();
+#if BIGINTEGER_DEBUG
+ Debug.Assert(dres.sane());
+#endif
+
+ // The remainder is in dend_body. Copy, divide by the original scaling
+ // factor, and zap leading zeroes.
+ mres.used = dend.used;
+ for (j = 0; j < dend.used; j++) {
+ mres.body[j] = dend_body[j];
+ }
+ mres.u_renormalise();
+#if BIGINTEGER_DEBUG
+ Debug.Assert(mres.sane());
+#endif
+
+ if (scaleup > 1) {
+ carry = 0;
+ for (j = mres.used-1; j >= 0; j--) {
+ carry += mres.body[j];
+ mres.body[j] = (byte)(carry/scaleup);
+ carry = B_BASE*(carry%scaleup);
+ }
+#if BIGINTEGER_DEBUG
+ Debug.Assert (carry == 0);
+#endif
+ mres.u_renormalise();
+#if BIGINTEGER_DEBUG
+ Debug.Assert(mres.sane());
+#endif
+ }
+
+ }
+
+
+ // Test framework
+
+#if BIGINTEGER_DEBUG
+ public static void Test ( ) {
+ int i, j, t, k, m;
+ BigInteger bi, bj, bk, bm;
+
+ BigInteger a, b;
+ a = new BigInteger(1);
+ for (int n = 1; n <= 10; n++) {
+ b = new BigInteger(n);
+ a *= n;
+ }
+ Console.WriteLine("{0}", (double)a);
+
+ for (i = -10007; i <= 10007; i++) {
+ Console.WriteLine ( "i = {0}", i );
+
+ bi = new BigInteger(i);
+ t = (int)bi;
+ Debug.Assert(i == t);
+
+ for (j = -10007; j <= 10007; j++) {
+ bj = new BigInteger(j);
+ t = (int)bj;
+ Debug.Assert(j == t);
+ bk = bi + bj;
+ k = (int)bk;
+ if (i+j != k) {
+ bi.ToString();
+ bj.ToString();
+ bk.ToString();
+ Debug.Assert(i + j == k);
+ }
+
+ bk = bi - bj;
+ k = (int)bk;
+ if (i-j != k) {
+ bi.ToString();
+ bj.ToString();
+ bk.ToString();
+ Debug.Assert(i - j == k);
+ }
+
+ bk = bi * bj;
+ k = (int)bk;
+ if (i*j != k) {
+ bi.ToString();
+ bj.ToString();
+ bk.ToString();
+ Debug.Assert(i * j == k);
+ }
+
+ if (j != 0) {
+ QuotientRemainder(bi, bj, out bk, out bm);
+ k = (int)bk;
+ m = (int)bm;
+ Debug.Assert(k == i / j);
+ Debug.Assert(m == i % j);
+ }
+ }
+ }
+ Console.WriteLine("done");
+ }
+#endif
+
+}
projects / ghc-hetmet.git / commitdiff