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:


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
To explain the mathematics with int and long, the next fragment should explain enough: An int value is easily converted into an long by masking it with the long value 0x00000000ffffffffL.
   * 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;
Using this technique, all functions were implemented.

Montgomery transformation

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
Montgomery's basic idea is: Instead of calculating the modulo to m, which can be any number, the input numbers are transformed that m' = 2**n, which makes modulo and division computations very easy and fast, since you either shift right or you omitt leading bits. The normal multiplication is then completed by an reduction algorithm, which also does the back transformation for the result.
  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')

  res = montgomery(r')
Since the montgomery function is much faster than the previous modulo computation, a big speedup is the reward! For further information have a look to


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:

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.


Explaining the results

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.


Verify it

Download the implementation 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