mersenneforum.org Fast isPrime() for n < 2^32
 Register FAQ Search Today's Posts Mark Forums Read

2011-05-25, 08:07   #34
JohnFullspeed

May 2011
France

7·23 Posts
speed

Quote:
 Two hours?!? It takes PARI 11 seconds on this machine. (Technically that's "just" to 4.26e9 since this computer is running 32-bit gp.)
sorry my explicatiuon must be wrong

2 hours to compute the first 200 000 000 of primes
so 7200 secondes
7200/200000000= 0,000036 sec by prime
ang 1 000 000 000 of values are tested
7200 / 1000000000= 0,0000072
I don't find It's slow.
You can go faster with a stieve (not ErashotÃ¨ne) but it more hard to programme

I give the time for DIVISION methoid:This method is slow and like you I use an other(Fermat)

It seems that you make a small mistake

If the value has 20 digits and is a primes product
necessary on of the factor is smaller than 2^32
So if you have all the primes smaller 2^32 you are sur th find the other
Liike you have 200 000 000 of primes soif uin fact the value is prime you will make 200 000 000 of divisions.

Let Primes be an array with the 200M of primes

for i:=1 to nb_Primes do
If A mod Primes[ I]=0 then trouve

John

2013-08-18, 07:19   #35
danaj

"Dana Jacobsen"
Feb 2011
Portland, OR

11100001002 Posts

I realize this is an old thread, but thought it wouldn't hurt to add a little.

Quote:
 Originally Posted by CRGreathouse I know that many people have checked this, but I don't know which implementations of BPSW were used (though as you point out, it's at least two).
I've tested Feitsma's PSP/SPSP database with a number of Lucas tests, without any trial division. None had counterexamples to 2^64.
1. Standard Lucas-Selfridge
2. Strong Lucas-Selfridge
3. Extra-Strong (Grantham) Lucas with Baillie-OEIS parameters (OEIS A217719)
4. "almost" extra-strong Lucas (ES test without the U=0 condition, which is what Pari uses for its "BPSW" test) with Baillie-OEIS parameters
5. "almost" extra-strong test with Pari's parameters (similar to the above but incrementing P by 2 instead of 1, no explanation in the code as to why they chose that)
6. GMPY2's strong BPSW (WraithX's mpz_prp)
7. MPIR's PSP2+Fibonacci / SPSP2+Lucas-Selfridge combination (seemingly based on Chen and Greene's work rather than BPSW). It's super fast, but also is non-portable outside of MPIR (much like Pari internals would be).
8. GAP's weird Lucas test (an odd mishmash of Lucas and extra-strong Lucas that doesn't seem to help much over the standard Lucas test)
1-5 are my C and C+GMP implementations. I implemented 8 using my Lucas code to emulate the GAP source algorithm as best I could. I also tested Jim Sinclair's 7-base M-R test. which (no surprise) also had no counterexamples. The performance of 4/5 is the fastest, though in GMP one can recover U from V relatively cheaply making the full extra strong test just about the same speed once over 128 or so bits.

Using my C code on an x86_64 that takes advantage of asm mulmod (ty WraithX!), doing a SPSP2 + AESLSP test on a prime takes as long as ~ 2.7 M-R tests. A strong Lucas-Selfridge test takes longer, but since the range is fixed and none have counterexamples, we can use whichever one of the above is fastest for us.

For 32-bit, the hash with single test seems like the winner. Albeit only two M-R tests are needed up to 1050M now, but still if we're after the best possible performance, a hash plus 1 test is better than 1-3 (three tests is the most needed for 32-bits).

For 64-bit, at least on x86_64 and probably gcc+Power7, I think BPSW is faster than M-R tests. Your actual results may vary depending on implementation details. A hash to 3 tests vs. 4 would be murkier. I like the simplicity of testing the Lucas test vs. the hash, but some may disagree.

Note that using the SPSP-2 database as a test sample is misleading for benchmarks. By definition these are all composites that pass the SPSP-2 test. The BPSW test will have to run its full test (SPSP-2 which of course will pass, then the Lucas test which will fail). For the particular set of bases in zerothbase's code, it also will run a SPSP-2 test, but then most numbers will fail the next base. Swap the two initial bases and it will run almost twice as fast on this data set since almost everything will be weeded out on the first M-R test. While I suppose it is application specific, in general one would want to test on random inputs that have made it through the initial small-factor checks (Steve checks to 7, Jim to 2, I found improvements on random inputs using up to 7 followed by up to 53).

Interestingly, with GMP on a 200-bit prime I found my ESLSP test to run about the same speed as 6 M-R tests, and the SLSP test about the same as 8 M-R tests. I assume this is due to GMP greatly optimizing the mpz_powm internals. The two other GMP Lucas implementations I've compared run slower than mine, and it's faster than Pari's implementation on large numbers, so this isn't just poor coding of the Lucas test. This might be useful to know for someone looking at using GMP on a 32-bit machine for 64-bit results. Once past 64 bits, some form of BPSW is a better choice than M-R tests for most purposes.

Quote:
 Originally Posted by R.D. Silverman If the objective is proved primes,[...]
(quoting from over 2 years ago). Using BPSW below 2^64 would seem to give one a proven prime based on the computer-assisted proof of Feitsma-Galway (exhaustive list of PSP-2's under 2^64) plus verification of the particular Lucas test used. The BLS75 proofs (even just theorem 5 for factors of N-1) are awfully fast for most small (< 128-bit) numbers, but you still have to verify the primality of each factor found, which means more tests.

 2018-07-28, 13:02 #36 bradley   Jul 2018 1 Posts This table of hashes can be used to test a 64 bit number for primality. For 49 bit numbers it requires 1 or 2 sprp tests depending on the number. 64 bit numbers can be tested with 1, 2, or 3 sprp tests. https://techneon.com/download/is.prime.64.base.data This next table is for testing 32 bit numbers. It uses a single sprp test. https://techneon.com/download/is.prime.32.base.data It would be helpful if anyone could independently verify the tables.

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong jasong 35 2016-12-11 00:57 FloatingPoint Operation Billion Digits 39 2015-10-21 02:15 Andi47 Puzzles 20 2009-04-01 02:35 ixfd64 Hardware 1 2005-11-21 21:28 maheshexp Math 2 2004-05-29 01:54

All times are UTC. The time now is 05:14.

Wed Apr 1 05:14:32 UTC 2020 up 7 days, 2:47, 0 users, load averages: 1.28, 1.32, 1.40

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.