Predict M48...

[Christenson]

Originally Posted by davieddy

Why is that?

David

I think it's because P-1, like LL-D, is *never* going to get a prize for finding M48. It only makes it easier for someone else to find it.

Therefore, not too many do it...or, as Mr P-1 states, do a good job....leaving those of us doing a good job finding factors more quickly than we would if we ran LL. Remember, the minimum work to proving status of any given large set of exponents happens when we are indifferent to whether we prove the status by any particular method.

P95:
If we get a 4x speedup on LL or (eventually) P-1 on GPUs, and LL isn't all that memory hungry, does it make sense to run multiple exponents in parallel on LL? [I'm doubtful this will speed things up much on P-1, due to its memory-intensiveness]. How bad is the CPU impact of running LL on CUDA?

[R.D. Silverman]

Originally Posted by Prime95

I can see merit to your argument that we should do more P-1 rather than more TF, but the GPUs are only 100x faster at TF. IIRC, they are 4x faster at LL. GPUs cannot do P-1, but if they could they'd also be only 4x faster (or less).

If they (GPU) can do LL, then they can do P-1; the iterations are
the same. They are modular multiplications mod M_p. And, as you say,
they would only be 4x faster.

The difference in speed between TF and LL on a GPU does mean that
it is better to spend more time on the former, but one gets fairly
rapid diminishing returns on TF. If there is no factor less than (say) 70 bits,
it is unlikely that there is one of 71 or 72 bits.....

One can indeed optimize the parameter selections, but the calculations
would be quite sensitive to the speed differences in the various pieces
of hardware.

[davieddy]

Originally Posted by R.D. Silverman

If they (GPU) can do LL, then they can do P-1; the iterations are
the same. They are modular multiplications mod M_p. And, as you say,
they would only be 4x faster.

The difference in speed between TF and LL on a GPU does mean that
it is better to spend more time on the former, but one gets fairly
rapid diminishing returns on TF. If there is no factor less than (say) 70 bits,
it is unlikely that there is one of 71 or 72 bits.....

One can indeed optimize the parameter selections, but the calculations
would be quite sensitive to the speed differences in the various pieces
of hardware.

All becomes clear.

This is what a math argument is.

David

[davieddy]

Originally Posted by Christenson

I think it's because P-1, like LL-D, is *never* going to get a prize for finding M48. It only makes it easier for someone else to find it.

The question was intended as "rhetorical".

But since you have risen to the bait (like others)
I may as well point out that a double check LL might
find M48, but TF/P-1 won't.

David

[science_man_88]

Originally Posted by davieddy

The question was intended as "rhetorical".

But since you have risen to the bait (like others)
I may as well point out that a double check LL might
find M48, but TF/P-1 won't.

David

David it's the first ll that found it it's the second that confirms it so LL-D will not find it it will confirm it or deny it. Even I know this and I'm usually the thickest skulled person on these forums.

[fivemack]

If someone finds a zero residual, then there will be a double-check done immediately on the fastest hardware available to confirm.

What LL-D offers is the possibility of finding a number for which the correct residual is zero, but the first run maybe years earlier hit a hardware problem and so the Mersenne prime was missed.

[Christenson]

Bob: It is certainly possible to get a GPU to do P-1. However, at the moment, the possibility is still theoretical -- you can't download the program just yet. And, as a student, I'm not quite ready to make it real.

I'm curious as to why LL is only 4x faster on a GPU...that is, comparatively, where are the bottlenecks on TF versus LL iterations, and why does that leave us with a 100x speedup on TF but only a 4x speedup on LL?

[R.D. Silverman]

Originally Posted by Christenson

Bob: It is certainly possible to get a GPU to do P-1. However, at the moment, the possibility is still theoretical -- you can't download the program just yet. And, as a student, I'm not quite ready to make it real.

I'm curious as to why LL is only 4x faster on a GPU...that is, comparatively, where are the bottlenecks on TF versus LL iterations, and why does that leave us with a 100x speedup on TF but only a 4x speedup on LL?

Memory bandwidth will be a bottleneck. TF takes only a few bytes
of storage per processor. TF is also embarrasingly parallel; FFT's are not.
There may be other problems as well.

[cheesehead]

Originally Posted by Prime95

Getting this thread back to the math/optimization problem....

P-1 and LL tests are done on the same caliber of Intel/AMD machine. The P-1 bounds are selected comparing the time it takes to run P-1 to the cost of running 2 LL tests times the chance of P-1 finding a factor. Barring any bugs in my understanding of P-1's chance of finding a factor or in my programming, increasing P-1 bounds would be a bad idea because that extra P-1 time would remove more candidates if it were used for LL testing instead.

