Type of work I'm doing
 

Hi!

The Prime95 says I'm working on "Trial Factoring M87471793 to 2^69". Does this mean I don't work on finding a new prime? I know any work counts, but I read in a very old post that there were four types of work you could do. Only one of them were testing for new primes (directly). How is this so, I can't remember choosing any particular assignment? If I really want to test for my own prime, am I able to do so? In such case, what do I do?

[QUOTE=Unregistered;343876]Hi!

The Prime95 says I'm working on "Trial Factoring M87471793 to 2^69". Does this mean I don't work on finding a new prime? I know any work counts, but I read in a very old post that there were four types of work you could do. Only one of them were testing for new primes (directly). How is this so, I can't remember choosing any particular assignment? If I really want to test for my own prime, am I able to do so? In such case, what do I do?[/QUOTE]

At the moment, you're searching for a small factor. If you find one, then the number is not prime and you will have disposed of that exponent.

If you don't, then what happens next depends upon the type of assignment you have. Have a look at your worktodo.txt file. If the line with 87471793 in it begins with "Test=", then you will go on to test that exponent for primality. If it begins with "Factor=" then you won't, and the exponent will be given to someone else for testing.

[QUOTE=Unregistered;343876]"Trial Factoring M87471793 to 2^69". Does this mean I don't work on finding a new prime? I know any work counts, but I read in a very old post that there were four types of work you could do. Only one of them were testing for new primes (directly). How is this so, I can't remember choosing any particular assignment? If I really want to test for my own prime, am I able to do so? In such case, what do I do?[/QUOTE]
What are the specifications for your PC? If it is 'old' PrimeNet will give it Trial Factoring work by default (you are correct that TF can not find a prime, but can find a factor, proving it is not prime.) If you chose 87471793 to test all the way to the end (the LL test), Prime95 will first run some TF and a P-1 test as needed. These are a wise investment as they can more rapidly remove a number of exponents that have factors.

If you just want to run LL tests on number that PrimeNet will assign, open the program. Then from the menu select Test > Worker Windows. In options for "Type of work to get", select "First time tests".

Thanks!

If i choose "world record numbers to test" or "100.000.000 digit numbers test", how long time will my computer use for this _if_ the number is a prime?

If i choose "first time tests", will my computer test numbers that are smaller than the current world record?

Are these three options the only one that do "full tests" on "new" numbers?

Funny/interesting, this...

Now, I chose "world record tests" in the "worker windows"-menu-option in Prime95. But as a trial factor test finished, i didnt get a new assignment... i know the scheduled assignment have to finish, but the communication thread did not show that i got a new... is this a bug? im using the latest software on windows7.

I also tried setting the work to "world record testing" at www, under account type, but then, as three trial factor tests ended, i only got more trial factoring assignment from the server (in the communication thread)...

Hi.

I'm sorry for the trouble, because now it works. I got LL-assignment. I think it will begin as soon as the previous scheduled TF-assignments are done! :-)

Thanks.

PS: For the future, if I must uninstall Prime95 and restart, is it best to set the work type in www? It seems that it will get TF-assignments automatically at start-up...

[QUOTE=Unregistered;343906]If i choose "world record numbers to test" or "100.000.000 digit numbers test", how long time will my computer use for this _if_ the number is a prime?

If i choose "first time tests", will my computer test numbers that are smaller than the current world record?

Are these three options the only one that do "full tests" on "new" numbers?[/QUOTE]
Doing a LL test takes the same amount of time if a number is prime or not (it has to go all the way to the end to find out the results).
How long it take depends on your computer a lot. Most likely it will take about a year.

Right now there are about 32,000 numbers that will be handed out as "first time tests" that are smaller than the record (that was found this year).

Yes these are the options for "new" numbers.
[QUOTE=Unregistered;343909]Now, I chose "world record tests" in the "worker windows"-menu-option in Prime95. But as a trial factor test finished, i didnt get a new assignment... i know the scheduled assignment have to finish, but the communication thread did not show that i got a new... is this a bug? im using the latest software on windows7.

I also tried setting the work to "world record testing" at www, under account type, but then, as three trial factor tests ended, i only got more trial factoring assignment from the server (in the communication thread)...[/QUOTE]The settings on the machine are primary, if I recall correctly.
What type of processor, speed, and memory do you have?

[QUOTE=Unregistered;343919]PS: For the future, if I must uninstall Prime95 and restart, is it best to set the work type in www? It seems that it will get TF-assignments automatically at start-up...[/QUOTE]Set it on the machine. If PrimeNet is giving you TF when you have "What ever makes sense" set on the machine, that means you have an older or slower machine. It may take more than a year and a half for a 100,000,000 digit number and more than 6 weeks for a record number.

