On 21 Apr 00, at 16:24, [EMAIL PROTECTED] wrote:
> The reason is quite simple: Prime95 can do speedy
> factoring up to 64 bits by using the 64-bit mantissa of
> an x86 register float to store the trial factor (and
> various intermediate quantities modulo the trial factor)
> and doing integer multiply (which is normally quite slow
> on x86) by way of the FPU, which can pipeline the MULs.
> As soon as the trial factor size exceeds this 64-bit
> natural wordsize, one must go to a double-word
> representation, hence the factor-of-four-or-so slowdown.
Well, 96-bit integer operations on IA32 architecture are reasonably
natural. But, in general, you get less help from the FPU, & you need
1.5 ^ 2 times as many operations to do triple-precision arithmetic as
you do to do double-precision arithmetic. Plus, on the Intel, you
start running out of registers & need to write intermediate results
to memory, which costs extra cycles ...
>
> I'm in agreement with Brian Beesley on this issue:
> especially now that there's the capability to do P-1, I
> think sieving to > 64 bits will prove to be a waste of
> time, since we should be able to find nearly all the
> factors > 64 bits that sieving would turn up more
> cheaply using P-1.
No - we will only find _some_ of the factors > 64 bits, but P-1 is
running a lot quicker than trial factoring out at the large end. e.g.
less than one week to run P-1 on 33219281 (B1=145000, B2=1015000)
compared with about 3 weeks to trial factor to 69 bits. If we get
only one in four of them, that's cost effective. BTW P-1 will find
_some_ factors > 69 bits as well.
>
> That assumes that our priority is maximizing GIMPS
> throughput, rather than being able to say with certainty
> that such-and-such a number has no factors less than,
> e.g., sixty-eight bits.
Precisely.
>
> George, when do you expect sufficient data to be able
> to quantify the relative effectiveness of sieving vs.
> P-1 for these larger factor size ranges?
The statistical probabilities are reasonably well modelled in, e.g.,
Riesel "Prime Numbers & Computer Methods for Factorization" p156 ff.
Regards
Brian Beesley
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
