CLN, GMP inputs

[Hans Aberg]

I had a look at the (non-GNU) CLN, a C++ number library built on top of GMP
(a URL is mentioned on GNU's all software; for some reason GMP is not
listed there).

Here are some of its features that I think might be integrated into GMP
(but the stuff below is just some inputs):
- Finite Z/nZ numbers.
- Uses ref count. (But this is the traditional variation with double memory
allocations, I think.)
- Uses "unboxed" (no pointer, non-dynamic) representation for small numbers.

As for the Z/nZ types, I have the idea of a type binary<n> with exactly n
bits, where n is natural number, which should be the generalization of the
C/C++ integral types. C/C++ are so written that one never can ensure the
exact number of bits from compiler to compiler, so therefore I think a
library with such a low-level optimized type might be useful.

Then, when n is not 2^k (or 0), one gets the other Z/nZ. I also know that
in cryptology, one uses the finite fields F_{p^k}, where p is a prime
number, and k is an integer >= 1. As speed is crucial in such contexts, it
might be interesting to have library functions for such fields.

As for the ref count and the unboxed number representation, perhaps it is
possible to implement it on the C-level: One only mimics what one might do
in C++. I then get ideas along the following lines:

In gmp.h, one defines something like:

typedef struct {
  union {
    mp_int     _mp_n;
    mp_limb_t* _mp_all;  /* Pointer to all.  */
  };
  int unboxed;
} __mpz_struct;

#define _mpz_alloc  _mp_all[0]
#define _mpz_count  _mp_all[1]
#define _mpz_size   _mp_all[2]
#define _mpz_d      _mp_all + 3


typedef struct {
  union {
    mp_float   _mp_f;
    mp_limb_t* _mp_all;         /* Pointer to all.  */
  };
  int unboxed;
} __mpf_struct;

#define _mpf_prec  _mp_all[0]
#define _mpf_exp   _mp_all[1]
#define _mpf_count _mp_all[2]
#define _mpf_size  _mp_all[3]
#define _mpf_d     _mp_all + 4

Here, mp_int and mp_float are the unboxed number representations (say the
word optimal int and double).

Then in order to handle the ref count, one needs to add:
  void mpz_detach(mpz_ptr);
  void mpf_detach(mpz_ptr);
removing the argument from the reference cluster. A definition might look like
  void mpz_detach(mpz_ptr x) {
    if (x->unboxed && x->_mp_z_count > 1) {
      mpz_shed(x);
      x->_mp_all = mpz_clone(x->_mp_all);
    }
  }

If, in addition, the library should be thread safe, one needs something like
  void mpz_lock(mpz_ptr);
  void mpz_unlock(mpz_ptr);
  void mpf_lock(mpz_ptr);
  void mpf_unlock(mpz_ptr);
-- I figure that the library isn't thread safe as it now stands, because
the functions gets references to objects, and if those referenced objects
are not locked, another thread might screw it up by changing them too in
mid-computation.

The programming style then becomes:

mpz_add(mpz_ptr w, mpz_srcptr u, mpz_srcptr v) {
  mpz_lock(w); mpz_lock(u); mpz_lock(v);
  mpz_detach(w);
  if (u.unboxed && v.unboxed) /* Set w = u + v */
  ...
  mpz_unlock(w); mpz_unlock(u); mpz_unlock(v);
}

Where the ... is essentially as before.

Possibly this might work.

  Hans Aberg