Bug 9061 – BigInt | BigInt, BigInt & int

Two missing BigInt operations: import std.bigint: BigInt; void main() { auto x = BigInt(1) | BigInt(1); auto y = BigInt(1) & 1; } Those operations are used in a Binary GCD: http://en.wikipedia.org/wiki/Binary_GCD_algorithm#Iterative_version_in_C

*** Issue 8919 has been marked as a duplicate of this issue. ***

*** Issue 9432 has been marked as a duplicate of this issue. ***

*** Issue 10387 has been marked as a duplicate of this issue. ***

While working on this today, I noticed an unpleasant detail. What should be the result of this: import std.bigint: BigInt; void main() { BigInt a = "0xB16_B16_B16_B16_B16_B16_B16_B16_B16"; BigInt b = 4; BigInt c = a & ~b; // Unset bit 3 assert(c == BigInt("0xB16_B16_B16_B16_B16_B16_B16_B16_B12"); } And if the comment is correct, then this is wrong: import std.bigint : BigInt; void main() { BigInt a = "0xB16_B16_B16_B16_B16_B16_B16_B16_B16"; BigInt b = 4; BigInt c = a & b; // Separate bit 3 assert(c == 4); } I would argue that the latter behavior is better, and a separate function may be required for the former. Also, how should ~b work, if at all?

(In reply to comment #4) > While working on this today, I noticed an unpleasant detail. What should be the > result of this: > > import std.bigint: BigInt; > > void main() { > BigInt a = "0xB16_B16_B16_B16_B16_B16_B16_B16_B16"; > BigInt b = 4; > BigInt c = a & ~b; // Unset bit 3 > assert(c == BigInt("0xB16_B16_B16_B16_B16_B16_B16_B16_B12"); > } > > And if the comment is correct, then this is wrong: > > import std.bigint : BigInt; > > void main() { > BigInt a = "0xB16_B16_B16_B16_B16_B16_B16_B16_B16"; > BigInt b = 4; > BigInt c = a & b; // Separate bit 3 > assert(c == 4); > } > > I would argue that the latter behavior is better, and a separate function may > be required for the former. > > Also, how should ~b work, if at all? This is what Python 2.6.5 answers to your questions: >>> a = 0xB16B16B16B16B16B16B16B16B16 >>> b = 4 >>> c = a & ~b >>> c == 0xB16B16B16B16B16B16B16B16B12 True >>> a = 0xB16B16B16B16B16B16B16B16B16 >>> b = 4 >>> c = a & b >>> c 4L >>> ~b -5

(In reply to comment #5) > This is what Python 2.6.5 answers to your questions: > > >>> a = 0xB16B16B16B16B16B16B16B16B16 > >>> b = 4 > >>> c = a & ~b > >>> c == 0xB16B16B16B16B16B16B16B16B12 > True > > > >>> a = 0xB16B16B16B16B16B16B16B16B16 > >>> b = 4 > >>> c = a & b > >>> c > 4L > >>> ~b > -5 So basically SEX[0]. That sounds nice (heh), but how do we deal with uints? Also, std.bigint.BigInt uses signed magnitude, whereas Python uses 2's complement. Certainly it's possible to make BigInt behave the same as in Python, but I'm unsure we want to. It's certainly a data point, though. [0]: http://en.wikipedia.org/wiki/SEX_(computing)

Java / openjdk uses two's complement and GMP uses sign + magnitude but behaves as if two's complement for bitwise operations.

Python has a library to use the very efficient GNU MP library: http://code.google.com/p/gmpy/ The results are the same (mpz is the multiprecision integer of MP): >>> from gmpy import mpz >>> a = mpz(0xB16B16B16B16B16B16B16B16B16) >>> b = mpz(4) >>> c = a & ~b >>> c mpz(224904433524448119807227542465298L) >>> c == mpz(0xB16B16B16B16B16B16B16B16B12) True >>> a = mpz(0xB16B16B16B16B16B16B16B16B16) >>> b = mpz(4) >>> c = a & b >>> c mpz(4) >>> ~b mpz(-5)

So that's all decided, then. The remaining problem is, as stated above, uints. As we all know, uints don't have sign bits. This means there's no sign to extend. Hence, we're back to the described problem, only slightly different. In this case, the result should be padded with 1s: import std.bigint : BigInt; void main() { BigInt a = "0xB16_B16_B16_B16_B16_B16_B96_B16_B16"; uint b = 0x8000_0000; BigInt c = a & ~b; // Unset bit 31 assert(c == BigInt("0xB16_B16_B16_B16_B16_B16_B16_B16_B16"); } In this case, the result should be padded with 0s: import std.bigint : BigInt; void main() { BigInt a = "0xB16_B16_B16_B16_B16_B16_B96_B16_B16"; uint b = 0x8000_0000; BigInt c = a & b; // Separate bit 31 assert(c == 0x8000_0000); } I'm starting to think the best solution is to simply disallow bitwise operations that involve both a uint and a BigInt, and this is what I'll implement, unless a solution is presented (that is different from 'pad with 0s', 'pad with 1s', 'pad with highest bit' and 'pad with inverse of highest bit', *and* sensible).

(In reply to comment #9) > *and* sensible. I'm pretty sure the answer is that it should do the same thing as converting to BigInt, then performing the bitwise operation.

I was thinking of something more along the lines of defining ~ (complement operator) as negating the sign and subtracting one, and then when you do &,|,^, you take the two's complement on the fly.

(In reply to comment #10) > (In reply to comment #9) > > *and* sensible. > > I'm pretty sure the answer is that it should do the same thing as converting to > BigInt, then performing the bitwise operation. That means example one is going to break. This is not in line with the principle of least astonishment.

(In reply to comment #9) > I'm starting to think the best solution is to simply disallow bitwise > operations that involve both a uint and a BigInt, and this is what I'll > implement, In such cases a strategy to use is ask what the most common use cases are. And look at their expected performance. If I have code like: BigInt & 1 And I have to replace it with: BigInt & BigInt(1) Or: BigInt & BigInt.one What is the performance? When a design is not clear, a design strategy is to start with a conservative API (disallowing some operations), and only later allow some of them, when you have a better idea of the needs. Allowing more operations later is possible, while restricting an API later is harder and breaks code.

(In reply to comment #12) > (In reply to comment #10) > > (In reply to comment #9) > > > *and* sensible. > > > > I'm pretty sure the answer is that it should do the same thing as converting to > > BigInt, then performing the bitwise operation. > > That means example one is going to break. This is not in line with the > principle of least astonishment. Sure it is: import std.stdio; void main() { long a = 0xB16_B16_B16_B16_B16; uint b = 0x8000_0000; long c = a & ~b; writefln("%X", c); }

(In reply to comment #14) > (In reply to comment #12) > > (In reply to comment #10) > > > (In reply to comment #9) > > > > *and* sensible. > > > > > > I'm pretty sure the answer is that it should do the same thing as converting to > > > BigInt, then performing the bitwise operation. > > > > That means example one is going to break. This is not in line with the > > principle of least astonishment. > > Sure it is: > > import std.stdio; > > void main() > { > long a = 0xB16_B16_B16_B16_B16; > uint b = 0x8000_0000; > long c = a & ~b; > writefln("%X", c); > } So it is. I retract my statements and will implement it like that, then.

(In reply to comment #15) > So it is. I retract my statements and will implement it like that, then. Are you working on this?

I am. Expect a pull request within the next ten days.

Ask, and thou shalt receive: https://github.com/D-Programming-Language/phobos/pull/1721

Fixed: https://github.com/D-Programming-Language/phobos/commit/05738e116c597f17edc13f31c3cda06c38e2239c If the performance is not satisfactory a new enhancement report should be created.