Double factorial and primorial

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> _facfac_ or _dblfac_ ?

Since the established name is "double factorial", I think one should use
some reasonable abbreviation of that term. _dblfac_ seems good enough to
me, if _double_fac_ is too long.

> I believe that it is worse than factoring. By the way I implemented only
> mpz_primorial_ui (as we have _fac_ui), i.e. I did not implement primorial
> for general mpz_t numbers, but for unsigned int only.

For mpz_fac_ui, the most obvious limitation on what can be computed is
the size of the output. (2^32)! is 122 GB, which you probably wouldn't
want to compute on a 32-bit machine. (2^64)! is some 1049537417 TB, which
seems even more unreasonable. I don't know how to compute
log(promordial(n)), but I imagine it will also be pretty large.

But for computing the *number* of primes up to, output size is no issue.
The question is the computation time as a function of the input size. I
wouldn't be surprised if inputs larger than a single limb are totally
unreasonable, but I'm not sure.

Hence, the comparison with factoring, 64 bit numbers seem easy. Counting
the number of primes up to 2^64 may well be a lot harder. Maybe there's
no better way to compute the number of primes than to use the sieve of
Erathostenes' to generate them all?

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.