User TJAOI - Page 40

bloodIce · 2017-09-25, 09:57

Once upon a time, I had tried an idea to systematically walk through primes and find factors for Mersenne expos, but I was lagging on speed. It was simply:
1. For each prime number (N) starting from any range (one can start from TF432 or TF65 if one wishes), sieve and keep the primes that are mod8=(+/-1).
2. Then, one either factors (N-1)/2 until all 10^9 factors are found or just tries the list of all prime Mersenne expos if any is a factor of (N-1)/2. Lets say n1, n2, n3 are such prime expos.
3. One simply checks if 2^n1-1 is divided by N, as well 2^n2-1, 2^n3-1 to eliminate a candidate.
4. Go to next prime :-).

I was lacking computational efficiency (under python is slow :-)), but I am sure there could be a GPU code to help. I guess it looks as "search through k" as LaurV is mentioning. If one keeps the list of all primes <10^9 in memory of a GPU, the sieving code could be very efficient. Then it is couple of Mersenne TFs or none per candidate prime N.

henryzz · 2017-09-25, 10:03

Quote:

Originally Posted by Dubslow

Unlike RDS, he stuck to math and facts.

I agree he did limit it to moaning rather than straying to insults. TBH it was a harsh comparison.

LaurV · 2017-09-25, 12:37

Quote:

Originally Posted by henryzz

You sound like RDS

Told you I learned a lot of things from this forum

Anyhow, me and ma'man are good now, he actually took it very well, and if he learned something new, I do not mind what he thinks about me. Case closed.

LaurV · 2017-09-25, 13:21

Quote:

Originally Posted by bloodIce

If one keeps the list of all primes <10^9 in memory of a GPU, the sieving code could be very efficient.

That was exactly what my Pari snippet was doing, except sieving. I would not ask if you ran it, because then I would be accused again of being RDS-ish

If some sieving is added, then it becomes like your algorithm.

