Talk:CalmoSoft primes: Difference between revisions
→Sequence length: Further comment.
(→Sequence length: Further comment.) |
|||
Line 43:
::Of course the real key to performance is ''not'' summing all 12.5e14 consecutive subsequences and testing every single one of those for primality, which would take quite some time no matter how good your compiler or how many cores you had. --[[User:Petelomax|Petelomax]] ([[User talk:Petelomax|talk]]) 01:55, 12 April 2023 (UTC)
:::An area I've been investigating is how best to check if the candidate sequence sums are prime or not which is quite slow in Wren for the larger sums. My 'Int.isPrime' routine uses an implicit {2, 3} basis for wheel factorization which, curiously, seems optimal for Wren - if I try to use {2, 3, 5} as in the C++ example - it's slightly slower.
:::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)
| |||