mersenneforum.org MultiSieve from the command line (on Windows)
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2007-12-14, 19:15 #1 monst     Mar 2007 179 Posts MultiSieve from the command line (on Windows) Hello Rogue, I've been using MultiSieve and gcwsieve a lot recently. I was wondering if there is any way to run the Windows version of MultiSieve from the command line. If not, what are the chances of "reverting back" with this feature? Did you ever release a version with the "SieveUntil" option that you put in for me in Nov, 2005? I would like to retain that capability. Also... a performance question for you and Geoff: Several years back, you mentioned that it was more efficient to sieve GCs and GWs at the same time in MultiSieve. Is this also true for gcwsieve? ... or would it be more efficient to sieve them separately? Thanks, -- monst
2007-12-14, 20:28   #2
rogue

"Mark"
Apr 2003
Between here and the

2×7×11×41 Posts

Quote:
 Originally Posted by monst Hello Rogue, I've been using MultiSieve and gcwsieve a lot recently. I was wondering if there is any way to run the Windows version of MultiSieve from the command line. If not, what are the chances of "reverting back" with this feature? Did you ever release a version with the "SieveUntil" option that you put in for me in Nov, 2005? I would like to retain that capability. Also... a performance question for you and Geoff: Several years back, you mentioned that it was more efficient to sieve GCs and GWs at the same time in MultiSieve. Is this also true for gcwsieve? ... or would it be more efficient to sieve them separately? Thanks, -- monst
Which sieve option are you referring to?

If you mean Cullens and Woodalls, then it would be easy to modify gcwsieve so that MultiSieve wouldn't be needed. I sent the code to Geoff a while ago, but he hasn't implemented it yet. In lieu of that you can use MultiSieve to sieve up to a point where p > max n, then switch to gcwsieve.

BTW, I haven't touched the code in a while. If desired (and Geoff has the time), he and I could easily craft other stand-alone programs to replace the different parts of MultiSieve. They would undoubtably be much faster than the last incarnation of my program.

 2007-12-14, 23:21 #3 monst     Mar 2007 17910 Posts The sieve options I'm interested in now are Generalized Cullens and Generalized Woodalls. I am using MultiSieve and gcwsieve as you suggest. So I would welcome Geoff's addition of being able to start the sieve in gcwsieve. I am also interested in Hyper Cullens and Hyper Woodalls. Any plans for a hcwsieve in the future? (with sieve-starting capability...)
2007-12-15, 01:28   #4
geoff

Mar 2003
New Zealand

13×89 Posts

Quote:
 Originally Posted by monst Hello Rogue, Also... a performance question for you and Geoff: Several years back, you mentioned that it was more efficient to sieve GCs and GWs at the same time in MultiSieve. Is this also true for gcwsieve? ... or would it be more efficient to sieve them separately?
For gcwsieve, in theory, there is a small advantage to sieving Cullen and Woodall together: it saves the time to generate the candidate prime factors p; saves one modular inverse per p; and often reduces the size of the greatest gap between exponents (because there are more exponents over the same interval).

However in practice when there are many thousands of exponents in the sieve the difference is hardly noticeable, and on some machines the effect of the extra L2 cache space used (8 bytes for each Cullen and each Woodall in the sieve) is more important. There might be more of a difference when there is only a small number of exponents in the sieve, less than a few hundred say, but gcwsieve is not optimised for that situation anyway.

The only real answer is to test it for yourself and see which method is faster.

Quote:
 Originally Posted by rogue I sent the code to Geoff a while ago, but he hasn't implemented it yet. In lieu of that you can use MultiSieve to sieve up to a point where p > max n, then switch to gcwsieve
I have the code for testing primes p < max exponent n, but there is still more that needs to be done to generate the sieve from scratch.

When I get time I plan to make it possible for gcwsieve to generate a sieve from scratch, if only because the only way to do that in Linux is to run MultiSieve in a Windows emulator, or by trial factoring with PFGW which is slow. But this will just be a convenience feature, it probably won't be any faster than MultiSieve, and might be slower.

 2007-12-15, 16:53 #5 monst     Mar 2007 179 Posts Geoff, another approach for the interim could be to lift the restriction in gcwsieve to be able to read in MultiSieve files with multiple bases in them. I'm not suggesting sieving multiple bases, just reading in the multiple-base MultiSieve file and writing out multiple single-base files in the 3 formats supported -- based on the current rules you have in gcwsieve (existance of --multisieve switch and variable or fixed C). Your thoughts?
