Timeline for Best known primality test for the whole intervals of integers up to $10^{20}$ — like the sieve of Eratosthenes
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 17, 2020 at 11:06 | history | edited | user1123502 | CC BY-SA 4.0 |
varepsilon looks more nicely than epsilon
|
| Jul 17, 2020 at 11:01 | comment | added | user1123502 | @MaxAlekseyev I still have not tested it on processors with big cache size. | |
| Jul 17, 2020 at 10:50 | comment | added | user1123502 | @MaxAlekseyev For now this primesieve looks like the best know practical sieve. But I suspect that good algorithm will be 10 times faster for primes starting from $10^{15}$, at least on processors like x5-Z8350. | |
| Jul 17, 2020 at 10:46 | comment | added | user1123502 | @GerhardPaseman 1. Wheel sieving is useful, but not a simple thing: it is cache unfriendly, at least by naive implementation. 2. It may be possible to use 10^18 primes to estimate, say, Brun's constant more precisely. And 10^20 is upper limit. 3. GPU version is interesting, but I still do not understand GPU programming (but plan to learn it sometimes). BTW, the sieve of Eratosthenes seems to be GPU unfriendly due to demand for random writes and big cache size. I shall carefully read your question mathoverflow.net/q/243490 | |
| Jul 14, 2020 at 10:09 | comment | added | Max Alekseyev | Primesieve is good in practice: github.com/kimwalisch/primesieve | |
| Jul 13, 2020 at 16:02 | comment | added | Gerhard Paseman | I'm thinking of a GPU version of an algorithm based on mathoverflow.net/q/243490 . You can add a comment there if you are interested and would like to contribute. Gerhard "Is Going For Gentle Solicitation" Paseman, 2020.07.13. | |
| Jul 13, 2020 at 15:53 | comment | added | Gerhard Paseman | Since you have roughly 10^18 primes with 20 decimal digits, what are you going to do with them? Gerhard "Please Don't Print Them Out" Paseman, 2020.07.13. | |
| Jul 13, 2020 at 15:32 | history | edited | user1123502 | CC BY-SA 4.0 |
added possible answer
|
| Jul 12, 2020 at 16:28 | comment | added | Gerhard Paseman | Wheel sieving is ready to use. You might find that in combination with some other tests useful. Gerhard "Sometimes Settles For Pretty Good" Paseman, 2020.07.12. | |
| Jul 12, 2020 at 14:24 | comment | added | user1123502 | @GeoffreyIrving Sometimes it may be possible to modify point test into amortized test, just like trial division test may be modified into the sieve of Eratosthenes and have some perfomance gain. But, of course, I am more interested in the "ready to use" tests. | |
| Jul 12, 2020 at 14:19 | comment | added | Geoffrey Irving | Just a comment since this is a point test rather than an amortized test, but in case it’s useful for others: Michal Foriˇsek and Jakub Janˇcina, Fast Primality Testing for Integers That Fit into a Machine Word. | |
| Jul 12, 2020 at 13:32 | history | edited | user1123502 | CC BY-SA 4.0 |
minor corrections
|
| Jul 12, 2020 at 13:26 | history | edited | user1123502 | CC BY-SA 4.0 |
minor corrections
|
| Jul 12, 2020 at 13:24 | history | edited | Martin Sleziak |
added a top-level tag; see: https://meta.mathoverflow.net/questions/1457/why-are-mo-tags-formatted-as-they-are
|
|
| Jul 12, 2020 at 13:20 | history | edited | user1123502 | CC BY-SA 4.0 |
added 63 characters in body
|
| Jul 12, 2020 at 13:17 | review | First posts | |||
| Jul 12, 2020 at 14:25 | |||||
| Jul 12, 2020 at 13:14 | history | asked | user1123502 | CC BY-SA 4.0 |