20030127, 14:39  #1 
"Tony Gott"
Aug 2002
Yell, Shetland, UK
3×107 Posts 
Factoring with GLucas
Are there any good reasons why it is not possible to produce a program to do factoring with a Mac?
Or is just that LL has been considered more important, and that when time permits that factoring may be considered a possibility.... 
20030127, 20:51  #2 
Oct 2002
Lost in the hills of Iowa
2^{6}·7 Posts 
I suspect that LL is considered more important  trial factoring doesn't take very long, and there's some of us that run machined dedicated to doing nothing BUT trial factoring.
Per the "World Status Report" on Primenet, trial factoring assignments leading edge is up in the high 22,000,000 range while the leading edge for LL testing is in the mid 18,000,000 range. PLenty of "already been TFed, need LLed and DCed" factors around. 8) 
20030128, 15:42  #3 
"Tony Gott"
Aug 2002
Yell, Shetland, UK
3·107 Posts 
It's just that I have a number of Macs (5) working on the distributed.net OGR project at present, which I would like to have working on Prime95. I don't want to run DC or LL with them, and so wondered about trial factoring.

20030128, 21:29  #4 
Aug 2002
Termonfeckin, IE
ACB_{16} Posts 
I would also like to request an Mlucas type UNIX version of factoring. I have some slow sparcs that are useless for LL or DC but would be okay on factoring. Like bayanne I'm currently running OGR on them but would love to run factoring instead. :)

