5
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ Or perhps it is because your add algorithm is naive and you shouldn't re-event the wheel, especially if it is a strong, tested refined and well thought one \$\endgroup\$ – Bruno Costa Jul 8 '14 at 23:34
  • \$\begingroup\$ @BrunoCosta there are other languages with much better optimized arbitrary precision number packages than Java, so your assumption that their algorithm is "a strong, tested refined and well thought one" might not necessarily be well-founded! \$\endgroup\$ – Brian J. Fink Jul 8 '14 at 23:41
  • \$\begingroup\$ @BrunoCosta Was it you who voted my question down? \$\endgroup\$ – Brian J. Fink Jul 8 '14 at 23:44
  • 1
    \$\begingroup\$ "there are other languages with much better optimized" everything. everything is the end of that sentence when we're talking about Java. Java is a pretty high abstraction level language meaning what it lacks in efficiency, it makes up for in developer time. Another language being more efficient at something then Java isn't necessarily because a specific Java algorithm is poorly implemented--it could just be that Java isn't as efficient as a language versus whatever you're comparing this algorithm to. \$\endgroup\$ – nhgrif Jul 9 '14 at 0:48
  • 2
    \$\begingroup\$ @BrunoCosta, if you have such strong feelings about this, you're free to write a review of OPs code. \$\endgroup\$ – RubberDuck Jul 9 '14 at 13:01
12
\$\begingroup\$

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.longVal + addend.longVal if the two inputs are small enough for long value representations, and also if the sum will fit in a primitive long. In other words, it is much faster for smaller values than for values that exceed Long.MAX_VALUE/MIN_VALUE

Algorithm

I have, in the past, tried to out-perform BigDecimal (not BigInteger), by building a mutable version of BigDecimal. It became really complicated really fast. The concept of a MutableBigInteger is nice, but the reality is that it becomes a mess, fast. There are some open source attempts at this, though I believe they are all languishing in disuse. The reason is simple.... BigInteger is, by an large, fast. The penalty of the Immutable memory hit because you need to create new values and arrays often, is outweighed by the cost of memory management and expansion that is required otherwise.

Finally, the individual operations inside the BigInteger class are able to use the native storage mechanism directly when doing calculations, and you don't need to do the translations for each bit, for example. In other words, 'wrapping' BigInteger is never going to give you the performance that BigInteger itself can give, simply because the internals of BigInteger can access the more efficient internal data structures.

\$\endgroup\$
  • \$\begingroup\$ "Java defaults all boolean values to false when declared (unless specifically initialized to true)" – this is not true for local variables, as local variables are not assigned a default value and must be explicitly initialized. So the explicit initialization of carry to false is actually not redundant. \$\endgroup\$ – Stingy Aug 11 '19 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.