Nearly finished (re)integrating GMP for bignums.

Nearly finished (re)integrating GMP for bignums.

[Rob Browning]

I've finished much of the work (re-doing it after losing my previous
effort :<), but I still have to figure out how to handle the
ipv6->bignum code in sockets.c, and how to deal with random.c.  In the
former, raw operations are used.  I'm tempted to just rewrite the
computation as mathematical operations on the input char[] items
rather than trying to optimize it with larger memcpy operations.
Thoughts?  One thing I note is that it looks like the code presumes
that an INUM will always fit into a 32bit integer.  Do we guarantee
that, or is there the possibility we might allow 64bit inums?  I
wasn't sure which guarantees we planned to make.

With respect to random.c, we have a pluggable random number system,
and ATM the bignum randoms are computed using the
"get_32_random_bits()" function provided by the random state object.
However GMP has its own random number generators, including ones for
bignums.  Any thoughts on how we should handle this?

After I get the system to compile, I'll then be adding tests (and
probably benchmarks).  I don't want to commit it until I feel fairly
confident its correct, and hopefully have some sense of the relative
performance.

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Nearly finished (re)integrating GMP for bignums.

[Marius Vollmer]

Rob Browning <rlb@defaultvalue.org> writes:

> One thing I note is that it looks like the code presumes
> that an INUM will always fit into a 32bit integer.  Do we guarantee
> that, or is there the possibility we might allow 64bit inums?  I
> wasn't sure which guarantees we planned to make.

Aren't we already using 64 bits for scm_t_bits on some platforms (such
as the Alpha and IA64)?  Even if we don't, code should use
SIZEOF_SCM_T_BITS, etc.

> With respect to random.c, we have a pluggable random number system,
> and ATM the bignum randoms are computed using the
> "get_32_random_bits()" function provided by the random state object.
> However GMP has its own random number generators, including ones for
> bignums.  Any thoughts on how we should handle this?

I think we should use the GMP generators unless they are not as good
as ours.  But I doubt that.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Nearly finished (re)integrating GMP for bignums.

[Rob Browning]

Marius Vollmer <mvo@zagadka.de> writes:

> Aren't we already using 64 bits for scm_t_bits on some platforms (such
> as the Alpha and IA64)?  Even if we don't, code should use
> SIZEOF_SCM_T_BITS, etc.

I'm not sure.  It's been a while since I was messing around with guile
on a 64 bit platform (last time was porting issues on an alpha and
ia64).  I can check...

>> With respect to random.c, we have a pluggable random number system,
>> and ATM the bignum randoms are computed using the
>> "get_32_random_bits()" function provided by the random state object.
>> However GMP has its own random number generators, including ones for
>> bignums.  Any thoughts on how we should handle this?
>
> I think we should use the GMP generators unless they are not as good
> as ours.  But I doubt that.

Hmm, OK.  Well for now I may see about just trivially integrating the
gmp bignums into the current "plugin" system which only allows for a
generator to generate 32 random bits at a time.  If I do, I'll list
"coming back later to see if we should rearrange things more
thoroughly" as a TODO item.

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Nearly finished (re)integrating GMP for bignums.

[Mikael Djurfeldt]

Marius Vollmer <mvo@zagadka.de> writes:

>> With respect to random.c, we have a pluggable random number system,
>> and ATM the bignum randoms are computed using the
>> "get_32_random_bits()" function provided by the random state object.
>> However GMP has its own random number generators, including ones for
>> bignums.  Any thoughts on how we should handle this?
>
> I think we should use the GMP generators unless they are not as good
> as ours.  But I doubt that.

This is actually a little tricky.  I'd like to bring up two points
about this issue:

1. Marius, do you suggest to use the GMP generators as a source of
   random bits for random.c, that is to "plug in" the GMP generator as
   a replacement for scm_i_uniform32?

   That would be OK, but using scm_i_uniform32 "in parallel" with the
   GMP generators would probably not be.

   It is a dangerous mistake to use multiple pseudo-random generators
   within the same application, the reason being that while each
   generator on its own will have an extremely long cycle in its
   number series, interference between the series can give
   deterministic behavior.  For example, the difference between the
   outputs of two generators might have a short cycle.  Interference
   can occur in any number of strange ways if two generators
   simultaneously affect the same program.

