Search
Member List
Calendar
Help
|
Fast prime finder??
|
|
08-05-2016, 12:46 AM
(This post was last modified: 08-05-2016 12:50 AM by Claudio L..)
Post: #15
|
|||
|
|||
RE: Fast prime finder??
(08-04-2016 11:54 PM)Namir Wrote: I have working code for the HP-Prime which implements the Solovay algorithm. I will make a brief mention of this algorithm in one of my HHC2016 talk.s According to Wikipedia, Solovay-Strassen was superseded by Miller-Rabin and Baillie-PSW methods. Miller-Rabin is one of the most widely used and studied. https://en.wikipedia.org/wiki/Miller–Rab...ality_test Depending on the number of primes and the values of the primes you test against, it works better or worse. Some people spent a lot of time looking for the best values to maximize its performance: https://miller-rabin.appspot.com The best cases are quite amazing: with only one test it can find all primes up to 341531 without letting anything slip, while only 7 tests guarantee perfect results up to 64-bit integers. Baillie-PSW seems like a cocktail of 4 other filters, one after another to get even better results, at the expense of slightly higher complexity. |
|||
|
|
« Next Oldest | Next Newest »
|
| Messages In This Thread |
|
Fast prime finder?? - Namir - 07-28-2016, 08:22 PM
RE: Fast prime finder?? - Claudio L. - 07-29-2016, 02:50 AM
RE: Fast prime finder?? - Namir - 07-29-2016, 07:27 AM
RE: Fast prime finder?? - Namir - 07-29-2016, 12:03 PM
RE: Fast prime finder?? - ttw - 08-01-2016, 09:59 PM
RE: Fast prime finder?? - Namir - 08-02-2016, 12:01 AM
RE: Fast prime finder?? - ttw - 08-03-2016, 08:36 AM
RE: Fast prime finder?? - Namir - 08-03-2016, 11:07 AM
RE: Fast prime finder?? - Namir - 08-03-2016, 11:50 AM
RE: Fast prime finder?? - Namir - 08-04-2016, 11:54 PM
RE: Fast prime finder?? - Claudio L. - 08-05-2016 12:46 AM
|
User(s) browsing this thread: 1 Guest(s)