mpz_prevprime

[Seth Troisi]

On Mon, Mar 9, 2020 at 2:05 AM Marco Bodrato <bodrato at mail.dm.unipi.it>
wrote:

> Ciao,
>
> Il 2020-03-09 02:56 Seth Troisi ha scritto:
> > From Marco Bodrato's analysis I got inspired and modified nextprime to
>
> Your analysis is much deeper than mine :-)
> I do not have much time now... but I glanced at the code and write here
> a few comments.
>
Thanks for the comments, I'll improve the code with these in mind.


> > You can see some of my thresholds and testing input in this google
> > sheet[1]. The end result is sieve up ~ LOG2(N) ^ (20/7) / 3268
>
> Funny numbers :-)


>
In the code, you compute LOG2(N) ^ (20/7) / 3268. (A comment says "/
> 1880")

I updated the comment and tweaked the constant again

>

Then, if the result is greater than 430000000, you cut it.
> Cutting seems a good idea, but I'd do the reverse:
>   if nbits is larger than (430000000*3268) ^ (7/20) = 17940, set limit to
> 430000000,
>   compute otherwise.

Happy to do it this way.

>
>
> For 10,000 bit numbers this sieves up to 80 million (which takes ~4
> > seconds but reduces nextprime from ~300seconds to ~200 seconds)
>
> Seems interesting :-)
>
> > I cleaned up the code without any of the debug printing in the 3rd
> > patch nextprime_sieve_clean.patch which I'd love people to consider
>
> Some random comments:
>
> If you use TMP_DECL, then you don't need to use also TMP_SDECL.
> The same for TMP_MARK and TMP_SMARK; or TMP_FREE and TMP_SFREE.
>
Thanks

>
> I'm happy to see that you used gmp_primesieve and the macros for it,
> but...
> ... maybe that code is too messy? I mean, my code with the
> LOOP_ON_SIEVE_ macros...
> You did not use that sieve to directly loop on primes, but you used it
> to loop on primes for building a primegap table, and then use that table
> to loop on primes...


It's highly possible I misunderstand how these macros are supposed to be
used.
I also dislike the boiler plate of the macros but I didn't like handrolling
my own sieve
or sacrificing a huge amount of speed by using  gmp_nextprime (~8x slower).

I don't understand "I mean, my code with the LOOP_ON_SIEVE_ macros..."

If you have suggestions or code pointers for a better pattern I'd
appreciate that.



Did you try to use the gmp_primesieve function directly?
>
I'm not sure what you're referencing here, I tried with
gmp_primesieve_t ps;
gmp_init_primesieve (&ps);
prime = gmp_nextprime (&ps);
but it was ~8x slower

If sieve_limit = 430000000, you are allocating 17M for mp_limb_t *sieve,
> then another 22M for primegap_tmp, and both are kept in memory.
> I believe that looping with primegap is faster, but... how many times do
> we need too loop, on average? I mean, how often is the /*Sieve next
> segment*/ code used?
>

next_mult is also in memory so another 88 MB, I didn't think ~100M of RAM
in the worst case was very much.
If that's an issue we can always reduce the max sieve_limit to 200M or 100M
and reduce max memory.

Is there a way to unalloc a TMP_ALLOC_LIMBS before TMP_FREE?

Sieve next segment is rare, the average gap is ln(n), if INCR_LIMIT was
changed to be a variable it could be set
so /*sieve next segment*/ happened on average less than once, and then the
primegap array could be removed as you're correct in guessing it's not the
slow part.


> In the array char *sieve, you use only the even entries. Maybe you can
> reduce its size by half, and remove some "*2" around the code?
>
it's only 4000 entries so I wasn't bothering at this time, but it would be
easy to change.

Ĝis,
> m
>

Thanks for the comments, they have given me more energy to work on this.