Talk:CalmoSoft primes: Difference between revisions
→Sequence length: Discovered what was making {2, 3, 5} wheel slower.
m (→Raku incorrect) |
(→Sequence length: Discovered what was making {2, 3, 5} wheel slower.) |
||
| (One intermediate revision by the same user not shown) | |||
Line 45:
:::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.
::::Just as a matter of interest, it turned out that what was making the {2, 3, 5} basis wheel slightly slower than {2, 3} in Wren was the cost of accessing the wheel increments via a list. If I don't use a list, then it's 25% quicker! --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 10:04, 27 April 2023 (UTC)
:::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)
| |||