Brian J. Beesley writes:
> If it really is that bad, then it's probably not worth doing. I once
> tested all the prime exponent Mersennes with exponents from about 10
> million thru about 21 million for factors smaller than 2^33 or so,
> using mersfacgmp on a Pentium 90MHz, in a couple of days.
The factoring program I used to trial-factor the 10 million plus
digit Mersenne numbers with exponents up to 36 million up to 2^40
takes only 20 _seconds_ to trial factor all 159,975 numbers to a
depth of 2^32 on a PII-350. That's including the disk I/O involved in
reading the exponents from a file & writing the results. Possible
factors were checked for +/-1 (mod 8) and screened for divisibility
by the smallest 10 primes before passing to the factoring routine,
which was called 1,267,515 times.
That does sound like it's faster, but let me go thru some numbers. I
don't recall exactly, but I'm sure my earlier run took less than 72
hours; 72 hours divided by 20 seconds is 72*3600/20 = 12960. Brian
stopped at 2^32 and I went to at least 2^33 for a factor of two;
12960/2 = 6480. His average exponent is about 34.5 million and mine
was less than half that at 15.5 million or so, meaning I checked about
twice as many potential factors; 6480/2 = 3240. My exponent range
included 665,365 primes; 6480*159,975/665,365 is about 1560. My time
also included the disk I/O, the primes program to generate the
exponents and, perhaps, another program running, but call that even;
/usr/games/primes is fast.:) A PII compared to a Pentium, I have no
numbers on, but 350 MHz vs. 90 MHz is not quite a factor of 4; 1560/4
= 390. Hm, I looked for all the factors, whereas it looks like the
data Brian sent me only has first factors, but I'm not sure what that
ratio would be; a (probably high) guess of 2 would leave a ratio of
195. I can't think of anything else, so it does look like Brian's
code is a _lot_ faster. On the other hand, the last time I compared
mersfacgmp to Prime95's factorer, the ratio wasn't this high (more
like 36 to 40, as I recall).
So, Brian, care to make your code available to the rest of us? :)
If my numbers are close, your code may even be faster than George's.
Have you compared it to George's? If so, how far off are my numbers
above? And what did I forget to account for? :)
One other thing that's different is that mersfacgmp sieves using more
than 10 primes; I guess I'd better run some timing tests with smaller
sieves, which has been on my list for a long time now. And compare it
with Prime95 again.
The slower your factoring routine is, the more sieving out of trial
factors helps the execution speed. Though there is always a cutoff
point - executing even just a Fermat test to base 2 (to determine
whether the trial factor is probably prime, with low confidence)
takes longer than the actual trial factoring (the code involved is
pretty well the same, but 2kp+1 > p).
Yes, I actually almost put a base-2 Fermat test in mersfac.c at one
point, before realizing that it was essentially the 'does it factor?'
check but longer, by exactly that ratio of 2kp+1 to p.
v19 has FFT sizes up to 2^22 (4 million), it should be capable of
handling exponents up to approx. 80 million. Which is more than
makes sense with current hardware.
Ah; then my info is out of date (not surprising; I haven't had time to
keep up for a while now).
Will
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
