mersenneforum.org fond of a factor? Turn yourself in to become insane.
 Register FAQ Search Today's Posts Mark Forums Read

 2019-10-04, 09:09 #1508 LaurV Romulan Interpreter     Jun 2011 Thailand 31·271 Posts yeah, that's what we said... ye only made it (too) technical... hehe
 2019-10-04, 14:41 #1509 Maciej Kmieciak   Nov 2018 Poland 2·7 Posts 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
2019-10-04, 15:30   #1510
Dylan14

"Dylan"
Mar 2017

22×113 Posts

Quote:
 Originally Posted by Maciej Kmieciak 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.

2019-10-04, 15:31   #1511
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

2×32×157 Posts

Quote:
 Originally Posted by Maciej Kmieciak 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

2019-10-04, 17:00   #1512
Maciej Kmieciak

Nov 2018
Poland

2·7 Posts

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?

2019-10-04, 17:56   #1513
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

2×32×157 Posts

Quote:
 Originally Posted by Maciej Kmieciak 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.

 2019-10-12, 16:21 #1514 Jan S   Oct 2018 Slovakia 24·3 Posts 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)
2019-10-12, 16:50   #1515
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

14C516 Posts

Quote:
 Originally Posted by Jan S 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?

2019-10-12, 16:53   #1516
petrw1
1976 Toyota Corona years forever!

"Wayne"
Nov 2006

10AE16 Posts

Quote:
 Originally Posted by retina 76.5107 bits Is that just outside the TF depth?
Inside. GPU to 72 is taking this range to 77 bits.

2019-10-12, 17:29   #1517
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

531710 Posts

Quote:
 Originally Posted by petrw1 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?

2019-10-12, 17:46   #1518
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

11010011001002 Posts

Quote:
 Originally Posted by retina 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

 Similar Threads Thread Thread Starter Forum Replies Last Post ewmayer Programming 3 2016-09-30 07:15 markdjonson Information & Answers 9 2012-12-31 15:34 Rafael Information & Answers 12 2012-01-02 19:38 rogue Lounge 10 2008-11-21 05:25 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