Problem with gmp_randinit_set

[Marco Bodrato]

Ciao,

Il Lun, 20 Febbraio 2017 10:18 am, Marco Bodrato ha scritto:
> fear) give a number greater than 2^19937 as a result. Even if we
> change them to take care of the possible carry in those last
> additions, we may have problems with the (few!) numbers in the range
> 2^19937-20000..2^19937.

I realized that I can stop being worried :-)
Niels' code, mine, and the current one behave exactly the same with
classes modulo 2^19937-20023 with two possible representation in
[0..2^19937[.
They all will represent the numbers (n) in the range 0..20022 with their
equivalent (2^19937-20023+n). The sketched proof follows.

Lemma 1: if x >= 20023, reduced(x) >= 20023.

Two cases:

a) x < 2^19937, all proposed reduction code will give reduced(x)=x.

b) x >= 2^19937, all proposed reduction code compute (with some n>=0):
  lower(x) + higher(x) * 20023 * 2^n
where higher(x) is zero iif lower(x) == x.
If higher(x)==0 , then reduced(x)=x >= 20023.
If higher(x)>=1 , then reduced(x) >= higher(x) * 20023 >= 20023.

Proof:
The input value r of mangle_seed(r) is r>=2, during exponentiation (e>20)
the variable will eventually become bigger than 20023 (2^20>20023).

Thanks to Lemma 1, once the values get larger than 20023, it will remain
larger till the end of the function.

I may try to remove the mpz dependency from file rand/randmts.c ...

Best regards,
m

-- 
http://bodrato.it/papers/