Double factorial and primorial
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Tue Dec 20 08:03:08 CET 2011
Ciao,
Il Lun, 19 Dicembre 2011 9:15 pm, Niels Möller ha scritto:
>> In fac_ui.c there already is a function for sieving: bitwise_primesieve.
>> It fills an mp_ptr "with the characteristic function of composite"s, and
>> it returns the count of "prime integers in the interval [4, n]".
>
> That's going to use a lot more memory than necessary. To sieve all
Right, but it was fast to write down and test :-)
> primes up to n, you need to first create a list of primes up to sqrt(n),
> and represent it in any convenient way which lets you iterate over it
> Above sqrt(n), do the sieving blockwise. Create a bitmap of a suitable
> blocksize (it should fit in the cache), let this bitmap represent some
The bitwise_primesieve() works more or less as you suggest. Using the two
functions: first_block_primesieve, and block_resieve.
If we really want a prime_count function in GMP I can write a more clever one
>> counting the primes in [1,2^34] required half the time of
>> (sieving and) multiplying all primes in [1,3*2^28].
>
> So sieving is a significant part of the work for the primorial function.
Counting primes in [1,3*2^28] is 1/60 than counting in [1,2^34], i.e.
1/120 of the time to compute primorial(3*2^28).
> I imagine you already arrange the multiplications so you get roughly
> balanced operations?
Of course, this is done by the function mpz_prodlimbs(), in mpz/fac_ui.c
I'm sure it can be improved ;-)
Regards,
m
--
http://bodrato.it/
More information about the gmp-devel
mailing list