mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Lone Mersenne Hunters (https://www.mersenneforum.org/forumdisplay.php?f=12)
-   -   fond of a factor? Urn yourself to become remains (https://www.mersenneforum.org/showthread.php?t=13977)

LaurV 2019-10-04 09:09

yeah, that's what we said... :razz: ye only made it (too) technical... hehe

Maciej Kmieciak 2019-10-04 14:41

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

Dylan14 2019-10-04 15:30

[QUOTE=Maciej Kmieciak;527298]One more newbie question. Why TF on bigger exponents is faster than on smaller ones? It seems counterintuitive[/QUOTE]

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.

James Heinrich 2019-10-04 15:31

[QUOTE=Maciej Kmieciak;527298]One more newbie question. Why TF on bigger exponents is faster than on smaller ones? It seems counterintuitive[/QUOTE]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 [url=https://www.mersenne.ca/exponent/83]M83[/url], 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 [url=https://www.mersenne.ca/exponent/830000063]M830,000,063[/url], 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 2[sup]40[/sup]-2[sup]41[/sup]:
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?

Maciej Kmieciak 2019-10-04 17:00

[QUOTE]Does that make sense?[/QUOTE]
Yeah, now I understand. Thank you.

[QUOTE]for M10,000 k is between 54975581 and 109951162, giving [B]54,975,581 [/B]candidates to test
for M10,000,000 k is between 54975 and 109951, giving [B]54,975[/B] candidates to test
for M1,000,000,000 k is between 549 and 1099, giving [B]549[/B] candidates to test[/QUOTE]

And the chance of finding a factor remains 1/40 regardless of the number of candidates?

James Heinrich 2019-10-04 17:56

[QUOTE=Maciej Kmieciak;527309]And the chance of finding a factor remains 1/40 regardless of the number of candidates?[/QUOTE]Yes, chance of factor should be roughly 1/<bitdepth> regardless.

Jan S 2019-10-12 16:21

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)

retina 2019-10-12 16:50

[QUOTE=Jan S;527828]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)[/QUOTE]76.5107 bits

Is that just outside the TF depth?

petrw1 2019-10-12 16:53

[QUOTE=retina;527830]76.5107 bits

Is that just outside the TF depth?[/QUOTE]

Inside. GPU to 72 is taking this range to 77 bits.

retina 2019-10-12 17:29

[QUOTE=petrw1;527832]Inside. GPU to 72 is taking this range to 77 bits.[/QUOTE]That's what I initially thought. So a TF failure. Someone has a bad GPU card?

Prime95 2019-10-12 17:46

[QUOTE=retina;527834]That's what I initially thought. So a TF failure. Someone has a bad GPU card?[/QUOTE]

A look at the history [url]https://www.mersenne.org/report_exponent/?exp_lo=97388611&exp_hi=&full=1[/url] shows that GPUs had only taken the exponent to 2^74


All times are UTC. The time now is 22:53.

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