Ciao Adrien,
Il 2022-08-11 17:43 Adrien Prost-Boucle ha scritto:
For primorial, when thinking on the code I considered that the call to
mpz_prodlimbs (x, factors, j)
is the one responsible for (re)sizing x to whatever appropriate for the
result.
Indeed, prodlimbs can resize the mpz_t to the needed size.
(and I think I got confused with the reuse of name x in nested loop)
This was a (stylistic) error of mine.
https://gmplib.org/repo/gmp/rev/d337756619a0
If sizing x correctly before the call mpz_prodlimbs() garantees that
mpz_prodlimbs()
will not resize it, then the current implementation is efficient
indeed.
That's the aim of the code, avoid resizing. I had also another goal:
in the future maybe move the computations to the mpn level...
Does the code success in avoiding resize? But maybe it always allocate a
too large area (that's a waste too)?
The code reads:
size = n / GMP_NUMB_BITS;
size = size + (size >> 1) + 1;
This means that we reserve an area for a result ≤ 2^(n*3/2) ≤ (2.829)^n,
right?
Wikipedia [ https://en.wikipedia.org/wiki/Primorial ] says:
Using more advanced methods, Rosser and Schoenfeld showed that n# ≤
(2.763)^n
and in Theorem 4, formula 3.14, showed that for n≥563, n# ≥ (2.22)^n
Does our code make sense, is it tight enough?
This could have deserved a bit of comment ;-)
If we are sure that the trick works... yes, we should write something
:-)
Ĝis,
m
--
http://bodrato.it/papers/
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
