Go Back > Math Stuff > Computer Science & Computational Number Theory

Thread Tools
Old 2011-05-25, 08:07   #34
May 2011

7·23 Posts
Default speed

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

JohnFullspeed is offline   Reply With Quote
Old 2013-08-18, 07:19   #35
"Dana Jacobsen"
Feb 2011
Bangkok, TH

38616 Posts

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

Originally Posted by CRGreathouse View Post
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.

Originally Posted by R.D. Silverman View Post
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.
danaj is offline   Reply With Quote
Old 2018-07-28, 13:02   #36
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.

This next table is for testing 32 bit numbers. It uses a single sprp test.

It would be helpful if anyone could independently verify the tables.
bradley is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Do normal adults give themselves an allowance? ( fast or not to fast - there is no question!) jasong jasong 35 2016-12-11 00:57
How to Check if Non-Mersenne Number isPrime? FloatingPoint Operation Billion Digits 39 2015-10-21 02:15
How fast is the dog? Andi47 Puzzles 20 2009-04-01 02:35
I wonder how fast this is... ixfd64 Hardware 1 2005-11-21 21:28
Fast way to square??? maheshexp Math 2 2004-05-29 01:54

All times are UTC. The time now is 06:26.

Sat Jul 11 06:26:45 UTC 2020 up 108 days, 3:59, 0 users, load averages: 1.11, 1.08, 1.17

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

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.