View Single Post
Old 2006-04-13, 17:50   #25
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

22×3×7×139 Posts
Default

Sorry about the nomenclatural confusion (Peter Montgomery and I have last names beginning with the same letter, after all), but that's a different Mfactor than the one being discussed in this thread. Peter's code is very fast on a small set of 64-bit hardware (Alpha and SGI MIPS) for which Peter wrote custom assembly code subroutines for key operations, but be aware that that code can go only up to 63 bits, and even less on some platforms (as you note). Should be fine for using on slower hardware though, since you're not going to want to be factoring very deep there, to begin with.

To reiterate: although the 2 codes are intended for the same purpose and use similary underlying algorithms, the implementations are completely independent, i.e.

M(ayer)factor != M(ontgomery)factor

As to the question about optimizations for 32-bit hardware, I have no plans for my mfactor code along these lines - just not worth the effort. Your same test example to 60 bits needs around a minute on decent 64-bit hardware running around 2GHz - even factoring in the clock speed difference that's nearly an order of magntiude faster in terms of per-cycle performance. My intention is not to discourage you from playing with this, but just to say that optimizing for 32-bit isn't where I'll be spending my own time.

Oh, here's the on-screen output from my run, just to illustrate that we're talking about different codes:

Code:
Mfactor build flags:
TRYQ = 4
THREE_OP128 = FALSE
NUM_SIEVING_PRIME = 100000
USE_FLOAT not defined
USE_FMADD not defined
FACTOR_STANDALONE = 1
FAC_DEBUG = 0
DBG_SIEVE not defined
NOBRANCH = 1
QUIT_WHEN_FACTOR_FOUND not defined
USE_65BIT not defined
USE_128x96 = 1
P2WORD not defined
P3WORD not defined
P4WORD not defined
Mfactor self-tests:
Testing 63-bit factors...
Testing 64-bit factors...
Testing 65-bit factors...
Testing 96-bit factors...
Factoring self-tests completed successfully.
INFO: No factoring savefile t77485997 found ... starting from scratch.
searching in the interval k=[0, 7449361920], i.e. q=[1.000000e+00, 1.154442e+18]
each of 16 (p mod 60) passes will consist of 456 intervals of length 272272
max sieving prime = 1299721
Time to set up sieve = 00:00:00.080
pass = 0....
pass = 1....
pass = 2....
pass = 3....
pass = 4....
pass = 5....
pass = 6....
pass = 7....
pass = 8....
pass = 9....
pass = 10....
pass = 11....
pass = 12....
pass = 13....
pass = 14....
pass = 15....M77485997 has a factor: 1152331426770601081. Program: E2.8x

M77485997 has 1 factors in [1.000000e+00, 1.154442e+18], passes 0-15
Performed 299545084 trial divides
checksum1 = 03A973A58DED4EBE
Clocks = 00:01:12.439
73.910u 0.013s 1:14.64 99.0%    0+0k 0+0io 17pf+0w

Last fiddled with by ewmayer on 2006-04-13 at 18:04
ewmayer is offline   Reply With Quote