2007-12-16, 01:09   #6
geoff

Mar 2003
New Zealand

13×89 Posts

Quote:
 Originally Posted by monst Geoff, another approach for the interim could be to lift the restriction in gcwsieve to be able to read in MultiSieve files with multiple bases in them. I'm not suggesting sieving multiple bases, just reading in the multiple-base MultiSieve file and writing out multiple single-base files in the 3 formats supported -- based on the current rules you have in gcwsieve (existance of --multisieve switch and variable or fixed C). Your thoughts?
It would be easier for me to write a small program to split the variable-b ABC file into multiple fixed-b files. (There is probably a unix command that does it already :-). You could then invoke gcwsieve seperately for each file. Would that do?

Last fiddled with by geoff on 2007-12-16 at 01:10

 2007-12-16, 14:34 #7 monst     Mar 2007 179 Posts I took another approach that minimizes data entry into MultiSieve. I wrote a program that generates single-base GCW (Generalized Cullen/Woodall) starting files for MultiSieve. I make sure n and b are not both odd (since 2 is a factor for these numbers) and instruct MultiSieve to begin sieving at 3 via the header line... ABC $a*$b^$a$c // CW Sieved to: 3 This allows me to launch MultiSieve with the "Continue Sieveing" selection. The only parameter I need to change from run to run is the "Save File Name". I do not change the log file name. These files start off very large. After a few seconds MultiSieve eliminates alot of the candidates, reducing the file size a lot, but creates (or appends to) a large log file. I'm using a version of MultiSieve that has a "SieveUntil" feature implemented through the ini file. I set this just high enough to sieve past the Max k (max n in gcwsieve) so the file can then be run with the more efficient gcwsieve. I need to keep deleting the log file after every few MultiSieve runs since it gets very large. (I don't think I can suppress the logging in MultiSieve.) So bottom line is this... I am past the interim file manipulation request. I have better control with the method I'm using so I'm all set here. (Actually I had started writing a parser as you suggested when I decided on this other method.) What would be most beneficial is having command line control of the entire process. This would require one of the following: 1.) Command line control of MultiSieve -- actually this would only be needed for "Continue Sieving" with "SieveUntil" control. OR... 2.) Being able to start the sieve in gcwsieve Last fiddled with by monst on 2007-12-16 at 14:35
2007-12-18, 02:37   #8
geoff

Mar 2003
New Zealand

48516 Posts

Quote:
 Originally Posted by monst I'm using a version of MultiSieve that has a "SieveUntil" feature implemented through the ini file. I set this just high enough to sieve past the Max k (max n in gcwsieve) [/SIZE]
Be aware that gcwsieve doesn't actually reduce the size of the sieve as factors are found, it just marks the candiate so that duplicate factors are not reported, so to get best performance you will need to stop and restart it every now and then. This is because gcwsieve was designed for the deep end of the sieve where factor density is very low.

Quote:
 I am past the interim file manipulation request. I have better control with the method I'm using so I'm all set here. (Actually I had started writing a parser as you suggested when I decided on this other method.)[/SIZE]
This awk command will split a MultiSieve variable-base ABC file in.txt' into seperate fixed-base files <base>.txt' suitable for input to gcwsieve:
Code:
awk '/ABC/{H=$0;next}!F[$2]{F[$2]=$2".txt";print H>F[$2]}{print>>F[$2]}' in.txt
I have a working prototype of a program that will start sieving a single base from scratch. It had three phases:

1. Remove terms with algebraic factors and those divisible by two.

2. Remove terms with factors p in 2 < p <= sqrt(n_max). This takes up to p(p-1) modular multiplications for each p.

3. Remove terms with factors p in sqrt(n_max) < p <= n_max. This takes two modular multiplications per remaining term for each p.

(The algorithm gcwsieve uses takes one modular multiplication per remaining term for each p > n_max).

Last fiddled with by geoff on 2007-12-18 at 02:48 Reason: phase 2

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post pepi37 Linux 4 2015-07-16 22:06 mu5tan6 Software 14 2015-03-20 17:21 Gabe Brown Information & Answers 3 2009-12-12 14:01 wongnog Information & Answers 1 2008-07-20 11:29 monst Software 19 2008-01-31 07:07

All times are UTC. The time now is 23:09.

Mon May 17 23:09:29 UTC 2021 up 39 days, 17:50, 0 users, load averages: 1.67, 2.06, 2.34

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.