Double factorial and primorial

[bodrato at mail.dm.unipi.it]

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/