Welcome!
 

Welcome to GIMPS! I hope you stick around. A huge number of people never finish their first assignment when they see how long it takes.

Setting up your automatic assignments online is probably a good idea though doing it through the program is fine too. Prime95.exe will regenerate any missing .txt files that it needs so you can erase everything except the .exe and it will start over from scratch and you can change your settings. You can also do that through the menus in the program itself. See Test > Worker Windows.


The Primenet server tries to balance out its workload according to what needs to be done. Trial Factoring spends a small amount of time on each exponent testing small prime factors to see if the exponent can be cleared early. P-1 factoring is a different kind of factoring done once trial factoring is finished. After P-1, the actual, direct as you called it, Lucas Lehmer test begins. P-1 is barely keeping up with the LL tests so some times the server will assign P-1 to anyone taking "Whatever makes sense". "Whatever Makes Sense" is the best way to help make sure the server workload is balanced.

The amount of time your computer will take to test the numbers is highly dependent on your hardware. What is your CPU?

First time tests are done on any exponent which is ready for LL tests but has not had one done yet. Double check tests are another LL test done on an exponent which came up composite once. This is to check that the calculations were done without errors.

World record tests are like first time tests but you are specifically asking for numbers which are LARGER than the current world record. GIMPS isn't just trying to find the biggest ones. It's trying to test them [I]all[/I].

100,000,000 digit tests are special because there is a huge prize for finding a prime number with one hundred million digits. It's $150,000 of which $50,000 will go to you if you find it through GIMPS. These tests take a LONG, LONG time to run. It might take you over a year.

[QUOTE=Uncwilly;343958]
Doing a LL test takes the same amount of time if a number is prime or not (it has to go all the way to the end to find out the results).
How long it take depends on your computer a lot. Most likely it will take about a year.
[/QUOTE]

Ah, I see. But I don't understand it. If a number is a composite, then you find that out be finding the smallest divisor. If it's a prime, you have to test all the possible divisors? Or is the LL-algorithm different from this?

[QUOTE=Uncwilly;343958]
What type of processor, speed, and memory do you have?
[/QUOTE]

i5-2500 @ 3.3 GHz. My computer have 16 GB RAM, but I assigned only 1. Perhaps it will run faster if i increase? I don't use the machine for awything else, actually.

[QUOTE=Uncwilly;343958]
Set it on the machine. If PrimeNet is giving you TF when you have "What ever makes sense" set on the machine, that means you have an older or slower machine. It may take more than a year and a half for a 100,000,000 digit number and more than 6 weeks for a record number.
[/QUOTE]

Thats weird, I didnt think my machine was old or slow in this context. Yeah, about 3 weeks according to the schedule to complete LL on a world record number. But the TF did go much faster than what the schedule said.

[QUOTE=TheMawn;343959]
Welcome to GIMPS! I hope you stick around. A huge number of people never finish their first assignment when they see how long it takes.
[/QUOTE]

Thanks!

The Prime95 says that the chance of finding a world record prime, running 4 threads, were about 1:115,000. And also that it will take about 3 weeks to complete this.

It seems unvalid to me, but if it actually is true, then the chances are better than in the "lottery" that we have here, which are about 1:5,000,000. Hehe.

[QUOTE=TheMawn;343959]
The amount of time your computer will take to test the numbers is highly dependent on your hardware. What is your CPU?
[/QUOTE]

i5-2500 @ 3,30 GHz.

[QUOTE=Unregistered;343967]Ah, I see. But I don't understand it. If a number is a composite, then you find that out be finding the smallest divisor. If it's a prime, you have to test all the possible divisors? Or is the LL-algorithm different from this?[/QUOTE]

That method you describe is far too inefficient. LL test is a more efficient method. Comparing the "school method" you describe, with LL test, is even worse then comparing a snail with a supersonic airplane. We are talking about the same speed proportion, except that in the case of LL versus "school method", you have to add few thousand zeroes at the end of the speed number, in the favor of LL tests... :razz:

More details [URL="http://www.mersenne.org/various/math.php"]here[/URL].

LL tests will [B]*not*[/B] run faster if you assign more memory to them. 1GB is plenty enough. The only work type which is affected by the memory amount is the "stage 2 of P-1/ECM", which you don't normally do if you do "first tests" or "world records", etc. Even for that, not the speed is affected, but the chance to find a factor (i.e. more memory increases the chance).

Hi, I am "Unregistered" (now registered).

