Mersenne Digest Friday, October 12 2001 Volume 01 : Number 891 ---------------------------------------------------------------------- Date: Tue, 09 Oct 2001 15:09:08 -0700 From: "Robert Braunwart" Subject: Mersenne: Re: Mersenne Digest V1 #889 >From: softmade@mailtag.com >To: rbraunwa@hotmail.com >Subject: Mersenne: Re: Mersenne Digest V1 #889 >Date: Tue, 09 Oct 2001 00:43:58 -0500 > >Speaking of calculating, > > >What do you think the best is the best approach for this problem? > >Calculate the n th. (any number) decimal digit of the expansion of a >regular rational 1/n (not necessarily the same n), with n a prime number, >without calculating the preceding digits. > >Please give a example using substitution into formula. > >This is not a test question for a class. It is part of my personal number >theory studies. > > >Thanks >Dan > >------------------------------------------------------------------------- > >-> I second this suggestion. I would be very interested in seeing a >calculator >-> page, or at least a detailed formula. I neglected to keep track of the >-> individual credit for my earliest numbers, and now I am curious. These >go >-> back to v. 15, I believe. >-> >-> --Bob Braunwart >-> >-> >-> >Date: Fri, 5 Oct 2001 17:36:14 -0400 >-> >From: "Digital Concepts" >-> >Subject: Mersenne: What are the PrimeNet formulas for calculating LL >and >-> >Factoring credit? >-> > >-> >This is a multi-part message in MIME format. >-> > >-> >- ------=_NextPart_000_02A6_01C14DC4.3B0A3CE0 >-> >Content-Type: text/plain; >-> > charset="iso-8859-1" >-> >Content-Transfer-Encoding: quoted-printable >-> > >-> >First a short memory recollection... A few months back I wrote in = >-> >explaining that I wanted to compare contributions (work done in CPU = >-> >years) between clients running under a team umbrella. I was privately >= >-> >replied to and referred to the benchmark page as the way they would do >= >-> >it. More recently, someone asked the same thing and I believe George = >-> >referred them to the status page. I've done it both ways and they come >= >-> >out very close, but I assume the status page is the one that is going >to = >-> >be kept current as new releases and timings come along, and the one = >-> >George uses. >-> > >-> >Either time though, it was mentioned how difficult it was to calculate >= >-> >factoring years, and I see why. Yet there must be a formula. Who here >= >-> >is a PrimeNet rep? >-> > >-> >With this info, maybe someone might volunteer a calculator page, where >= >-> >someone could enter an exponent and get the LL value, and optionally = >-> >whatever criteria is stored in factoring messages to PrimeNet, to = >-> >determine the Factoring value. >-> > >-> >Thanks for you consideration, >-> >Carleton Garrison LL#164 F#291 G#253 www.teamprimerib.com >-> > >-> >-> >-> _________________________________________________________________ >-> Get your FREE download of MSN Explorer at >http://explorer.msn.com/intl.asp >-> >-> >_________________________________________________________________________ >-> Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm >-> Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers > _________________________________________________________________ Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 9 Oct 2001 18:34:20 -0400 (EDT) From: Jason Stratos Papadopoulos Subject: Re: Mersenne: Re: Mersenne Digest V1 #889 > >Speaking of calculating, > > > > > >What do you think the best is the best approach for this problem? > > > >Calculate the n th. (any number) decimal digit of the expansion of a > >regular rational 1/n (not necessarily the same n), with n a prime number, > >without calculating the preceding digits. > > > >Please give a example using substitution into formula. Look up the Bailey-Borwein-Plouffe formula for extracting digits of pi, and use similar methods. It should boil down to an exponentiation and a long divide. jasonp _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 9 Oct 2001 23:39:33 GMT From: Peter-Lawrence.Montgomery@cwi.nl Subject: Re: Mersenne: Extracting digit of real number To: mersenne@base.com Subject: Mersenne: n-th decimal digit in real number Date: Tue, 09 Oct 2001 15:09:08 -0700 Mime-Version: 1.0 Content-Type: text/plain; format=flowed Message-ID: X-OriginalArrivalTime: 09 Oct 2001 22:09:08.0593 (UTC) FILETIME=[048F1610:01C1510F] Sender: mersenne-invalid-reply-address@base.com Precedence: bulk Status: R "Robert Braunwart" wrote >What do you think the best is the best approach for this problem? > >Calculate the n th. (any number) decimal digit of the expansion of a >regular rational 1/n (not necessarily the same n), with n a prime number, >without calculating the preceding digits. > Let x be a positive real number. If d is the n-th decimal digit of x, then d is an integer 0 <= d <= 9 FLOOR(10^n * x) == d (mod 10) For example, if x = sqrt(2) = 1.4142135 ..., and n = 4, then FLOOR(10^4 * x) = FLOOR(14142.135 ...) = 14142. Reduce this modulo 10, to find the fourth decimal digit (to the right of the decimal point) is a 2. >Please give a example using substitution into formula. If r is a rational number, say r = r1/r2, with r1, r2 positive integers, then FLOOR(10^n * r) mod 10 = FLOOR(10*(r1*10^(n-1) mod r2)/r2) For example, to get the fourth decimal digit of 3/7, evaluate 3 * 10^3 mod 7 = 3000 mod 7 = 4. FLOOR(10*4/7) = FLOOR(40/7) gives 5, which agrees with 3/7 = .428571 ... _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 10 Oct 2001 12:42:04 EDT From: EWMAYER@aol.com Subject: Mersenne: Re: MLucas benchmarks Tony Gott wrote: > How does the new version 2.8c compare with Prime95 beta-version 21.4 as far > as benchmarks is concerned? I can't speak to Glucas' performance on the Itanium until Guillermo sends me the precise numbers, but I suspect it will be somewhat faster even than the Prime95 code for the P4, since the Itanium has better floating- point functionality: whereas the P4 (and most of the high-end RISC platforms) can do at most one floating add and one floating multiply per cycle, the Itanium can do any two of the following per cycle: floating add floating mul fused floating mul/add . That means that under ideal circumstances (equal number of fadd and fmul, no data dependencies to worry about) the Itanium could do twice as much floating--point arithmetic per cycle as the P4 or (say) the Alpha 21264. FFT code is of course far from ideal in these terms, as it tends to be dominated by floating adds, but simply the ability to do two of these per cycle could speed things up by 50% or more over a CPU which can do just one add per cycle. As for the Alpha (which is now apparently the second-fastest RISC platform for Mersenne testing), my timings of the soon-to-be-released Mlucas 2.7c and Guillermo's timings of Mlucas 2.8 indicate that on the 21264 the per-cycle performance is similar to Prime95 on the P4; on the older 21164, the performance is close to Prime95 on the P3. In a multiprocessor setup one will get significantly better performance that for Prime95 running on a multi-CPU setup, since the RISCs have much better bus bandwidth - I see no slowdown even when running an LL tests on each CPU of a quad-processor Alpha; Prime95 would slow down by 20-30% under similar circumstances. > It would be just fantastic if the full power of the Altivec in Apple G4 > could be utilised as it has been in the RC5 distributed project. Is this > ever likely? Indeed it would be wonderful, but don't get you hopes up too high - as Jason Papadopoulos mentioned, the AltiVec is designed for multimedia performance, which leads to rather different functionality than one needs for large-integer work. I still hold out hope that a mixed floating-integer approach (doing a floating FFT side-by- side with a modular integer transform, then combining the results to allow for more significant bits per convolution output digit) may someday allow both the PowerPC core and Altivec unit to work together to speed LL testing, but it would require some very intricate coding even if it did prove feasible. And of course, it remains to be seen whether one can achieve any gains this way even on processors which have truly awesome integer capabilities, such as the Alpha 21264 and the Itanium - besides the fact that the modular transform needs about twice as many operations as the floating one (one needs to do a lot of double-width multiplies and modding of intermediate results), there are highly nontrivial algorithmic issues still to be solved. As an example of the latter, consider the case where one does a floating FFT side-by-side with a modular transform over the gaussian (complex) integers modulo some small Mersenne prime (technically one is operating over the Galois field GF(q^2), where q is a Mersenne prime.) These fileds have a lot of very nice properties, such as the fact that a modular transform looks very much like the floating FFT, and arithmetic modulo a Mersenne prime can be done very efficiently via simple masks, shifts and adds. For power-of-two transform lengths i've actually implemented such a scheme and got it working - using GF(M61^2) for the modular math I was able to get roughly 50 bits per input digit, compared to around 19 for pure floating-point code. But the compiler I was using did a poor job interleaving floating and integer operations, and I suspect that this may be a problem generally, i.e. that most compilers are optimized for code dominated by either floats or ints, but not both. But let's assume we either find a compiler that is really good at keeping both the FPU and integer units of our target CPU busy. Next problem: for non-power-of-two runlengths, the outputs of the forward integer transform will occur in a fundamentally different ordering than for the FFT, i.e. this wonderful idea of the modular transform mirroring the floating FFT is out the window when it comes to the dyadic-squaring phase between the forward and inverse transforms. Assuming that this can be overcome, next problem: the normalization and carry propagation stage is extremely difficult to implement efficiently for such a scheme, since one can't simply round each floating output; rather, one first has to use the corresponding modular output to correct the bottom log2(q)/2 bits of the floating output, then do the normalization, then get the normalized floating modular data back from that, and so forth. It won't do to spend 30% of one's time in the carry phase if that wipes out any gains one gets from the mixed-transform approach. So there's lots to be done yet even to evaluate whether such a scheme is feasible (in the sense that it can be made to run fast) on *any* platform, to say nothing of one whose integer capabilities were devised with 8,16 and 32-bit multimedia applications in mind. I remain optimistic, but I've seen first-hand the coding and algorithmic work that is required, and it's no small amount. If it's any consolation, the pure floating-point codes non-x86 clients can use have improved by more than a factor of 2 in speed in the past 2 years, so it's not like the conventional FFT-based approach has stalled out in terms of efficiency. Cheers, - -Ernst _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 10 Oct 2001 13:28:51 EDT From: EWMAYER@aol.com Subject: Mersenne: Re: MLucas benchmarks I wrote: > rather, one first has to use the corresponding modular > output to correct the bottom log2(q)/2 bits of the > floating output If one has an approximate floating output and the same number modulo q (exactly) in hand, the one can obviously use the latter to correct up to the log2(q) least- significant bits of the former, i.e. there should be no divide by 2 in there. What I intended to say was that this allows one to use up to log2(q)/2 more bits per INPUT to the convolution (since outputs scale quadratically with input word size). For example, if one does the modular transform modulo the Mersenne prime M61, then floating outputs may be in error by as much as 2^60 (we lose one bit since floating outputs are signed) and still be exactly reconstructed, and this allows us to use roughly 30 more bits per input word. - -Ernst _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 10 Oct 2001 13:28:59 EDT From: EWMAYER@aol.com Subject: Mersenne: Re: MLucas benchmarks I also wrote: > Next problem: > for non-power-of-two runlengths, the outputs of the > forward integer transform will occur in a fundamentally > different ordering than for the FFT, i.e. this wonderful > idea of the modular transform mirroring the floating FFT > is out the window when it comes to the dyadic-squaring > phase between the forward and inverse transforms. At this point, the astute reader will be saying to him- or-herself, "Wait a minute: since we're taking about a dyadic (pointwise) complex squring here, who cares that the complex and modular data are arranged in different patterns? Just square 'em and let the inverse transform do the unscrambling for you." Sadly, things aren't quite so simple. Consider (say) a length N = 6 DFT of a strictly real input vector. The outputs will occur in the following pattern: X0 X1 + i*Y1 X2 + i*Y2 X3 X2 - i*Y2 X1 - i*Y1 Note the symmetry: X(N-j) = ~X(j), where ~ denotes complex conjugation. This symmetry allows us to cut the transform length in half, and in fact all the fast FFT-based large-integer codes use some variant of this strategy, be it implicitly in the structure of a real-input FFT (Prime95 uses such a method) or explicitly by doing a complex-input FFT and then combining outputs with index pairs (j, N-j) appropriately prior to doing the dyadic squaring (Mlucas uses this latter approach). In either case, one is making use in some fashion of the (j, N-j) symmetry of the outputs of a complex DFT applied to real input data, and this symmetry no longer holds when one is doing a modular transform over the field GF(q^2) and the runlength is not a power of 2. - -Ernst _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 9 Oct 2001 18:34:20 -0400 (EDT) From: Jason Stratos Papadopoulos Subject: Re: Mersenne: Re: Mersenne Digest V1 #889 > >Speaking of calculating, > > > > > >What do you think the best is the best approach for this problem? > > > >Calculate the n th. (any number) decimal digit of the expansion of a > >regular rational 1/n (not necessarily the same n), with n a prime number, > >without calculating the preceding digits. > > > >Please give a example using substitution into formula. Look up the Bailey-Borwein-Plouffe formula for extracting digits of pi, and use similar methods. It should boil down to an exponentiation and a long divide. jasonp _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 12 Oct 2001 11:20:18 -0400 From: "Thern, Royal E" Subject: Mersenne: Assigned numbers that were already done I recently received an exponent, ostensibly for first-time LL testing, that seemed rather low (in the 11,000,000's). I looked at cleared.txt, and this had indeed been already done, by Account ID = XXX (I'll keep the actual name and exponent anonymous for privacy). Then I looked for other exponents cleared by XXX, looked them up in status.txt, and see that most of them have also been reassigned recently. Is something going on? Is there a reason why 'cleared' exponents are reassigned, or is there some error here? Is there some suspicion that the first tests were wrong? (I'll tell you the exponent and XXX if you ask, but a little detective work would also reveal it.) - -Roy _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ End of Mersenne Digest V1 #891 ******************************