+++ /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 / blobdiff