20030129, 15:02  #5 
Aug 2002
223 Posts 
Me three, I'd love to run some factoring on my Macs. Something with an interface like Prime95, where I don't have to set bounds for each exponent.
I wish I could code... :( :( :( 
20030130, 23:04  #6 
Oct 2002
Lost in the hills of Iowa
700_{8} Posts 
*chuckle*
That reminds me that I haven't gotten all my older K5 and P5class machines converted over from OGR to mprime yet. 9) 
20030203, 20:44  #7  
∂^{2}ω=0
Sep 2002
República de California
3×5^{3}×31 Posts 
Quote:
improving an early Mersenne factorer I wrote about 5 years ago (in Fortran!) Porting it to C, improving/debugging the smallprimes sieve, extending the factoring range beyond 64 bits, etc. I may have something for you to play with in the next couple of weeks, once I clean it up a bit more. But some caveats: The optimal platforms for factoring are those that allow one to efficiently compute the fulllength 128bit product of two unsigned 64bit integers. Only a few platforms have actual hardware support for this: the Alpha (where one uses a normal 64bit unsigned integer multiply, a.k.a. MULQ to get the lower 64 bits, and the special UMULH machine instruction to get the upper 64), the Itanium (where xma.hu plays the role of UMULH) and (surprise!) the humble x86. The reason the x86 can compute such a product quickly is that its nonstandard 64bit floatingpoint register mantissa allows one to use a floatingpoint multiply (which is pipelined and quite fast) to get the upper 64 bits of the product! The lower 64 still need to be gotten separately  one can simply use integer MUL for this. All 3 of the above platforms thus have excellent integer multiply support. (Actually, while all generations of Alpha have supported MULQ and UMULH, the 21064 didn't pipeline them and the 21164 only partially pipelined them, so these were merely decent at factoring. OTOH, on the 21264 and beyond, integer multiplies, while still having fairly large latency, are fully pipelined, so with proper code structuring, factoring absolutely screams.) The MIPS chips used in SGIs have a single machine instruction (DMULTU) to get BOTH halves of the 128bit product, but it needs around 14 cycles and is unpipelined (or at least it was the last time I had access to an SGI, which was an R10000), which makes it about as fast as the Alpha 21164, namely about half as fast as the x86 and about 1/6 as fast as the Alpha 21264. Mac and Sparc fans will no doubt be disppointed to hear that these CPUs (especially the Sparc) are not very good for factoring. The mac has only hohum integer multiply support (and the AltiVec unit on the G4 only handles products up to 32 bits wide, so is of no help in the present context) and the Sparc has absolutely dismal integer multiply support. Both of these are much better used doing LL testing, since OTOH they have good FPUs. Cheers, Ernst 

20030203, 23:35  #8 
Aug 2002
Termonfeckin, IE
3^{2}·307 Posts 
Thanks for the post Ernst. I can test the version out for you when you want but from your post it seems these old dogs will have to stay on OGR. They are simply too slow for even the slowest doublecheck.
But let us see what kinds of speeds we can get :) 
20030204, 03:13  #9 
Aug 2002
49_{10} Posts 
Ernst,
I'd certainly be up for helping out testing any new factoring code for the Alpha. Drop me an email if you need any help. Gareth 
20030204, 21:51  #10  
∂^{2}ω=0
Sep 2002
República de California
26551_{8} Posts 
OK, I cleaned up the code a bit and put the latest beta version
onto John Pierce's hogranch.com server (where I also keep my Mlucas ftp archive.) To get the sources, click on the following or type them into your browser's URL field: ftp://www.hogranch.com/pub/mayer/factor.c ftp://www.hogranch.com/pub/mayer/types.h (You can also do an anonymous ftp to get the files, if you prefer). The current code only has assembly code macros for fast 128bit integer products for Alpha  it should run correctly on other platforms, but will be relatively slow (especially on x86, Itanium and SGI, where we should be  and eventually will be  using the hardware instructions I mentioned in my previous posting for getting the upper half of a 128bit product.) Maximum factoring depth of the current version is 65 bits, i.e. 2^65. As a simple short selftest, let's factor M(M31) (that is, M2147483647) to a depth of 2^57: The input: factor 2147483647 57 The output (this was on a 1GHZ Alpha ev68): searching in the interval [1.000000e+00, 1.441152e+17] each of 16 (p mod 60) passes will consist of 2.0540 intervals of length 272272 max sieving prime = 224743 Time to set up sieve = 00:00:07.599 pass = 1 pass = 2 pass = 3 pass = 4 pass = 5 pass = 6 pass = 7 pass = 8 pass = 9 pass = 10 pass = 11 M2147483647 has a factor: 87054709261955183. Program: E2.8x Note that MM31 also has the smaller factor 295257526626031, but this one normally would be found on pass 12, and by default the program is set up to quit as soon as it finds a factor. To search exhaustively in the given range (i.e. to do all 16 factoring passes), near the top of the sourcefile set QUIT_WHEN_FACTOR_FOUND to 0 (1 is the default) and recompile. If the program finds a factor, just submit the line containing the factor to Primenet. (See http://hogranch.com/mayer/README.html#6 for simple instructions on how to manually submit results to Primenet, if you haven't done so before). If the program fails to find a factor, just submit the line that looks like the following: M15940453 no factor to 2^57. Program: E2.8x As an example of the 65bit factoring capability, try M15940453 to depth 2^65. This should find a factor on the first pass, so you can see if the program is working properly without excessive runtime. pass = 1 M15940453 has a factor: 21739844021752941079. Program: E2.8x (This needed about 11 minutes on the ev68  other platforms will need longer, often quite a bit longer.) Note that factoring to depth 2^65 takes significantly longer than to depth 2^64, since between 2^64 and 2^65 (where there is roughly the same number of factor candidates as between 1 and 2^64) we must use multiword integer arithmetic. Have fun, Ernst {Added a few hours later:} Quote:
I won't have time to fix the # directives today, so if you want to compile it, you'll have to either modify your local source appropriately or find an OSF/TruUnix v5 system to build on. Cheers, Ernst 

20030207, 18:25  #11  
Jan 2003
North Carolina
2·3·41 Posts 
Quote:
fwiw  I used the following compile command: $ cc/decc/lis/mach/nodebug/arch=host /opt=(inline=speed,level=5,tune=host) factor.c Thank you. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Glucas/Mlucas errors...  Xyzzy  Mlucas  19  20160507 18:29 
Glucas Source  nuggetprime  Software  13  20110114 19:51 
OS X Glucas build  rtharper  Software  3  20070613 23:28 
Glucas and GIMPS  optim  Software  6  20040405 21:32 
GLucas....  bayanne  Software  5  20030815 16:14 