[QUOTE=LaurV;343997]That method you describe is far too inefficient. LL test is a more efficient method. Comparing the "school method" you describe, with LL test, is even worse then comparing a snail with a supersonic airplane. We are talking about the same speed proportion, except that in the case of LL versus "school method", you have to add few thousand zeroes at the end of the speed number, in the favor of LL tests... :razz:

More details [URL="http://www.mersenne.org/various/math.php"]here[/URL].
[/QUOTE]

Hehe, ok. I knew that it was fast, I just forgot that there are several ways to attack finding primes. :razz:

[QUOTE=LaurV;343997]
LL tests will [B]*not*[/B] run faster if you assign more memory to them. 1GB is plenty enough. The only work type which is affected by the memory amount is the "stage 2 of P-1/ECM", which you don't normally do if you do "first tests" or "world records", etc. Even for that, not the speed is affected, but the chance to find a factor (i.e. more memory increases the chance).[/QUOTE]

Ok, then I leave it at 1 GB. :)

Thanks.

[QUOTE=LaurV;343997]That method you describe is far too inefficient. LL test is a more efficient method. Comparing the "school method" you describe, with LL test, is even worse then comparing a snail with a supersonic airplane. We are talking about the same speed proportion, except that in the case of LL versus "school method", you have to add few thousand zeroes at the end of the speed number, in the favor of LL tests... :razz:[/QUOTE]

Several million more like.

Note to the original author: We are not saying that an LL test is several million times faster than trial division as a method of primality testing. That would be adding just 6-7 zeros at the end of the speed number.

If it was several billion times faster, that would be adding 9-10 zeros. Several trillion times faster would add 12-13 zeros.

Instead of using a single computer, we could distribute the task across many. Suppose every atom in the universe is a computer. Some estimates put that number at about 10[sup]80[/sup] That would add about 80 zeros to the speed factor.

The LL test is much faster than that. Words cannot express how much faster adding several million zeros to the speed number is. The human mind cannot picture it.

Now turn that around. If an LL test takes three weeks, think how long it would take to prove our numbers prime using TF alone.

[QUOTE=LaurV;343997]The only work type which is affected by the memory amount is the "stage 2 of P-1/ECM", which you don't normally do if you do "first tests" or "world records", etc.[/quote]

Acually there is quite a high chance that a newly assigned first time test will need P-1 pretesting.

[quote]Even for that, not the speed is affected, but the chance to find a factor (i.e. more memory increases the chance).[/QUOTE]

I don't think that's correct, even in practice.

What actually happens is, unless the client has sufficient memory to make using the Brent-Suyama extension worthwhile (multi-gigabytes on numbers in the current test range), more memory increases the speed at which the client is able to complete stage 2 to particular limits. However, the client takes this into account when computing those limits, preferring to increase the limits (thereby increasing the chance of finding a factor) in exchange for spending more time, when the memory allocation is generous.

I could so happen, I suppose, that the effect of this is to exactly cancel out the time saving, but I don't think it does, and I can think of no reason why it should.

[QUOTE=Unregistered;343967]Ah, I see. But I don't understand it. If a number is a composite, then you find that out be finding the smallest divisor.[/QUOTE]

