More accurate calculation of sieve array size

[Marco Bodrato]

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/