1 // Big Integer class for .NET
2 // (c) The GHC Team 2001
5 // Constructors from Single, Double, Currency, String
9 using System.Diagnostics;
11 public class BigInteger : IComparable, IConvertible, IFormattable {
18 const int B_BASE = 256;
19 const double B_BASE_FLT = 256.0;
26 Debug.Assert(this.sane());
30 public BigInteger(Int32 n) {
32 this.body = new byte[this.size];
33 this.sign = this.used = 0;
36 Debug.Assert(this.sane());
50 this.body[this.used] = (byte)(n % B_BASE);
55 Debug.Assert(this.sane());
59 public BigInteger(UInt32 n) {
61 this.body = new byte[this.size];
62 this.sign = this.used = 0;
65 Debug.Assert(this.sane());
71 this.body[this.used] = (byte)(n % B_BASE);
76 Debug.Assert(this.sane());
80 public BigInteger(Int64 n) {
82 this.body = new byte[this.size];
83 this.sign = this.used = 0;
86 Debug.Assert(this.sane());
100 this.body[this.used] = (byte)(n % B_BASE);
105 Debug.Assert(this.sane());
109 public BigInteger(UInt64 n) {
111 this.body = new byte[this.size];
112 this.sign = this.used = 0;
115 Debug.Assert(this.sane());
121 this.body[this.used] = (byte)(n % B_BASE);
126 Debug.Assert(this.sane());
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;
135 for (i = 0; str[i] != 0; i++) {
138 this.body = new byte[this.size];
139 this.sign = this.used = 0;
147 while (Char.IsDigit(str[i])) {
149 // multiply this by 10
151 for (j = 0; j < this.used; j++) {
152 t = 10 * this.body[j] + carry;
153 this.body[j] = (byte)(t % B_BASE);
157 Debug.Assert(carry < B_BASE);
160 this.body[this.used++] = (byte)carry;
167 for (j = 0; j < this.used; j++) {
168 carry += this.body[j];
169 this.body[j] = (byte)(carry % B_BASE);
176 this.body[this.used++] = (byte)carry;
182 Debug.Assert(this.sane());
188 static readonly BigInteger Zero = new BigInteger(0);
189 static readonly BigInteger One = new BigInteger(1);
190 static readonly BigInteger MinusOne = new BigInteger(-1);
196 public static implicit operator BigInteger(SByte n) {
197 return new BigInteger((Int32)n);
200 public static implicit operator BigInteger(Byte n) {
201 return new BigInteger((UInt32)n);
204 public static implicit operator BigInteger(Int16 n) {
205 return new BigInteger((Int32)n);
208 public static implicit operator BigInteger(UInt16 n) {
209 return new BigInteger((UInt32)n);
212 public static implicit operator BigInteger(Char n) {
213 return new BigInteger((Int32)n);
216 public static implicit operator BigInteger(Int32 n) {
217 return new BigInteger(n);
220 public static implicit operator BigInteger(UInt32 n) {
221 return new BigInteger(n);
224 public static implicit operator BigInteger(Int64 n) {
225 return new BigInteger(n);
228 public static implicit operator BigInteger(UInt64 n) {
229 return new BigInteger(n);
234 public static Boolean ToBoolean(BigInteger n) {
235 throw new InvalidCastException();
238 public static explicit operator Boolean(BigInteger n) {
242 Boolean IConvertible.ToBoolean(IFormatProvider p) {
243 return ToBoolean(this);
246 public static DateTime ToDateTime(BigInteger n) {
247 throw new InvalidCastException();
250 DateTime IConvertible.ToDateTime(IFormatProvider p) {
251 return ToDateTime(this);
254 public static explicit operator DateTime(BigInteger n) {
255 return ToDateTime(n);
258 public static SByte ToSByte(BigInteger n) {
265 res = (SByte)n.body[0];
273 SByte IConvertible.ToSByte(IFormatProvider p) {
274 return ToSByte(this);
277 public static explicit operator SByte(BigInteger n) {
281 public static Byte ToByte(BigInteger n) {
288 res = (Byte)n.body[0];
293 Byte IConvertible.ToByte(IFormatProvider p) {
297 public static explicit operator Byte(BigInteger n) {
301 public static Int16 ToInt16(BigInteger n) {
308 for (i = n.used-1; i >= 0; i--) {
310 res = (Int16)(res * B_BASE + d);
318 Int16 IConvertible.ToInt16(IFormatProvider p) {
319 return ToInt16(this);
322 public static explicit operator Int16(BigInteger n) {
326 public static UInt16 ToUInt16(BigInteger n) {
333 for (i = n.used-1; i >= 0; i--) {
335 res = (UInt16)(res * B_BASE + d);
340 UInt16 IConvertible.ToUInt16(IFormatProvider p) {
341 return ToUInt16(this);
344 public static explicit operator UInt16(BigInteger n) {
348 public static Char ToChar(BigInteger n) {
349 throw new InvalidCastException();
352 Char IConvertible.ToChar(IFormatProvider p) {
356 public static explicit operator Char(BigInteger n) {
360 public static Int32 ToInt32(BigInteger n) {
367 for (i = n.used-1; i >= 0; i--) {
369 res = res * B_BASE + d;
377 Int32 IConvertible.ToInt32(IFormatProvider p) {
378 return ToInt32(this);
381 public static explicit operator Int32(BigInteger n) {
385 public static UInt32 ToUInt32(BigInteger n) {
392 for (i = n.used-1; i >= 0; i--) {
394 res = res * B_BASE + (UInt32)d;
399 UInt32 IConvertible.ToUInt32(IFormatProvider p) {
400 return ToUInt32(this);
403 public static explicit operator UInt32(BigInteger n) {
407 public static Int64 ToInt64(BigInteger n) {
414 for (i = n.used-1; i >= 0; i--) {
416 res = res * B_BASE + d;
424 Int64 IConvertible.ToInt64(IFormatProvider p) {
425 return ToInt64(this);
428 public static explicit operator Int64(BigInteger n) {
432 public static UInt64 ToUInt64(BigInteger n) {
439 for (i = n.used-1; i >= 0; i--) {
441 res = res * B_BASE + (UInt64)d;
446 UInt64 IConvertible.ToUInt64(IFormatProvider p) {
447 return ToUInt64(this);
450 public static explicit operator UInt64(BigInteger n) {
454 public static Decimal ToDecimal(BigInteger n) {
461 for (i = n.used-1; i >= 0; i--) {
463 res = res * B_BASE + (Decimal)d;
468 Decimal IConvertible.ToDecimal(IFormatProvider p) {
469 return ToDecimal(this);
472 public static explicit operator Decimal(BigInteger n) {
476 public static Single ToSingle(BigInteger n) {
483 for (i = n.used-1; i >= 0; i--) {
485 res = res * (Single)B_BASE_FLT + d;
493 Single IConvertible.ToSingle(IFormatProvider p) {
494 return ToSingle(this);
497 public static explicit operator Single(BigInteger n) {
501 public static Double ToDouble(BigInteger n) {
508 for (i = n.used-1; i >= 0; i--) {
510 res = res * B_BASE_FLT + d;
518 Double IConvertible.ToDouble(IFormatProvider p) {
519 return ToDouble(this);
522 public static explicit operator Double(BigInteger n) {
526 override public String ToString() {
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]) );
532 Console.Write ( "\n" );
533 return "(some number or other)";
536 public String ToString(IFormatProvider p) {
537 return ToString(null, p);
540 public String ToString(String fmt) {
541 return this.ToString();
544 public String ToString(String fmt, IFormatProvider p) {
545 throw new InvalidCastException();
548 public Object ToType(Type ty, IFormatProvider n) {
549 throw new InvalidCastException();
552 // public object GetFormat(Type
554 public TypeCode GetTypeCode() {
555 return TypeCode.Int64;
561 if (this.sign == 0 && this.used != 0) {
564 if (this.sign != -1 && this.sign != 0 && this.sign != 1) {
573 if (this.used > this.size) {
576 if (this.used == 0) {
579 if (this.body[this.used-1] == 0) {
585 void u_renormalise() {
586 while (this.used > 0 && this.body[this.used-1] == 0) {
589 if (this.used == 0) {
598 public void renormalise() {
599 while (this.used > 0 && this.body[this.used-1] == 0) {
602 if (this.used == 0) {
610 static int maxused_addsub ( BigInteger x, BigInteger y ) {
612 Debug.Assert(x.sane());
613 Debug.Assert(y.sane());
615 return 1 + (x.used > y.used ? x.used : y.used);
618 static int maxused_mul ( BigInteger x, BigInteger y ) {
620 Debug.Assert(x.sane());
621 Debug.Assert(y.sane());
623 return x.used + y.used;
626 static int maxused_qrm ( BigInteger x, BigInteger y ) {
628 Debug.Assert(x.sane());
629 Debug.Assert(y.sane());
631 return (x.used > y.used ? x.used : y.used);
636 Debug.Assert(this.sane());
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) {
649 Debug.Assert(x.sane());
650 Debug.Assert(y.sane());
651 Debug.Assert(res.size == maxused_addsub(x,y));
655 res.sign = res.used = 0;
669 Debug.Assert(res.sane());
673 public BigInteger Negate() {
675 Debug.Assert(this.sane());
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];
684 res.sign = -(this.sign);
688 public static BigInteger Add(BigInteger x, BigInteger y) {
690 Debug.Assert(x.sane());
691 Debug.Assert(y.sane());
693 BigInteger res = new BigInteger();
694 res.size = maxused_addsub(x, y);
695 res.used = res.sign = 0;
697 if ( (x.sign >= 0 && y.sign >= 0) ||
698 (x.sign < 0 && y.sign < 0)) {
699 // same sign; add magnitude and clone sign
701 if (x.sign < 0 && res.sign != 0) {
706 // signs differ; use sdiff
707 if (x.sign >= 0 && y.sign < 0) {
712 Debug.Assert(x.sign < 0 && y.sign >= 0);
718 Debug.Assert(res.sane());
723 public BigInteger Increment() {
727 public static BigInteger Sub(BigInteger x, BigInteger y) {
729 Debug.Assert(x.sane());
730 Debug.Assert(y.sane());
732 BigInteger res = new BigInteger();
733 res.size = maxused_addsub(x, y);
734 res.used = res.sign = 0;
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
741 Debug.Assert(res.sign != 0);
748 // signs are the same; use sdiff
749 if (x.sign >= 0 && y.sign >= 0) {
754 Debug.Assert(x.sign < 0 && y.sign < 0);
759 Debug.Assert(res.sane());
764 public BigInteger Decrement() {
768 public static BigInteger Multiply(BigInteger x, BigInteger y) {
770 Debug.Assert(x.sane());
771 Debug.Assert(y.sane());
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;
778 if (x.sign == 0 || y.sign == 0) {
779 res.sign = res.used = 0;
781 Debug.Assert(res.sane());
786 if (x.sign != y.sign) {
790 Debug.Assert(res.sane());
795 public static BigInteger Divide(BigInteger x, BigInteger y) {
797 QuotientRemainder(x, y, out q, out r);
801 public static BigInteger Remainder(BigInteger x, BigInteger y) {
803 QuotientRemainder(x, y, out q, out r);
807 public static Int32 Compare(BigInteger x, BigInteger y) {
809 Debug.Assert(x.sane());
810 Debug.Assert(y.sane());
812 if (x.sign < y.sign) {
815 if (x.sign > y.sign) {
819 Debug.Assert(x.sign == y.sign);
832 public Int32 CompareTo(Object o) {
833 return Compare(this, (BigInteger)o);
836 public static Boolean Equals(BigInteger x, BigInteger y) {
837 return Compare(x, y) == 0;
840 override public Boolean Equals(Object o) {
841 return this == (BigInteger)o;
844 override public Int32 GetHashCode() {
847 for (i = 0; i < this.used; i++) {
848 h = (h << 4) + this.body[i];
849 UInt32 g = h & 0xf0000000;
858 // Overloaded operators
860 public static BigInteger operator +(BigInteger x) {
864 public static BigInteger operator -(BigInteger x) {
868 public static BigInteger operator +(BigInteger x, BigInteger y) {
872 public static BigInteger operator -(BigInteger x, BigInteger y) {
876 public static BigInteger operator ++(BigInteger x) {
880 public static BigInteger operator --(BigInteger x) {
884 public static BigInteger operator *(BigInteger x, BigInteger y) {
885 return Multiply(x, y);
888 public static BigInteger operator /(BigInteger x, BigInteger y) {
892 public static BigInteger operator %(BigInteger x, BigInteger y) {
893 return Remainder(x, y);
896 public static Boolean operator ==(BigInteger x, BigInteger y) {
900 public static Boolean operator !=(BigInteger x, BigInteger y) {
901 return !Equals(x, y);
903 public static Boolean operator <(BigInteger x, BigInteger y) {
904 return Compare(x, y) == -1;
907 public static Boolean operator <=(BigInteger x, BigInteger y) {
908 return Compare(x, y) < 1;
911 public static Boolean operator >(BigInteger x, BigInteger y) {
912 return Compare(x, y) == 1;
915 public static Boolean operator >=(BigInteger x, BigInteger y) {
916 return Compare(x, y) > 0;
920 // Quotient and remainder (private)
922 public static void QuotientRemainder(BigInteger x, BigInteger y, out BigInteger q, out BigInteger r) {
924 Debug.Assert(x.sane());
925 Debug.Assert(y.sane());
929 throw(new System.DivideByZeroException());
933 q = new BigInteger();
934 r = new BigInteger();
935 q.used = r.used = q.sign = r.sign = 0;
937 Debug.Assert(q.sane());
938 Debug.Assert(r.sane());
943 uqrm(x, y, out q, out r);
944 if (x.sign != y.sign && q.sign != 0) {
947 if (x.sign == -1 && r.sign != 0) {
952 Debug.Assert(q.sane());
953 Debug.Assert(r.sane());
958 // Unsigned ops (private)
960 static int ucmp(BigInteger x, BigInteger y) {
963 Debug.Assert(x.sane());
964 Debug.Assert(y.sane());
966 if (x.used < y.used) {
969 if (x.used > y.used) {
972 for (i = x.used-1; i >= 0; i--) {
973 if (x.body[i] < y.body[i]) {
976 if (x.body[i] > y.body[i]) {
983 static void uadd ( BigInteger x, BigInteger y, BigInteger res ) {
988 Debug.Assert(x.sane());
989 Debug.Assert(y.sane());
990 Debug.Assert (res.size == maxused_addsub(x,y));
993 res.body[res.used-1] = 0;
995 if (x.used > y.used) {
1005 for (i = 0; i < n; i++) {
1006 t = x.body[i] + y.body[i] + c;
1008 res.body[i] = (byte)(t-B_BASE);
1012 res.body[i] = (byte)t;
1017 for (i = n; i < longer.used; i++) {
1018 t = longer.body[i] + c;
1020 res.body[i] = (byte)(t-B_BASE);
1023 res.body[i] = (byte)t;
1028 #if BIGINTEGER_DEBUG
1029 Debug.Assert(res.used == longer.used+1);
1031 res.body[longer.used] = (byte)c;
1034 res.u_renormalise();
1035 #if BIGINTEGER_DEBUG
1036 Debug.Assert(res.sane());
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));
1051 for (i = 0; i < y.used; i++) {
1052 t = x.body[i] - y.body[i] - b;
1054 res.body[i] = (byte)(t + B_BASE);
1058 res.body[i] = (byte)t;
1063 for (i = y.used; i < x.used; i++) {
1066 res.body[i] = (byte)(t + B_BASE);
1069 res.body[i] = (byte)t;
1073 #if BIGINTEGER_DEBUG
1074 Debug.Assert (b == 0);
1078 res.u_renormalise();
1079 #if BIGINTEGER_DEBUG
1080 Debug.Assert(res.sane());
1084 static void umul(BigInteger x, BigInteger y, BigInteger res) {
1087 #if BIGINTEGER_DEBUG
1088 Debug.Assert(x.sane());
1089 Debug.Assert(y.sane());
1090 Debug.Assert(res.size == maxused_mul(x,y));
1093 for (j = 0; j < y.used; j++) {
1097 for (i = 0; i < x.used; i++) {
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);
1103 #if BIGINTEGER_DEBUG
1104 Debug.Assert (carry < B_BASE);
1107 res.body[i+y.used] = (byte)carry;
1110 res.used = x.used+y.used;
1111 res.u_renormalise();
1112 #if BIGINTEGER_DEBUG
1113 Debug.Assert(res.sane());
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;
1122 #if BIGINTEGER_DEBUG
1123 Debug.Assert(isor.sane());
1124 Debug.Assert(dend.sane());
1125 Debug.Assert(isor.used > 0); // against division by zero
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];
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.
1138 mres.used = dend.used;
1139 for (j = 0; j < mres.used; j++) {
1140 mres.body[j] = dend.body[j];
1142 dres.u_renormalise();
1143 mres.u_renormalise();
1144 #if BIGINTEGER_DEBUG
1145 Debug.Assert(dres.sane());
1146 Debug.Assert(mres.sane());
1151 if (isor.used == 1) {
1153 // Simple case; divisor is a single digit
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]);
1161 dres.used = dend.used;
1162 dres.u_renormalise();
1164 // Remainder is the final carry value
1168 mres.body[0] = (byte)carry;
1170 dres.u_renormalise();
1171 mres.u_renormalise();
1172 #if BIGINTEGER_DEBUG
1173 Debug.Assert(dres.sane());
1174 Debug.Assert(mres.sane());
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);
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];
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);
1208 // Don't bother to multiply; just copy.
1209 for (j = 0; j < dend.used; j++) {
1210 dend_body[j] = dend.body[j];
1212 for (j = 0; j < isor.used; j++) {
1213 isor_body[j] = isor.body[j];
1216 // Extend dividend with leading zero.
1217 dend_body[dend.used] = tmp[isor.used] = 0;
1222 for (j = 0; j < isor.used; j++) {
1223 t = scaleup * isor.body[j] + carry;
1224 isor_body[j] = (byte)(t % B_BASE);
1227 #if BIGINTEGER_DEBUG
1228 Debug.Assert (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);
1237 dend_body[dend.used] = (byte)carry;
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);
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]);
1255 Console.Write("\n");
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])
1260 (B_BASE*isor_body[isor.used-1] + isor_body[isor.used-2]);
1261 if (vh > B_BASE-1) {
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 );
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.
1274 for (j = 0; j < isor.used; j++) {
1275 t = vh * isor_body[j] + carry;
1276 tmp[j] = (byte)(t % B_BASE);
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");
1287 Console.WriteLine("delta = {0}", delta );
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]) );
1294 if (tmp[j] > dend_body[j+delta]) {
1298 if (tmp[j] < dend_body[j+delta]) {
1303 // If we did guess too large, decrement vh and subtract a copy of
1304 // isor from tmp. This had better not go negative!
1306 #if BIGINTEGER_DEBUG
1307 Console.WriteLine ( "guess too large" );
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);
1317 tmp[j] = (byte)(tmp[j] - isor_body[j] - carry);
1321 //if (carry > 0) {pp(isor);pp(dend);};
1322 //Debug.Assert(carry == 0);
1324 Debug.Assert(tmp[isor.used] > 0);
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]);
1332 Console.Write("\n");
1336 // Now vh really is the i'th quotient digit.
1337 // Subtract (tmp << delta) from
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]
1347 dend_body[j+delta] = (byte)(dend_body[j+delta] - tmp[j] - carry);
1351 #if BIGINTEGER_DEBUG
1352 Debug.Assert(carry==0);
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");
1361 // park vh in the result array
1362 #if DEBUG_SAINTEGER_UDIV
1363 Console.WriteLine("[{0}] <- {1}", i-isor.used, vh );
1365 dres.body[i-isor.used] = (byte)vh;
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());
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];
1382 mres.u_renormalise();
1383 #if BIGINTEGER_DEBUG
1384 Debug.Assert(mres.sane());
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);
1394 #if BIGINTEGER_DEBUG
1395 Debug.Assert (carry == 0);
1397 mres.u_renormalise();
1398 #if BIGINTEGER_DEBUG
1399 Debug.Assert(mres.sane());
1408 #if BIGINTEGER_DEBUG
1409 public static void Test ( ) {
1411 BigInteger bi, bj, bk, bm;
1414 a = new BigInteger(1);
1415 for (int n = 1; n <= 10; n++) {
1416 b = new BigInteger(n);
1419 Console.WriteLine("{0}", (double)a);
1421 for (i = -10007; i <= 10007; i++) {
1422 Console.WriteLine ( "i = {0}", i );
1424 bi = new BigInteger(i);
1426 Debug.Assert(i == t);
1428 for (j = -10007; j <= 10007; j++) {
1429 bj = new BigInteger(j);
1431 Debug.Assert(j == t);
1438 Debug.Assert(i + j == k);
1447 Debug.Assert(i - j == k);
1456 Debug.Assert(i * j == k);
1460 QuotientRemainder(bi, bj, out bk, out bm);
1463 Debug.Assert(k == i / j);
1464 Debug.Assert(m == i % j);
1468 Console.WriteLine("done");