2. What do you mean by a "good" RNG?  I'd say it is good if it is
   fast.  Our generator is fast.  Can you name any single other
   criterion which is not "religious" and which our generator doesn't
   fulfil?  (I'm talking about something measurable here.)

   I'm no expert in RNG:s, but when doing research before writing
   random.c I couldn't find any arguments against using the current
   MWC generator.  As stated in a commentary in random.c, it has a
   cycle length of 4.6e18 and passes all tests in the "DIEHARD" RNG
   test suite.  At any rate, it should be sufficient for standard
   Guile use.

   (For those doubting the utility of speed in a RNG, I can only note
   that for me it's very important.  In my simulation software I often
   generate large random matrices and need to have multiple sources of
   simulated "noise".)

Ideally, the bignum code would use the pluggable source of random bits
in random.c and the GMP generators would be provided as optional
plugins for random.c.  Rob, is this possible?

Mikael


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Nearly finished (re)integrating GMP for bignums.

[Rob Browning]

Mikael Djurfeldt <djurfeldt@nada.kth.se> writes:

> 2. What do you mean by a "good" RNG?  I'd say it is good if it is
>    fast.  Our generator is fast.

I wonder how fast the GMP RNGs are (I currently have no idea).

> Ideally, the bignum code would use the pluggable source of random
> bits in random.c and the GMP generators would be provided as
> optional plugins for random.c.  Rob, is this possible?

I'm not sure yet -- what I was considering was if (in the short term)
I can just replace the one BIGNUM based chunk of code in there with
calls to manipulate GMPs (or just calls to scm_i_big* functions).  At
the very least, the code has to be changed so that it doesn't try to
manipulate BIGDIG stuff directly anymore since all the implementation
specific stuff is gone.

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Nearly finished (re)integrating GMP for bignums.

[Rob Browning]

Mikael Djurfeldt <djurfeldt@nada.kth.se> writes:

> Ideally, the bignum code would use the pluggable source of random bits
> in random.c and the GMP generators would be provided as optional
> plugins for random.c.  Rob, is this possible?

The main issue I have now is that in scm_c_random_bignum, the code
directly manipulates the old bignum internals.  So I'll need to
convert that to GMP. i.e.:

  LONG32 *bits, mask, w;
  nd = SCM_NUMDIGS (m);
  /* calculate mask for most significant digit */
#if SIZEOF_INT == 4
  /* 16 bit digits */
  if (nd & 1)
    {
      /* fix most significant 16 bits */
      unsigned short s = SCM_BDIGITS (m)[nd - 1];

To be sure have the details right -- SCM_NUMDIGS gives the number of
elements in SCM_BDIGITS, where the last element is the most
significant digit right?

I'll need to figure out how this should map onto the available GMP
operations.  Right now I don't expose much from numbers.c
"bignum-wise", but I'm thinking of adding some _i_ functions that map
onto gmp operations, and would probably also be appropriate for any
other bignum implementation, i.e.:

  void scm_i_bigadd_ui (SCM dest, SCM src, unsigned long n);
  void scm_i_bigsub_ui (SCM dest, SCM src, unsigned long n);
  void scm_i_bigneg (SCM dest);

etc.  These prototypes follow the GMP calling convention which can be
convenient since it allows you to express both "in-place"
modifications where dest == src, or copy operations where dest != src.
The ability to do "in-place" operations can be important when dealing
with large bignums because you don't necessarily want to have to
allocate a new bignum for each operation.

Alternately, I could just support in-place operations:

  void scm_i_bigadd_ui (SCM big, unsigned long n);

or I could only support our more traditional "always copy on write"
style operations:

  SCM scm_i_bigadd_ui (SCM big, unsigned long n);

The whole point of the scm_i_big* functions would be for use by other
parts of guile where the code needs to operate directly on bignums.

The alternative is to just expect the other code use SCM_I_BIG_MPZ(x),
to get hold of the mpz_t value and then manipulate that directly.  The
direct approach could be faster, and gives more flexibility, but of
course it's less portable (presuming we ever change our bignum
implementation again).

In truth, ATM we don't have that much code outside numbers.c that
manipulates bignums directly.  Aside from the GC and eq, it's mostly
random.c and socket.c so far.  So it may not be a big deal either way.

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Nearly finished (re)integrating GMP for bignums.

[Kevin Ryde]

Mikael Djurfeldt <djurfeldt@nada.kth.se> writes:
>
> 2. What do you mean by a "good" RNG?  I'd say it is good if it is
>    fast.

In gmp we're looking at a Blum-Blum-Shub algorithm for possible
inclusion, it's based on cryptographic principles, and so supposedly
suits such applications (which are rather specialized of course).

>    Our generator is fast.  Can you name any single other
>    criterion which is not "religious" and which our generator doesn't
>    fulfil?  (I'm talking about something measurable here.)

For reference, the next gmp will be have a Mersenne Twister generator
contributed by Pedro Gimeno, and it'll be the default too
(gmp_randinit_default).  It's fast, and very random according to those
who pay attention to such things (I'm no expert).

Rob Browning <rlb@defaultvalue.org> writes:
>
> I wonder how fast the GMP RNGs are (I currently have no idea).

The current linear congruential generator isn't as good as it could
be, it uses bignum operations even for the common case of a modulus
that fits in one or two machine words.

Mersenne Twister ought to end up being as fast or faster than L-C, and
the lack of randomness of L-C is well-known, so there oughtn't be any
direct call for the latter any more, not except maybe for special
purposes like experimenting with very un-random sequences.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Nearly finished (re)integrating GMP for bignums.

[Rob Browning]

Mikael Djurfeldt <djurfeldt@nada.kth.se> writes:

> Ideally, the bignum code would use the pluggable source of random bits
> in random.c and the GMP generators would be provided as optional
> plugins for random.c.  Rob, is this possible?

For now, I think I'd like to consider just translating the existing
scm_c_random_bignum to manipulate mpz_t values rather than the old
bignum digits.

If you (or anyone else) is familiar with this function, could you
explain the critical parts?  I can probably figure out how to
translate it eventually by just looking at the code, but that process
would probably go a lot faster if I had an overview.

I'd like to know things like how critical it is that it operate on
16-bit chunks -- what interdependencies does that create, etc.  If
possible, it'll probably be faster and easier to work with larger
chunks when manipulating the mpz_t's.

Thanks

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Nearly finished (re)integrating GMP for bignums.

[Mikael Djurfeldt]

Rob Browning <rlb@defaultvalue.org> writes:

> Mikael Djurfeldt <djurfeldt@nada.kth.se> writes:
>
>> Ideally, the bignum code would use the pluggable source of random bits
>> in random.c and the GMP generators would be provided as optional
>> plugins for random.c.  Rob, is this possible?
>
> For now, I think I'd like to consider just translating the existing
> scm_c_random_bignum to manipulate mpz_t values rather than the old
> bignum digits.
>
> If you (or anyone else) is familiar with this function, could you
> explain the critical parts?  I can probably figure out how to
> translate it eventually by just looking at the code, but that process
> would probably go a lot faster if I had an overview.

Sorry for not answering earlier.  I've been away on vacation.

The logic is very simple:

SCM scm_c_random_bignum (scm_t_rstate *state, SCM m)

Takes a random state (source of random bits) and a bignum m.
Returns a bignum b, 0 <= b < m.

It does this by allocating a bignum b with as many base 65536 digits
as m, filling b with random bits (in 32 bit chunks) up to the most
significant 1 in m, and, finally checking if the resultant b is too
large (>= m).  If too large, we simply repeat the process again.  (It
is important to throw away all generated random bits if b >= m,
otherwise we'll end up with a distorted distribution.)

Here's the step-by-step description:

1. Compute a 32-bit bitmask for use when filling bits into the most
   significant long word in b's bit space.  A combination of
   conditionals and an 8-bit lookup table (scm_masktab) is used.

2. Allocate b and assign the bit space address to the variable "bits".

3.1 Generate the most significant bits using the mask.

3.2 Fill up the rest of the bit space.

3.3 Use scm_i_normbig to cut away leading zeros and/or convert to inum.

3.4 If b >= m, go to 3.1.

4. return b

> I'd like to know things like how critical it is that it operate on
> 16-bit chunks -- what interdependencies does that create, etc.

No dependencies, except that you'd obviously have to adjust the
conditionals for generating the mask.

> If possible, it'll probably be faster and easier to work with larger
> chunks when manipulating the mpz_t's.

I suggest you work with 32-bit chunks since this is what is returned
by scm_the_rng.random_bits (state).

Best regards,
Mikael


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Nearly finished (re)integrating GMP for bignums.

[Mikael Djurfeldt]

Mikael Djurfeldt <djurfeldt@nada.kth.se> writes:

> The logic is very simple:

I've now inserted this description into proper places in random.c and
comitted it to CVS.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Nearly finished (re)integrating GMP for bignums.

[Rob Browning]

Mikael Djurfeldt <djurfeldt@nada.kth.se> writes:

> It does this by allocating a bignum b with as many base 65536 digits
> as m, filling b with random bits (in 32 bit chunks) up to the most
> significant 1 in m, and, finally checking if the resultant b is too
> large (>= m).  If too large, we simply repeat the process again.
> (It is important to throw away all generated random bits if b >= m,
> otherwise we'll end up with a distorted distribution.)

It looks like the old code handled 16-bit chunks at a time.  I just
wanted to make sure it was OK to go ahead and use the full "unsigned
long" random_bits range per-chunk instead if that works out better.

Thanks

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Nearly finished (re)integrating GMP for bignums.

[Mikael Djurfeldt]

Rob Browning <rlb@defaultvalue.org> writes:

> Mikael Djurfeldt <djurfeldt@nada.kth.se> writes:
>
>> It does this by allocating a bignum b with as many base 65536 digits
>> as m, filling b with random bits (in 32 bit chunks) up to the most
>> significant 1 in m, and, finally checking if the resultant b is too
>> large (>= m).  If too large, we simply repeat the process again.
>> (It is important to throw away all generated random bits if b >= m,
>> otherwise we'll end up with a distorted distribution.)
>
> It looks like the old code handled 16-bit chunks at a time.  I just
> wanted to make sure it was OK to go ahead and use the full "unsigned
> long" random_bits range per-chunk instead if that works out better.

No, in fact, the old code also used all 32 random bits a long word at
a time.  And, yes, that should be OK with our RNG.

M


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel