Problem with gmp_randinit_set
Marco Bodrato
bodrato at mail.dm.unipi.it
Thu Mar 2 20:37:52 UTC 2017
Ciao,
Il Mar, 21 Febbraio 2017 5:14 pm, Pedro Gimeno ha scritto:
> Marco Bodrato wrote, On 2017-02-21 15:21:
>> value and (2^n-k-value) will be mangled to the same seed...
>> <snipped additional problem>
>
> Well, these are more bugs then.
> As I said it's all or nothing. Either compatibility is kept, or the
> whole thing is changed to a better and faster seeding function.
Maybe a compromise is possible.
I attach a patch, it applies to the current development code... it is not
meant to be simply a proposed replacement for the seeding function, it's a
proof of concept.
It extends the seeding xxtea_randseed_mt() function proposed by Pedro
Gimeno taking into account also the highest bit, in such a way that:
- every seed in the range 0 <= seed < 2^19936 generate a different
random sequence;
- every seed in the range 2^19936 <= seed < 2^19937 generate a different
random sequence;
- there are exactly two seeds 0 <= seed1 < 2^19936 <= seed2 < 2^19937
that generate the same sequence. (It's easy to compute both, if needed)
I recall that with the current function there are (literally) dozens of
seeds giving the same sequence in the range 0 <= seed < 2^19937, with the
proposed one there is a single couple, for a grand total of exactly
2^19937-1 different sequences.
It defines a legacy_randseed_mt() function that manipulates the given seed
to obtain the value that must be passed to the xxtea_randseed_mt()
function to generate exactly the same sequence that the old (current)
randseed_mt() function generates.
The attached patch uses legacy_randseed_mt. So that nothing changes.
Of course the real proposal is to _change_ the randseed function, and to
give (as an internal extra function, or as a source code to be inserted in
programs needing it) a function that allows anyone to obtain the same
sequences GMP generated till today.
Comments are welcome,
mb
PS: there is at least one program requiring that our random functions
generate exactly the expected numbers for some given seeds:
tests/mpz/t-gcd.c
--
http://bodrato.it/papers/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: rand.patch
Type: text/x-patch
Size: 4299 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-bugs/attachments/20170302/1eb74d72/attachment.bin>
More information about the gmp-bugs
mailing list