$Id: README.html,v 8.1 2007/06/23 22:33:35 wedgingt Exp $All files with version number 8.1 are from the same release. Primary changes from version 7.1, released in December 2003, include: 1. Quick ports to Cygwin (http://www.cygwin.com/ a UNIX-like front end for MSWindows) and more recent Apple computers (but none with Intel hardware, which I have not had access to). 2. Addition of sprpgmp, sprplip, 1strsgmp, 1strslip, and others, if only to this README file (i.e., some of them may have been in the prior release, but weren't mentioned here). 3. Addition of -a option to ecm3, which may already be obsolete. 4. Numerous small bug fixes, none of which are likely to have affected calculations.
If you want to try to factor Mersenne numbers, you will have to make do with the full instructions below; there are too many possibilities and a couple of other libraries that are likely needed.
Further, you should read the top of the Makefile (or Makefile.nofac, if you use it); there are several kinds of computers that will run the programs faster if they are compiled slightly differently as noted in the Makefile.
But, if all you want to do is look for Mersenne Primes using the Lucas-Lehmer test, are willing to wait years, perhaps, for a single result, you have a UNIX computer that understands email to Internet addresses, you have a list of exponents to test from the Manual Testing web page and you have unpacked the tar or zip file that the mers package comes in, then it's likely that all you need to do is:
% make -f Makefile.nofacand wait for it to compile and test the Lucas-Lehmer testers (fftlucas, mersenne1, mersenne2, and MacLucasUNIX). Then, simply paste the list (including any 'Test=' prefix, if you want; fftll will strip it off) into fftll via stdin (standard input) like this:
% ./fftll -a -m -c50000 - Test=1234567,50 Test=1234569,50 EOF(where 'EOF' means to hit the end-of-file character, usually control-D). Or paste the list into a file and name the file instead of that last '-' on the fftll command line.
The LL test programs do not (yet) support networking; the Internet will be used only for email. If you want fftll to use a particular LL test program, then, before starting fftll as above, do, for example:
% setenv FFTLUCAS MacLucasUNIX or: % FFTLUCAS=MacLucasUNIX % export FFTLUCAS(depending on whether you have a csh look-a-like shell or a sh look-a-like). MacLucasFFTW is likely the fastest - but least tested - of the LL test programs provided by this package. Checkpoint files produced by (recent) prior versions of the other LL test programs should be read and used correctly by MacLucasFFTW.
% make >& make.output(give any other arguments to make that you want right after "make"). If that complains about a "null redirect" or similar, then you're using a Bourne (sh) or compatible shell and it wants something like:
% make > make.output 2>&1to do the same thing (put stdout and stderr in the same file). Then, after the make completes, email me the file. On most UNIX machines that have email to the Internet:
% mail wedgingt@acm.org < make.outputwill do it. The contents of make.output may not have everything I need to solve the problems, but it should tell me what questions to ask you to get the info I need from your computer.
Since I presently only have access to RedHat Linux for testing this package, I have to rely on others to test the package on other platforms and send me back changes, guesses at things to try, or at least the error messages. Further, note that George Woltman's programs run much faster on nearly all Intel platforms, including Intel Linux, FreeBSD, NT, Windows 95, Windows 3.x, etc., and that at least one port of George's programs to OS/2 has been announced on the mailing list. Further, John Sweeney has taken many of the ideas from George's code and produced a C language version for Macintosh PowerPC systems (the binary of which is also on George's web page just above); it too appears to be faster than this package's programs on the same hardware. With help from several other people, I have ported John Sweeney's code back to UNIX and it seems to run correctly on several UNIX variants, including Linux, SunOS, SGIs, and IBMs with PowerPC CPUs, so it is now included in this package as MacLucasUNIX. Also, Ernst Mayer has written a Fortran90 program for doing Lucas-Lehmer tests, so, if you have a Fortran90 compiler, that's probably going to be faster than mersenne1 - but perhaps not MacLucasUNIX - of this package. See my Mersenne page for more and links to others with much more information on these other programs and how to get them.
The other README files (README.fftlucas and README.mersenne1) were originally comments at the top of their respective .c files; they are now very out-of-date and are only retained to show each program's origins, references, and so on. In fact, none of the usage information that was in those files in prior releases was accurate; it's now been deleted entirely to prevent further confusion.
None of the "guts" (calculations-related code) of these programs (with the exceptions of extract and fftll) originated with me; my changes have all been to improve usability and portability, to take advantage of "long double" or "long long" if they're available, define the details of the checkpoint formats, and similar things.
The top of the Makefile and my personal web pages document where the current release of the package can be found. Please install the most recent version you can get a copy of; the programs are being almost constantly improved in terms of both speed and usability. If you can't get it any other way, let me know and I'll email you a copy.
All of the programs that do extensive calculations call setup.c's setup() function, which reduces the priority as low as I know how to lower it so that other programs are always preferred by the CPU. Setup() also sets some signal handlers so that a SIGTERM (terminate, usually 15; sent by the usual UNIX shutdown command), a SIGINT (interrupt, usually 2; often control-C), or a SIGHUP (hangup, usually 1; often sent by logging out) tells the program to save what it's doing and exit as soon as possible, usually within a few seconds.
Note that ecm3 will never print every prime factor of composite exponent Mersenne numbers because of several possible algebraic factorizations. First:
GCD(2^a - 1, 2^b - 1) = 2^GCD(a, b) - 1For example, a prime exponent Mersenne number is a factor of all Mersenne numbers whose exponent is a multiple of that prime. Second:
M(2*n) = 2^(2*n) - 1 = (2^n)^2 - 1^2 = (2^n - 1)*(2^n + 1)
= M(n)*(M(n) + 2)
Ecm3 will thus only print factors of M(n) + 2 for M(2*n). Third:
M(4*n - 2) + 2 = 2^(4*n - 2) + 1 = (2^(2*n - 1) - 2^n + 1) *(2^(2*n - 1) + 2^n + 1) So L and M are defined as: L = 2^(2*n - 1) - 2^n + 1 M = 2^(2*n - 1) + 2^n + 1and ecm3 tries to factor both of them whenever it is given a Mersenne exponent that is an odd multiple of 4.
Ecm3 pulls all of these "predictable" factors out using zgcd() of the freeLIP package before trying to factor what remains. See the description of the "mers format" for more details, especially regarding ecm3's output, and my mersenne web page for some related proofs.
In the Makefile, the locations of libgmp.a, freeLIP, and FFTW will likely have to be edited based on where each is installed on your system. Note that some users have complained about versions of libgmp before 2.0.2. Only the versions of freeLIP that have a "double" grow parameter to the zecm() and zfecm() functions are new enough to compile with ecm3 and ecmfactor cleanly. The only simple alternative to having libgmp and freeLIP is to not compile the factoring programs by:
% mv -i Makefile Makefile.fac % mv -i Makefile.nofac Makefile... before running "make". Mersfacint does not require either libgmp.a or freeLIP, but Makefile.nofac does not try to compile it.
Otherwise, the installation will likely consist of simply typing "make" to your shell and waiting for the package to compile and test itself; exceptions are noted below. The package is well tested under SunOS 4.x and 5.x, (RedHat) Linux, HPUX, DEC Ultrix, DEC Alpha OSF, SGI Irix 5.x, and probably others I'm forgetting at the moment; only SunOS 5.x and SGIs using cc presently need Makefile edits, though HPUX and DEC machines benefit from different optimization options. SGIs running Irix 6.x are reported to have problems; please let me know if you do not have problems there or if you can solve them.
If your computer has a 'long double' type with one compiler (say, the FSF's gcc) but not with a different compiler (say, the cc that came with the operating system), using the compiler that has 'long double' should result in substantially faster Lucas-Lehmer test programs, since the FFT run length can often be reduced due to the greater floating point precision.
Extract is reported to compile fine using djgpp on Win/NT 4.0.
Compilation has been at least attempted under OpenVMS on DEC Alphas.
Support for the Amiga has improved, but a gcc compiler problem there is currently stalling further progress, though I have heard nothing on this since the v2.7.2.1 release of gcc.
The usual format read and written by both rw.c and ecm3.c and most of the others is documented in mersfmt.txt .
By default, most programs except extract read from stdin and write to stdout. Extract defaults to reading George Woltman's DATABASE file and printing a human-readable copy of it on stdout. Most programs treat arguments that do not start with a "-" as filenames or, if positive integers that do not name files, exponents. "-" by itself means read stdin now rather than not at all or - if no other file arguments are given - only after all other arguments are processed, including with fftll. The usage information for programs that use rw.c's input() is briefly described near the top of rw.c itself and will be printed as part of most error messages related to incorrect usage. Somewhat longer descriptions of options for all of the programs and fftll:
-a For trial factoring only, do not stop on finding the first
factor; keep looking for more. Ecm3, ecmfactor, mmtrial, and
merskfac always behave this way. Otherwise, it is not the
default for programs using rw.c's input().
-b For fftll and the Lucas-Lehmer test programs, use a (much
faster) binary checkpoint format that is not portable between
machines nor useful via TCP/IP (default).
-b # For ecm3 and ecmfactor, specify the bound on the first
elliptic curve. Note that the "M( exponent )E: work bound"
and "M( exponent )e: bound curves" formats make this choice
per exponent.
-c # Create a new checkpoint after every # iterations
(Lucas-Lehmer testers and fftll only). Any value less than
5000 will be treated as 5000. Overrides the
FFTLUCAS_CHECKPOINT environment variable, which can also be
used to set this checkpoint interval. Default is no
checkpointing at all.
-c # For ecm3 and ecmfactor, specify the number of curves to try
at each bound used; defaults to 1.
-d Duplicate the normal output to stderr. Mostly so that "-d -n"
will print the results locally as well as sending them to the
server. Can also be given as "-d-", "-d -", "-dstderr", "-d
stderr", or, to write to stdout, "-dstdout" or "-d stdout",
or, to write to a particular file, "-dfilename" or "-d
filename". Note that "-d -n", e.g. will be treated the same
as "-dstderr -n". Default is to not duplicate the output.
This will never truncate a file; it always appends.
-D For ecm3, sprpgmp, and sprplip only, print any pseudo-prime
(but not proven prime) cofactors.
-e # For programs that use rw.c's input(), gives the power of two
at which trial factoring should stop. As a special case,
'-e 1' will factor from the prior extent past the next higher
power of two. The default is to do the number of trials given
by -m.
-g # For ecm3 and ecmfactor, specify the growth ratio by which the
bound is increased after the number of curves given by -c have
been completed. For # >= 1.0, the new bound will be the old
bound times #; for 0.0 < # < 1.0, the new bound will be based
on the old bound, obnd, using a somewhat messy function:
exp(# * log(obnd + exp(log(obd)/ #))) + 1
that attempts to use the "optimal" bounds for ECM. The
default is 0.63, which seems to match the freeLIP
documentation's table for "optimal" bounds. Paul Zimmerman
of
ECMNet has suggested using 2/3 (0.666666666...) for this
option.
-h For programs that call rw.c's input(), use the human readable
checkpoint format, which is portable between computers with
the same length of double (or long double) and can be sent
over TCP/IP. This option is only valid with fftlucas and
fftll when using fftlucas; using it with any of the other
LL testers will print an error and exit to avoid a problem
with human readable checkpoint round off errors.
-h For contract, print a brief help message and exit.
-i For contract, specify the file to read from.
-i # For ecm3 and ecmfactor, specify the info parameter to freeLIP's
zfecm() function. Zero, the default, will print no additional
info; one will print the bound used for each curve and some
timing info; two will also print the time for each of the two
phases. Larger values' lowest two bits will be used the same
way; the higher bits will print different info about the
progress thru the input file, the next exponent to be worked
on, etc. Values larger than three will cause ecm3 to print more
information; it uses the higher bits as toggles to decide what
other info to print.
-i For fftll only, -i means it should "input"/read new exponents
per the other options and arguments but not start any
Lucas-Lehmer programs, instead simply storing the new
exponents read in so that an fftll already running or to be
started later will find and read in the new exponents.
-L For ecm3 only, do ECM on the Mersenne number with the lowest
sum of exponent, ECM bound, and base 2 logarithm of the
remaining cofactor. Since the ECM bound increases with each
set of curves (-c) if no factor is found, this will rotate
among the Mersenne numbers read in. This seems to favor
finding small factors sooner than without -L.
-l # For ecm3 and ecmfactor, specify the largest ECM bound to be
used for any exponent. This is the only restriction that
might cause ecm3 or ecmfactor to exit before it has completely
factored all the numbers read. If -L is also given, the limit
given with -l applies to the sum used by -L, not (just) the
bound.
-l # For merspm1, gives the smoothness limit or bound to be used
by the P-1 method.
-m # For trial factoring only, check # (more) possible trial
factors (values of k in 2*k*p + 1). Default is one sieve pass
(which itself defaults to about 98,000 trials, quite small).
This can also be specified in the input with a line like
"trials 98000", which all programs using rw.c's input() know
about and, if not a trial factorer, skip and ignore. In the
-n (TCP/IP) case, the server uses "trials #" lines to control
how long the client runs without interaction.
-n Networking; see below for how to
compile the programs to allow this flag. Presently only
useful with the trial factorers mersfacgmp, mersfacint,
and mersfaclip. No later arguments are processed and input
and output (-o but not -d) are redirected to the server via
TCP/IP. If a local copy of results is wanted, use -d before
-n. If no hostname is given with -n, the value of the
environment variable MERS_SERVER_HOST (if set and not empty)
or "localhost" is used. If the connection to the server
breaks during calculations, the data is appended to the file
"mersarch.txt" and the program attempts to contact the server
again. If it is unsuccessful, it simply factors the same
Mersenne farther, again appending to "mersarch.txt", and tries
to connect again. This will continue as long as it cannot
connect and can factor further. Once it does connect, it
sends the server the contents of the "mersarch.txt" file,
removes it, and resumes reading from the server;
"mersarch.txt" will never be removed or truncated otherwise.
The only server that will work with these programs using -n
is my (unreleased) server that I am slowly making portable
enough to release.
-o For programs that use rw.c's input(), -o is like -d, but for
the "primary" output rather than the duplicate output, but
this defaults to stdout, including when used like "-o-" and
"-o -". This always appends, never truncates.
-o For contract, ecm3, and ecmfactor, specify the output file, but
"-o-" will create a file named "-" and "-ostdout" will create
a file named "stdout" (e.g.).
-p # Port number to connect to server with. The default is the
environment variable MERS_SERVER_PORT or, if that is not set
or is non-numeric, 2203. Ignored if -n is not given later.
-p For ecm3 only, check the primality of the initial cofactors
of the Mersenne numbers read in before trying to factor them.
Uses freeLIP's reasonably fast code to do a base 3 pseudo-prime
test followed by four more pseudo-prime tests with random bases
if required.
-P For ecm3 only, do nothing except check the primality of
cofactors that need checking (based on 'c:' lines). This makes
it behave more or less like sprplip or sprpgmp and sprpgmp should
be considerably faster, so ...
-r # # For ecm3, ecmfactor, extract, fftll, and programs that use
rw.c's input(), limit all testing to exponents between or
equal to the two numbers given. Data for exponents outside
the range will be read correctly and ignored. This also
applies to input from the server via -n; the range is reported
to the server on connecting to it.
-s For trial factoring, do a "small" number of trial factors
for each exponent (this is mostly for the tests in the
Makefile). The number of trials is presently one sieve
pass, presently 98,304 trials if the sieve array's size
is not changed from the distribution value of 4096.
-t Print (real or "wall clock") time information to stderr. If
you have getrusage() and #define USE_RUSAGE, the user and
system CPU times will also be printed; see below in the
Makefile section for how to do this.
-u For contract, ignore information for Mersenne numbers
of known primality (that is, for composite exponents or for
which a factor or LL test residue is known).
-v Print some version information. Other arguments are processed
normally; this does not cause an exit. The version info is
always sent to the server when connecting to it if the -n flag
is given.
-v For contract, increment the verbosity of the output to the
user (counts of exponents, e.g.).
-v For ecm3 and ecmfactor, print some usage information and continue.
-1, -2, -3, -4, -m
For extract only, indicates how many columns to use when
printing the data from the DATABASE file. The first three,
-1, -2, and -3, will print the exponent, the power of two
indicating the extent of factoring (if -2 or -3), and the flag
indicating how many Lucas-Lehmer tests have already been
performed (-3), separated by commas. -4 and -m print the same
info as -3, but in the format that I developed on my own
before GIMPS was formed: "M( exponent )[UH]: extent". Nearly
all of the programs will now read the -1, -2, -4, and -m
output formats of extract; fftll can read the -1 and -2
formats.
Unknown arguments starting with "-" cause error and usage messages to
be printed and the program to exit, except in the cases of extract,
which simply prints a warning and continues with the next argument,
and contract, which ignores them completely. Contract prints a usage
message and exits if any argument does not start with a "-". If FFTLUCAS_CHECKPOINT is in the environment, it is taken to be the number of iterations between writing checkpoint files by the LL test programs (fftlucas, mersenne1, mersenne2, and MacLucasUNIX); it is checked once before all arguments, so a -c command line option will override any value in the environment.
The checkpoint file names are hard-wired to "#", "c#", and "t#" (without the quotes) where # is the exponent being LL-tested. This is so that fftll, the shell script, can find them easily after a machine reboot or (fftll) restart. All three names are known to fftll; the LL test programs only write to "c#", renaming the prior "c#" to "t#" each time. Fftll is usually "smart" enough to use the "t#" file if the "c#" appears corrupt and the sole purpose for the "t#" file is to recover if the new "c#" file is corrupted by a machine crash or something similar.
The LL test programs (MacLucas*, mersenne1 & 2, and fftlucas) can, of course, read checkpoint files produced by any of the four programs, even binary ones from stdin (as long as any binary checkpoint was produced on a computer of the same architecture).
None of the programs can test an exponent below 31, but all Mersenne numbers with an exponent less than 787 are completely factored anyway, so this limit of 31 may increase in the future. Most of the programs can check any odd exponent Mersenne, but only prime exponent Mersennes can themselves be prime and composite exponent Mersennes have factors that the trial factorers will not check for. Ecm3 can factor any Mersenne number with an exponent above 31.
Mersfacint does not run at all if it cannot find a native 64 bit integer type (usually 'long' (DEC Alphas, e.g.) or 'long long' (Intel Linux)).
Other than those that start with "-", extract treats all arguments as file names to open. If the last component (everything after the last "/") of the filename is "DATABASE" or "database", extract assumes it is a copy of George Woltman's DATABASE file and prints it out in a human-readable power-of-2 format now documented in mersfmt.txt that can be read by most of the programs. Other arguments are checked to see if they look like checkpoint filenames; if they do, the files are opened and the exponent, FFT run length, and iteration count are read and printed (plus the rest of the first line if it's a human-readable file) to stdout. If they don't look like checkpoint filenames, a warning is printed and extract starts over with the next argument. All lines, except for a DATABASE file, are prefixed by the appropriate filename. As a small example of some of the features of fftll and extract, the following should "do the right thing" with a list of exponents contained in one of more mail messages in the file named "email" and pull the range of exponents from the DATABASE file in the current directory:
% fftll -i email -r 1234566 1234600Since fftll sorts the exponents uniquely (eliminating duplicates), it is even safe to repeat this command or for "email" to contain exponents in the range given; each exponent will still only be LL tested once.
% make DEFINE=-DTCPIPIf you have getrusage(), adding -DUSE_RUSAGE will print user and system CPU times along with the wall clock time given -t.
For SunOS 5.x (commonly mis-called Solaris, which technically applies to SunOS 4.x as well), see the top of the Makefile for some small editing you need to do before compiling. Or compile using:
% make DEFINE=-DSOLARISor:
% make DEFINE="-DSOLARIS -DTCPIP"if you also want TCPIP support.
For SGI's, setup() calls the SGI-specific function "schedctl(NDPRI, 0, NDPLOMIN)" to reduce the priority as low as possible, completely out of competition with normal programs. If similar things are present in other operating systems, please let me know.
On any computer, look for "OPT" to check the optimization, debugging, and profiling options to gcc or cc. In particular, I'm told that a couple of additional optimizer options will improve the speed by 20-30% under HPUX, different ones will give a 40% or so improvement for some AIX machines, and gcc on SGI's wants to know the exact CPU type; see the Makefile for details.
Also, "make TIME=time" will use the UNIX time program to run the tests to give you an idea of how long they take.
Please, as always, send any comments, questions, bug reports, bug fixes, code suggestions, etc. to me. Please include version numbers of the relevant files, at least of the file with main() in it or of this README.html file. See above for details on a simple way to email me the output from make.
Will Edgington
wedgingt@acm.org (permanent)
wedgingt@garlic.com
Personal web pages,
including a slowly evolving Mersenne page with links to
www.mersenne.org (George Woltman's), Luther Welsh's, Ernst
Mayer's, Paul Zimmerman's ECMNet, and others.
Version $Id: README.html,v 8.1 2007/06/23 22:33:35 wedgingt Exp $
mers package, tar'd and gzip'd
beta mers package, tar'd and gzip'd