Note that to sieve, you do not need to keep any prime in memory. First of all, you can generate them as faster as access them in an indexed manner in memory (see the comments about the Erathostenes' sieve here). Second, it makes no sense to sieve higher than a a hundred thousand primes or so. Why should you waste memory to store 50 million primes? Sieving with first 40k primes (as Prime95 is doing) can find all primes to 38 bits, i.e. about 23*10^10, and it will eliminate almost all your candidates, therefore it will br faster, in that point, to make exponentiation than to continue sieving.

Even mfaktX, has sieving limit to primes below 100k, see the parameter SievePrimesMax in the mfaktc.ini, for example. And when you make tuning, it establishes itself somewhere at 80-90k (about 9000 primes). Why? because sieving higher, your candidate list becomes smaller and smaller, and after a while it will be faster to eliminate candidates doing exponentiation, than continuing to sieve.

Therefore, about 10 kilo words is all you need to store the primes used for sieving, in a vector in global RAM, and read them sequential. But you still need to split the candidates in classes, to make the storage more convenient and sieving more "uniform". If you try to program it, you will see what I mean (I "smoked" these things from all joints... hehe, still thinking about them when I have time to spare).

bloodIce · 2017-09-25, 15:25

Quote:

Originally Posted by LaurV

That was exactly what my Pari snippet was doing, except sieving. I would not ask if you ran it, because then I would be accused again of being RDS-ish

Of course I have run your Pari-scripts

. Since your original discussion with James (about "k", what will that be 5-6 years ago), and I have learned a lot from your scripts (and in general from your opinions in this forum).

Quote:

If some sieving is added, then it becomes like your algorithm.

Yeah, I know it is no-brainer, but it helps of course.

Quote:

Note that to sieve, you do not need to keep any prime in memory. First of all, you can generate them as faster as access them in an indexed manner in memory (see the comments about the Erathostenes' sieve here). Second, it makes no sense to sieve higher than a a hundred thousand primes or so. Why should you waste memory to store 50 million primes? Sieving with first 40k primes (as Prime95 is doing) can find all primes to 38 bits, i.e. about 23*10^10, and it will eliminate almost all your candidates, therefore it will br faster, in that point, to make exponentiation than to continue sieving.

With all my respect I disagree. I cannot get how accessing a pointer (to a prime) from memory can be slower than generating primes each time I need to do a mod or simple division, which will be for each prime candidate N. I just generate them once (yes, it is Erathostene's sieve) and store them. Of course I agree, this is tremendous load of memory (the trade-off).

Even better of course would be a partial factorization of a candidate (N-1)/2 to a limit 10⁹. However, higher the N, slower the factorization, expectedly. After TF60 or even earlier, I think it was faster to do all mod-divisions with the full list of primes for a candidate N, than to partially-factor it (on average). For Ns starting at >TF100 the full list of ((N-1)/2 mod Mersenne_expo ==0) would win on speed.

Quote:

Even mfaktX, has sieving limit to primes below 100k, see the parameter SievePrimesMax in the mfaktc.ini, for example. And when you make tuning, it establishes itself somewhere at 80-90k (about 9000 primes). Why? because sieving higher, your candidate list becomes smaller and smaller, and after a while it will be faster to eliminate candidates doing exponentiation, than continuing to sieve.

I meant, actually building a list of candidate expos for having that factor N. I do not eliminate in the mod/division part, but build candidate expos in that step. Every hit for me: ((N-1)/2 mod Mersenne_expo ==0) is a potential candidate to have that factor N or I am missing the bigger picture here?

Sieving is only to have mod8=(+/-1), as you pointed to me long time ago. Yes, my siever is elementary, and could be improved I am sure.

Quote:

Therefore, about 10 kilo words is all you need to store the primes used for sieving, in a vector in global RAM, and read them sequential. But you still need to split the candidates in classes, to make the storage more convenient and sieving more "uniform". If you try to program it, you will see what I mean (I "smoked" these things from all joints... hehe, still thinking about them when I have time to spare).

I agree with the "uniform load". That was my problem for my multicore version. Some cores would finish quickly then others, because of an uneven number of trial divisions in a thread. I cannot know how many divisions I need to perform to exclude a candidate N, before partially-factoring it or mod it towards a list. However, I agree I can classify the output in classes to distribute the load more evenly.

P.S. A list/array of all prime Mersenne expos <10⁹ in memory should not be more than 250 Mb if I calculate correctly (~50 000 000 x 4bytes), so it is not a huge deal in my opinion. The problem for me is that every TF I needed to perform was slow. I know that Prime95 and mfaktc are orders of magnitude quicker and I think that is what was missing.

science_man_88 · 2017-09-25, 21:22

Quote:

Originally Posted by bloodIce

Of course I have run your Pari-scripts

. Since your original discussion with James (about "k", what will that be 5-6 years ago), and I have learned a lot from your scripts (and in general from your opinions in this forum).

Yeah, I know it is no-brainer, but it helps of course.

With all my respect I disagree. I cannot get how accessing a pointer (to a prime) from memory can be slower than generating primes each time I need to do a mod or simple division, which will be for each prime candidate N. I just generate them once (yes, it is Erathostene's sieve) and store them. Of course I agree, this is tremendous load of memory (the trade-off).

Even better of course would be a partial factorization of a candidate (N-1)/2 to a limit 10⁹. However, higher the N, slower the factorization, expectedly. After TF60 or even earlier, I think it was faster to do all mod-divisions with the full list of primes for a candidate N, than to partially-factor it (on average). For Ns starting at >TF100 the full list of ((N-1)/2 mod Mersenne_expo ==0) would win on speed.

I meant, actually building a list of candidate expos for having that factor N. I do not eliminate in the mod/division part, but build candidate expos in that step. Every hit for me: ((N-1)/2 mod Mersenne_expo ==0) is a potential candidate to have that factor N or I am missing the bigger picture here?

Sieving is only to have mod8=(+/-1), as you pointed to me long time ago. Yes, my siever is elementary, and could be improved I am sure.

I agree with the "uniform load". That was my problem for my multicore version. Some cores would finish quickly then others, because of an uneven number of trial divisions in a thread. I cannot know how many divisions I need to perform to exclude a candidate N, before partially-factoring it or mod it towards a list. However, I agree I can classify the output in classes to distribute the load more evenly.

P.S. A list/array of all prime Mersenne expos <10⁹ in memory should not be more than 250 Mb if I calculate correctly (~50 000 000 x 4bytes), so it is not a huge deal in my opinion. The problem for me is that every TF I needed to perform was slow. I know that Prime95 and mfaktc are orders of magnitude quicker and I think that is what was missing.

the thread you are talking about starting 5 years ago last month ( I have it bookmarked) you can know k mod 3 and use p mod 3 to show a whole set are divisible by 3 or not. so it only takes r candidates or less per prime r to show if it divides any in the arithmetic progression of candidates. etc. you can use a lot of short cuts like that.

Madpoo · 2017-10-02, 22:38

Quote:

Originally Posted by ATH

TJAOI actually found 827 first factors that I can find (see full lists below).

FYI there are currently 834 factors where TJAOI found the first one (as of right now). The smaller exponents are ECM of course (213 of them, up to M2440943), the rest are TF. Looks like all of the ECM stuff is using B1=50K, B2=5M.

Code:

LaurV · 2017-10-03, 05:24

Yet (in the light of our former posts), to make it clear, none of the TF factors were found "by k" (i.e. missed by GIMPS, and found later by TJAOI's exhaustive search).

Or...?

(edit: i.e. you count the first factors "wrongly" in this case, hehe, the question was never about how many factors they find, but about how many factors which we missed, they find. All factors we find with mfaktX and P95's TF are first factors. We all have our own collections of "first" factors found. But the question was if and how he helps GIMPS, i.e. finding factors that actually save us LL work, by their own ("by k", or whatever) method. Again, the guy/girl/group is worth our admiration that they are following their goal, and this remark is under no way intended to diminish their merits, but we think that their resources would be much better used doing "normal" TF, from the GIMPS point of view. We do not talk about the resources they use for ECM or other types of work, and we know they are quite a "complex" contributor, we only try to compare the factoring method they are using, with the one GIMPS is using).

flagrantflowers · 2017-10-03, 23:47

Quote:

Originally Posted by LaurV

but we think that their resources would be much better used doing "normal" TF, from the GIMPS point of view.

As always everyone is encouraged to do the work that they find interesting…

I personally find this extraordinarily interesting even if, in some peoples' opinions, it is not an ideal use of resources.

alpertron · 2017-10-08, 00:56

Quote:

Originally Posted by LaurV

...you count the first factors "wrongly" in this case, hehe, the question was never about how many factors they find, but about how many factors which we missed, they find. All factors we find with mfaktX and P95's TF are first factors...

From Primenet data for M6811111 it is clear that the only prime factor known of that Mersenne number was found by TJAOI.

LaurV · 2017-10-13, 10:23

Quote:

Originally Posted by alpertron

From Primenet data for M6811111 it is clear that the only prime factor known of that Mersenne number was found by TJAOI.

OK, that's one... It didn't save GIMPS any time, however, because the 6M DC were long passed when the factor was found, but that is a clear GIMPS miss which they (TJAOI) found, and it is ok with us, based on the rule that "is nicer to expose a factor, than to expose a verified LL residue".

2017-10-03, 05:24	#437
LaurV Romulan Interpreter Jun 2011 Thailand 7×1,373 Posts	Yet (in the light of our former posts), to make it clear, none of the TF factors were found "by k" (i.e. missed by GIMPS, and found later by TJAOI's exhaustive search). Or...? (edit: i.e. you count the first factors "wrongly" in this case, hehe, the question was never about how many factors they find, but about how many factors which we missed, they find. All factors we find with mfaktX and P95's TF are first factors. We all have our own collections of "first" factors found. But the question was if and how he helps GIMPS, i.e. finding factors that actually save us LL work, by their own ("by k", or whatever) method. Again, the guy/girl/group is worth our admiration that they are following their goal, and this remark is under no way intended to diminish their merits, but we think that their resources would be much better used doing "normal" TF, from the GIMPS point of view. We do not talk about the resources they use for ECM or other types of work, and we know they are quite a "complex" contributor, we only try to compare the factoring method they are using, with the one GIMPS is using). Last fiddled with by LaurV on 2017-10-03 at 05:35

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Old User	Unregistered	Information & Answers	1	2012-10-18 23:31
The user CP has gone :(	retina	Forum Feedback	5	2006-12-05 16:47
Changing My User ID	endless mike	NFSNET Discussion	1	2004-10-31 19:38
OSX yet? new user here	KevinLee	Hardware	6	2003-12-12 17:06
help for a Mac user	drakkar67	Software	3	2003-02-11 10:55

2017-09-25, 09:57	#430
bloodIce Feb 2010 Sweden 173 Posts	Once upon a time, I had tried an idea to systematically walk through primes and find factors for Mersenne expos, but I was lagging on speed. It was simply: 1. For each prime number (N) starting from any range (one can start from TF432 or TF65 if one wishes), sieve and keep the primes that are mod8=(+/-1). 2. Then, one either factors (N-1)/2 until all 10^9 factors are found or just tries the list of all prime Mersenne expos if any is a factor of (N-1)/2. Lets say n1, n2, n3 are such prime expos. 3. One simply checks if 2^n1-1 is divided by N, as well 2^n2-1, 2^n3-1 to eliminate a candidate. 4. Go to next prime :-). I was lacking computational efficiency (under python is slow :-)), but I am sure there could be a GPU code to help. I guess it looks as "search through k" as LaurV is mentioning. If one keeps the list of all primes <10^9 in memory of a GPU, the sieving code could be very efficient. Then it is couple of Mersenne TFs or none per candidate prime N.