Sieving together with Rieselsieve

[hhh]

I had just the idea of the century.
Why are we not sieving together with rieselsieve? We are searching for the same kind of numbers to have factors, and if we put together our dat files, we gain almost one time more speed.
As we just restarted over for secondpass sieving, I think it would be possible to coordinate things and put our forces together.
I had the idea and needed to post it immediately, even though I know not very much about riesel; if it's bullshit, I present you my sincere apologies. I will read a little bit the internet and post again, more concretely.
All excited yours Hadrian


EDIT Ok as I see it, Riesel has lot more k's, and thus much more work. Their sieving is slower. To add some of our number would probably not make a big speed slowdown for them, but sieving their stuff would considerably slow down.
We are with the secondpass sieving right now at 100T, or about that, just where they are with firstpass sieve. (Right?)
As we have time until our firstpass PRP reaches 20M to catch up the firstpass sieve with the secondpass sieve dat, I think we could bare a slowdown here.
I like both projects which are quite similar: both have a possible end, search for the same kind of primes. I'm not a project chauvinist.
Psychologically, Riesel people are probably more likely to accept such a sharing, as it doesn't change a much for them and they have not sieved so far. If a seventeenorbust guy doesn't want to share, he could still do firstpass sieving.

The way it is, it's waste of resources, as far as I can see it. Let's put together what is the same, and stop this waste.

The only problem I can see is if the newly needed tool is going to be called soselator or riebistrator.
:confused: :D
Yours H.

Please consider my categoric post on the main forum, too.

[vjs]

hhh,

The major problem is that riesel doesn't sieve the same sort of numbers that we do. They sieve k*2^n-1 were we do k*2^n+1 ... unfortunately the sieving is totally different. I.E. mods don't work the same etc.

Basically this means that the sharing of k's don't provide any speed-up benifit even if they were able to work together. Second from what I've read in their forums B2 is suggesting not to sieve any deeper, they want more people to prp test to remove the # of k that they have??? Can't say that I agree but there was some problem sieving deeper I believe...

THe only project we could partner with would be psp. Mystwalker is working with them very closely he pops in from time to time, They have sieve up to 100T as well.

I'd also liek to add that we have 25T less than 100T not yet reserved we also have several of the 75T less than 100T currently in progress. The major goal of the high-n low-p sieve is to finish up all of these ranges less than 100T.

[jasong]

Originally posted by vjs
hhh,

The major problem is that riesel doesn't sieve the same sort of numbers that we do. They sieve k*2^n-1 were we do k*2^n+1 ... unfortunately the sieving is totally different. I.E. mods don't work the same etc.

Basically this means that the sharing of k's don't provide any speed-up benifit even if they were able to work together. Second from what I've read in their forums B2 is suggesting not to sieve any deeper, they want more people to prp test to remove the # of k that they have??? Can't say that I agree but there was some problem sieving deeper I believe...
Not that I even pretend to understand the math, but the man who is supposedly working on the "supersiever" and quit for whatever reason says that it IS possible to combine sieves and get an overall advantage. The "evidence" involving postings on the Riesel Sieve forum convince me that a neglected version of the supersiever exists in alpha stage somewhere and is not some hoax, although I think it exists separately as a +1 version and a -1 version. The problem is convincing the dude to get back on track. After all, he is just a volunteer.

[vjs]

Chuck is the super siever guy. I've e-mailed him in the past but have not seen a working version.

[Mystwalker]

Originally posted by vjs
THe only project we could partner with would be psp. Mystwalker is working with them very closely he pops in from time to time, They have sieve up to 100T as well.

I'm certain ltd and Citrix would love to have the sievings combined. Earlier merge considerations mainly failed due to the completely different sieving depths (~600T vs. ~50T). As those 14 k's that are left for PSP won't be all excluded before n=20M, a bigger n range for sieving could be useful as well.

Combining both sieves should be a no-brainer. Just add the k's and you're all set up (after having sieved out the few first G's from PSP k's 20M < n < 50M).

It would be interesting to know the performance impact - and the motivation of SoB sievers to to this combined search. I'm pretty sure PSP sievers don't mind sieving PSP&SoB with n < 50M in exchange. :)
From a point of view of both projects combined, that merge should be quite efficient.

[vjs]

Agreed Mystwalker,

I tried doing this with the 20M dats when PSP had 15 and sob had 11, it was quite a bit slower but not that bad.

