mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2011-07-14, 01:43   #1
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

6,451 Posts
Default GPU TF work and its impact on P-1

Quote:
Originally Posted by fivemack View Post
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

Last fiddled with by davieddy on 2011-07-14 at 02:03
davieddy is offline   Reply With Quote
Old 2011-07-14, 11:03   #2
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

24·107 Posts
Default

Quote:
Originally Posted by davieddy View Post
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.
Christenson is offline   Reply With Quote
Old 2011-07-14, 14:42   #3
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

6,451 Posts
Default

Quote:
Originally Posted by Xyzzy View Post
Two GPU setups net you 540GHz/days per day.

Quote:
Originally Posted by TheJudger View Post
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
Quote:
Originally Posted by Xyzzy View Post
So little that we would not waste the electricity.
Quote:
Originally Posted by davieddy View Post
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
Quote:
Originally Posted by Christenson View Post
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

Last fiddled with by davieddy on 2011-07-14 at 15:02
davieddy is offline   Reply With Quote
Old 2011-07-15, 22:24   #4
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7·167 Posts
Default

Quote:
Originally Posted by davieddy View Post
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 is offline   Reply With Quote
Old 2011-07-15, 22:41   #5
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7·167 Posts
Default

Quote:
Originally Posted by davieddy View Post
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.
Mr. P-1 is offline   Reply With Quote
Old 2011-07-15, 23:11   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

161008 Posts
Default

Quote:
Originally Posted by Mr. P-1 View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-07-16, 01:33   #7
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22·32·5·13 Posts
Default

Quote:
Originally Posted by davieddy View Post
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?
Quote:
Originally Posted by R.D. Silverman View Post
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.
wblipp is offline   Reply With Quote
Old 2011-07-16, 01:51   #8
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

11001001100112 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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

Last fiddled with by davieddy on 2011-07-16 at 02:20
davieddy is offline   Reply With Quote
Old 2011-07-16, 08:47   #9
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

100100100012 Posts
Default

Quote:
Originally Posted by davieddy View Post
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.
Mr. P-1 is offline   Reply With Quote
Old 2011-07-16, 10:57   #10
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

6,451 Posts
Default

Quote:
Originally Posted by davieddy View Post
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.
Quote:
Originally Posted by Mr. P-1 View Post
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 is offline   Reply With Quote
Old 2011-07-16, 11:19   #11
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

11001001100112 Posts
Default

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

Last fiddled with by davieddy on 2011-07-16 at 11:22
davieddy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Impact of AI xilman Lounge 19 2017-01-26 16:03
First pre-impact discovery for NEO search! cheesehead Astronomy 42 2013-11-22 04:54
GPUs impact on TF petrw1 GPU Computing 0 2013-01-06 03:23
Another Impact on Jupiter Spherical Cow Astronomy 24 2009-08-12 19:32
NASA's Deep Impact... ixfd64 Lounge 5 2005-07-06 13:46

All times are UTC. The time now is 19:29.

Sun Nov 29 19:29:41 UTC 2020 up 80 days, 16:40, 4 users, load averages: 1.25, 1.39, 1.35

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.