mersenneforum.org Other Primes
 Register FAQ Search Today's Posts Mark Forums Read

2021-01-26, 07:13   #232
bur

Aug 2020

1328 Posts

Quote:
 Originally Posted by a1call Suppose you are testing 10000 candidates with 1M decimal digits each. And each PRP test takes 4 days and you have 10 threads available. Suppose you run PRP tests on 9 of them and trial factoring on the other. In the 1st 4 days anything divisible by small primes will be knocked out by TF. In the next 4 days candidates divisible by larger primes will be knocked out, next 4 days even larger.... Any candidates that are knocked out of the queue at anytime means you don't have to spend 4 days for a PRP test on them.
I only saw this now, sorry. Sounds convincing at first, but why not use 2 out of 10 threads, or 7 or all?

Fundamentally you have two methods to remove a candidate for good, TF or PRP. If one is faster on average, you have the highest average throughput when using that method exclusively. I don't see how it can be different.

Quote:
 Congrats to Rudi Tapper and PrimeGrid for the prime 3* 2^16819291 - 1 with 5,063,112 decimal digits and top5000 entrance rank of 21.
After 5 days verifying it was finally added to the list.

Last fiddled with by bur on 2021-01-26 at 07:16

2021-01-26, 08:21   #233
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2·7·11·13 Posts

Quote:
 Originally Posted by bur Fundamentally you have two methods to remove a candidate for good, TF or PRP. If one is faster on average, you have the highest average throughput when using that method exclusively. I don't see how it can be different.
By that logic there would be no justification to use more than one method, either TF or PRP-Testing on any given range. But that's not the case now, is it?
Both methods are used in practice to weed out candidates they are better at sieving. TF for candidates with smaller factors and PRP-Testing for the rest, even though one would have to be faster on acreage on the whole set than the other.

2021-01-26, 15:24   #234
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

2×5×11×43 Posts

Quote:
 Originally Posted by a1call By that logic there would be no justification to use more than one method, either TF or PRP-Testing on any given range. But that's not the case now, is it? Both methods are used in practice to weed out candidates they are better at sieving. TF for candidates with smaller factors and PRP-Testing for the rest, even though one would have to be faster on acreage on the whole set than the other.
No, you are fully misunderstanding what he said.

If TF is faster, use it exclusively. At some point in your TF efforts, TF is no longer faster, and PRP becomes faster. At that crossover point, use PRP exclusively.

This is clearly the most efficient path, yet you wave your hands and use all sorts of words to make yourself feel better that it's not true.

2021-01-27, 09:43   #235
LaurV
Romulan Interpreter

Jun 2011
Thailand

5×1,871 Posts

Quote:
 Originally Posted by a1call By that logic there would be no justification to use more than one method, either TF or PRP-Testing on any given range.
That's a fallacy. It would be true if the speed of each method would be constant as you go deeper, but it is not. The TF speed decreases exponentially, it halves with every bitlevel. The speed of PRP decreases slower with the size of the exponent (range, size of the FFT). In a certain point they will cross. As VBCurtis says.

By "speed of TF" we mean how fast you can eliminate an exponent, by finding a factor. TF programs seem "much faster", they do many tests in the wallclock time taken by a PRP test, but to find a factor, you need to do many assignments (roughly, equal to the bitlevel, i.e. if you look for 70 bits factors, you will need to test about 70 exponents, to find a factor). If your hardware can test 70 exponents to 70 bits faster than it takes for the same hardware to do a PRP for an exponent of the same size (plus or minus a little change, considering the certification process, error rates, vanity of having a factor as opposite of having a PRP residue, whatever rows your boat), then YOU SHOULD CERTAINLY DO ONLY TF to 70 bits.

This is how GIMPS works since its inception, if we make abstraction of the people who only run TF because they want more credit, or they like to have found factors, or (I would say "selfish") people who only run LL/PRP because they want the glory of finding a prime and take George's money. Most users here will try to help the project most, by optimizing their rate of getting rid of exponents, at front wave, either doing TF or PRP. Of course, the options will wary in time, according with the exponent size at the front level and the bitlevel that has to be trial-factored, you can do PRP today because the bitlevels are very deep here, and TF next month if your exponent gets higher and the bitlevel is lower or stays the same, but once the exponent and bitlevel is given, and assuming you know your hardware, you should optimally chose ONE of them, and DO THAT ONE ONLY.

Last fiddled with by LaurV on 2021-01-27 at 09:58

 2021-02-19, 08:30 #236 paulunderwood     Sep 2002 Database er0rr 3,617 Posts Congrats to Serge Batalov for the smallest known 1 million digit prime: 10^999999 + 308267*10^292000 + 1 Can this be limbo-ed?
2021-02-19, 08:48   #237
JeppeSN

"Jeppe"
Jan 2016
Denmark

101001102 Posts

Quote:
 Originally Posted by paulunderwood Congrats to Serge Batalov for the smallest known 1 million digit prime: 10^999999 + 308267*10^292000 + 1 Can this be limbo-ed?
This beats an idea of simply doing 10^999999 + k*10^(333333-m) ± 1 with m very small. Such a prime would be simpler to test than Serge Batalov's, but not quite as close to 10^999999. /JeppeSN

2021-02-19, 19:36   #238
sweety439

Nov 2016

1011000001002 Posts

Quote:
 Originally Posted by paulunderwood Congrats to Serge Batalov for the smallest known 1 million digit prime: 10^999999 + 308267*10^292000 + 1 Can this be limbo-ed?
The smallest known 1 million digit prime is 10^999999+593499

2021-02-19, 19:42   #239
paulunderwood

Sep 2002
Database er0rr

70418 Posts

Quote:
 Originally Posted by sweety439 The smallest known 1 million digit prime is 10^999999+593499
That may be the smallest PRP. No proof of primality, unless you have a new theorem

 2021-03-02, 18:52 #240 paulunderwood     Sep 2002 Database er0rr 3,617 Posts DRUG is PRP top We had a nice email from Jeff Gilchrist this morning saying one of his computers had reported: Code: 2^13380298-27 is base 3-Fermat PRP! (4027872 decimal digits) Time : 9677.550 sec. 2^13380298-27 is Fermat, Lucas and Frobenius PRP! (P = 5, Q = 5, D = 5) Time : 75222.576 sec. We would like to thank rouge for his sieve and Jean and George for their software. It is official now Last fiddled with by paulunderwood on 2021-03-05 at 05:38
 2021-03-11, 22:52 #241 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100100101010012 Posts A new Generalized Cullen number - 4'143'644 decimal digits.
2021-03-12, 21:01   #242
pepi37

Dec 2011
After milion nines:)

2·709 Posts

Quote:
 Originally Posted by Batalov A new Generalized Cullen number - 4'143'644 decimal digits.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 3 2017-08-10 13:47 emily Math 34 2017-07-16 18:44 Mickey1 Miscellaneous Math 1 2013-05-30 12:32 Unregistered Information & Answers 0 2011-01-31 15:41 troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 11:14.

Sat Apr 10 11:14:53 UTC 2021 up 2 days, 5:55, 1 user, load averages: 1.04, 1.19, 1.26