Re: Mersenne: Are problems more likely in the last 1% of a 10,gigadigit LL?
-Original Message- From: Russel Brooks [EMAIL PROTECTED] How about a Prime95 option where it makes a daily backup for you, saved to a datestamp fileid? It could save them to a subdirectory with the exponent name. That would make it easy for the user to do a cleanup occasionally. There is already a feature which does effectively the same thing. Set 'InterimFiles=100' in prime.ini and it will write a save file in the working directory with a sequential extension every million iterations (or however often you set it). You must manually edit the prime.ini file, it's not a menu option. It's still a good idea to back up the savefile to some other medium every so often in case you lose your whole hard drive. Regards, Steve Harris _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: TMS XP-15 DSP card
This XP-15 ( http://www.superdsp.com/ ) bad boy DSP card looks pretty impressive, how useful would it be in searching for Mersenne primes? At $14,000 a pop, how would it compare to a farm of P4's? According to the Presentation pdf, it is 42 times as fast as a 1.4GHz P4 at a 1024K FFT! The killer thing is that the vector processing unit only handles 32 bit IEEE FP numbers... Laurent _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Are problems more likely in the last 1% of a 10,gigadigit LL?
Steve Harris wrote: There is already a feature which does effectively the same thing. Set 'InterimFiles=100' in prime.ini and it will write a save file in the working directory with a sequential extension every million iterations (or however often you set it). You must manually edit the prime.ini file, it's not a menu option. Maybe we could have another option, InterimKeep=x or such, that only the last x files are kept? Does Prime95 delete the interim files after successfully completing an exponent? If not, that might be enabled with another option, or by some logic that cleans up files in excess of InterimKeep even if they are of a previous exponent. This should keep disk space usage unter control while allowing a good chance of backtracking to a good residue in case of an error. Alex _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Are problems more likely in the last 1% of a 10,gigadigit LL?
On 14 Feb 2002, at 0:47, Russel Brooks wrote: George Woltman wrote: ***NOTE: There is an important lesson to be learned here. All testers of 10M digit numbers should backup their save files regularly!! You don't want a hardware glitch, disk crash, etc. cause you to loose months of work. How about a Prime95 option where it makes a daily backup for you, saved to a datestamp fileid? It could save them to a subdirectory with the exponent name. That would make it easy for the user to do a cleanup occasionally. Look up InterimFiles in undoc.txt This is a highly convenient method of getting backups. It's also easy enough to have a scheduled daily job move these checkpoint files to an archive directory throw away the oldest ones just leaving the last N. Well it's trivial on a linux system, I guess it's easy enough on a windoze system - especially if you already have a task scheduler running (e.g. because you installed Norton Antivirus). Regards Brian Beesley _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Are problems more likely in the last 1% of a 10 gigadigit LL?
On 13 Feb 2002, at 16:39, George Woltman wrote: ***NOTE: There is an important lesson to be learned here. All testers of 10M digit numbers should backup their save files regularly!! You don't want a hardware glitch, disk crash, etc. cause you to loose months of work. Same applies to LL tests, or even DC assignments, running on slow systems - these can take months too. Is there _ever_ an excuse for _not_ backing up recently created / modified files - which obviously includes Prime95/mprime save files? Regards Brian Beesley _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Are problems more likely in the last 1% of a 10,gigadigit LL?
Steve Harris wrote: From: Russel Brooks [EMAIL PROTECTED] How about a Prime95 option where it makes a daily backup for you, There is already a feature which does effectively the same thing. Set 'InterimFiles=100' in prime.ini and it will write a save file in the working directory with a sequential extension every million iterations (or however often you set it). You must manually edit the prime.ini file, it's not a menu option. Thanks Steve, I'll give it a try. Cheers... Russ _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Re: Are problems more likely in the last 1% of a 10,gigadigit LL?
On Thu, Feb 14, 2002 at 10:55:00PM +, Russel Brooks wrote: My save files are @1.5M in size. I could save quite a few before space was any concern (too me). Mine are @7M -- and I'm of those who prefer speed and sound level (two Ultra160 SCSI 1rpm 18.2GB disks, in RAID-1, both very quiet) over diskspace -- people are buying _cheap_ 80-100GB disks without even blinking nowadays. /* Steinar */ -- Homepage: http://www.sesse.net/ _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Re: Are problems more likely in the last 1% of a 10,gigadigit LL?
My home office has among other things a Compaq RAID array of 5 36GB drives and a few 18GB/9GB as well. MAN OH MAN that thing gets loud! If it weren't for all the other machines and the fan that blows straight on all of them, those drives would drive me nuts. As it is, everything else combined managed to be even louder. :) How well do the save files compress? Probably not much, being psuedo-random binary, but maybe a bit... in which case if you had an NTFS partition you could make your Prime directory compressed, or periodically zip up your old save files. Just a thought. Hey, I just tried and they do compress sort of okay... 71% of original size just using default zip settings. Using max compression doesn't improve anymore than the default. Curiously, using zip -1 (lowest compression) results in the smallest file by a few ten thousand bytes... due to smaller library I'm sure. I doubt George would be interested in working in a little simple zip routine when saving/reading save files? It might slow it down too much for some folks (although honestly, it takes a fraction of a second to zip using the lowest compression level), but maybe a nice option for those looking to save a bit of space when testing large exponents. Especially if you save interim files or have 2 saved files... the space savings would add up quickly. Aaron -Original Message- From: [EMAIL PROTECTED] [mailto:mersenne-invalid- [EMAIL PROTECTED]] On Behalf Of Steinar H. Gunderson Sent: Thursday, February 14, 2002 3:19 PM To: [EMAIL PROTECTED] Subject: Mersenne: Re: Are problems more likely in the last 1% of a 10,gigadigit LL? On Thu, Feb 14, 2002 at 10:55:00PM +, Russel Brooks wrote: My save files are @1.5M in size. I could save quite a few before space was any concern (too me). Mine are @7M -- and I'm of those who prefer speed and sound level (two Ultra160 SCSI 1rpm 18.2GB disks, in RAID-1, both very quiet) over diskspace -- people are buying _cheap_ 80-100GB disks without even blinking nowadays. /* Steinar */ -- Homepage: http://www.sesse.net/ _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Re: Are problems more likely in the last 1% of a 10,gigadigit LL?
On Thu, Feb 14, 2002 at 03:54:41PM -0800, Aaron Blosser wrote: I doubt George would be interested in working in a little simple zip routine when saving/reading save files? AFAIK, most of the space is due to the data being stored in floating-point format instead of integer. There was some talk about a common save format among Mersenne testing programs (an integer-based one was suggested), but I don't know how it went from there? /* Steinar */ -- Homepage: http://www.sesse.net/ _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: some thoughts on short-length convolutions
Recently, I've been playing around with the use of the Chinese Remainder Theorem (CRT) to effect efficient short-length convolution algorithms. For those of you not familiar with CRT, a brief tutorial: given two length-n vectors, A = [a_0, a_1, ... , a_(n-1)] and B = [b_0, b_1, ... , b_(n-1)], we can view each as the coefficients of a polynomial of degree n-1, i.e. the vector A represents the polynomial a0 + a1*x + ... + a_(n-1)*x^(n-1) . Cyclic convolution of the vectors A and B now corresponds to the polynomial product modulo P = x^n - 1 (i.e. every output term of the full double-length polynomial product of form c_(n+k)*x^(n+k) gets 'folded' in with the c_k*x^k term, since x^(n+k) == x^k modulo x^n - 1); acyclic convolution corresponds to polynomial product modulo Q = x^n + 1 (output terms folded similarly but with a sign change, e.g. c_k*x^k + ... + c_(n+k)*x^(n+k) becomes [c_k - c_(n+k)]*x^k ). If the polynomials P and Q can be factored over the rational numbers, then CRT allows us to reduce the input polynomials modulo the factors, compute a set of shorter-length subconvolutions (also modulo the factors) and then reconstruct the desired outputs of the convolutions modulo P and Q from the outputs of the shorter subconvolutions. If P and Q are highly composite, one can generally construct highly efficient convolution algorithms this way. As one specific case, I've been working on length-6 convolutions. For n=6, P and Q have the factorizations P = x^6-1 = (x^3-1)*(x^3+1) = (x-1)*(x+1)*(x^2-x+1)*(x^2+x+1), Q = x^6+1 = (x^2+1)*(x^4-x^2+1). Naive convolution of two length-6 real vectors needs 36 multiplies and 36 adds (same for cyclic and acyclic). The goal is to try to minimize the total operation count (add + multiply), with special emphasis on multiply (that means, given two alternatives with similar total opcount, we prefer the one with fewer multiplies.) Using CRT, and considering one of the input vectors to be fixed (for instance if we were doing many convolutions with different A inputs but all with the same B) the best I've managed to achieve so far is: Cyclic (mod P) convolution: 8 mul, 40 add Acyclic (mod Q) convolution: 15 mul, 41 add . (I can do the acyclic with as few as 12 mul, but only at the cost of ~10 more adds.) Does anyone know of algorithms more efficient than the above? * * * On a related note: for odd-length convolutions, we may not need to consider cyclic and acyclic separately. That's because we can usually (I suspect always, but haven't proven this yet) find a combination of sign changes on the input terms which converts one into the other, so we need only consider the cheaper of the two (which usually appears to be the cyclic, although why this should be so isn't obvious to me - perhaps x^n - 1 generally is smoother in terms of its factorization than is x^n + 1; for instance, x^n - 1 always has at least the factor x-1.) As an example, consider a length-3 acyclic convolution, with output coefficients as follows: x^0: a0.b0-a1.b2-a2.b1 x^1: a0.b1+a1.b0-a2.b2 x^2: a0.b2+a1.b1+a2.b0 If we flip the sign of a0, a2 and b1, we get a cyclic convolution out of this, just with the signs of the x^0 and x^2 outputs flipped. Interestingly, one of the 'bibles' of the field, by H. Nussbaumer, doesn't seem to be aware of this trick: Nussbaumer's length-3 cyclic convolution algorithm needs 4 mul, 11 add; his length-3 acyclic, OTOH, needs 5 mul and a whopping 20 add. This is insane, since as just shown we can very easily convert a length-3 acyclic into a length-3 cyclic. For even-length convolutions, this trick fails, since we can only flip an even number of signs this way, and a length-n acyclic has precisely n*(n-1)/2 minuses, which is always an odd number. However, there one can ask whether there exists a set of sign changes on the inputs which converts all but one of the signs to pluses. In that case, one could simply do a length-n cyclic convolution (assuming it's more efficient than its acyclic counterpart) on the sign-changed inputs, and then one additional multiply and two adds would suffice to fix the single residual minus-signed term. I need to see whether this can be done for the length-6 case: in that case the opcount would drop to a mere 9 multiplies and 42 adds. -Ernst
Re: Mersenne: Re: Are problems more likely in the last 1% of a 10,gigadigit LL?
- Original Message - From: Aaron Blosser [EMAIL PROTECTED] I doubt George would be interested in working in a little simple zip routine when saving/reading save files? It might slow it down too much for some folks (although honestly, it takes a fraction of a second to zip using the lowest compression level), but maybe a nice option for those looking to save a bit of space when testing large exponents. Especially if you save interim files or have 2 saved files... the space savings would add up quickly. My vote goes towards leaving Prime95 just the way it is... I prefer to have a program do one thing well rather than have it try to do everything under the sun... It is *so* easy to script these files to be compressed and backed up, even in Windows... I know very little about Windows scripting since I come from a Unix background, but I was able to whip a batch file together in less than 5 minutes that does the job for me... If I can do it anyone can... Maybe there is a market for an additional program to manage save files... Setiathome is notorious for having oodles of add-on programs to add functionality... I personally would like to see Prime95 go the other direction to a simpler CLI interface, like Mlucas, but I'm sure I'm in the minority... (BTW, Mlucas rules!) I do miss the old days when things were simpler (I bet George doesn't, though!) but time marches on... Mike (Xyzzy) _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Re: Trial Factoring: Back to the math
Rich Schroeppel [EMAIL PROTECTED] writes: The cost analysis of trial factoring by GCDs of 2^P-1 with the product of many small candidate divisors ignores an important optimization: All the candidates can be multiplied together mod 2^P-1, and ONLY ONE GCD NEEDS TO BE DONE. The major cost is probably the multiplications. Reduction mod 2^P-1 is particularly fast, but the same principle applies to random ultra-large targets. The products are probably best done by grouping pairs of trial divisors, then pairs of pairs, etc. The lowest levels can be chopped away if we use divisors in arithmetic progressions, which can be grouped by (say) eight at a time, and the products evaluated as an octic polynomial, which can be reduced to evaluating eight bignum additions per polynomial. The easiest way to develop the necessary finite difference parameters is to evaluate a few products directly, and calculate the differences. This dodges the nuisance of computing polynomial products and Stirling numbers. An excellent point, Rich. So now (assuming we do 1 p-bit input products) the single gcd is negligible. Generating each p-bit input product needs a product of 2 p/2-bit terms, which were generated from 4 p/4-bit terms, etc. With log2(p) levels in this recursion, generating each input vector needs O(p * ((log(p))^2) work, which is asymptotically the same as for the gcd, but with a much smaller constant buried in the O() (Modular multiply of each new input vector with the accumulated modular product needs just a single p-bit multiply and O(p * log(p)) work, and thus is negligible compared to generating the input vector from the individual factor candidates themselves). Thus the asymptotic opcount remains a factor of log(p) times as great as for the one-candidate (or a few candidates) at a time method, but there are benefits to this method which may make it attractive, especially on hardware where we can do gcd very fast (e.g. using floating-point), and when the size of the candidate factors exceeds the size that lends itself to fast hardware multiply. Are you aware of anyone who has implemented an efficient version of such a method? It would be nice to have some idea of its speed in practice before spending the significant programming time it would need to code a (say) Mersenne-optimized version of it for various hardware targets. -Ernst
