GPU TF work and its impact on P-1

[davieddy]

Originally Posted by fivemack

If I recall correctly, the GPUs are a bit faster than the fastest-available CPUs at doing LL tests, and something like a hundred times faster than the fastest-available CPUs at trial factoring. So it makes sense to devote them to trial-factoring.

ATM
On electric bill grounds, it makes NO sense to do LL tests on GPUs

On all grounds, it makes no sense to do TF on CPUs.

If any further disincentive were needed to explain the reluctance
to embark on, and complete, a first time LL test, the thought that
a GPU could TF an extra 6 bits in ~ a day is a further deterrent.

This boosts the likelihood of primality by about 9%.

(It may also render P-1 pointless, but the clamour to do this
in the 53M+ range is barely audible!)

So GPUs contribute most effectively to the prime search
by TFing an extra 6 bits in the 53M range.
They should receive some acknowledgement (10%),
should it yield a prime.

David

[Christenson]

Originally Posted by davieddy

ATM
On electric bill grounds, it makes NO sense to do LL tests on GPUs

David

Can you support that with some numbers? I calculated that the TF could remove perhaps 10% of the LL tests, leaving the other 90% still needed.

[davieddy]

Originally Posted by Xyzzy

Two GPU setups net you 540GHz/days per day.

Originally Posted by TheJudger

But only for Trial Factoring.
Primenet needs more horsepower on Lucas Lehmer and Double Checks.
Xyzzy: how much throughput has your setup (2x GTX 570?) for LL/DCs?

Oliver

Originally Posted by Xyzzy

So little that we would not waste the electricity.

Originally Posted by davieddy

ATM
On electric bill grounds, it makes NO sense to do LL tests on GPUs

On all grounds, it makes no sense to do TF on CPUs.


So GPUs contribute most effectively to the prime search
by TFing an extra 6 bits in the 53M range.
They should receive some acknowledgement (10%),
should it yield a prime.

David

Originally Posted by Christenson

Can you support that with some numbers? I calculated that the TF could remove perhaps 10% of the LL tests, leaving the other 90% still needed.

I was citing Xyzzy.
You know more than I do about the electricity needed to do a given
LL test on a GPU instead of a CPU.

LL for M4570xxxx 36% done. ETA Aug 12th. Celeron 440 @2GHz.
Prime95 v25.11;( FFT 2560K.
You already have the credit for TFing from 68 to 74 bits.
When it turns out prime, I shall acknowledge your contribution
and even pay for the electricity you used

The probability of you finding no factor was 67/73,
so the probability of one or more was 6/73 (~8%).

BUT it had P-1 done with B1=480000 B2=4080000.
Can someone supply a simple formula to tell me what
the probability of P-1 finding a factor between 2^X and 2^(X+!)
was?

David

[Mr. P-1]

Originally Posted by davieddy

an extra 6 bits ... may also render P-1 pointless

mprime chose B1=530000, B2=13382500 for one of my assignments with the (correct) TF bit depth of 68. Changing the depth to 74, and leaving all other settings the same, it choose B1=355000, B2=5946250.

Extra TF makes P-1 less valuable, which is reflected in the reduced bounds. But it does not make it pointless (assuming the program's calculation of the optimal bounds is correct, of course).

[Mr. P-1]

Originally Posted by davieddy

Can someone supply a simple formula to tell me what
the probability of P-1 finding a factor between 2^X and 2^(X+!)
was?

I don't have a simple formula, but you should be able to find what you need in sections 2 and 3 of Bob Silverman's paper.

[R.D. Silverman]

Originally Posted by Mr. P-1

I don't have a simple formula, but you should be able to find what you need in sections 2 and 3 of Bob Silverman's paper.

The probability that a large integer N (N --> oo) has a factor betwen x
and x^(1+e) is e/(e+1). The proof I give uses Mertens' Theorem.

[wblipp]

Originally Posted by davieddy

Can someone supply a simple formula to tell me what
the probability of P-1 finding a factor between 2^X and 2^(X+!) was?

Originally Posted by R.D. Silverman

The probability that a large integer N (N --> oo) has a factor betwen x and x^(1+e) is e/(e+1). The proof I give uses Mertens' Theorem.

That's an upper bound because it includes factors that P-1 will not find. My guess is that the k from 2kp+1 will behave like a random integer, so you can use the Dickman Function on (x/2p) to calculate the probability the factor will be found. I'd further guess the probabilities are independent and can be multiplied together for a reasonable estimate.

[davieddy]

Originally Posted by R.D. Silverman

The probability that a large integer N (N --> oo) has a factor betwen x
and x^(1+e) is e/(e+1). The proof I give uses Mertens' Theorem.

If x=2^70 and x^(1+e)=2^71 then e=1/70
Probabity is 1/71. We knew this (except I thought it was 1/70).

I am interested in the probability of P-1 (with GIMPS optimized bounds)
finding a factor between 2^70 and 2^71.

From data helpfully supplied in This thread post#595
I judge that the probability of P-1 finding a factor between 2^(70+x)
and 2^(71+x) is P(x) = P(0)*2^(-x/8)

In the 53M exponent range, (well P-1 ed) 1500 factors were found
in about 21000 attempts (7% as roughly expected)

I reckon P(0) ~ 7/12 % ~ 0.6%

This tallies with George's recollection that P-1 finds
30-40% of the factors between 2^70 abd 2^71.



David

[Mr. P-1]

Originally Posted by davieddy

This tallies with George's recollection that P-1 finds
30-40% of the factors between 2^70 abd 2^71.

That statement is only an approximation, and it tells us about how the aggregate of P-1 computations actually done by the project perform. It does not tell us how to relate the P-1 bounds to the probability of success.

[davieddy]

Originally Posted by davieddy

If x=2^70 and x^(1+e)=2^71 then e=1/70
Probabity is 1/71. We knew this/
I am interested in the probability of P-1 (with GIMPS optimized bounds)
finding a factor between 2^70 and 2^71.

From data helpfully supplied in This thread post#595
I judge that the probability of P-1 finding a factor between 2^(70+x)
and 2^(71+x) is P(x) = P(0)*2^(-x/8)

In the 53M exponent range, (well P-1 ed) 1500 factors were found
in about 21000 attempts (7% as roughly expected)

I reckon P(0) ~ 7/12 % ~ 0.6%

This tallies with George's recollection that P-1 finds
30-40% of the factors between 2^70 abd 2^71.

Originally Posted by Mr. P-1

That statement is only an approximation, and it tells us about how the aggregate of P-1 computations actually done by the project perform. It does not tell us how to relate the P-1 bounds to the probability of success.

That's why "tallying" was relevant. James Heinrich promptly
supplied (see link) numbers of all known factors for exponents 40-60M
broken down by range and bits.

The frequency for bits >72 halved every 8 bits, hence my guess
that P(x) = (7/1200) 2^(-x/8).
Summing 2^(-x/8) for x=0 to oo gives 12.

So P-1 finds 40% of 71 bit factors (for a "good" hit rate of 7%),
hence George's 30-40%.

Each extra bit of TF reduces the yield of a subsequent P-1 by 11/12.

David

BTW a plausible alternative formula is:
P(x) = (7/1200) 2^(-x/8) * 70/(70+x)
But:
1) I can't readily sum it
2) The difference is unimportant for my intended purposes.
Is there a theoretical justification for either version?

[davieddy]

@Mods:
Would posts from #16 onwards usefully be moved to "P-1 factoring anyone?"?