Bug in BigInteger.add() or my math mistake?
Hello,
I'm trying to do some radix conversions on 128-bit numbers using BigInteger. I'm getting some wierd results, so I'm wondering if this is a bug in the JDK, or if I've made a mistake with my math (I'm on JDK 1.5.0_10-b03).
Here's what I'm doing (in English). Code follows below, too.
1.) Start off with two 'long' numbers (MSB & LSB).
2.) Create a BigInteger using MSB (the Most Sig Bits).
3.) Bitshift the newly created BigInt left by 64 bits.
4.) Add LSB to the BigInteger (The LSB is a 'long' number, so all 64 of its bits should be appended into the newly opened 64 bits of the BigInteger.
This works, except that if LSB is negative, the final 128bit BigInteger is incorrect. The last 2 MSB's of the BigInteger (i.e., bit 66 and 65 of the BigInteger, assuming the rightmost bit of the 128 bits is index 0) is 1 less than it should be.
In the test case below, bits 65 and 64 are '01' (decimal 1), while they should be '10' (decmial 2).
This error does not happen if the 2 baseline 'long' arguments (MSB and LSB) are both positive. I suspect this has something to do with the sign of the LSB arguement, but the sign bit should be bit 64 of the long number, and should just get added into the BigInteger without affecting the other 64 MSB bits.
In addition, if I create a BigInteger using the string constructor (where the string is a concatenation of 2 long numbers in hex format, e.g., then this discrepancy does not happen).
-
import java.math.BigInteger;
import junit.framework.TestCase;
public class BigIntegerCreationTestor extends TestCase
{
/**
* Does the test.
*/
public void testBigInteger()
{
long baselineMSB = 0x2a42940641c94eb2L;
long baselineLSB = 0xaf6578135552b65cL;
// long baselineLSB = 0x2a42940641c94eb2L;
this.testBigIntegerCreation(baselineMSB, baselineLSB);
/*
* for(int i = 1; i > 0; i++) { baselineMSB += 0xFFFFFFFFL; baselineLSB +=
* 0xFFFFFFFFL; this.testBigIntegerCreation(baselineMSB, baselineLSB); }
*/
}
/**
* Take two longs. Create a BigInteger with the first long (the Most Sig
* Bits). Bitshift the newly created BigInt left by 64 bits. Add the LSB
* long into to the BigInteger. The LSB is a 'long' number, so all 64 of its
* bits should be appended into the remaining 64 bits of the BigInteger.
*
* This works, except that if the LSB long value is negative, the final 128
* bit BigInteger is incorrect. The last 2 MSB's of the BigInteger (i.e.,
* bit 66 and 65 of the BigInteger, assuming the rightmost bit of the 128
* bits is index 0) is 1 less than it should be. In the test case below,
* bits 65 and 64 are '01' (decimal 1), while they should be '10' (decmial
* 2).
*
* This error does not happen if the 2 baseline 'long' arguments
* (baselineMSB and baselineLSB) are both positive. I suspect this has
* something to do with the sign of the LSB arguement, but the sign bit
* should be bit 64 of the long number, and should just get added into the
* BigInteger upto position 64, without affecting the MSB bits.
*/
private void testBigIntegerCreation(long baselineMSB, long baselineLSB)
{
System.out.println("baselineMSB(B10): " + baselineMSB);
System.out.println("baselineLSB(B10): " + baselineLSB);
String badBiggyInB2 = "";
// This works, and is fine, but we don't use it to demonstrate an error.
// BigInteger goodBiggy = new
// BigInteger("2a42940641c94eb2af6578135552b65c", 16);
String sMSB = Long.toBinaryString(baselineMSB);
while (sMSB.length() < 64)
{
sMSB = "0" + sMSB;
}
String sLSB = Long.toBinaryString(baselineLSB);
while (sLSB.length() < 64)
{
sLSB = "0" + sLSB;
}
assertTrue(sMSB.length() == 64);
assertTrue(sLSB.length() == 64);
BigInteger goodBiggy = new BigInteger((sMSB + sLSB), 2);
// The errant BigInteger Creation Process
BigInteger badBiggy = BigInteger.valueOf(baselineMSB);
badBiggyInB2 = badBiggy.toString(2);
System.out.println("Incorrect Half BigInteger(B2): " + badBiggyInB2);
System.out.println("Incorrect Half BigInteger(B16): "
+ badBiggy.toString(16));
System.out.println("baselineMSB(B2): "
+ Long.toBinaryString(baselineMSB));
System.out.println("Correct BigInteger(B16): "
+ Long.toHexString(baselineMSB));
badBiggy = badBiggy.shiftLeft(64);
badBiggyInB2 = badBiggy.toString(2);
System.out.println("Incorrect Almost Full BigInteger(B2): "
+ badBiggyInB2);
System.out.println("Correct BigInteger(B2): " + goodBiggy.toString(2));
badBiggy = badBiggy.add(BigInteger.valueOf(baselineLSB));
badBiggyInB2 = badBiggy.toString(2);
System.out.println("baselineLSB (B2): "
+ Long.toBinaryString(baselineLSB));
System.out.println("Incorrect Full BigInteger(B2): " + badBiggyInB2);
System.out.println("Correct BigInteger(B2): " + goodBiggy.toString(2));
System.out.println("Incorrect Full BigInteger(B16): "
+ badBiggy.toString(16));
System.out
.println("Correct BigInteger(B16): " + goodBiggy.toString(16));
System.out.println("Incorrect Full BigInteger(B32): "
+ badBiggy.toString(32));
System.out
.println("Correct BigInteger(B32): " + goodBiggy.toString(32));
if (!(badBiggy.equals(goodBiggy)))
{
System.out.println("TEST FAIL: baseline 'badBiggy' ("
+ badBiggy.toString(16)
+ ") is **NOT EQUAL** to 'goodBiggy' ("
+ goodBiggy.toString(16) + ") but should be.");
System.out.println("Difference in Hex is: "
+ goodBiggy.subtract(badBiggy).toString(16));
}
assertTrue(badBiggy.equals(goodBiggy));
System.out.print("PASS for MSB: " + baselineMSB + " and LSB: "
+ baselineLSB);
}
}
