help a total noob get started

[nmathew]

I'm interested in helping with one of the distributed mathematical projects. To be perfectly honest, I don't know for sure if I will pick this project, but it seems like a good place to start.

For background, I have a BS in chemistry, and I'm fairly comfortable with computer lingo so long as it stays away from UNIX specifics(winblowz user for convinience). So far, following the math and most of the programming ideas hasn't been an issue.

I am a but lost by the terms used here. I have picked up what sieving is for instance, but from what I can gather, there isn't a single FAQ on this board that would help me out. If so, please direct me there.

I'd like to know what programs I should use, what hardware is best at what projects, and simple things such as that.

I will be using several CPU's. An Athlon 64, two Athlon XP CPUs, a Pentium 4 or two (with hyperthreading), a pentium pro, and possibly a pentium 3. It's a wide range of chips, and it would be nice if I used them in an efficient manner.

I'll probably be bringing around 8-9 gHz to the project. I don't know if that's enough for you guys to bother helping me out or not, but a solid FAQ as talked about elsewhere on the board would really make it easier for people like me to get involved.


Thanks for any help in advance.

[Mystwalker]

I looked around a bit and figured out that there is none on this board (which indeed can be improved), but I found a "F.A.Q." button on the SeventeenOrBust Homepage. This guides you to the TPR Seventeen or Bust client FAQ , for example. There are surely still a lot of questions open after having read that, but it seems to be a good start.

There is another detailed description ("What we are doing" - reedited by Nuri) somewhere around, but I can't find it ATM.

A lot of additional information about sieving can be found on MikeH's All Things SoB Sieving page - the point "Regular sieving" provides a short instruction of what it takes to sieve.

