Factoring with GLucas

[bayanne]

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....

[QuintLeo]

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-)

[bayanne]

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.

[garo]

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. :)

[Paulie]

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... :( :( :(

[QuintLeo]

*chuckle*

That reminds me that I haven't gotten all my older K5 and P5-class machines converted over from OGR to mprime yet.

9-)

[ewmayer]

Originally Posted by garo

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. :)

Funny you should ask...I've recently been working on cleaning up and
improving an early Mersenne factorer I wrote about 5 years ago (in Fortran!)
Porting it to C, improving/debugging the small-primes 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 full-length 128-bit product of two unsigned 64-bit integers.
Only a few platforms have actual hardware support for this: the Alpha
(where one uses a normal 64-bit 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 64-bit floating-point register
mantissa allows one to use a floating-point 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 128-bit 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
ho-hum 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

[garo]

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 :)

[gowen72]

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

[ewmayer]

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 128-bit
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 128-bit product.)

Maximum factoring depth of the current version is 65 bits, i.e. 2^65.

As a simple short self-test, 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 65-bit 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 multi-word integer arithmetic.

Have fun,
-Ernst

{Added a few hours later:}

Originally Posted by gowen72

When trying to compile it under OSF v4 I noticed that the preprocessor doesn't like your coding style!

The C preprocessor that comes with OSF v4 insists that the # for preprocessor directives are put
in column 1. Although you can have whitespaces after the #, to indent the actual directive.

Thanks for the note.

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

[nomadicus]

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.)

VMS checks out and the run times as consistent with your processor vs. the one I have.
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.