Changeset 3903

Timestamp:

08/23/08 01:55:47 (3 months ago)

Author:

Don Clugston

Message:

And here's mod. That was easy.

Files:

trunk/tango/math/BigInt.d

r3900	r3903
107	107	///
108	108	BigInt opDiv(T: BigInt)(T y) {
109		this = divInternal(this, y);
110		return *this;
	109	return divInternal(*this, y);
111	110	}
112	111	///
…	…
117	116	r.data = biguintDivInt(data, u);
118	117	r.sign = r.isZero()? false : this.sign != (x<0);
119		return *this;
	118	return r;
	119	}
	120	///
	121	BigInt opDivAssign(T: int)(T x) {
	122	assert(x!=0);
	123	uint u = x < 0 ? -x : x;
	124	data = biguintDivInt(data, u);
	125	sign = isZero()? false : sign ^ (x<0);
	126	return *this;
120	127	}
121	128	///
…	…
129	136	}
130	137	///
131		BigInt opDivAssign(T: int)(T x) {
132		assert(x!=0);
133		uint u = x < 0 ? -x : x;
134		data = biguintDivInt(data, u);
135		sign = isZero()? false : sign ^ (x<0);
136		return *this;
137		}
138
	138	BigInt opModAssign(T:int)(T y) {
	139	assert(y!=0);
	140	uint u = y < 0 ? -y : y;
	141	int rem = biguintModInt(data, u);
	142	// x%y always has the same sign as x.
	143	// This is not the same as mathematical mod.
	144	assignUint(rem);
	145	return *this;
	146	}
	147	///
	148	BigInt opModAssign(T: BigInt)(T y) {
	149	this = modInternal(this, y);
	150	return *this;
	151	}
	152	///
	153	BigInt opMod(T: BigInt)(T y) {
	154	return modInternal(*this, y);
	155	}
139	156	///
140	157	BigInt opNeg() { negate(); return *this; }
…	…
296	313	return r;
297	314	}
	315	static BigInt modInternal(BigInt x, BigInt y) {
	316	if (x.isZero()) return x;
	317	BigInt r;
	318	r.sign = x.sign;
	319	r.data = biguintMod(x.data, y.data);
	320	return r;
	321	}
298	322	static BigInt divInternal(BigInt x, BigInt y) {
299	323	if (x.isZero()) return x;

r3900	r3903
336	336	}
337	337
	338	uint [] biguintMod(uint [] x, uint [] y)
	339	{
	340	if (y.length > x.length) return x;
	341	if (y.length == 1) return biguintDivInt(x, y[0]);
	342	uint [] result = new uint[x.length - y.length + 1];
	343	uint [] rem = new uint[y.length];
	344	schoolbookDivMod(result, rem, x, y);
	345	while (rem.length>1 && rem[$-1]==0) rem = rem[0..$-1];
	346	return rem;
	347	}
	348
338	349	public:
339	350	// Converts a big uint to a hexadecimal string.