mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2013-01-02, 20:36   #1
Jellyfish420
 
Jan 2013

19 Posts
Default Where to start

Basic overview.....i recently OCed my pc and started running P95 for stress. Thinking bout how big these numbers actually are and that 47 have ever been found has sparked my interest. I been doing LL tests on one core and TF on the other for bout 2weeks. Reading around on this forum. And i understand, to an extent, about what a mersenne prime is... But when people start talking bout different factors, and bit levels, and all the other good stuff i am totally lost. Ive searched around and i can find what stuff means but without a more basic knowledge the more advanced stuff really doesn't mean much. So after all that reading where do i start? Anyone got some links to some good reading? I need to learn the basics so i have something to build off of. Thank you to anyone that can help
Jellyfish420 is offline   Reply With Quote
Old 2013-01-02, 22:55   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

160358 Posts
Default

So when we talk about "exponents", such as s 59,xxx,xxx exponent, we mean that we're talking about the number 259,xxx,xxx-1, but it seems you know that.

The LL test is a guaranteed test of primality -- if it's says 2^p-1 is composite, then if definitely is, and if it says it's prime, it definitely is. Of course, as you've probably figured out, running an LL test takes quite a bit of time, even with highly-optimized assembly on modern processors, so if we can avoid the test, we've saved a bunch of computing time.

The easiest way to avoid the LL test is to prove that 2^p-1 is composite by showing that it has a factor. This is what trial factoring is: literally just try all numbers below a certain bound to see if they divide 2^p-1. (It's not quite like that -- but that's the idea.) So first we check all numbers below (say) 2^59. If TF fails to find such a factor, then we say that 2^p-1 has no factors less than 2^59, or alternately, we say that 2^p-1 was TFed to 59 bits. (That's because any number < 2^59 is 59 bits in binary representation.) Then we check for factors from 2^59 to 2^60, when we can say (if no factor was found) that 2^p-1 was TFed to 60 bits. Then we check between 2^60 and 2^61, etc. up to a certain bound where doing TF becomes more expensive that just doing the LL test -- typically around 72 or 73 bits for exponents in the 59 million range. (That's if the TF is done on a GPU -- for CPUs the crossover is around 69 bits.)

All in all, a bit more than ~60% of candidate exponents are found to have a small factor, meaning we save a lot of CPU time from doing useless LL tests. (Note: we also use a factoring method called P-1 ("p minus 1") factoring, but that works differently from TF.)

