Extended-Precision Native Integers for Java

When performance counts

Lou is the author of Zen of Windows 95 Programming (Coriolis Group, 1996). He can be contacted at [email protected].

To address performance problems in the JDK 1.1's BigInteger class, I implemented mInt, my own "monster" integer library. The main difference between Sun's implementation and mine is that BigInteger offers arbitrary precision, meaning the representation of a number is adjusted as needed. For example, if the result of adding two numbers won't fit in an integer the same size as that of the operands, the result is created with additional precision, and no overflow or underflow errors are possible. My library, however, provides signed integers fixed at 256 bits. Even though this is "only" four times the number of bits in the Java primitive type long, it still yields 77 decimal digits -- more than enough for most applications.

A subtler difference between the implementations is that Sun represents the number as a series of bytes that are logically combined to form one huge binary integer. My library represents each mInt as an array of 4-byte integers, which are also treated as parts of a single integer. This approach simplifies some parts of the implementation and lets the code operate on 32 (instead of 8) bits at a time.

What's in the Code

The mInt library is a 32-bit Windows DLL built from a single source file, MINT.C (available electronically; see "Availability," page 3). MINT.DLL supports the four basic arithmetic functions, conversions from binary to ASCII (both decimal and hex) and decimal string to binary, and some bit-wise operations, including shifting left and right. From a Java point of view, the native methods are nontraditional in two respects -- immutability and use of exceptions.

