  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.

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     