Dear All: nigel was down for several days at the beginning of
November for a major OS upgrade, so I'm just catching up with
the last dowzen-or-so Mersenne digest. The mailing list server
also bounced me after trying and failing to deliver several
M-digest, so several postings I sent out in the last few weeks
also got bounced, without me receiving a notice to that effect.
So I'll repost and address some things I came across in the
last three weeks' digests, all in one smorgasboard message;
please pardon me if it seems a tad schizophrenic:
On 11/2, Peter Montgomery wrote:
>Let's assume that the FFT computation loses 12 bits
>of significance for FFT lengths in the range of interest.
>Now consider an LL test on Mp where p ~= 5 million:
>
> Mantissa Output Radix FFT
> bits bits length
>
> 53 41 2^11 524288 (Alpha)
> 64 52 2^16 327680 (Pentium)
> 110 98 2^40 131072 (Proposed)
While Peter's numbers are strictly speaking correct, the conclusions
are misleading. First off, he allows the Pentium to use a non-power-of-2
FFT length, but not the Alpha. In fact, with 53 mantissa bits, even using
a power-of-two length of 2^18 = 262144 (more familiarly referred to as
"256K" by GIMPSers), one can test exponents to around 5.2 million.
Second, Prime95 gains the benefit of x86 80-bit floating operands only
while data are in registers; all floating loads and stores from/to
memory are on 64-bit IEEE floating data. As George explained to me
a long time ago, this is because 80-bit loads and stores, while available
on the x86, take twice as long as 64-bit loads and stores, and since
using 8-bit operands throughout will cut the FFT length by less than
a factor of 2, it's not worth doing this way.
Compared to strict 64-bit reals, the extra accuracy gotten by 80-bits-
only-while-in-registers arithmetic is marginal: for N=256K, Prime95 can
test exponents up to 5.26 million, only around 1% larger than a true
64-bit program can do.
* * *
{originally attempted to send on 11/17:}
Subject: Re: the Halloween memoranda
A tad off-topic, but after all, GIMPS is also in many ways
an open-source software (OSS) project:
http://www.opensource.org/halloween.html
And, of course, author Eric Raymond is a GIMPSer.
Keep up the good work, Eric!
* * *
On 11/2, George Woltman wrote:
>I'd like to challenge the readers to produce the best algorithm
>and/or code for finding factors of Mersenne numbers greater than 64-bits.
On reading this, I apparently had the same thought as Conrad Curry:
"Such an algorithm already exists - it's called the Pollard p-1 method."
In reply, I propose a
COUNTERCHALLENGE: using reasonable computational cost estimates and known
statistics regarding the the size distribution of factors, convince us that
sieving is a more efficient way of finding factors > 64 bits than p-1,
for exponents of current interest (say, > 1 million.)
With regard to the p-1 cost estimate: assume that the stage 1 uses a
precomputed product of small prime powers (i.e. a left-to-right binary
exponentiation, costing the same as one LL test iteration per product
bit) and that stage 2 is based on a fast polynomial evaluation, with
a circular convolution length yielding a reasonable memory requirement,
say no more than 256MB of RAM. Assume the cost of doing the GCDs is
trivial.
I think you'll see that the only advantage of sieving is certainty:
if we sieve to B bits without finding a factor we can confidently say
that there are no factors < 2^B. What we can say with p-1 (or ECM, for
that matter) is probabilistic. But if I can find 90% of factors < 2^B
using p-1 and doing half the work of sieving to do so, that's a trade
I'll make any day.
Cheers,
Ernst
