mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Lone Mersenne Hunters

Reply
 
Thread Tools
Old 2019-10-04, 09:09   #1508
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

31·271 Posts
Default

yeah, that's what we said... ye only made it (too) technical... hehe
LaurV is offline   Reply With Quote
Old 2019-10-04, 14:41   #1509
Maciej Kmieciak
 
Nov 2018
Poland

2·7 Posts
Default

One more newbie question. Why TF on bigger exponents is faster than on smaller ones? It seems counterintuitive

Last fiddled with by Maciej Kmieciak on 2019-10-04 at 14:45
Maciej Kmieciak is offline   Reply With Quote
Old 2019-10-04, 15:30   #1510
Dylan14
 
Dylan14's Avatar
 
"Dylan"
Mar 2017

22×113 Posts
Default

Quote:
Originally Posted by Maciej Kmieciak View Post
One more newbie question. Why TF on bigger exponents is faster than on smaller ones? It seems counterintuitive
Recall that any factor of a Mersenne number must have the form of 2*k*p+1, where p is prime. Clearly, if p is larger, then a smaller k is needed to get to the same bit level.
Case in point: for M22040009 you need to test to k = 26782920567714 to get to 2^70 whereas for M220400143 you have to test to k = 2678291412717 to get to the same point.
Dylan14 is offline   Reply With Quote
Old 2019-10-04, 15:31   #1511
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

2×32×157 Posts
Default

Quote:
Originally Posted by Maciej Kmieciak View Post
One more newbie question. Why TF on bigger exponents is faster than on smaller ones? It seems counterintuitive
Mersenne factors are in the form of 2*k*<exponent>+1, where k is more-or-less any number from 1 to very-big (there are some restrictions on what k can actually be, but ignore those for now).
The smallest possible factor for any Mersenne number is where k=1.
Take for example M83, which does indeed have such a factor:
(2 * 1 * 83) + 1 = 167 (roughly 7.4 bits)
and 167 is a factor of M83.
But if we take a larger exponent, say M830,000,063, then the smallest possible factor is:
(2 * 1 * 830000063) + 1 = 1660000127 (roughly 30.6 bits)

So you can see the larger the exponent, by necessity the factors are also bigger.

TF software doesn't work by bitlevel directly (that's just a convenient measure of progress) but by checking all the valid k values between the two bit levels. Due to the relationship between exponent and k and bitsize, you have fewer possible k values at a given bitlevel for larger exponents.

To illustrate, consider three exponent ranges, that you want to TF from 240-241:
for M10,000 k is between 54975581 and 109951162, giving 54,975,581 candidates to test
for M10,000,000 k is between 54975 and 109951, giving 54,975 candidates to test
for M1,000,000,000 k is between 549 and 1099, giving 549 candidates to test
So even though the bitsize of the factors that might be found is constant, as the exponents get larger there are fewer possible candidates that need to be checked.

Does that make sense?

Last fiddled with by James Heinrich on 2019-10-04 at 15:32
James Heinrich is offline   Reply With Quote
Old 2019-10-04, 17:00   #1512
Maciej Kmieciak
 
Nov 2018
Poland

2·7 Posts
Default

Quote:
Does that make sense?
Yeah, now I understand. Thank you.

Quote:
for M10,000 k is between 54975581 and 109951162, giving 54,975,581 candidates to test
for M10,000,000 k is between 54975 and 109951, giving 54,975 candidates to test
for M1,000,000,000 k is between 549 and 1099, giving 549 candidates to test
And the chance of finding a factor remains 1/40 regardless of the number of candidates?
Maciej Kmieciak is offline   Reply With Quote
Old 2019-10-04, 17:56   #1513
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

2×32×157 Posts
Default

Quote:
Originally Posted by Maciej Kmieciak View Post
And the chance of finding a factor remains 1/40 regardless of the number of candidates?
Yes, chance of factor should be roughly 1/<bitdepth> regardless.
James Heinrich is offline   Reply With Quote
Old 2019-10-12, 16:21   #1514
Jan S
 
Oct 2018
Slovakia

24·3 Posts
Default

P-1 found a factor in stage #2, B1=915000, B2=21045000, E=12.
UID: js2010/SATURN, M97388611 has a factor: 107653599012618660746761 (B1=915000, B2=21045000)
Jan S is offline   Reply With Quote
Old 2019-10-12, 16:50   #1515
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

14C516 Posts
Default

Quote:
Originally Posted by Jan S View Post
P-1 found a factor in stage #2, B1=915000, B2=21045000, E=12.
UID: js2010/SATURN, M97388611 has a factor: 107653599012618660746761 (B1=915000, B2=21045000)
76.5107 bits

Is that just outside the TF depth?
retina is online now   Reply With Quote
Old 2019-10-12, 16:53   #1516
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

10AE16 Posts
Default

Quote:
Originally Posted by retina View Post
76.5107 bits

Is that just outside the TF depth?
Inside. GPU to 72 is taking this range to 77 bits.
petrw1 is offline   Reply With Quote
Old 2019-10-12, 17:29   #1517
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

531710 Posts
Default

Quote:
Originally Posted by petrw1 View Post
Inside. GPU to 72 is taking this range to 77 bits.
That's what I initially thought. So a TF failure. Someone has a bad GPU card?
retina is online now   Reply With Quote
Old 2019-10-12, 17:46   #1518
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

11010011001002 Posts
Default

Quote:
Originally Posted by retina View Post
That's what I initially thought. So a TF failure. Someone has a bad GPU card?
A look at the history https://www.mersenne.org/report_expo...exp_hi=&full=1 shows that GPUs had only taken the exponent to 2^74
Prime95 is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Turn off GCC sse-using optimizations? ewmayer Programming 3 2016-09-30 07:15
2 of 4 cores slow down significantly when I turn main monitor off markdjonson Information & Answers 9 2012-12-31 15:34
When I run PRIME95, my computer threatens to turn off Rafael Information & Answers 12 2012-01-02 19:38
A fond farewell rogue Lounge 10 2008-11-21 05:25
turn off your integrated Snd card in CMOS nngs Hardware 0 2005-05-20 01:31

All times are UTC. The time now is 06:05.

Wed Apr 8 06:05:41 UTC 2020 up 14 days, 3:38, 2 users, load averages: 1.59, 1.48, 1.42

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.