Is there any chance of getting PSP to sieve 20M<n<50M out to about 2^45 (35T ???) those first few T are very very slow and have alot of factors. I think skipping the 35T-100T range for PSP numbers wouldn't be that bad. At least having the mutual dat is an idea.

How much effort is being put into that project currently???

[hhh]

Looks like I knew the way to meet, but showed up at the wrong's persons place... Oops...
If there is a ?-50M dat for psp, I can take some bunches and help to catch up our second pass sieve.
It's always good to look further around.
I just checked out at the mersenneforum, PSP has sieved to about 100 000G soon, so perhaps, if we all agree (vote?), we should stop the SP sieve there, help PSP catch up, and then go for it together.
Shall I post over there, too? And dear admins, could you change the name of this thread, (PSP instead of Riesel), please (perhaps together with a not in my first post? Thank you.
Yours H.

[vjs]

HHH,

I think the current consences is to finish secondpass sieve to 100T and stop there (with the expection of rechecking suspect ranges above 100T). At the same time or during finish all of first pass sieving upto the limit of proth with the 991-50M dat.

It's sort of up to the PSP people if they would like to sieve with a 991(or less) to 50M dat. I'm not sure if they do? Their first pass testing is less than 2M...

I posted a while back about the maximum efficiency of proth with the 53M dat size. The response was a little cold.

You could try again, I know mystwalker did alot of work with psp in the past...

[vjs]

It would be interesting to know the performance impact - and the motivation of SoB sievers to to this combined search.

For answers to most of these questions check out my postings in the high-n sieve effort main thread.

Summary...

Time vs dat size ... most efficient ~53M with a flat spot between about 45-55M this is dat size, didn't seem to matter with the number of k used.

Increasing the number of k decreases the client speed. However, I did a recent test. On my machine I get about 600 kp/s with the 9k and the 991<n<50M dat. If you remove all but 2k's the speed only increased to about 1000 kp/s.

I would think that adding psp's 14k's (forgot about the prime) to our 9k's would reduce the speed to about 50-65% <--- (gut feeling of our current speed).


and the motivation of SoB sievers to to this combined search.

Personally I'd like to see psp sieve out the first 25T of 20M<n<50M before the efforts are combined. I spent a tremendous amount of time sieving the first 3T. Basically the client speed was 20 kp/s for the first few 100G increasing to about 300 kp/s by 1T. (Yes this is the same machine that now gets 600kp/s with the 991<n<50M dat).

[ltd]

Personally i would like to see a combination of the different sieve efforts but
i don't know what i must do to persuade all SOB sievers to join in as it will bring much more advantage to PSP as it wouold bring to SOB. You have a lot more sieving power here then we have at PSP. There is one more reason why it is a now or never situation for PSP. As we have sieved deeper then directly needed for the size of PRP tests we do at the moment we could spare all sieve resources to catch up with the 50Mil sieve file.

Lars

[hhh]

I have some hope that it would be possible to convince Sob's people to do the joint effort because
- our projects have almost the same aim.
- people who sieve are likely to be doing that because of efficiency, and not for score, somehow, because they want to be as useful as possible (being even more efficient should be more like an other thrill(?).
- I started my distributed computing with SoB, but I'm not restraint to this; if there is something else I think useful, I can switch; we are all members of a community, I think, and not defending 'our' project. I know that many people are working for different projects in the same time, too.
- Until now, there was no negative reaction (We don't have to search it, neither).

We can just make a poll, and then see what it yields.

BTW, the corresponding thread in the PSP forum is here:

http://www.mersenneforum.org/showthread.php?t=4310

Regards, H.

[ceselb]

Originally posted by vjs
Chuck is the super siever guy. I've e-mailed him in the past but have not seen a working version.

I'm helping out a bit with the 'super siever', there is no working code as of yet but work is in progress.
There are a number of things to be done, but you will know once (if) it gets finished.

[hhh]

Sieving with PSP seem well on the way.

citrix said it would be in fact possible to write a siever for 2^n+1 and 2^n-1 in the same time; it is not sure, though, when it will be ready.

So, the question is: if there is the possibility, do we want to take Riesel into account, too? If yes, we should perhaps post over there, too, so they can start catching up.
What do you think?

Curious, H.

[vjs]

HHH,

I would personally wait Riesel has alot of k's currently. Riesel has also posted "people should be testing not sieving".

There are alot of things that "could" happen and "are" possible. But until they happen I wouldn't start anything.

Besides if a new super-siever client ever comes out who knows how it will function. It might respond differently to dat sizes or number of k's...

Example for proth sieve there are three important variables for k,n, p and +/-1. The + or - is one of the primary steps so you currently can't do both. Proth then "sieves" each p against, k and looks for a matching n. So adding k's actually increases the efficiency of the client (speed is still reduced but) and n-range has some optimal size.

Anyways the point is if there were a new client that could do both + and - at the same time who knows how it will work. Also the most efficient use of that client may be to sieve only one k at a time or perhaps n-range has no effect?

Point being lets leave riesel out at the moment their numbers are different and can't be combined using proth.

[Mystwalker]

Well, Lee now revises (http://www.rieselsieve.com/forum/viewtopic.php?t=460) his earlier decision (and suggestion) to stop sieving and started it again.

[vjs]

That's a good decision IMHO, however if I were him I'd look at breaking the dat up into two pieces instead of stopping sieve next time.

Often times k's share mods so with over 70k you would think that 2 dats could be created without much loss in efficiency. But then again there is all the administrative overhead I guess.

[Citrix]

The new PSP dat's sieving has begun:-

Join in !!!

http://www.mersenneforum.org/showthread.php?t=4341

Citrix


PS: If anyone wants my help combining the +1 and -1 sieving clients let me know.

[vjs]

Citrix,

I really believe it is too soon for you guys to make this a public effort.

[smh]

The new PSP dat's sieving has begun:-

Whats the point of significantly slowing down SOB sieving? SOB is still undersieved and IMO is better of by switching to the normal 50M SOB dat file and get ranges that aren't sieved to 50M done.

SOB is about solving a conjecture, PSP is just one of the many projects to find large primes. Who is interested in the lowest prime sierpinskie number? It won't be proven by this project anyway.

If you want to find a large prime there are better forms to look for.

IMO stick with the Sierpinskie or Riesel conjecture and ditch PSP. It's a waste of resources.

[hhh]

Well, that's one possible viewpoint, and it has been stated before already, by a PSP guy, btw. I still believe it's not a bad idea, because:
- PSP is not any large prime project; if it would be that, one could just abandon it completely, as Mersenne is much more effective for large primes. I see it more like an annex to SoB.

[- Then there is the efficiency thing: we sieve thier numbers, but sieving becomes more efficient and they will sieve a little bit our numbers, too, so finally we have only a little speed-loss for sob, (I hope). BTW I don't think is undersieved but somehow overPSPed, as the PSPpeole should switch (though I don't blame them at all, they are the backbone of this project).]
EDIT: I realized that this argument is bullshit. What I meant: The efficiency gain will hopefully make tolerable the speed loss due to larger sieve power at SoB.

- My interpretation of Seventeen or bust is that this project is going on until we foung 17 k's (Or sombody proved the assertion somehow else.) Perhaps it takes hundred years. But it means not that we cannot help out some friendly people, if its easy to do so. All the idea is based on the fact that it will not significantly slow down the project, and that the overall gain for the DC (or Sierpinsky) community is bigger then the loss for SOB.

Finally: why are you stating that PSP will not prove the smallest Prime Sierpinsy number?

Regards, H.

[hhh]

I did some benchmarking on my laptop with

the SoB SoB.dat
the PSP SoB.dat and
a combined one of both.

Here are the numbers:

SoB: 367kp/s 30MB
PSP: 259kp/s 35MB
both:200kp/s 22MB

I used the 53000 range, open for both projects. The biggest dat used the less memory, don't know why.

The overall speedup will be even bigger when we reach the PSP-unsieved ranges and find all these first-pass factors.

So, I will try to do this range. I may take a while, but... If you are opposed, tell me, I will start only in a few days. (Of corse I don't put only this machine to work).

53000-54000 reserved hhh

[Joe O]

Originally posted by hhh


53000-54000 reserved hhh

Actually this range is already being sieve for SoB with the 991-50M dat.

[vjs]

Why don't you reserve 90000-95000 for the combined effort. I believe this is also first pass with psp as well would be a nice range.

[hhh]

Ok, I have to apologize. So, let's do the following:
53000 54000 UNRESRVED by hhh

EDIT: undoing impertinent mistakes.

[jasong]

Maybe people will be mad at me for resurrecting a dead topic, but I'd like to touch on something that wasn't covered in this thread.

It is this: The rumors are that the new siever will be INCREDIBLY fast compared to what we have now. To the point where it would probably take Riesel sieve and PSP only a few months to catch up to SoB, and even with the combination, the combined sieve would probably STILL be faster than SoB alone.

My opinion is this: Sievers sieve for two main reasons, efficiency and points. If we combine the scoring, as well as the sieving, and the people involved have a system up quickly(say, within 2-3 weeks of the super-siever coming out), I think everyone involved will be very happy with the results.

Just my opinion.

[vjs]

I don't think bringing up this post makes anyone upset or something like that.

Also, I think the idea of combining te sieve is not a bad one, especially if the speed of the new client is BLISTERING compared to the current one.

However I don't see the point of combining the scores? They are still different projects with a different k/n base etc... Plus can't you look at it in the following way as well?

Doing a combined sieve your actually participating in several different projects and scoreing in them as well. Now also consider that those projects can have their own scoring systems, might attract more people wouldn't it.

One of the major problems that I see... what if we do incorperate the prp results into the scoring. Or what about P-1 factor, would riesel people or psp people be upset when we score a 300K+ factor? B/c if we were to use the current point system a max score for psp or riesel factor would only be ~40K?

Worth some thought... but I think in the end we will be happy just to see a very fast client and a combined efficient effort.

[Nuri]

If such a thing happens, a two way scoring would work best. :looney:

One within the combined sieving effort, and one within the particular projects (even better if incorporated with the project's prp scores).

[Mystwalker]

I think that it's a good thing to combine the sieving tasks, as it increases overall throughput. Indeed, I currently sieve a combined range for PSP (which just found a prime (http://www.mersenneforum.org/showthread.php?t=5266)!!!) and SoB.

I don't know if it's possible to simultaneously sieve Riesel and Proth numbers at the same time. Proth_sieve can't, the new sieve client probably can - but some months back, Chuck was pretty unsure about this. I'd say that at least in the beginning, this won't be possible. Once it is, I would immediately include Riesel as well. :)

[hhh]

So, we are back on my initial post:smoking: .

If it is possible to sieve together with Riesel, there is this minor issue that riesel is still sieving until 10M only, AFAIK. Does anybody have reliable informtion whether or not the client can combine k*2^n+1 and k*2^n-1?
If yes, we should perhaps start quickly a combined PSP/Riesel catchup.

Anyways, I'm all smiling:) . Cheers, H.

[Greenbank]

There should be no reason why the sieving cannot be combined.

Proth:

k*2^n+1 = 0 (mod p) is solving 2^n = -1*(k^-1) (mod p)

Riesel:

k*2^n-1 = 0 (mod p) is solving 2^n = k^-1 (mod p)

Working out the RHS for each is almost trivial, it's solving the DL for a set of possible answers that is the tricky part.

[bryan[RS]]

hhh- just to clarify, we are currently sieveing up to n=20M over at RieselSieve. There's no plans (at least in the short term) to increase that, but as part of a combined effort, anything is possible I guess. So, we are a ways back from the n=50M effort.

Bryan

Stats Administrator
RieselSieve Project

[hhh]

']...but as part of a combined effort, anything is possible I guess. So, we are a ways back from the n=50M effort.


That's not such a big deal. It is possible to catch up to a reasonable level in a few months. PSP proved it. And no need to resieve everything before joining the efforts.
I'm looking forward to the things that may come.

H.

[Joe O]

There should be no reason why the sieving cannot be combined.

Proth:

k*2^n+1 = 0 (mod p) is solving 2^n = -1*(k^-1) (mod p)

Riesel:

k*2^n-1 = 0 (mod p) is solving 2^n = k^-1 (mod p)

Working out the RHS for each is almost trivial, it's solving the DL for a set of possible answers that is the tricky part.
Alex,
While what you wrote is true, and I actually have programmed combining Riesel and Sierpinski in the same run. The problem is in the size of the Riesel Dat. I know that they just found another prime, and so it is smaller than what I tested with. But it is still too large to combine with anything else. Unless you want to page instead of sieve that is. Another issue is speed. Some tests and initializations of variables that can be done once for each p, have to move down and be done for each k within each p. Hence they are executed many more times. So with all due respect, ....

Someone once said: "Just because you can do something, doesn't mean that you should do it"

[TTn]

Combined sieving and relative primality can be used for the Riesel form.
http://mersenneforum.org/showthread.php?p=70030#post70030


Please see my program RMA.NET 0.83T.http://15k.us/files/RMA.exe
We need help testing this version on various target machines.

[Ken_g6[TA]]

Can you adjust the ratio of Baby Steps to Giant Steps in the BSGS algorithm to lower the memory requirements?

Also see my post in the FPGA thread. It seems Pollard Rho can be used to solve the DLP with very little memory, and maybe solve several in parallel like BSGS!

[jasong]

The problem is in the size of the Riesel Dat. I know that they just found another prime, and so it is smaller than what I tested with. But it is still too large to combine with anything else. Unless you want to page instead of sieve that is. Another issue is speed. Some tests and initializations of variables that can be done once for each p, have to move down and be done for each k within each p. Hence they are executed many more times. So with all due respect, ....

Someone once said: "Just because you can do something, doesn't mean that you should do it"
Since you're the main man on this, I'll take your word for it and drop the issue.

thanks for taking the time to comment.

[geoff]

I expect that the sieve range difference (20M riesel.dat vs 50M SoB.dat) will mean this is not efficient, but for anyone is interested in experimenting with the effects of combining SoB.dat and riesel.dat, sr2sieve can do this. Put SoB.dat and riesel.dat in the same directory and run `sr2sieve -rs -p<pmin> -P<pmax>'. To sieve SoB.dat or riesel.dat alone for comparison, run `sr2sieve -s ...' or `sr2sieve -r ...'.

The algorithm used by sr2sieve does not care much about +1 or -1, other things being equal it should not make any difference that there are both Sierpinski and Riesel sequences together in the sieve.

[Greenbank]

Geoff's sr2sieve is rivalling the speed of proth_sieve/jjsieve already, and it doesn't implement SPH.

Infact, I'm beginning to think that the reason it is as fast, and may eventually eclipse the speed of proth_sieve/jjsieve, is that it doesn't bother with SPH.

SPH requires vast (compared with cache sizes) chunks of memory to store the factors of each p-1 for each p in the sieve window. It's also a sparsely populated array. I'm not 100% sure that benefit gained from using SPH actually outweighs the effort and slowdown (from cache perspective) of calculating the p-1 factors, storing them, and then retreiving them for use in SPH along with all of the CRT work that is required.

This is just vague idea at the moment, I hope to do some work to back it up (or prove myself wrong). :)

[geoff]

I added a few dummy terms to extend the current riesel.dat to 50M. SoB.dat is the combined SoB/PSP one. These are the estimated times to sieve a 1G range starting at p=1000T with sr2sieve 1.5.14 on a 2.9GHz P4:


SoB.dat (19k, 50M) 35.2 min (473 kp/s, 27Mb)
riesel.dat (67k, 50M) 87.3 min (191 kp/s, 42Mb)
Both seperately 122 min
Both together (86k, 50M) 104 min (160 kp/s, 46Mb)

So there is some work to be saved by combining SoB and RieselSieve sieving if they are both working on the same n range.

[hhh]

Well, there are strong arguments for such a collaboration, but some against it as well.
If I understand the bottommost graph at http://boinc.rieselsieve.com/ correctly, they are currently sieving at p=1.5P=1500000G, which means that they have caught up with SoB in a few months and are already taking some advance. Here I even don't speak of the combined PSP/SoB effort yet.

On the other hand, if the site http://stats.rieselsieve.com/kstats.php is still up to date, they have some 3.5 million candidates remaining below n=10M. At their current work rate of 1000 LLR and 1000 factors a day, that means that they can keep crunching for at least 4 years. So the motivation to start over with a 50M sieving could be reduced.

On the other hand, if they happen to touch the limits of current software or of efficiency somewhen, and want to restart sieving, it would be cool if they could take the Sierpinski side into the boat.

One would of course have to think about what would be their advantage. 30% more overall efficiency don't sound so good if you do 99% of the work.

Yours H.

[birdman2584]

I believe that second link you posted is outdated. There have been requests on the Riesel Sieve forums to have it updated.

Thanks

[vjs]

I think this has been talked about quite a bit in the past. I'm not sure how much was public or in the forums.

The semi-conclusion at that time was Riesel was and is using a 1-20M dat, psp and SoB a 1-50M dat. By the time riesel makes it to ~18M the number of k's they would have will be significantly less than current.

What this basically means is that combining with any project that is sieveing to 50M is not a good idea for them or us.

PSP on the other hand is a good match, SoB currently has less k's by about 50% but both projects will continue prp beyond 20M in the short term (compared to riesel).