Brian J. Beesley wrote: >On 19 Oct 99, at 15:05, Ken Kriesel wrote: > > > Surely there are other programs. There must be various factoring efforts > > running on non-Intel processors under non-Microsoft operating systems. > >Indeed there are. There are several factoring programs in the mers >suite, also Ernst Mayer's Mfactor program. Um, That's Peter Montgomery's Mfactor program. I chose a similar name for my Lucas-Lehmer code since Peter and I plan to eventually merge the two, probably along with a p-1 factorer. >Actually there is a _big_ performance gain in using 64-bit processors >(instead of IA32 architecture) to trial factor up to 2^63 (or perhaps >2^64), particularly as Alpha, Sun Ultra etc. have (integer) divide >instructions which are more efficient than Intel's rather weak >effort. (39 clocks ...) Actually, none of the good factorers use integer divide. They all use (to check whether M(p) = 2^p-1 == 0 modulo a candidate factor q) left-to- right binary exponentiation (see Knuth, Vol. 2) and check whether 2^p == 1 (mod q). The modding is usually a Montgomery-style divisionless mod, which (for q up to around 64 bits) needs a 64x64==>128-bit integer multiply. Alpha and MIPS support such a multiply in hardware: Alpha uses MULQ for the lower 64 bits of the product, UMULH for the upper; MIPS uses DMULTU to get both halves. On the Pentium, owing to its 64-bit floating register mantissa, UMULH can be emulated via floating-point multiply. (IA-64 has an explicit machine instruction, xma.hu, which does just that.) On platforms like SPARC, one uses several 64x64==>64-bit integer multiplies to build a 128-bit product. >My guess is that someone really needs to make these existing >factoring programs easier to use in order to make them more popular. Yes, bundling a good factorer with an LL tester will help. >Factoring programs need savefiles rather less than LL testers; >perhaps they need their own format savefile, rather than trying to >"overload" the LL savefile format with complications it doesn't >really need. One needs to differentiate between sieve-based factoring (described above), which needs very few bytes in its savefile (exponent, desired factoring depth, current q) and p-1 or ecm factoring, which generates residues of the same size as the LL test. The latter wouldn't require many more bytes to be able to share the same savefile format as an LL test, e.g. assuming one uses 8-byte integers: integer contains ------- --------------------------- 0 exponent 1 task: 0 = sieveing | 1 = p-1, 2 = ecm | 3 = LL testing 2 desired depth | stage 1 depth | 0=first check, 1=DC 3 unused | stage 2 depth | if DC, -2 offset 4 current q | current prime | current iteration 5:6 unused | if 2, ecurve data | unused 7:7+(p/64) unused | p-1 or ecm residue| LL residue If we were planning to be able to share such files via a PrimeNet repository, we'd want to add a generous amount of space (say 1kB or more) to the header to summarize the residue history, i.e. who did what task, between what dates, to what depth, and on what machine. -Ernst _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