Basically, sieving finds factors for the tests (often called "k/n" pairs, as the k value and the n value specify the number to be tested for primality: k*2^n+1) that have to be done by the "main project client" otherwise.
Sieving is extremely favorable for AthlonXP and P3 CPUs (and also PPro's, I guess).

When it comes to P4s, they are less good for sieving (esp. with a low FSB / memory bus), but really perform great when doing the regular testing (also called "PRPing", as they are PRP test, where PRP stands for PRobable Prime) or factoring*. They should be used there. I'm not sure about Athlon64s - AFAIK, they are good at sieving, but could also be fast at PRPing/factoring. Experience from an owner is needed here...


*Factoring tries to find a factor for a k/n pair as sieving, but it more or less takes "the other way round" - I won't go into details right now; ask if you are more interested in it.

I hope I was able to answer some of your questions and that you feel happy at this project.

[Mystwalker]

I have found the file I was looking for and completed some adaptions, as a few things changed in the last months (like finding a new prime ).

The factoring part is still missing, though. Maybe I find some time tomorrow to write it down. If someone wants to look over the changes, I'm happy about every constructive feedback.

[Nuri]

May be this is a good opportunity to create a compact explanation version of what SoB is all about...

I'm moving the content from the txt file to post format, just to encourage forum members for comments/additions. I've not changed much so far, but will try to contribute as I find time for it.

Cheers,

Nuri


What are we doing?
What is PRPing?
What is sieving?
What are we double checking?
What is factoring and the P-1 stuff you are discussing? (to come) <<< factoring missing>>>
Which is best for me/my PC? (smth. like that?)

What are we doing?

We are trying to find a prime of the form k*2^n+1, for one of the following eleven k:
4847, 10223, 19249, 21181, 22699, 24737, 27653, 28433, 33661, 55459, 67607, and for any positive integer n.

When Seventeen or Bust Project started there were seventeen k values for which we were trying to find a prime, hence the name Seventeen or Bust. We have already found six primes, so we only have eleven to go.

A short description is also available at http://www.seventeenorbust.com/ under the topic "What Is It?" on the main page.


What is PRPing?

To find these remaining eleven primes, we are using a client based on the PRP program. This program checks a number to see if it is prime or not. Sometimes it can only say that it is PRobably Prime hence its name.

Seventeen or Bust started PRPing wherever the previous researchers had left off. In some cases n was about 300,000 (3*10^5 or 300K), in other cases n was about 2,000,000 (2*10^6 or 2M).


What is sieving?

One way to prove that a number is not prime is to break it down into its prime factors. Centuries ago (around 240 BC) Eratosthenes used trial division by the known small primes to determine if a number was prime or not. His method is now called the "Sieve of Eratosthenes". While the current sieve programs are much more sophisticated and faster than trial division, we still call the process sieving. The benefit of sieving comes from the fact that it eliminates values of n more efficiently than PRPing k*2^n+1.



A Short History of SoB Sieve Effort

The primary sieve effort started in January 2003 when PRPing was testing n values approaching n = 3,000,000 (3*10^6 or 3M). Prior to that time, Louie Helm (one of the cofounders of this project along with David Norris) had been sieving all along using the supercomputers at the University of Michigan, but this is when the effort "went public". Louie decided on the range 3M < n < 20M for the primary sieving effort.

Prior to the initiation of public sieve in January 2003, the sieve clients were only able to check for one k at a time, whereas the client that we started using for the public sieve can check for all then eleven k simultaneously. Since the beginning of the official sieving effort, there has been many algorithm enhancements, resulting in more than 50 times increase in sieve client speed with respect to the first version that we started using in January.

As the speed improvements of the sieve client were taking place, the idea of starting a second sieve effort, that would sieve the range 1 < n < 3,000,000 started to flourish. The main objective of this second sieve effort was to eliminate the number of candidates for future double checking of the PRP tests for n below 3M. This is where its name comes from. So, we are not double checking the sieving at "Double Check Sieve" (or "Low n Range Sieving"). We are sieving to decrease the number of candidates for future double checking of previous PRP efforts. As sieve clients were much slower previously (and could only sieve for one k at a time), it was not possible for Louie to sieve the range n below 3M deep enough, despite allocating a significant amount of computing power to the effort.

While we originally started the Double Check Sieve with 1 < n < 3M, we changed the sieve range to 300K < n < 3M at p=1,500,000,000,000 (15*10^11 or 1,500,000,000K or 1,500,000M or 1,500G or 1.5T) to speed up the sieving of the low n range. The range 1 < n < 300K has been checked a couple of times by other means. So we have not completely ignored it, just eliminated it from the low n range sieving, since it is as important as it was.

There is also a third sieve, which simply combines the ranges of the "Primary Sieve" and "Low n Range Sieve", checking for 300K < n < 20M simultaneously. This is why it is called "Dual Sieve". Dual Sieve is just a few percent slower when compared to the Primary Sieve, but the factors for Low n Range comes for free. To participate in Dual Sieve, simply post your reservation and completion for the same range on both Sieve Coordination and Double Checking Coordination threads, and of course, do not forget to use the related SoB.dat file (n300K-20M). Factor submission is the same for all sieves.

The Dual Sieve eventually switched over to a range of 1M < n < 20M and kind of merged with the original sieve. There was no further need to find factors for smaller n's because those are all checked twice by the PRP client or will be in the near future.

This Dual Sieve is the main sieve project by now, while the DC sieve is still active nevertheless.

Happy sieving!


How can I participate to Sieving?

To sieve you need a computer, a client, a SoB.dat file, and a range to sieve.

The fastest client for most platforms (Windows, Linux, BSD; all x86 CPUs only) is Mikael Klasson's proth_sieve, which can be obtained here: http://n137.ryd.student.liu.se/proth_sieve.php
For other platforms (SunOS/Sparc, OSX/PPC and Linux/Alpha), there's NbeGon from Phil Carmody, available here: http://fatphil.org/maths/sierpinski/
Please note that development of this client has been closed a long time ago, thus the performance is way below that of proth_sieve.

The SoB.dat files can be obtained from MikeH's "All Things SoB Sieving" page: http://www.aooq73.dsl.pipex.com/
They contain all n values in the range that had not been eliminated by sieving at the time the file was created. The included sob.txt file has the same n values in 'clear' just for your information.


To participate in the sieve reserve a block on the respective range sieve (found here: http://www.free-dc.org/forum/forumdi...?s=&forumid=51 ). When you have factors submit them the normal way ( URL=http://www.seventeenorbust.com/sieve/ - be sure that you are logged in so the factors can be accounted to you). When the block has been processed, post the completion on the coordination thread the same way that you posted the reservation.


The current sieve and factoring statistics, ably done by MikeH, can be found here: http://www.aooq73.dsl.pipex.com/scores.txt
We have two GAP analyses, one for 1500G < p < 10000G ( http://www.aooq73.dsl.pipex.com/holesLowN1.txt ), and one for 10000G < p < 30000G (url=http://www.aooq73.dsl.pipex.com/holesLowN2.txt ).
Mike updates these on every 6 hours.


What is factoring and the P-1 stuff you are discussing?


hcgrove has made an excellent site about Factoring for Seventeen or Bust

[Frodo42]

hcgrove has also made this excellent site on P-1

[hc_grove]

Originally posted by Nuri
May be this is a good opportunity to create a compact explanation version of what SoB is all about...

I'm moving the content from the txt file to post format, just to encourage forum members for comments/additions. I've not changed much so far, but will try to contribute as I find time for it.

Wouldn't it be better to post this in the main forum?

... whereas the client that we started using for the public sieve can check for all then twelve k
simultaneously.

Eleven!

[Nuri]

Originally posted by hc_grove
Wouldn't it be better to post this in the main forum?

I agree. I posted it here, just because the thread stated here. May be one of the moderators can move the entire thread to our main forum page.

Eleven! [/B]

Done. Thx.

[Mystwalker]

Originally posted by hc_grove
Eleven!

I wrote that "twelve" on purpose, as it was the amount of k's we searched at that time (note the "then" prior to it).
Maybe we should change it to "all the remaining"...

[ceselb]

Moved to main forum, enjoy.

[royanee]

Are the links at the bottom broken? Also, Low n sieving as practically completed. Right?

[hhh]

There are still noobs who would like to do factoring but don't get started. Me for example.

With the information above I collected
sbfactor.exe
results.txt
sob.dat (to which there is no link　in the factoring section)

Now, I need to know which parameters I have to put in (as far as I understood, sbfactor is a command line program), after reserving a range, of course.

I remember having seen that we might have to put in beginning and end of the range,　two numbers B1 and B2, the available memory...

In one word, could you please give me an example of the use, like

sbfactor .. .. .. .. .. ..

replacing .. by variables and saying what they are good for?

Also the actually best choice of B1 and B2 would be interesting.

I have some P4 Celeron 2 GHz with 256 MB Ram.

Thank you in advance; I am sorry to disturb you, but really, it's not easy in the beginning.
I

[jasong]

Would someone please post the following link at the beginning of the factor reservation thread:

http://www.sslug.dk/~grove/sbfactor/

Except for the fact that I reserved WAY too much on my first try(totally my fault), this link was a tremendous help.

thank you

[OmbooHankvald]

Hi, I'm beginning to understand sbfactor, but there is one thing I still can't figure out: How do I find out what values of B1 and B2 I should use? Yes, I have read Garo's explanation at hc_grove's site but, frankly, I didn't understand anything (I'm not that good at math)

Can't you keep a constantly updated place where you write the current "optimal" B1 and B2?? Or is it different from CPU to CPU?

Help!

OH

[hc_grove]

Originally posted by OmbooHankvald
Hi, I'm beginning to understand sbfactor, but there is one thing I still can't figure out: How do I find out what values of B1 and B2 I should use? Yes, I have read Garo's explanation at hc_grove's site but, frankly, I didn't understand anything (I'm not that good at math)

You shouldn't normally set B1 and B2 yourself, but just let the program (sbfactor or mprime/prime95) choose them based on several values that are easier to understand, e.g.

• Sieve depth
• Factor value
• amount of RAM

Can't you keep a constantly updated place where you write the current "optimal" B1 and B2?? Or is it different from CPU to CPU?

The current sieve depth could be placed somewhere, bu it doesn't change very often, and running with a value slightly off doesn't ruin anything, and if you read the factoring forum, I guess you'll find out when people change what value they use. At the moment I'd say 49.7 (correspond to the 90% sieve point) is a reasonable value.

The factor value tells how many prp tests you expect a factor will save. Choosing a value smaller than 1 or greater than 2, makes very little sense. When p-1 factoring bagan, most people used 1.5, but at times some people have been using smaller values to make tests faster. This is probably the value you should change if any.

Stage 2 of the factoring can use a lot of RAM, but you are the only one who knows how much RAM you need for other programs, and thus how much you can allow it to use. Personally I'd say that if you can't allow it to use to use at least 256MB (preferably a lot more) you shouldn't be factoring.

[garo]

Don't use sbfactor. Use the latest version of Prime95 v24.13 at http://mersenne.org/gimps/p95v2413.zip

And use the perl script posted elsewhere in the forum to create wtd files. I would recommend using 49.5 as sieve depth and 1.7 as factor value. A higher sieve depth or a lower factor value seems to result in Prime95 saying no P-1 factoring is required. The reason fo this is that SOB has sieved evry deeply and the chance of finding a factor in P-1 is so small that P-1 does not save any time with lower factor values.