Immutability is a trait that drives Java novices crazy. Trained by years of passing variables by reference to subroutines, many programmers inevitably want to modify a String or Integer object passed to a method, and find that they can't. These classes, like others in the standard Java libraries, are immutable, meaning there's no way to change an instance of them. Once the object is created, you have to replace it wholesale with a new instance with the desired value. This is done largely to provide safety in multithreaded environments. mInt is not immutable; when you add mInt Y to mInt X with the statement X.Add(Y), the result is stored in X, replacing its original value. I did this for performance reasons, since making a numeric class immutable can lead to many object instantiations and place a burden on the garbage collector when performing complex, iterative calculations. Also, I reasoned that mInts will be "specialty classes" used heavily in one area of a program for a calculation that can't be performed with Java's primitive types, and can be easily isolated from threading issues. If you require immutable mInts, it's a straightforward code conversion. I've implemented the Add() method several ways to demonstrate different techniques, including one variation (test2Add()) that shows how to make a native method immutable friendly. (Of course, you'll also have to remove the methods that modify the value of an existing mInt, such as SetFromInt32().)

I didn't use exceptions, preferring instead to use a Windows API-like convention. mInt methods return a Boolean True for success and False for failure, with a specific error code available that contains the last nonzero error code set. The last error code is a static variable, meaning one instance is global to the entire class. Also note that it is not reset by a successful operation. Methods are provided to get, set, get and set, and get and clear the last error value. This design decision is less defensible than the immutability one, and is largely a matter of personal taste. But again, my code can easily be made exceptional, so to speak, and I've provided the test3Add() method in mInt.java (see Listing One) that shows how to do this by wrapping the pedestrian Add() method. You can use this technique to provide both forms of methods in the same class with little performance impact and without code duplication.

Details, Details

Most of the mInt library uses a split implementation, with the real work being done on unsigned versions of mInts in separate subroutines. I find this organization easier to manage because it separates the Java-to-C interface details from the code that does the actual work.

The Add(), Subtract(), conversion, and bitwise operations are straightforward, even though some are implemented in C, and some in Java. (I left the logical operations in Java for the sake of variety; if you need higher-performing versions, they can be ported to C, using the Add() implementation as an example.) Multiplication is also straightforward -- the algorithm merely does a binary version of the manual multiplication method we all learned in grade school, shifting the cumulative result and adding one input to it as needed.

Division is more complicated, requiring you to preshift the denominator until it is as large as possible without making it exceed the value of the numerator. You then build the quotient by setting its low-order bit when the numerator is greater than the denominator, subtracting the denominator from the numerator, then always shifting the denominator right and quotient left. (Describing his algorithm is like trying to describe a spiral staircase without using your hands. Examine the loop in the UDivide() function in MINT.C, and it should make sense.) Because of Java's inability to return more than one output from a function (and because people rarely use both the quotient and remainder from an integer division), I decided to make Divide() and Remainder() separate methods. This could be changed by creating a new class with two mInt members, quotient and remainder, and have a new Divide() method return an instance of this class.

There's almost no detection and handling of special cases in the library. Once you speed up addition, subtraction, and shifting left multiple bits, there's little reason to implement the usual strength-reduction optimizations. For example, an early version of the library did things like detect division by a power of two, then shift one argument to the right the proper number of bits. It turned out that the performance gain for this type of optimization was minimal, and it added overhead to all ordinary operations. (For more on optimization, particularly as related to JNI, see the accompanying text box entitled "Sheng's Optimization Trick.")

Conclusion

If you want to expand or change the mInt library, it's easily rebuilt. First, if you make any changes to the portions of mInt.java that define native methods, you must compile that file with javac, then regenerate the C header, MINT.H (available electronically), with the command javah -jni mint.

Next, make the necessary changes to the C code, rebuild the DLL, and you're done. Obviously, if your changes are local to the C file, such as implementing a new algorithm for an existing method or function, then you can simply rebuild the DLL without changing the .java file or regenerating the header.

Listing One

// mInt library copyright (c) 1997 Lou Grinzo

</p>
import java.lang.System;
class mIntError extends Exception
{
  private int last_error;
  mIntError(int le) { last_error = le; };
  int GetLastError() { return last_error; }
}


</p>
class mInt
{
  private static final int num_components = 8;
  private int the_int[] = new int[num_components];
  private static int last_error = 0;


</p>
  public static final int mInt_OK             = 0;
  public static final int mInt_overflow       = 1;
  public static final int mInt_underflow      = 2;
  public static final int mInt_divide_by_zero = 3;
  public static final int mInt_invalid_char   = 4;


</p>
  // Load the native methods and cache fieldIDs for last_error and the_int
  static
  {
    System.loadLibrary("mInt");
    cacheFID();
  }
  static private native void cacheFID();


</p>
  // Constructors of various flavors //////////////////////
  // See the called Set* methods for more details
  mInt(int x0, int x1, int x2, int x3, int x4, int x5,
    int x6, int x7)
  { Set(x0,x1,x2,x3,x4,x5,x6,x7); }
  mInt(int x)
  { SetFromInt32(x); }
  mInt(mInt x)
  { SetFrommInt(x); }
  mInt(String s)
  { SetFromString(s); }


</p>
  // Accessors and converters /////////////////////////////
  public int[] GetInts()
  {
    int[] x = new int[num_components];
    System.arraycopy(the_int,0,x,0,num_components);
    return x;
  }
  // Treat the ints as hex components of a huge signed integer
  public void Set(int x0, int x1, int x2, int x3, int x4,
    int x5, int x6, int x7)
  {
    the_int[0] = x0;           the_int[1] = x1;
    the_int[2] = x2;           the_int[3] = x3;
    the_int[4] = x4;           the_int[5] = x5;
    the_int[6] = x6;           the_int[7] = x7;
  }
  // Set the low-order int32 and sign-extend
  public void SetFromInt32(int x)
  {
    the_int[num_components - 1] = x;
    int temp = 0;
    if(x < 0)
      temp = -1;
    for(int i = 0; i < num_components - 1; i++)
      the_int[i] = temp;
  }
  // Simply copy the entire the_int array
  public void SetFrommInt(mInt x)
  {
    System.arraycopy(x.the_int,0,the_int,0,num_components);
  }
  public native int SetFromString(String s);
  public native String HexString();
  public native String toString();


</p>
  // Math methods /////////////////////////////////////////
  public void Abs()
  {
    if(the_int[0] < 0)
      Negate();
  }
  public native boolean Add(mInt y);
  public boolean AddInt32(int x)
  { return Add(new mInt(x)); }
  // Demos non-cached field access
  public native boolean testAdd(mInt y);
  // Demos object creation
  public native mInt test2Add(mInt y);
  // Wrap the primitive Add() to use exception
  public void test3Add(mInt y) throws mIntError
  {
    if(!Add(y))
      throw new mIntError(GetAndClearLastError());
  }
  public native boolean Subtract(mInt y);
  public boolean SubtractInt32(int x)
  { return Subtract(new mInt(x)); }
  public native boolean Multiply(mInt y);
  public boolean MultiplyInt32(int x)
  { return Multiply(new mInt(x)); }
  public native boolean Divide(mInt y);
  public boolean DivideInt32(int x)
  { return Divide(new mInt(x)); }
  public native boolean Remainder(mInt y);
  public boolean RemainderInt32(int x)
  { return Remainder(new mInt(x)); }


</p>
  // Compare two mInts, returning -1, 0, or 1 if
  // this is <, ==, or > x, like common C usage
  public native int Comp(mInt x);
  public mInt Max(mInt x, mInt y)
  {
    if(x.Comp(y) >= 0)
      return new mInt(x);
    else
      return new mInt(y);
  }
  public mInt Min(mInt x, mInt y)
  {
    if(x.Comp(y) <= 0)
      return new mInt(x);
    else
      return new mInt(y);
  }
  // Bit twiddlers ////////////////////////////////////////
  public native void    Negate();
  public native boolean ShiftLeft();
  public native void    ShiftRight();


</p>
  public void AND(mInt x)
  {
    for(int i = 0; i < num_components; i++)
      the_int[i] &= x.the_int[i];
  }
  public void OR(mInt x)
  {
    for(int i = 0; i < num_components; i++)
      the_int[i] |= x.the_int[i];
  }
  public void NOT()
  {
    for(int i = 0; i < num_components; i++)
      the_int[i] = ~the_int[i];
  }
  public void XOR(mInt x)
  {
    for(int i = 0; i < num_components; i++)
      the_int[i] ^= x.the_int[i];
  }
  // Error detection methods //////////////////////////////
  int GetLastError()
  { return last_error; }
  int GetAndClearLastError()
  {
    int temp = last_error;
    last_error = mInt_OK;
    return temp;
  }
  int GetAndSetLastError(int x)
  {
    int temp = last_error;
    last_error = x;
    return temp;
  }
  void SetLastError(int new_last_error)
  { last_error = new_last_error; }
}


</p>


</p>

Back to Article

DDJ