Ciao,
Il 2020-03-24 18:54 Seth Troisi ha scritto:
On Tue, Mar 24, 2020 at 9:56 AM Marco Bodrato
<bodr...@mail.dm.unipi.it> wrote:
I propose a variation of your patch, you find it attached, on my
computer it's faster.
Couple of small notes but otherwise this looks good
+/* NP_SMALL_LIMIT = prevprime (LAST_PRIME ^ 2) */
In the light of the day this can be bumped slightly to
prevprime(nextprime(LAST_PRIME)^2) - 1 = 316960
I'm not sure.
I mean: with that list of primes we can certify primality up to that
limit, I agree.
But what about the exit condition?
The current code consider that a number is prime if(n/prime<prime).
To support n > LAST_PRIME^2, we should add one more branch in the loop.
+ /* Technically this should be prev_prime(LAST_PRIME ^ 2) */
I'd remove this, It's covered by the comment above
Right.
+ if (q < prime)
+ return t;
+ if (r == 0)
+ break;
Can this be rearranged to
+ if (r == 0)
+ break;
+ if (q <= prime)
+ return t;
I fear it can't. The case t=3, prime=3 would consider 3 a composite.
Moreover I believe that, on some architectures, q can be ready before r
is, so the order Torbjorn used should reduce latency. But I may be wrong
on that point.
The case t=3 can be healed with an if(t<9) return t; just before the
loop. Then we should measure speed on different platforms.
With the order you propose, we may use
NP_SMALL_LIMIT = prevprime (LAST_PRIME * (LAST_PRIME + 1))
right?
+ ASSERT (i < NUMBER_OF_PRIMES);
Should this be placed at the start of the loop or be?
+ ASSERT (i+1 < NUMBER_OF_PRIMES);
The ASSERT on i make sense just before i is used by the instruction
prime+=primegap[i], i.e. at the end of the loop. Isn't it?
If writing the code is not too complex, it may be interesting to
test if it is worth.
I'll try it out tonight
Great!
Did you try tweaking with the -p parameter? It can be useful when a
measure is "noisy".
Nope I had not, using -p3 seems to work just as well.
I would have used something like -p100000 or -p1000000, but if -p3 is
good for you, I'm happy :-)
Ĝis,
m
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
