> 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? :)
I put a development version on my anon ftp server about three days
ago. ftp://lettuce.edsc.ulst.ac.uk/gimps/DecaMega/factor95.c
This is the 95-bit-capable code I gave George about early April. It
isn't fully optimised, it needs to be turned into MASM source,
properly aligned & have removed the horrendous & slow kludge used to
work around a serious MS VC++ inline assembler bug.
The 63-bit-capable code I'm using is simply hacked down from this in
an obvious way. I didn't even bother to look for any more
optimization which would be possible as a result of the various
temporary results being one 32-bit word shorter.
The sieving I'm messing about with is embedded in the "engine" that
generates possible factors, rather than the factoring code itself.
>
> 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? :)
Well, against my code is that it stops as soon as it finds one factor
(strictly in order, so it should always find the smallest). Quite
frequently one finds that the first factor one tries works
(if p = 3 mod 4 and 2p+1 is prime, this is _guaranteed_, but
obviously isn't worth coding as a special case). Also my program
reads a list of exponents from a file rather than generating them,
however I don't think there's much speed penalty involved in this
either way. My code is written so that various multiple-precision
operations will "early out" is the high word is zero, this happens a
lot when the factors are < 2^32, mind you I could write a one-stage
version for factors < 2^31 which would be faster still.
The code I'm using to output factors is inefficient, but I don't
think that's a major factor. The PII-350 timings are actually for one
thread on a dual PII-350 system, there were two instances of Prime95
running LL tests in the background. For this reason I think a fairer
PII-350/P90 ratio would be 4.5 rather than the usual 5. (4 is
definitely low...)
Will change the "engine" to keep going to 2^33 after finding the
first factor & report the results from that. Meanwhile, ran again to
2^40 with sieveing of first 10 primes & got 266,072,661 calls in 3530
secs. Bearing in mind sieving overheads etc. it looks like I'm
getting better than 10 uS per pass of the factoring routine. I don't
know how this relates to Prime95's internal reporting, the same
system gets "0.036 sec per iteration" factoring (using the routine
that works to 2^62) running Prime95, but I don't know what that's
measuring.
There's definitely a few percent to be wrung out of my code, when I
get a chance.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
