More accurate calculation of sieve array size

Marco Bodrato bodrato at
Thu Aug 11 23:22:53 CEST 2022

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.

> 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, 

Wikipedia [ ] says:

     Using more advanced methods, Rosser and Schoenfeld showed that 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 



More information about the gmp-devel mailing list