[QUOTE=R.D. Silverman;264744]Please note that there is no need to do [B]both[/B] trial division [B]and[/B]
P-1 because running P-1 to limit B2 in step 2 will find any factors that
trial division would find up to 2 B2 p + 1.[/QUOTE]

p ~ 2^26
TF to 2^70
B2 needs to be 2^43 ~ 10^13

In our case B2 was 4080000

[QUOTE=R.D. Silverman;264744]Please note that there is no need to do [b]both[/b] trial division [b]and[/b]
P-1 because running P-1 to limit B2 in step 2 will find any factors that
trial division would find up to 2 B2 p + 1.[/QUOTE]

Whooops...didn't know the P-1 bounds...and my machines found two P-1 factors this weekend on unrelated regular primenet assignments.

However, I'm sure I've seen Prime95 say that the last bit of TF follows P-1, so some part of davieddy's math here doesn't quite add up. My question is if P-1 can be optimized, given the knowledge that TF has been done to a certain level...so it doesn't waste its time on possibilities that have been checked by TF.

[QUOTE=Christenson;264758] My question is if P-1 can be optimized, given the knowledge that TF has been done to a certain level...so it doesn't waste its time on possibilities that have been checked by TF.[/QUOTE]

No, but the opposite is true. Run P-1 first. Then don't bother running TF
on the bounds covered by P-1.

Now also:

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

Now suppose we run TF to 2 K p + 1.

Ask yourself: what is the (conditional) probability of finding a factor
between 2 B2 p + 1 and 2 K p + 1 [b] given[/b] that P-1 failed?

The unconditional probability of finding a factor in [2 B2 p + 1, 2 K p + 1]
is easy to compute. In order that there be no factor in this interval
when P-1 [i]fails[/i], there has to be a certain condition present. If
2 L p + 1 is a divisor where B2 < L < K, then we know certain things
about L (i.e. it must have a prime power factor greater than B2).
This probability is not hard to compute. There may be other conditions as
well; I have not thought very deeply about this.

I think that you will find is that for "reasonable" B1 & B2, the chance
of P-1 missing a factor is not too high. (But my intuition might be wrong
here).

If I were doing things, rather than run both P-1 and TF, I would simply
increase the bounds on P-1 somewhat and give up on TF. This might
miss a few factors, but I think would save time overall. One would
need to compute the probabilities for various B1/B2 and TF bounds to
determine a good choice for the bounds, as well as compare the run-times.
I am not very motivated at the moment to do such analysis. It would
make a nice undergrad level research project.

It is possible to increase the B2 limit for P-1 with very little memory
penalty if one does not use a convolution based step 2. Of course, the
step 2 run time now becomes linear in B2.

[QUOTE=Christenson;264739]
Back to the regular TF work.....which I would normally carry to just 70 bits on an exponent this size.

in general, TF should search breadth-first, as this maximises the number of exponents that won't have to be LL'ed for a given amount of work, since each new bit level costs twice the preceding bit level. But I'm willing to do special favors now and then....[/QUOTE]

From the point of view of finding M48 asap, ALL factoring to date for
exponents > 60M is practically worthless.

I greatly appreciate your "special favor", and the enjoyable sense
of collaboration between CPU and GPU.

The LL wavefront advances by about 7 exponents per hour.
[b]ATM[/b] GPUs are great for TF alone. How many are needed to
TF the exponents in the 53M range to an extra bit or so,
thus incentivizing LL uptake, as you have done for my exponent?
10 or 20 or so.
I certainly feel morally obliged to complete this test now!
5% done.

David

[QUOTE=R.D. Silverman;264762]No, but the opposite is true. Run P-1 first. Then don't bother running TF on the bounds covered by P-1. ... we are sure there are no factors smaller than 2 B2 p + 1.[/quote]

This works but is non-optimal. With p ~2^26, B2~2^22, if we P-1 first we can skip TF to 2^49. Alas, TF to 2^49 can be done in a split second. It is much faster to do the TF to avoid the time consuming P-1.


[quote]If I were doing things, rather than run both P-1 and TF, I would simply
increase the bounds on P-1 somewhat and give up on TF. This might
miss a few factors, but I think would save time overall. One would
need to compute the probabilities for various B1/B2 and TF bounds to
determine a good choice for the bounds, as well as compare the run-times.
I am not very motivated at the moment to do such analysis. It would
make a nice undergrad level research project.[/quote]

This isn't too hard to optimize if all the work is being done on the same machine. However, we've recently had an influx of GPUs doing TF, whereas the LLs are mostly done on Intel/AMD CPUs. I don't know that you can solve for the optimal TF limits and P-1 bounds without knowing exactly how many GPUs and CPUs are active and what work type they are doing. Right now I'm stumbling around trying to find the best TF limits such that the TFers and LL testers progress at roughly the same rate.

GIMPS is weird in that the server has very limited abilities to allocate resources. GIMPS would be better served by moving much of the TF firepower over to LL testing. Since I can't do that, I do more TF than necessary to keep the over-allocated resource busy.

