Java speed measurement with the BigInteger.class

Since there are still JVMs available which come to you with some missing packages or classes (e.g. Netscape on MAC), there was a need for some classes to be coded (again). One of these classes is the java.math.BigInteger.class, which is required for RSA computations.

But it's not enough to implement some kind of a solution, it's a must to compete with existing solutions!

This article compares the own solution to 3 different JVMs.

The design of the implementation is very simple:

• For performance issues the largest possible word size was chosen: The type int, which allows to handle int overflows with the type long.
• To reduce overhead by copying data, all basic function implementations are using int arrays instead of BigIntegers.
• So BigInteger API functions are often only wrapper functions for the real implementation.
• The implementation should require no other (helper) classes.

This lead to this internal representation:

  private int []  data;     // data for BigInteger
  private int     len;      // used range in data
  private boolean positive; // sign of current number

  /**
   * Internal function to perform an addition on big integer arrays.
   * Pseudeo: res = a + b
   * @param res int array for the result. This array must be large enough to keep the result (al+1).
   * @param a int array of first operand.
   * @param al length of first operand. Regard: al >= bl.
   * @param b int array of second operand.
   * @param bl length of second operand.
   */
  private static int add(int [] res, int [] a, int al, int[]b, int bl)
  {
    long carry = 0;
    int i;
    for(i = 0; i < bl; ++i)
    {
      carry += a[i] & 0xffffffffL;
      carry += b[i] & 0xffffffffL;
      res[i] = (int)carry;
      carry >>= 32;
    }
    for(; carry != 0 && i < al; ++i)
    {
      carry += a[i] & 0xffffffffL;
      res[i] = (int)carry;
      carry >>= 32;
    }
    if (res != a)
    for(; i < al; ++i)
      res[i] = a[i];

    if (carry != 0)
      res[al++] = 1;

    return al;
  }

A special focus lies on the modPow function, which uses the Montgomery transformation to increase its speed. Let's regard the basic algorithm of modPow:

  given a, e, m => res = a**e mod m

  res = 1
  for b = each bit in e, from highest to lowest bit do
    res = res * res mod m
    if b == 1 then res = res * a mod m
  od

  given a, e, m => res = a**e mod m

  res = 1

  a' = 2**n * a mod m
  r' = 2**n * res mod m

  for b = each bit in e, from highest to lowest bit do
    r' = montgomery(r' * r')
    if b == 1 then r' = montgomery(r' * a')
  od

  res = montgomery(r')

After completion (and some testing) a set of test functions was written to verify the identity of the results and measure the speed of different computations:

• addition
• subtraction
• multiplication
• modulo
• modPow

Microsoft (R) Befehlszeilenlader für Java Version 5.00.3310
Copyright (C) Microsoft Corp 1996-2000. Alle Rechte vorbehalten.

Symantec Java! JustInTime Compiler Version 3.10.107(i) for JDK 1.1.x
Copyright (C) 1996-99 Symantec Corporation

java version "1.3.0"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.3.0-C)
Java HotSpot(TM) Client VM (build 1.3.0-C, mixed mode)
Copyright © 1995-2000 Sun Microsystems, Inc.

As you notice addition and subtraction are performing at the same speed. The first surprise is that Microsofts and Symantecs JVM is faster than my implementation at all other operations, while addition and subtraction - which are much easier to implement - are much slower. The solution: Microsoft and Symantec JVM are using native functions!

The Sun implementation with the Sun JVM performs nearly as fast as my implementation, but its size is 3 times larger.

• Good native implementations, gain speed by factor 3. (Microsoft native functions)
• Normal native implementations can't compete to Java! (Symantec native functions)
• It's worth to verify the implementations of all big vendors, there is still gain in speed and size.
• The Microsoft JIT and the Symantec JIT are similar in speed. The gap in addition and subtraction is probably based on slower function calls in Symantec.
• The Sun JIT performs about 50% slower than Symantec or Microsoft JIT for the measured functions.

Download the implementation de.bb.math.BigInteger.class and the test program and test it with your JVM. The values used above are for the last pass with 2048 on Windows 2000 with a Duron 650MHZ. For questions and submissions contact the author.

Copyright © 1999/2000 F.Fischell / S. Franke
last update 19.11.2000