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

[Mikael Djurfeldt]

Rob Browning <address@hidden> writes:

> Mikael Djurfeldt <address@hidden> 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