Talk:CalmoSoft primes: Difference between revisions
→Sequence length: Previous test was unfair to M-R.
m (→Raku incorrect) |
(→Sequence length: Previous test was unfair to M-R.) |
||
Line 47:
:::However, what does help is to use the Miller-Rabin test instead which brings the overall time down from 4.3 to 3.5 seconds. Unfortunately, you can't use this for checking primality generally as it's much slower than wheel-based factorization if you're checking a block of numbers which are mostly non-prime. I checked the first 1 million integers for primeness and Miller-Rabin took about 30 times as long. It's best used therefore for checking isolated large numbers as we have for this task. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 11:06, 12 April 2023 (UTC)
::::I've just realized that the above test was unfair because there's no need to use the full 'witness' array for smaller numbers. Using the table in [https://oeis.org/A014233 A014233] means that Miller-Rabin takes about 8.5 as long as wheel factorization to check the first million integers and the multiple falls to around 7.1 for the first three million numbers. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 16:03, 12 April 2023 (UTC)
| |||