This is the mail archive of the java@gcc.gnu.org mailing list for the Java project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: Using GMP for BigIntegers.


"Mark J. Roberts" <mjr@statesmean.com> writes:

> So, is GMP in your future?

Yes and no.  We do not want to have libgcj depend on GMP, because that
would "taint" libgcj with GMP's license (the LGPL), which would cause
problems for some users (such as embedded systems).  It would also add
a needless extra complication for people building libjava.  However,
we do want to provide an *option* to use GMP.  This should be a
libjava configuration option.  The default might be true if configure
finds a GMP shared library and false otherwise.

The libgcj BigInteger implementatin is designed to be used with
GMP.  The idea is not to rewrite BigInteger to use use GMP,
but to replace the gnu.gcj.math.MPN class to use GMP.  Notice
that MPN is nothing but a bunch of static methods that work on
arrays of 32-bit words.  Notice also that the API of those
methods are deliberately very similar to that of GMP's "mpn"
functions.

So the plan is to replace MPN with trivial wrappers around GMP mpn
functions.  For example:

public class MPN
{
  public static native int add_1 (int[] dest, int[] x, int size, int y);
  ....
}

jint gnu::gcj::math::MPN::add_1 (JArray<jint>* dest, JArray<jint>* x,
        jint size, jint y)
{
#ifdef USE_GMP
    return mpn_add_1 ((mp_limb_t *) elements(dest), (mp_limb_t *) elements(x),
        (mp_size_t) size, (mp_size_t) y)
#else
    // Transcription from the Java version.
    jlong carry = (jlong) y & 0xffffffffL;
    for (jint i = 0;  i < size;  i++)
      {
        carry += ((jlong) x[i] & 0xffffffffL);
        dest[i] = (int) carry;
        carry >>= 32;
      }
    return (jint) carry;
#endif
}

This approach of using the GMP mpn functions has these advantages:

* Gain the speed advantages of low-level (sometimes assembly) gmp routines.

* Handle memory allocation at the Java level, without the complications
of mpz-level memory management.

* Only a single heap object for "short* numbers (up to one limb's worth).
Only a two fields (ival and words) needed per BigInteger.

You might be able to avoid some function calls, by combining the
BigInteger and MPN classes into one class, and calling the mpn
functions directly when USE_GMP is set.  Perhaps:

#ifndef USE_GMP
static mp_limb_t
mpn_add_1 (mp_limb_t *RP, const mp_limb_t *S1P,
          mp_size_t SIZE, mp_limb_t S2LIMB)
          const mp_limb_t *S2P, mp_size_t SIZE)
{
  // some simple compact portable implementation of mpn_add_1
  // There may be a issue if we want to avoid copyright "tainting".
  // That is reduced if we use the Java MPN implementation,
  // and do not look at the C mpn version.
}
#endif

jint gnu::gcj::math::MPN::add_1 (JArray<jint>* dest, JArray<jint>* x,
        jint size, jint y)
{
    return mpn_add_1 ((mp_limb_t *) elements(dest), (mp_limb_t *) elements(x),
        (mp_size_t) size, (mp_size_t) y)
}

This can now be inlined - i.e. replace MPN.add_1 by mpn_add_1.

A tricky problem is how to handle machines for which gmp uses
64-bit "limbs".  My suggestion is to change ival to long and
words to long[] (for all machines); on 32-bit machines you would
treat each "long limb" as two limbs.  (You have to be careful
with endianess, though.)

One thing that really sucks with BigInteger is all the extra fields
that were added for Serialization.  We do want the serialization
format to match Sun's, but having duplicate fields is really bad.
The implementations of readObject and writeObject should be
fixed.

We would also be interested in a details about the bug you found.

> I'm probably going to add GMP support to my
> libjava anyway, so I can probably provide a rough implementation to use as
> a starting point really soon. If you're interested...

We are, assuming you make GMP be optional and not required.  I also
strongly suggest using the GMP mpn function and not the mpz functions.
-- 
	--Per Bothner
per@bothner.com   http://www.bothner.com/~per/

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]