(PS @chalsall: Something's wrong in the 33M-34M region of the graphs.)

Last fiddled with by Dubslow on 2013-01-02 at 22:57
Dubslow is offline   Reply With Quote
Old 2013-01-03, 00:47   #3
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

2·4,441 Posts
Default

Poke around on the Wiki, here is a good page to start on: http://mersennewiki.org/index.php/Category:GIMPS_FAQ
Uncwilly is offline   Reply With Quote
Old 2013-01-03, 01:57   #4
Jellyfish420
 
Jan 2013

19 Posts
Default

Ok, i get that... I should of been clearer in my first post. I get ,for the most part, whats happening. The compute is finding factors of exponents cause its faster to do that than to LL test every number. What im curious about is the math side of it. People start throwing around equations and i just look at them for a min and go WTF? And also what does everyone mean when they say something is to expensive? Up 2 posts its too expensive to factor over 72...
Jellyfish420 is offline   Reply With Quote
Old 2013-01-03, 01:59   #5
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

52×373 Posts
Default

Quote:
Originally Posted by Dubslow View Post
(PS @chalsall: Something's wrong in the 33M-34M region of the graphs.)
Yeah... I know...
chalsall is offline   Reply With Quote
Old 2013-01-03, 02:48   #6
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

Quote:
Originally Posted by Jellyfish420 View Post
Ok, i get that... I should of been clearer in my first post. I get ,for the most part, whats happening. The compute is finding factors of exponents cause its faster to do that than to LL test every number. What im curious about is the math side of it. People start throwing around equations and i just look at them for a min and go WTF? And also what does everyone mean when they say something is to expensive? Up 2 posts its too expensive to factor over 72...
Well, I can answer about "expensive". Essentially, what's the most efficient way to use available CPU/GPU cycles? (Or, how many exponents can we clear with x many cycles available?)

Well, as you can imagine, since 2^73 = 2 * 2^72, doing one bitlevel takes about twice as much work to TF than the previous bitlevel. (That is, TFing 2^73-2^74 takes twice as much work as TFing 72-73.) Furthermore, the chance of finding a factor is roughly 1/bitlevel, so as you do more and more TF, you have less and less chance of finding a factor. (I can't quite prove this latter statement, but it's related to the distribution of primes.)

Thus, at a certain point, it takes more CPU time (or GPU time, in the case of TF) to find a factor than run an LL test on one exponent.

For instance, if TFing one exponent from 72-73 bits takes one day on your GPU, then on average you'd expect to find one factor (that is, clear one exponent as not prime) once every 73 days. If running an LL test on your CPU takes 73 days, then this is the "crossover point"; you'll clear more Mersenne numbers by running LL tests than by TFing them to 74 bits, so 73 bits is where you stop TFing.

That's roughly what we mean by expense: how many C/GPU cycles it takes to complete a particular assignment.



What parts of the math don't you get? I was just guessing, and clearly I guessed wrong. Please be more specific.
Dubslow is offline   Reply With Quote
Old 2013-01-03, 03:16   #7
Jellyfish420
 
Jan 2013

19 Posts
Default

Gotcha. It takes less time to ll numbers that high rather than tf.... I swear i saw some numbers up to 80 bit level. I could be mistaken and thats not important. I been going down to factoring projects and stuff and when i get to lookin at them i have no clue. There is a thread named fft explination for non math people(somethin like that, cant post link im on an ipod) either way a few posts down they start explaining i just get totally lost. Ive even read it slow a few times over and still dont get it. The same with all threads that start talkkng bout all the diff equations for diff problems. Last math class i took was 15 years ago in high school and i only went up to algebra 2. I guess all this factoring and such is higher than that.... And to be honest if it was in there i probably forgot. Should i just get a text book and start working through it? Calculus? I would like to know some of this stuff, but i dont wanna have to ask a question every post. Id like to be able to contribute. There's alot of projects on here but i have no. Clue whats going on... Does that make it ant clearer what im asking?
Jellyfish420 is offline   Reply With Quote
Old 2013-01-03, 05:30   #8
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

Quote:
Originally Posted by Jellyfish420 View Post
Gotcha. It takes less time to ll numbers that high rather than tf.... I swear i saw some numbers up to 80 bit level. I could be mistaken and thats not important. I been going down to factoring projects and stuff and when i get to lookin at them i have no clue. There is a thread named fft explination for non math people(somethin like that, cant post link im on an ipod) either way a few posts down they start explaining i just get totally lost. Ive even read it slow a few times over and still dont get it. The same with all threads that start talkkng bout all the diff equations for diff problems. Last math class i took was 15 years ago in high school and i only went up to algebra 2. I guess all this factoring and such is higher than that.... And to be honest if it was in there i probably forgot. Should i just get a text book and start working through it? Calculus? I would like to know some of this stuff, but i dont wanna have to ask a question every post. Id like to be able to contribute. There's alot of projects on here but i have no. Clue whats going on... Does that make it ant clearer what im asking?
That's a bit better, yes. After Algebra 2 is usually some sort of trigonometry, then precalc and then calc. I'm quite sure sure how directly useful those would be to the sort of math done here -- but it would at least be higher level math than just algebra 2.

As for 80 bits, you probably have seen it. In the current LL range (exponents around 60M), you might see someone take an exponent to 74 or 75 bits TF -- 80 would be more or less impossible. In the 100 million digit range though, exponents around 332M, or exponents higher than that (like 900M -- PrimeNet tracks them up to 1B) you might see some higher TF levels, like 80 and beyond. It's a slightly counter intuitive (at first glance) fact that TFing a bit level gets easier with higher exponents -- it takes about half as long to TF a 100M exponent to 75 bits than a 50M exponent to 75 bits. For both this reason and the fact that a longer LL test means more TF required, means that these higher exponents are taken to higher bit levels. So you probably have seen an expo taken to 80 bits. Graph -- try zooming in.
Dubslow is offline   Reply With Quote
Old 2013-01-03, 07:40   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×7×11×29 Posts
Default

This might be a better link. Try clicking on rows. :P
LaurV is offline   Reply With Quote
Old 2013-01-03, 13:47   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by Jellyfish420 View Post
Basic overview.....i recently OCed my pc and started running P95 for stress. Thinking bout how big these numbers actually are and that 47 have ever been found has sparked my interest. I been doing LL tests on one core and TF on the other for bout 2weeks. Reading around on this forum. And i understand, to an extent, about what a mersenne prime is... But when people start talking bout different factors, and bit levels, and all the other good stuff i am totally lost. Ive searched around and i can find what stuff means but without a more basic knowledge the more advanced stuff really doesn't mean much. So after all that reading where do i start? Anyone got some links to some good reading? I need to learn the basics so i have something to build off of. Thank you to anyone that can help
Mersenne factors are of form 2*k*p+1 for 2^p-1 , p being a prime.

from this an example:

2^11-1 = 2047

2047/23 = 89

23=2*1*11+1
89=2*4*11+1

2047 = 2*93*11+1
science_man_88 is offline   Reply With Quote
Old 2013-01-03, 16:41   #11
Jellyfish420
 
Jan 2013

19 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Mersenne factors are of form 2*k*p+1 for 2^p-1 , p being a prime.

from this an example:

2^11-1 = 2047

2047/23 = 89

23=2*1*11+1
89=2*4*11+1

2047 = 2*93*11+1
So where did 23 and 93 come from? Factors of 2047? So in LL tests its does all these calculations for every iteration? I just thought there was one equation that each number went in... Didnt realize there was a handfull..

Ok 23 is a factor. And 93 is k.... But what is k and why is k 3 different numbers? I guess thats what is throwing me off the most. I always thought that the number stayed the same throughout the problem. ie. p=11 everywhere there is a p ... But k=23, 89, & 93.

Last fiddled with by Jellyfish420 on 2013-01-03 at 16:50
Jellyfish420 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Where should I start? christian_ Information & Answers 9 2016-01-22 19:28
Before you start... jasonp Operation Kibibit 65 2013-09-03 22:06
How to start? Thomas11 Lone Mersenne Hunters 29 2008-12-21 13:47
how to start with P-1? ValerieVonck Marin's Mersenne-aries 8 2006-04-29 22:21
How to start? OmbooHankvald Factoring 15 2005-09-03 13:42

All times are UTC. The time now is 09:44.

Fri Nov 27 09:44:43 UTC 2020 up 78 days, 6:55, 4 users, load averages: 1.75, 1.21, 1.12

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.