Download Reference Manual
The Developer's Library for D
About Wiki Forums Source Search Contact

BigInt fails division/modulus

Moderators: kris

Posted: 03/11/10 06:24:42 Modified: 03/11/10 14:55:21

Greetings,

I'm on 64-bit Vista. Trying out the BigInt? library, I'm getting the following problems:

Division gives the wrong values:

	BigInt a = 10;
	BigInt b = 2;
	a /= b;
	Stdout.format("{}\n", a.toInt()); // prints 2

Modulus crashes:

	BigInt a = 10;
	BigInt b = 2;
	a %= b; // throws object.Exception: Win32 Exception
	Stdout.format("{}\n", a.toInt());

Unrelated to that, but I would also like to suggest adding the following methods (or improved versions thereof):

	bool isEven(BigInt n) {
		return cast(bool)(((n >> 1) << 1) == n); // I assume this methodology can be improved upon with private access and understanding of the internals
	}

	// Based on [http://en.wikipedia.org/wiki/Exponentiation_by_squaring]:

	BigInt bigPow(BigInt x, BigInt n) {
		BigInt ret;
		if (n == 0) {
			ret = 1;
		}
		else if (n == 1) {
			ret = x;
		}
		else if (n == 2) {
			ret = x * x;
		}
		else if (isEven(n)) {	// even
			ret = bigPow(x, n >> 1);
			ret *= ret;
		}
		else {	// odd
			ret = bigPow(x, ((n - 1) >> 1));
			ret *= ret;
			ret *= x;
		}
		return ret;
	}

	// Based on [http://en.wikipedia.org/wiki/Modular_exponentiation]:

	BigInt modPow(BigInt base, BigInt exp, BigInt mod) {
		BigInt ret = 1;
		
		BigInt lexp = exp;
		while (lexp > 0) {
			if (!isEven(lexp)) {
				ret = (ret * base) % mod;
			}
			lexp >>= 1;
			base = (base * base) % mod;
		}
		
		return ret;
	}

I haven't tested these vastly (and in fact, can't test modPow() due to the modulus error), so I would recommend not trusting my code. I also have rand() and sqrt() functions that I've written, but I don't know that those are general purpose enough for inclusion. If so, here they are:

	BigInt bigSqrt(BigInt n) {
		BigInt x = n >> 1;
		BigInt prev = -1;
		
		while (true) {
			x = (x + (n / x)) >> 1;
			if (
				prev != -1
				&& x == prev
			) {
				break;
			}
			prev = x;
		}
		return x;
	}

	BigInt bigRand(BigInt n) {
		if (n < 0) throw new Exception("Parameter must be positive");
		
		BigInt ret;
		Random r = new Random();
		
		BigInt sub_rand(BigInt square, uint depth) {
			BigInt ret2;
			if (square >= int.max) {
				BigInt square2 = bigSqrt(square) + 1;	// compensate for precision loss
				ret2 = sub_rand(square2, depth + 1);
			}
			else {
				int count = 1 << depth;
				ret2 = 1;
				for (int L = 0; L < count; L++) {
					ret2 *= r.uniformR(square.toInt() + 1);	// compensate for precision loss
				}
			}
			return ret2;
		}
		
		do {
			ret = 0;
			
			if (n >= int.max) {
				BigInt square = bigSqrt(n) + 1;	// compensate for precision loss
				ret = sub_rand(square, 1);
			}
			else {
				ret = r.uniformR(n.toInt());
			}
		}
		while (ret >= n);	// Due to precision loss compensation, there's some chance that we'll go over. Just try again.

		return ret;
	}

Again, I would recommend double-checking that the output is as intended.

Author Message

Posted: 03/11/10 09:43:39

Hi Sage Rat,

could you please create a ticket (or tickets) for this?

Posted: 03/11/10 14:47:35

Alright. I'll split it into two tickets, one for the bug, one for the enhancements. I don't know how important various segments of the codebase are considered, or any of your other settings, so I'll just from-the-hipped the priority and so on.

Posted: 03/11/10 14:54:04 -- Modified: 03/11/10 15:24:15 by
Sage Rat

Edit: Nevermind