## Forum Navigation

# BigInt fails division/modulus

Moderators:
kris

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

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 2Modulus 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.