New sieve program....
 

Please go to Free-DC forum and check this thread:

[url]http://free-dc.org/forum/showthread.php?s=&threadid=10069[/url]

Cheers,

Carlos

I see only a 5% increase in new sieve.

[QUOTE=Citrix]I see only a 5% increase in new sieve.[/QUOTE]

It's not the final version!

Carlos

[QUOTE=Citrix]I see only a 5% increase in new sieve.[/QUOTE]

Silly me, I thought any increase would be welcome. I guess I will have to withdraw the program until there is an acceptable increase. Would 10% do?

Joe,

I like 5% also. I would even prefer a 0.000...1% increase. But since your program is currently not bug proof. I will stick to proth_sieve, unless you make your program so fast that missing a few factors doesn't matter anymore.

Waiting for such a fast program.

Citrix

[QUOTE=Citrix]Joe,

I like 5% also. I would even prefer a 0.000...1% increase. But since your program is currently not bug proof. I will stick to proth_sieve, unless you make your program so fast that missing a few factors doesn't matter anymore.

Waiting for such a fast program.

Citrix[/QUOTE]

Have you seen 0.30C miss any factors? If so please give me the particulars.

Nothing so far to report, I will let you know if I see any. I know proth_sieve misses some.

[QUOTE=Citrix]Nothing so far to report, I will let you know if I see any. I know proth_sieve misses some.[/QUOTE]

I'm also interested in specifics where proth_sieve misses a factor.

Email ltd (Lars) , he can give you a list of factors from the DB.

Citrix

I have a suggestion to make.

consider the Pohlig-Hellman algorithm that proth_sieve uses. Now when the probability of finding a factor is less than 0.001% for a prime then we skip that p.That way we can sieve faster and deeper and find more factors even though we will miss a few.

I think if this will be implemented, we can find more factors faster. What do you think?
You can give it a try and inform us of the results.

Note:- 0.001% can be any arbitary number, where it is most optimal and can be deepdent on p, where p is the prime being tested.

Thanks,
Citrix

2090037773 | 1*2^1896586+1
2090076869 | 1*2^2567662+1
2090099741 | 1*2^2154742+1
2090190901 | 1*2^1990658+1
2090281541 | 1*2^2645926+1
2090494501 | 1*2^2787326+1
2090593409 | 1*2^1719238+1
2090699453 | 1*2^31342+1
2090903141 | 1*2^2944934+1
2091284873 | 1*2^1039406+1
2091594709 | 1*2^873682+1
2091643537 | 1*2^2125654+1
2091853069 | 1*2^2745214+1
2092308833 | 1*2^1469318+1
2092944397 | 1*2^3260038+1
2093003257 | 1*2^499762+1


Missed by proth_sieve for k=1.

Joe have you tried using FFT to multiply. How do you multiply 2 50 bit numbers? What algorithm are you using to multiply?

Citrix

[QUOTE=Citrix]2090037773 | 1*2^1896586+1
2090076869 | 1*2^2567662+1
2090099741 | 1*2^2154742+1
2090190901 | 1*2^1990658+1
2090281541 | 1*2^2645926+1
2090494501 | 1*2^2787326+1
2090593409 | 1*2^1719238+1
2090699453 | 1*2^31342+1
2090903141 | 1*2^2944934+1
2091284873 | 1*2^1039406+1
2091594709 | 1*2^873682+1
2091643537 | 1*2^2125654+1
2091853069 | 1*2^2745214+1
2092308833 | 1*2^1469318+1
2092944397 | 1*2^3260038+1
2093003257 | 1*2^499762+1


Missed by proth_sieve for k=1.[/QUOTE]

Do you have a dat file?

Proth_sieve doesn't find any factors for k=1. So the mistake was mine. It is meant for k>1. Whereas your program finds factors for k=1.

Citrix

[QUOTE=Citrix]Joe have you tried using FFT to multiply. How do you multiply 2 50 bit numbers? What algorithm are you using to multiply?

Citrix[/QUOTE]

50 bit numbers are too small for FFT.

This link should help:-

[url]http://groups.google.com/group/sci.crypt/browse_frm/thread/16584f78726c6824[/url]

BTW, I wasn't saying that the new sieve client uses that algorithm. I've no idea what it uses.

But you'll notice that the fp unit version in the google groups thread was posted by Phil Carmody who has written several sieves for various apps.