[quote=davieddy]Not for the first time, Bob is talking through his arse.[/quote]

Mr. Silverman is making an effort to be more civil. Please return the favor.

[QUOTE=Prime95;264790]This works but is non-optimal. With p ~2^26, B2~2^22, if we P-1 first we can skip TF to 2^49. Alas, TF to 2^49 can be done in a split second. It is much faster to do the TF to avoid the time consuming P-1.




This isn't too hard to optimize if all the work is being done on the same machine.

[/QUOTE]

The difficulty is in the analysis of the conditional probability:
Given P-1 limits of B1, and B2, and a TF factoring bound K,
what is the conditional probability of [b]finding[/b] a factor with
TF (with the given bound) given that P-1 [b]failed[/b]. If this is
sufficiently low and depending on how long it takes to run P-1 and TF
to the given bounds, it may not be worthwhile to perform TF at all.

The mathemtical difficulty here is identifying all of the conditions
under which P-1 might fail, yet still have TF succeed. I already gave
one such condition.
[QUOTE]

However, we've recently had an influx of GPUs doing TF, whereas the LLs are mostly done on Intel/AMD CPUs. I don't know that you can solve for the optimal TF limits and P-1 bounds without knowing exactly how many GPUs and CPUs are active and what work type they are doing.

[/QUOTE]


Indeed. The fact that these machines all run at different speeds makes
the optimization quite difficult.

[QUOTE=Prime95;264790]This works but is non-optimal. With p ~2^26, B2~2^22, if we P-1 first we can skip TF to 2^49. Alas, TF to 2^49 can be done in a split second.

.[/QUOTE]

I suspect that B2 ~ 2^22 is too small.

Note also that P-1 will find quite a lot of factors that would also be found
by TF.

It might be worthwhile to go through the historical data and ask:
How often did TF find a factor that would have been missed by P-1
if it were run first? How often would P-1 have succeeded in finding
a factor that was first found by TF?

[QUOTE=Prime95;264790]

Mr. Silverman is making an effort to be more civil. Please return the favor.[/QUOTE]

Indeed...Bob's reply was quite civil. He answered my question, although I think at this point we have enough empirical data that we could get a good approximation of the number of factors in a given bit range that would be found by P-1. In perfect pure math fashion, he left that to me as an exercise!

As an operator of both CPUs and GPUs, my remark is that it is 10x easier to get a GHz day of GPU credit than CPU credit on my $100 GPU...and I suspect that is 128x for some with better GPUs than mine...which translates to 7 extra bit levels for the same effort measured on the clock. That removes ~10% additional LL candidates if the initial TF level is around 70.

We need to get the GPUs doing more LL and maybe P-1....I'm currently committed to some improvements to mfaktc, but most of the time has been spent on build tools and learning Prime95 and other bits like MPQS...we need a beginner's thread for doing LL on GPUs; my choice of mfaktc is actually arbitrary, and might have been different if my GTX210 had been able to run LL.

If it was my server, I'd set the TF level to 72 or 73 bits before handing out the LL assignments, and TF exponents approaching LL assignment first. I'd re-calculate my optima by devaluing TF effort by a factor of 10-100, for the reasons stated above...and consider getting an extra bit or two of TF on stuff awaiting LL-D assignments. From my perch, it feels (with no mathematical justification) like a slightly longer view is being taken of TF, with the exponents being removed from the LL pool below 60M being the criterion for which exponents to TF how far, rather than pulling in the time of discovery of M48. This is fine with me.

Oh, and.....
:direction:

[QUOTE=R.D. Silverman;264801]
It might be worthwhile to go through the historical data and ask:
How often did TF find a factor that would have been missed by P-1
if it were run first? How often would P-1 have succeeded in finding
a factor that was first found by TF?[/QUOTE]

A very sensible and relevant question, which I et al have raised before.

Bearing in mind that all exponents from ~1M to 1000M have been TFed
to 64 bits, what, in your esteemed opinion, is your estimate?

David

[QUOTE=Prime95;264790]
Mr. Silverman is making an effort to be more civil. Please return the favor.[/QUOTE]

I did, but someone has seen fit to delete it.

Stop playing God

[QUOTE=Christenson;264803]Gone off the course.[/QUOTE]
Yes indeed. There are 91 days left until we match the longest gap in the GIMPS era. And 114 days from hitting the average gap + 2 std dev.
10metreh has our next closest (non-expired) guess, 59,278,411 on 6/30/2011
And: [QUOTE]Countdown to testing all exponents below M(43112609) once: 868[/QUOTE]makes the guesses look like a bad bet:
tom11784.....38,066,453 [strike]6/23/2007[/strike]
T.Rex...........38,500,000
PrimeCrazzy..39,999,999 [strike]9/1/2007[/strike]
wpolly..........41,991,811 [strike]4/19/2008[/strike]
lycorn..........41,999,999 [strike]11/30/2007[/strike]
Andi47.........42,000,000 [strike]8/1/2007[/strike]
edorajh........42,500,000 [strike]10/1/2009[/strike]