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.) |
||
| (18 intermediate revisions by 3 users not shown) | |||
Line 1:
===Raku incorrect (now fixed) ===
I'm getting
<pre>
For primes up to two hundred and fifty:
The following sequence of 49 consecutive primes yields a prime sum:
11 + 13 + 17 + 19 + 23 + 29 +..+ 223 + 227 + 229 + 233 + 239 + 241 = 5,813
</pre>
which disagrees with the Raku output. For ease of reference, the relevant Raku output is
Line 13:
11 + 13 + 17 + 19 + 23 + 29...211 + 223 + 227 + 229 + 233, sum: 5,333
</pre>
Sadly, I don't think there is an OEIS entry I can check this against (tee hee) --[[User:Petelomax|Petelomax]] ([[User talk:Petelomax|talk]]) 02:48, 9 April 2023 (UTC)
:I agree with your result for primes < 250 and also disagree with some of the other Raku results. Your 2 second target for the stretch goal may be a bit ambitious for the interpreted languages as it takes Wren 2.6 seconds to sieve for primes up to 50 million before even starting to figure out the longest CalmoSoft prime sequence! --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 10:29, 9 April 2023 (UTC)
:::Fair point, twenty seconds it is - fwiw my sieve to 5e7 takes 1.4s, the rest 0.7s. --[[User:Petelomax|Petelomax]] ([[User talk:Petelomax|talk]]) 11:57, 9 April 2023 (UTC)
::::Just done Go which is coming in at less than 0.3 seconds. I don't know whether they've improved the compiler (now on version 1.20.3) but have been getting some quick results lately. When I have time, I'll update the C version and see how that compares. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 13:02, 9 April 2023 (UTC)
::::I've updated the C version now and it's 40 ms slower than Go even though the code is basically the same. So maybe the latter is getting faster these days. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 17:00, 9 April 2023 (UTC)
::I also agree your 250 prime result. I also agree that interpreted languages may struggle to do it in 2 seconds. See the notes on the Algol 68 stretch sample. --[[User:Tigerofdarkness|Tigerofdarkness]] ([[User talk:Tigerofdarkness|talk]]) 10:53, 9 April 2023 (UTC)
:::Re the Algol 68 stretch result, something seems to have gone awry as the sum of the sub-sequence (72619548630200) is clearly not prime. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 11:27, 9 April 2023 (UTC)
::::You are right - I've added a fixed version. - the sum is now 72618848632313, which agrees with the Phix sample.
::::Sadly takes somewhat longer than the Wren sample - does the Wren interpreter us a JIT compiler ? --[[User:Tigerofdarkness|Tigerofdarkness]] ([[User talk:Tigerofdarkness|talk]]) 13:26, 9 April 2023 (UTC)
:::::No, there's a single pass compiler which parses the Wren source directly to bytecode (no intermediate AST) which the VM then interprets. A number of devices are used to make Wren faster though I can't see JIT compilation happening as it would make the VM too complicated. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 14:03, 9 April 2023 (UTC)
===Sequence length===
I agree with the above comments about the majority of the time going in finding the primes under 50 000 000, however I did notice some performance improvement by considering the sequence lengths - assuming the sequence is more than 1 prime long:
* If the sequence starts with 2, it must have even length.
* If the sequence starts with 3 or more, it must have odd length.
--[[User:Tigerofdarkness|Tigerofdarkness]] ([[User talk:Tigerofdarkness|talk]]) 10:04, 10 April 2023 (UTC)
:It's a good point but, unfortunately, it makes no significant difference to my Wren example (0.1 seconds at most). Whilst it skips the primality test for sequences which have the wrong length, this seems to be counterbalanced by the cost of interpreting the extra code given that for these particular numbers there's not many iterations needed anyway before the longest sequence is found.
:What would make a difference is to speed up the sieving. The C++ entry is using ''primesieve'' which, amongst other tricks, uses all available cores to maximize speed. Unfortunately, Wren is single threaded and so this technique is not available to the CLI version though, in an embedded application, one could write a function to utilize this library from a C/C++ host which Wren could then call. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 13:23, 10 April 2023 (UTC)
::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.
::::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)
| |||