More accurate calculation of sieve array size
bodrato at mail.dm.unipi.it
Thu Aug 11 23:22:53 CEST 2022
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
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
> will not resize it, then the current implementation is efficient
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 [ https://en.wikipedia.org/wiki/Primorial ] 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