Talk:Find largest left truncatable prime in a given base: Difference between revisions
Talk:Find largest left truncatable prime in a given base (view source)
Revision as of 12:02, 10 April 2017
, 7 years ago→Discrepancy in auxiliary output: Splitting stuff.
(→Discrepancy in auxiliary output: Splitting stuff.) |
|||
Line 87:
===Discrepancy in auxiliary output===
====Tcl vs...====
The other solution showing these counts is Tcl and for base 12 it reports 1126 candidates at length 5 whereas the counts above for Perl 6 show 1124. This is the first discrepancy. Auxiliary output from the Fortran version also shows 1124 and matches the other counts from Perl 6 also. So, here are the 1124 five-digit base twelve candidates, in storage order:
====Schedule====
<pre>
5 candidates at length 1
Line 1,219 ⟶ 1,221:
1124 92951 = 4.5.9.5.11
</pre>
====Comparisons====
The Fortran version checks for possible factors up to 2800 by bignumber division before it starts on the MR process. [[User:Dinosaur|Dinosaur]] ([[User talk:Dinosaur|talk]]) 06:11, 9 April 2017 (UTC)
::One of the purposes of this task is to highlight problems with primality testing of a large number of large numbers. If you are using MR these are twofold: first being able to randomly select prime numbers fairly across the range 3 to the large number; second the number of prime numbers you are going to try. In the worst case for a single trial there is a 1 in 4 (usual case more like 1 in 50) chance that the large number is actually composite. This chance rapidly decreases with trials, but so does the time taken. So the recommendation is to do quick trials allowing some non prime candidates to be propagated, then a thorough check of
:::Indeed. An earlier version accidentally used a parameter BIGMRTRIALS instead of what I intended for the upper bound of direct division trials, 2800 (eventually chosen after some ad-hoc timing as resulting in faster runs than with say 3000 or 1500), and with a value of six, this meant that only 2, 3, and 5 were tested as possible factors by direct division. All else was via the MR test and so far, this provided the only occasion when a denunciation of "composite" did not occur in the first MR trial, though only for a few dozen out of a quarter of a million trials. With trial factors up to 2800 or so, all denunciations were made on the first MR trial: 517641 trials rejecting 282261 in the first go, and accepting 235380 in all of the second to sixth trials. This suggests that "no comment" from a MR trial might be more likely for numbers having a small prime factor, however, I'm sure this question has been investigated more thoroughly than that. So, in this case, as the horde of candidates is being produced then trimmed one MR trial would have sufficed, but this is hindsight.
:::Allowing a few extra (but wrong) candidates during the marshalling by avoiding repeated MR tests would save time that could be spent on more heavily testing the final few survivors, however, remember that the process is to produce not just a final number that is prime, but one that also is prime at each of its earlier stages. In other words, suppose a non-prime is admitted at say the five-digit level, and at the end (with say seven digits), some of its descendants may survive and turn out to be primes and possibly even the largest survivor. But alas, not all of its left-truncations (to six, five, four, ''etc.'' digits) would be primes.
:::Routine BIGMRPRIME does not try to be general and produce tests using the range [2:N - 1] for a bignumber N because of the nuisances of bignumber arithmetic when the number is big, just an ad-hoc trick with an upper bound of N1 = min(N - 1,20000000) then selecting A1 via pseudo-random function RAND into the range [2,N1] - with vexation since RAND can deliver 1 as its result. In other words, the full range of A1 in [2,N - 1] is not available for numbers above twenty million, but they seemed to work well enough that I didn't bother with yet more routines for bignumber arithmetic to handle this properly. Incidentally, the [[Miller–Rabin_primality_test]] page quotes two as the lower bound for A1, not three. A value of two in a binary computer could enable shortcuts in the calculations, for a faster initial trial before continuing with the full range of possibilities for A1. Somewhere I saw some remarks that certain trial values of A1 give definite results for N up to ... except that I didn't look closely. There might even be a collection of special values that are particularly effective at denouncing composite numbers, rather than floundering about with "random" choices... [[User:Dinosaur|Dinosaur]] ([[User talk:Dinosaur|talk]]) 12:02, 10 April 2017 (UTC)
==Odd base optimization==
| |||