What Phil is suggesting is a trick to speed up the implemntation of multiplication, it is not a method to multiply numbers.

I am more intrested in methods than implementations.

Citrix

[QUOTE=Citrix]What Phil is suggesting is a trick to speed up the implemntation of multiplication, it is not a method to multiply numbers.

I am more intrested in methods than implementations.

Citrix[/QUOTE]

Yes, but the reason that implementation is very fast is that it provides a very quick method of division, which is a core part of modulus.

Multiplying two numbers together is the easy part, quickly getting the modulus of that number (which may now be 100 bits if two 50 bit numbers are multiplied) is the hard part.

proth_sieve uses a variation of this algorithm and I think Chuck is working on improvements based on the SIMD (SSE2/3) instructions to make it even faster.

For fast methods look at the source for gmp on [url]http://www.swox.com/gmp[/url]

GMP is chock full of descriptions, with references to papers, for all of the different multiplication methods (and for many other mathematical functions). The PDF documentation for GMP is good too.

Can somebody kindly help me with basics of this program. I'm neither with SOB nor with RieselSieve, I'd like to sieve some small k's (k<300) and some "15k"-s (k with many small divisors).

1) Is there any restriction on k?
It seems it doesn't work for k > 2^31.

2) How do I start the very first time? I understand the format of sob/riesel.dat file is:
10 <-- number of k's in the file
1000 <-- n_min
1000000 <-- n_max
k=5 <-- first k
1005 <-- first exponent
+12 <-- delta to next exponent
...

Shall I create a file with many 1's in place of delta's? Actually I did and it works, but is there another way, so that the file is portable (smaller)? I hope I don't have to use NewPGen (?)

3) After sieving, how do I create a file for LLR? I tried the "-u" switch but it erases the input 'riesel.dat' creating an empty file. The same happens if I use "-full".

4) (a) What is the optimal number of k's to sieve at the same time? (b) How shall I select the exponent range n_min - n_max in order to minimize the number of "out of range" exponents?

Thanks.

[b]Can somebody kindly help me with basics of this program. I'm neither with SOB nor with RieselSieve, I'd like to sieve some small k's (k<300) and some "15k"-s (k with many small divisors).[/b]

I take it you're doing Riesel numbers (k*2^n[b]-1[/b]) since you mention LLR below in the post. Note that LLR is not the test you are looking for if you are doing Sierpinksi numbers (k*2^n[b]+[/b]1).

[b]1) Is there any restriction on k?
It seems it doesn't work for k > 2^31.[/b]

The only restriction is that it is a 32 bit signed integer, hence it won't work for k > 2^31. I think k cannot be 1 either.

[b]2) How do I start the very first time? I understand the format of sob/riesel.dat file is:[/b]

The format is correct.

[b]Shall I create a file with many 1's in place of delta's? Actually I did and it works, but is there another way, so that the file is portable (smaller)? I hope I don't have to use NewPGen (?)[/b]

You can't sieve below 1,000,000,000 with proth_sieve, you have to use something else for this. Once you've sieved to this level you can create your .dat file and use proth_sieve.

If k is not divisible by 3 then check (by trial division) whether you can remove all odd or all even n's from the .dat file (see my post above).

If k is divisible by 3 then you can't remove any automatically.

[b]3) After sieving, how do I create a file for LLR? I tried the "-u" switch but it erases the input 'riesel.dat' creating an empty file. The same happens if I use "-full".[/b]

Finish sieving then write a quick program to parse the input .dat file and your factors found file and remove any entries, write out the new .dat file. Not sure of the exact format for LLR so you'll have to handle that yourself.

[b]4) (a) What is the optimal number of k's to sieve at the same time? (b) How shall I select the exponent range n_min - n_max in order to minimize the number of "out of range" exponents?[/b]

Sieve them all at once, there's no point splitting up the k's to different files.

set n_min and n_max to exactly what you care about. proth_sieve does not guarantee to find every out of range factor so you cannot rely on it.

It only finds out of range factors when the search space has been reduced with enough useful information out of the Silver-Pohlig-Hellman stage.

Greenbank
 

Thanks for your replies. Now I have a few more questions, follow-up's.

1) Understood that 3 <= k < 2^31. Can you possibly include support for larger k's, let's say up tp 2^63?

