Why are these functions slower than BigInteger's included methods?

I tried writing alternative functions to Java's BigInteger.add(BigInteger.ONE), BigInteger.add(BigInteger), and BigInteger.subtract(BigInteger):

public static BigInteger increment(BigInteger x)
 {
  int i=0;
  while(x.testBit(i))
   x=x.clearBit(i++);
  x=x.setBit(i);
  return x;
 }

 public static BigInteger add(BigInteger x, BigInteger y)
 {
  boolean A, B, carry=false;
  BigInteger sum=BigInteger.ZERO;
  int firstBit=x.or(y).getLowestSetBit(),
      topBit=x.or(y).bitLength();
  for(int i=firstBit;i<=topBit;i++)
  {
   A=x.testBit(i);
   B=y.testBit(i);
   if((A^B)^carry)
    sum=sum.setBit(i);
   carry=(A&&B)||((A^B)&&carry);
  }
  return sum;
 }

 public static BigInteger subtract(BigInteger x, BigInteger y)
 {
  if(x.compareTo(y)==-1)
  return subtract(y,x).negate();
  boolean A, B, borrow=false;
  BigInteger diff=BigInteger.ZERO;
  int firstBit=x.or(y).getLowestSetBit(),
      topBit=x.or(y).bitLength();
  for(int i=firstBit;i<=topBit;i++)
  {
   A=x.testBit(i);
   B=y.testBit(i);
   if((A^B)^borrow)
    diff=diff.setBit(i);
   borrow=(!A&&B)||(!(A^B)&&borrow);
  }
  return diff;
 }

Instead of speeding my program up, they slowed it down. I'm thinking it might be related to the immutability of the Java BigInteger class: every time a new value is computed, a new BigInteger has to be created. Would I have different results if I wrote them as method overrides in a subclass, using MutableBigInteger?

Your question comes in multiple parts: General code review, adding algorithms, and then performance relative to standard BigInteger

General Review

Let's focus on this method, it shows essentially all the general issues I see:

public static BigInteger add(BigInteger x, BigInteger y)
 {
  boolean A, B, carry=false;
  BigInteger sum=BigInteger.ZERO;
  int firstBit=x.or(y).getLowestSetBit(),
      topBit=x.or(y).bitLength();
  for(int i=firstBit;i<=topBit;i++)
  {
   A=x.testBit(i);
   B=y.testBit(i);
   if((A^B)^carry)
    sum=sum.setBit(i);
   carry=(A&&B)||((A^B)&&carry);
  }
  return sum;
 }

-
Breathing room around operators is important for readability. The code like:

for(int i=firstBit;i<=topBit;i++)

should be:

for (int i = firstBit; i <= topBit; i++)

-
Java code styles use brace-at-line-end style. C, C++, C# and other C* languages use next-line style. This sort of brace style is often debated, but, all common Java code style standards require end-of-line. You will regularly be criticised when sharing Java code using this style. Your code should look like:

public static BigInteger add(BigInteger x, BigInteger y) {
    boolean ...

-
mixed initialization is confusing, and variables should be declared in their tightest scope:

boolean A, B, carry=false;

That declaration is redundant, and confusing. Java defaults all boolean values to false when declared (unless specifically initialized to true). So, the carry=false is redundant (since A and B are also false).

Further, A and B are horrible names for variables. For a start, they are upper case, then they have poor meanings, and finally, A is a real word that tends to create a specific meaning when read out of context.

While talking bad names, x and y are not good names either. Those names imply that the two input variables are coordinates, and not two values to be added. I would recommend names like augend and addend because those are the official names for the two terms used in addition.

Finally, A and B are only used in the context of the for-loop, and not outside that context, so they should be declared where they are used:

boolean augBit = augend.testBit(i);
boolean addBit = addend.testBit(i);

-
Complicated functions should not be used when creating compound variable declarations:

int firstBit=x.or(y).getLowestSetBit(),
    topBit=x.or(y).bitLength();

That should be split in three, actually. The x.or(y) is repeated twice, so should be extracted....

BigInteger orVals = augend.or(addend);
 int firstBit = orVals.getLowestSetBit();
 int topBit = orVals.bitLength();

-
1-liner if-statements and other 1-liner blocks. You have the 1-liner statement:

if((A^B)^carry)
     sum=sum.setBit(i);

1-liners are know to be a leading cause of bugs introduced during the maintenance cycle of code. The easy solution is to brace 1-liners always. The code should be:

if( (A ^ B) ^ carry) {
       sum=sum.setBit(i);
   }

Let's take a pause at this point, and see where we are at:

public static BigInteger add(BigInteger augend, BigInteger addend) {

    boolean carry = false;
    BigInteger sum = BigInteger.ZERO;

    BigInteger orVals = augend.or(addend);
    int firstBit = orVals.getLowestSetBit();
    int topBit = orVals.bitLength();

    for (int i = firstBit; i <= topBit; i++) {
        int augBit = augend.testBit(i);
        int addBit = addend.testBit(i);
        if ((augBit ^ addBit) ^ carry) {
            sum = sum.setBit(i);
        }
        carry = (augBit && addBit) || ((augBit ^ andBit) && carry);
    }
    return sum;
}

Alright, at this point, I can see the algorithm more clearly in the code, time to move on.....

Bug

Having isolated the code like this, it is apparent that there is a big bug too. If you have a carry coming from the highest bit sum, you ignore the carry... So, for example, if you have the two values 0x0f and 0x01, I would expect the sum 0x10, but you will not carry the last 1 bit in to the next value...

Performance

With the refactored code, it is clear that there are two major performance hits. The first is that the sum is a BigInteger value that gets recreated multiple times each loop (once for each set bit). Each time you call:

sum = sum.setBit(i);

you create a new BigInteger value, with the corresponding overheads, and memory allocations, etc. This could be a lot of allocations. The native Java routine breaks out of this situation by using primitive values and arrays, and keeps a bit-vector that is mutable for the duration of the addition cycle. By doing it that way, there is no memory management penalty....

A second issue related to performance, that is not obvious, is that the real BigInteger class does things both ways ..... it does a bit-vector for large integer values, but for 'small' values it uses a simple java long primitive. In other words, it simply does `long sum = augend.lo

StackExchange Code Review Q#56512, answer score: 13