about prime number generation
Marco Bodrato
bodrato at mail.dm.unipi.it
Sat May 21 09:14:26 CEST 2022
Ciao,
> On Thu, 2022-05-19 at 18:59, Garcia Moreno-Esteva, Enrique wrote:
>> Thank you for writing. Yes, I have looked into it. It is not
>> that fast once you get to really larger numbers, say past 10^10.
Well, I'm sure that the implementation that we could add to GMP would
not be faster :-/
Il 2022-05-19 23:41 Adrien Prost-Boucle ha scritto:
> To my eyes (and for gmp too) 10^10 is really small number
> for example ;-)
If you put 10^10 in an mpz_t variable and use it for simple arithmetic,
I agree, that's small for GMP.
But if you set an unsigned long to 10^10, and use it as the parameter
for some functions internally using primes... it's not that small.
Think to the following function calls:
mpz_fac_ui (z, 10000000000);
mpz_primorial_ui (z, 10000000000);
mpz_bin_ui (z, z, 10000000000);
> Around 10^10, this is roughly the 450 million-th, which is
> found in 20 msec on my laptop.
My code is some 50 times slower, and probably even worse when the size
grows.
> On the other side, the 450 million first primes are found
> in 20 minutes on the same machine (personal code,
There's a function for sieving in the file primesieve.c.
It needs a pointer to (10000000000/3/GMP_LIMB_BITS)+1 limbs, then
gmp_primesieve (pointer_to_sieve, 10000000000);
should sieve the 0..10000000000 range (with the Erathostenes' sieve) in
some tenths of seconds.
It does not generate the list of primes, but a compact bitmap.
And of course, the multi-threaded primesieve (by the same author of
primecount) is even faster :-)
Ĝis,
m
--
http://bodrato.it/papers/
More information about the gmp-discuss
mailing list