2a) I was able to start jjsieve to factor from 5 by entering p_min=3 and p_max on the command line. But it skips 3. It will be nice if you can add an option to start a completely new sieve so that jjsieve creates the .dat file. Running NewPGen to 1bn on 10 or 20 k's, then combining the output into a large .dat file is no fun :sad:

2b) When I group k's into .dat file is it better to have one .dat for k's divisible by 3 and one .dat for the others? Instead of a large file for all k's.

3) About "-u" and "-full" switches: Does it mean these two are not working? IMO, It will be nice to have them working to shrink the size of .dat from time to time, specially in early stages. By "file for LLR" I mean a file with a list of exponents, one per line, I can add the rest easily.

4) We at [URL=http://www.mersenneforum.org/forumdisplay.php?f=16]15k Search[/URL] have several projects running, for example:
PJ-1: 1 < k < 300
PJ-2: 15k like k=9225, 355424355, 3611911875 (all divisible by 3, 5 and other small primes, for example 355424355 = 3^4*5*11*13*17*19^2).
PJ-3: low weight, like k=253, 10943321, 355281299 (no one divisible by 3)

So if we use jjsieve we are going to have several .dat files (some ppl may prefer to sieve alone) and with some exceptions we sieve to smaller p than SOB and RieselSieve. I wonder is there any guidance how many k's to group in one .dat file, 4, 10, 16? Is it better to have the number of k's be a power of 2 or not? What's the smallest number of k's when it makes sense to use jjsieve?

BTW, FYI, the latest version of LLR can test k*2^n+1 too, but at "15k" we only test k*2^n-1.

It works with k=1, I tested it sometime back, if you read the thread above. It is though a bit slower with k=1.

Citrix
edit: You can work on proth_sieve <1G range. Just write your own sobstatus.dat and run the exe.

[b]Thanks for your replies. Now I have a few more questions, follow-up's.

1) Understood that 3 <= k < 2^31. Can you possibly include support for larger k's, let's say up tp 2^63?[/b]

I don't control proth_sieve, however I'll let Chuck/Joe_O know. I think the largest you'll get with proth_sieve/jjsieve would be 2^50.

[b]2a) I was able to start jjsieve to factor from 5 by entering p_min=3 and p_max on the command line. But it skips 3. It will be nice if you can add an option to start a completely new sieve so that jjsieve creates the .dat file. Running NewPGen to 1bn on 10 or 20 k's, then combining the output into a large .dat file is no fun :sad: [/b]

Try entering p_min = 2. It might work.

[b]2b) When I group k's into .dat file is it better to have one .dat for k's divisible by 3 and one .dat for the others? Instead of a large file for all k's.[/b]

Large file for all k's, otherwise you are duplicating work.

[b]3) About "-u" and "-full" switches: Does it mean these two are not working? IMO, It will be nice to have them working to shrink the size of .dat from time to time, specially in early stages. By "file for LLR" I mean a file with a list of exponents, one per line, I can add the rest easily.[/b]

No idea about this, again I'm not the author of the program, I've just used it quite a bit.

[b]4) We at [URL=http://www.mersenneforum.org/forumdisplay.php?f=16]15k Search[/URL] have several projects running, for example:
PJ-1: 1 < k < 300
PJ-2: 15k like k=9225, 355424355, 3611911875 (all divisible by 3, 5 and other small primes, for example 355424355 = 3^4*5*11*13*17*19^2).
PJ-3: low weight, like k=253, 10943321, 355281299 (no one divisible by 3)

So if we use jjsieve we are going to have several .dat files (some ppl may prefer to sieve alone) and with some exceptions we sieve to smaller p than SOB and RieselSieve. I wonder is there any guidance how many k's to group in one .dat file, 4, 10, 16? Is it better to have the number of k's be a power of 2 or not? What's the smallest number of k's when it makes sense to use jjsieve?[/b]

The more you have in one file the more efficient it is. It's also much easier to keep track of what ranges you have sieved if everything is in one file.

Interesting though, what do you hope to prove/find out from looking at these k values?

[b]BTW, FYI, the latest version of LLR can test k*2^n+1 too, but at "15k" we only test k*2^n-1.[/b]

Well, it's doing a Proth test, the LLR test does not work for k*2^n+1.

Sierpinski (k*2^n+1): Proth Test.
Riesel (k*2^n-1): Lucas-Lehmer-Riesel (LLR)