Distributed sieving discussions

[michaf]

Hi all,

Is it of any use if I start a srsieve for all Sierpinski's?

Actually, I started one yesterday, and it went to 4.5B in about 21 hours, for ALL remaining sierpinksi's (90) upto n=300000. Now taking about 15 seconds per n to be eliminated

There are now 233616 remaining pairs upto 300k.

I just hope I didn't duplicate too much work :> It'll teach me to return to my computer before I go to bed...

Cheers, Micha

[axn]

I am currently sieving all the k's (Sierpinskis as well as Riesels) for n <= 2M. Current depth is p=5G. Probably some duplication is happening.

[michaf]

darn :>

ah well... Is there a way I can join in the sieving;
If I understand correctly, it is easy to distribute the load a bit?

- That is, is there an intermediate sieve-file available
- should there be a distributed sieving-effort with ''sieve-parts'' of about 1G-size (or whatever is a good size)?

[axn]

I've moved the last three posts out to a new thread.

[michaf]

Thanks for moving it :>

How large are the save-files
- how much k/n pairs are remaining?
- what is the size of the file zipped up?

The found-factor files should be rather small, some 30 bytes per factor, so these could be easily mailed.

[axn]

Distributing the sieving should be relatively straightforward.

Currently there are 353 files - about 135 MB. It is around 20 MB when zipped. So, to distribute the sieving, you'll have to download the sieve files, and then we can have some sort of reservation thread (like RieselSieve).

The problem, as I see, is that currently the k's are at low n values (especiaaly the Riesel k's). That means, a lot of them will be eliminated pretty quickly, which means that a lot is sieving effort will be wasted. So I am reluctant to go for a full blown distributed sieving effort at this time.

[michaf]

That is very true.
Happy to see them eliminated quickly though...

I'd say they get much harder to find when n=100k is reached.
When 100k is reached, I reckon there will be about as much riesels left as sierpinskis? some 200 total?

is that a viable limit to start 'distributed sieving' for both riesel & sierp.?

Is there an estimate around to when that will be when going with the current rate?

Oh, and how quickly are you eliminating k/n pairs with your sieving right now?

Enough questions for the day :>

[axn]

Originally Posted by michaf

I'd say they get much harder to find when n=100k is reached.
When 100k is reached, I reckon there will be about as much riesels left as sierpinskis? some 200 total?

You're very optimistic! I expect another 20-30 k to be eliminated. That'd still leave us with 320-330 k's

Originally Posted by michaf

is that a viable limit to start 'distributed sieving' for both riesel & sierp.?

Is there an estimate around to when that will be when going with the current rate?

Probably. Although, I think we can start sooner than that -- like, maybe once the Riesel k's reaches 70000. At that point, we would have eliminated enough k's to not worry about possible sieve wastage.

Originally Posted by michaf

Oh, and how quickly are you eliminating k/n pairs with your sieving right now?

At this very moment, I am not sieving the whole thing -- instead I am doing a focused sieve on Riesel k's for n<=100,000. However, when I stopped the sieving, it was doing around 1 k/n pair every 5 seconds or so.

Originally Posted by michaf

Enough questions for the day :>

Anyway, all the above are just my opinions. If there is enough interest, we can start up a distributed sieving effort in short order. Of course, we need some serious bandwidth and hosting space to put up the sieve files

[geoff]

Originally Posted by axn1

Of course, we need some serious bandwidth and hosting space to put up the sieve files

I gather you are saving the files in NewPGen format, which is a bit inefficient. It should be quite a bit more compact to save in the default srsieve format. You can convert between these formats with the srfile utility.

I could quite easily add any other file format. I suggest the ABCD format, which only stores the 'deltas', the difference between the n values instead of the whole n value. ABCD can be read by pfgw, and is easy to convert to any other format, but is not very good for hand editing. Storing the three terms 1396*5^1000-1, 1396*5^1006-1, 1396*5^1020-1 would look like this:

ABCD 1396*5^$a-1 [1000]
6
14

The total usage would probably average about two bytes per remaining term, uncompressed, though I haven't seen the data. Any other sugestions?

[michaf]

I'd say the ABCD format would be nice for space-savings, but then,
20Mb is doable these days (not to mention that the file will be getting
smaller every 5 seconds :>)

How much candidates are left in total? as in how much k/n pairs?

say x: x*2 bytes in ABCD format --> compressed about 1/4th of that, so that would be x/2 bytes

with sr-sieve format that is 7 digits on average --> x*7/4 bytes
About 4 times as large as with ABCD format.

Is the human-readability of any relevance? The formats are easily converted to one another after all.

[axn]

Originally Posted by geoff

I gather you are saving the files in NewPGen format, which is a bit inefficient. It should be quite a bit more compact to save in the default srsieve format. You can convert between these formats with the srfile utility.

Yes, I am using the NewPGen format. What is srfile utility? How do you compile it? Do you have the make file?

Originally Posted by geoff

I could quite easily add any other file format. I suggest the ABCD format, which only stores the 'deltas', the difference between the n values instead of the whole n value.
[snip]
The total usage would probably average about two bytes per remaining term, uncompressed, though I haven't seen the data. Any other sugestions?

I did some testing.

Format      Size in KB      Size in KB     Size in KB  
          (Uncompressed)   (Compressed)      (Ultra)
--------- --------------  -------------   -----------
NewPGen             707            90              87
Default             364            83              80
Delta               193            46              36

As you can see, when compressed, only the delta format make any significant difference.

Ofcourse, since the idea of distributed sieving is to _sieve_, there is no requirement on the format being compatible with any testing programs. As long as the format can hold both Sierpinskis and Riesels together, it should be fine. The other requirement is that it should be easy for the siever to quickly remove a k (when a prime is found). This will avoid repeated downloads of the sieve file(s).