6
\$\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?

| improve this question | | | | |
\$\endgroup\$
  • 2
    \$\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
13
\$\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.

| improve this answer | | | | |
\$\endgroup\$
  • 2
    \$\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
1
\$\begingroup\$

You cannot be faster than the library doing operations one bit at a time.

If you want to be fast first understand that the hardware itself does addition in 32-bit or 64-bit integer sizes. So you should be doing so also. If you check the implementation of Java's BigInteger class, you will find it internally stores the BigInteger as an integer array. This is because Java already optimized addition for the underlying hardware.

Secondly, as pointed out in the previous answer, at the end of addition, you need a while loop which continues doing carries as long as adding 1 to the next bit (or 32/64-bit word) causes another carry.

You can make code faster than Java's BigInteger class but in the case of addition, you simply will not gain much as everything is already optimized for this trivial operation. If mutability is desired then making your own BigInteger class which allows this could speed things up, but you will have to rewrite your code to do the math with hardware optimized sizes and not individual bits.

For example of addition, using arrays of integers and even better multiplication which can be much faster than the O(n^2) of Java BigInteger, see this code: https://github.com/tbuktu/ntru/blob/master/src/main/java/net/sf/ntru/arith/SchönhageStrassen.java

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ Valid insights into arithmetic speed and at least one prominent, um, disingenuity in java.math.BigInteger. \$\endgroup\$ – greybeard Feb 17 at 6:54
  • \$\begingroup\$ O(n^2) [multiplication time] of Java BigInteger what JRE, what version did this apply to? They've heard of Bodrato, too. \$\endgroup\$ – greybeard Feb 18 at 18:36
  • \$\begingroup\$ AFAIK, there are not many standard libraries which typically include efficient multiplication algorithms. I feel they leave this up to the programmer for a variety of reasons. Namely because the Karatsuba/Toom-Cook methods and the FFT based Schönhage-Strassen/Furer method are complicated to implement and have no definitive ranges where the speed is optimal as its system dependent. In fact O(n^2) is faster than all methods until usually around 4096-8192 bits at least. The FFT methods become faster at even higher bit sizes and sometimes details cause ranges efficiency (eg. see code in post). \$\endgroup\$ – Gregory Morse Feb 19 at 20:46
  • \$\begingroup\$ It is a complicated issue as the hardware has very efficient multiplication using likely Karatsuba with lookup tables for base cases. But the cost of dividing big integers is also quite expensive where a simple O(n^2) loop with indexing easily comes out faster. Its not just the complexity of the multiplication but analyzing all the details of memory allocations, function calls, comparisons, etc at the hardware clock level, clearly depending on how each implementation is written, practically one becomes faster then slower again then faster, etc. So you have to find a library or roll your own \$\endgroup\$ – Gregory Morse Feb 19 at 20:50
  • \$\begingroup\$ hardware has very efficient multiplication using likely Karatsuba No way - higher radix Booth would be something to search for. A few dozen bits are far too few to benefit from Toom-Cook. Somewhere in the last decade, the KARATSUBA_THRESHOLD java.math.BigInteger uses to switch between "long multiplication" and Karatsuba has been raised (e.g., from 50 to 80 - int limbs, 1600→2560 bits - the threshold for Toom3 being thrice that). \$\endgroup\$ – greybeard Feb 20 at 6:03

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.