Actually it is the other way around. If we find a factor (it doesn't matter whether or not it is the smallest), then the number is composite.

If we don't find a factor, then we need to use another method to determine whether the number is prime or composite. That method is the LL test.

[QUOTE]If it's a prime, you have to test all the possible divisors? Or is the LL-algorithm different from this?[/QUOTE]

Totally different.

The LL algorithm itself is quite simple:

1. Start with the number 4.
2. Square it and subtract 2.
3. Repeat step 2 p-2 times, where p is the exponent you are testing.
4. If the result is divisible by Mp then Mp is prime. If not then Mp is composite.

What makes this feasible (i.e., millions of zeros faster than TF) is that it requires only about p operations, while TF would require about 2[sup]p[/sup] operations.

The algorithm is simple enough that any high-school programmer could implement it. (In fact, [url=http://en.wikipedia.org/wiki/Landon_Curt_Noll]one did[/url]). Implementing it [url=http://mersenne.org/freesoft/default.php]efficiently[/url] is another matter, as is understanding why the algorithm works in the first place. A good explanation can be found [url=http://primes.utm.edu/prove/prove3_2.html]here[/url], though you will need a certain level of mathematical sophistication to be able to understand it.

[quote]Thats weird, I didnt think my machine was old or slow in this context. Yeah, about 3 weeks according to the schedule to complete LL on a world record number. But the TF did go much faster than what the schedule said.[/quote]

That's because TF has only a small chance of finding a factor Obviously it would be a waste of time to spend weeks and weeks trying to find a factor which [i]might[/i] be successful, when an LL test will definitely decide the matter. Factoring is like playing roulette. We "bet" a small amount of compute time that we will find a factor. If we win, we save two lengthy LL tests. Most of the time we lose, but we only lose the compute time we steaked.

Of course we only do this as long as the odds are in our favour. Over millions of tests, the project comes out ahead. Roulette isn't really a gample for the casino, is it?

[quote]The Prime95 says that the chance of finding a world record prime, running 4 threads, were about 1:115,000. And also that it will take about 3 weeks to complete this.

It seems unvalid to me, but if it actually is true, then the chances are better than in the "lottery" that we have here, which are about 1:5,000,000. Hehe.[/quote]

That calculation is based upon an [url=http://primes.utm.edu/mersenne/heuristic.html]unproven conjecture[/url] about the distribution of primes among the Mersenne numbers.

If you were to give a person just enough information about what a prime number is, and asked them to tell you how they would determine the primality of a number, they would probably give you the most naive way that exists. Dividing a number k by every number up to k and seeing if one of them returns a whole number.

Next, one might realize that you don't need to divide a number by, for example, 4. If a division by 4 gives a whole number, then so does a division by 2. A much better way is to divide by every prime number up to k. Next, a person might notice that if, for example, you were to divide the number 173 by 17, you would get a smaller than 17 because 17 x 17 is 289. You don't even need to try 17 because if it DID give you a whole number, it would be smaller than 17 and you already tried all the ones smaller than 17! You can then eliminate all the prime numbers equal to or larger than the square root of k.

We've gone from trying all numbers up to k to trying all the prime numbers up to the square root of k. This is essentially what trial factoring is. It's a very brute force kind of method.

My video card, a GTX 670, can factor 2[SUP]60892163[/SUP]-1 to 2[SUP]74[/SUP] in about 5 hours. That is checking every single prime number up to roughly 18 sextillion. It takes about twice as much time to check every factor between 2[SUP]x[/SUP] and 2[SUP]x+1[/SUP] as it does 2[SUP]x-1[/SUP] and 2[SUP]x[/SUP]. So, going up to 2[SUP]75[/SUP] would take another 5 hours. 2[SUP]76[/SUP] would take 10 hours.

Assuming the trend continues, the time it takes to trial factor is O(2[SUP]n[/SUP]). To check 2[SUP]60892163[/SUP], you would need to go up to 2[SUP]30446082[/SUP] which is 2[SUP]30446008[/SUP] times longer than 10 hours.

It would take my video card around 2[SUP]30446011[/SUP] hours to do that. The universe is about 2[SUP]47[/SUP] hours old.

[B]It would take my video card around 2[SUP]30446011[/SUP] hours to [try every prime factor for M60892163]. The universe is about 2[SUP]47[/SUP] hours old.[/B]

I want to say this in it's own post since people might not read the whole thing I posted just previous to this.

[QUOTE=Mr. P-1;344005]Acually there is quite a high chance that a newly assigned first time test will need P-1 pretesting.[/QUOTE]

I disagree on this point.

While a few hundred first time LL tests were assigned without P-1 pre-done after the last Mersenne Prime was announced, we're back to the point where all LL tests are assigned with P-1 already done.

[QUOTE=Mr. P-1;344005]I could so happen, I suppose, that the effect of this is to exactly cancel out the time saving, but I don't think it does, and I can think of [B]no reason[/B] why it should.[/QUOTE]

I (also) disagree on this (different) point. I however, may be wrong. OTOH, the explanation you give in your last paragraph is quite right (about how the things happen). We only disagree on duration and the[B] reason[/B] is explained below.

If you read the link I provided above, about how GIMPS intelligently chooses the B1 and B2 limit, you will see that the story is "time related". If you spend the time T to do LL test, then maybe you can save two times T if you find a factor. So, how long time (x% of T) should you spend doing TF and P-1? It depends of the chance to find a factor.

If you have a method with a [B]higher chance[/B] to find a factor, it makes sense to chase that method [B]longer[/B] (in time). So, logically, it is viceversa than one should expect. But you can't chase that chance too long, as your odds improve only logarithmically, reported to the time you spend doing it (P-1, in our case). So, in case a factor is not found, you lost precious time, which would have been better invested in doing LL from the start. Therefore there is a "cutoff" somewhere, and that cutoff (B1 and B2) have to be intelligently chosen, to maximize the chance of finding a factor in a limited time (x% of T), but the time is still the limit. So, at the end, the time variation is tiny. Adding more memory to the stage 2, you will work about the same time on that P-1 assignment, but you might get luckier.