Gerhard Niklasch on Sat, 29 Aug 1998 19:55:54 +0200 (MET DST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: [PARI] MPQS error message: complement |
In response to Philippe Elbaz-Vincent's observations about MPQS's file descriptor leaks in version 2.0.11: > Is it possible to avoid simply this problem ? Option 1: point your favourite browser at <url:http://pari.home.ml.org/relv/2.0.11.beta/> (or, if the Monolith WWW redirector isn't working, directly at <url:http://hasse.mathematik.tu-muenchen.de/ntsw/pari/relv/2.0.11.beta/>), scroll down to near the end of the page, and fetch and apply the `MPQS file descriptor leak' patch from 3 August. Option 2: this will be fixed anyway (somewhat differently) in version 2.0.12, which I expect will be out soon. Version 2.0.11 had a bug which meant that almost every invocation of the MPQS factoring engine failed to close one of the files it had opened. On most operating systems, the effect will be that the gp process runs out of usable file descriptors after a while (the maximum available number of f.d.s per process is usually about 64 or 256, depending on operating system and default limit/ulimit settings; try `ulimit -a' if you are using a Bourne-like shell or ksh, or `limit' if you are using csh/tcsh, to find out your settings). Some background information may be useful at this point, since most of the documentation of what the LiDIA/PARI MPQS implementation does can only be found in commentary in the src/modules/mpqs.c file itself at present. MPQS, after initializing a number of things, spends most of its time accumulating relations of the form Y^2 congruent X (mod kN) where N is the number to be factored, k is a (small) multiplier chosen so as to get a good distribution of quadratic residues, fixed once and for all (depending on N) for every MPQS run, Y is an integer of ap- proximate size sqrt(kN), and X is an integer which is either completely factored over a precomputed `factor base' of small primes, or is the product of a moderately large number (a `large prime', although it isn't always prime) by a fully-factored-over-the-FB number. In the first case, we speak of a `Full Relation', in the second, of a `Large Prime Relation.' Two LP Relations containing the same `large prime' can be combined to produce a Full Relation. The Full Relations will at the end be used to compute congruences of the form Y^2 congruent X^2 (mod kN) (spanning the so-called kernel [of a linear map over GF(2)]), and any such congruence for which X+Y and X-Y aren't both divisible by N will produce a non-trivial factor of N. When N is large, many thousand Full Relations and several ten thousand LP Relations must be produced before we can hope to have a nontrivial kernel, so we need to save them on disk rather than holding them in memory. (For N as small as 25 or 30 digits, we still use files, but with any luck these files will never really be written to disk -- the factorization will be completed before any buffers are written out, provided you're under a Unix-like OS.) Up to six temporary files will be used side by side. Under Unix-like systems, they have names like /var/tmp/LPTMP.500.7267 where the directory is governed by environment variables and built- in defaults, the first number is the numerical user id, and the second number is the PID of the gp process (this avoids clashes when several users are running gp processes on the same machine). Under DOS, the names are simpler. The first name component is one of FNEW: new Full Relations, being appended as they are found. FREL: sorted Full Relations with duplicates eliminated. LPNEW: new LP Relations, being appended as they are found. LPREL: sorted LP Relations with duplicates eliminated and combinable relations combined. LPTMP: temporary files used whilst merging FNEW into FREL or LPNEW into LPREL (after sorting the new files in place). COMB: groups of combinable LP Relations found whilst merging LPNEW into LPREL; they will be processed into Full Relations for appending to FNEW shortly afterwards. If you turn on a very high level of debugging diagnostics, say gp > \g6 (or equivalently by calling the gp function gp > default(debug,6) ), MPQS will flood you with a vast amount of progress information, statistics, and news about files being opened, closed, renamed, removed, etc. (Level 7 is even more verbose, level 5 is probably the largest widely useful level, but doesn't yet show file access information.) These files are plain ordinary readable text files, albeit with poten- tially very long lines (100 or 200 characters per line). During a lengthy MPQS factorization, you can inspect e.g. the FREL and LPREL files, or monitor FNEW/LPNEW with tail -f . (Note however that output to these files is buffered and thus happens in bursts, and that merging works by writing a new LPTMP file and renaming that to FREL or LPREL, as the case may be. Also, depending on your operating system, the tail -f command may run into problems when FNEW and LPNEW are truncated to zero length after each sorting/merging phase.) Hope this answers a few questions, Gerhard