Since Silverman's suggestion is to run P-1 without any preceding (server-assigned) TF, the P-1 bounds selection algorithm will find that the TF bit level for an exponent is in the low 60s (to which the past LMH projects had taken all exponents), rather than the high 60s or low 70s as it now usually faces. In that case, it will select higher bounds as optimal, because of the new possibility of finding factors in the high 60s to low 70s bits. Since the probability that P-1 will find a factor for such an exponent will be greater than it used to be, higher bounds are justified.

The extra P-1 time will be less than the skipped TF time, and thus a net savings, by Silverman's argument.

(Personally, though that seems reasonable, I'd be more comfortable seeing specific numbers and time-costs/savings for how many would-also-have-been-TF-found factors P-1 will find between the powers of 2 we've been covering with server-assigned TF. How many would P-1 with those higher B1/B2 bounds miss that TF to currently standard power-of-2 limits would have found?

I see that Silverman has anticipated me in post #172.)

This is simply the mirror image of your later statement "When extra TF is done before P-1 has been performed, the extra TF reduces the P-1 bounds (because the chance of finding a factor is reduced)." <= less, less, increases, increased

- - -

Originally Posted by R.D. Silverman

Suppose you run P-1 to steps B1/B2. Thus, we are sure there are
no factors smaller than 2 B2 p + 1.

For exponents in the range 55M, I see these current factoring limits:

55000031,71,675000,29750000
55000181,71,660000,19140000
55000189,71,660000,19140000
55000207,71,660000,19140000
55000277,71,660000,19140000
 . . .

So, the first line shows that P-1 by itself with B1,B2 = 675000,29750000 eliminated all factors below 2 * 29750000 * 55000031 + 1 = 3272501844500001, which is below 2^52 and not very close to 2^71.

In order to guarantee finding factors up to 2^71 with P-1 alone, we'd have to use B2 = 2^71 / p = 42930580192487, over 100,000 time higher than currently-chosen P2. Which P-1 routines can handle B2 ~ 2^46?

So the no-TF scheme might be more efficient at eliminating LL tests, but it would leave much lower power-of-2 limits to which one could say definitely there were no smaller factors. Indeed, since exponents in the 55M range were already TFed to at least 2^60 by LMH, a P-1 B2 bound of 2^60 / p = 20962197360, which is ~1000 times as large as our current customary B2, would be necessary just to guarantee the same level of completeness that we already have through LMH TF.

[cheesehead]

Oops. I used p instead of 2p in the divisions. Revised numbers are below.

Originally Posted by cheesehead

In order to guarantee finding factors up to 2^71 with P-1 alone, we'd have to use B2 = 2^71 / p = 42930580192487, over 100,000 time higher than currently-chosen P2. Which P-1 routines can handle B2 ~ 2^46?

So the no-TF scheme might be more efficient at eliminating LL tests, but it would leave much lower power-of-2 limits to which one could say definitely there were no smaller factors. Indeed, since exponents in the 55M range were already TFed to at least 2^60 by LMH, a P-1 B2 bound of 2^60 / p = 20962197360, which is ~1000 times as large as our current customary B2, would be necessary just to guarantee the same level of completeness that we already have through LMH TF.

In order to guarantee finding factors up to 2^71 with P-1 alone, we'd have to use B2 = 2^71 / 2p = 21465290096243, over 70,000 times as large as currently-chosen P2. Which P-1 routines can handle B2 ~ 2^45?

So the no-TF scheme might be more efficient at eliminating LL tests, but it would leave much lower power-of-2 limits to which one could say definitely there were no smaller factors. Indeed, since exponents in the 55M range were already TFed to at least 2^60 by LMH, a P-1 B2 bound of 2^60 / 2p = 10481098679, which is over 300 times as large as our current customary B2, would be necessary just to guarantee the same level of completeness that we already have through LMH TF.

Completeness isn't everything, but eliminating server-assigned TF would dash the current GIMPS claim to comprehensive factor search up to levels of 2^70 and beyond. Would LMH or any other specialty group take on the project of extending TF on P-1ed-only-and-already-LLed exponents if doing so made no contribution to the search for Mersenne primes?

[davieddy]

Originally Posted by science_man_88

David it's the first ll that found it it's the second that confirms it so LL-D will not find it it will confirm it or deny it. Even I know this and I'm usually the thickest skulled person on these forums.

Originally Posted by fivemack

If someone finds a zero residual, then there will be a double-check done immediately on the fastest hardware available to confirm.

What LL-D offers is the possibility of finding a number for which the correct residual is zero, but the first run maybe years earlier hit a hardware problem and so the Mersenne prime was missed.

See "Is this a bug...or...?" thread in the Primenet forum.

David