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.