>>We will of course have to check factors considerably further than
>>we are doing on our current exponent range (due to the increased
>>LL iteration time.)
Yup. And don't forget that the larger the exponent, the fewer the
possible factors in a given range (e.g., from 0 to 2^40 or 0 to 2^63).
> Yes - on the principle that it's worthwhile to spend 5% to 10% of
> the LL testing time attemptimg to find at least one factor before
> we run a LL test, the pre-factoring should be run for 3 or 4
> weeks per exponent first (assuming PIII-500 class power). At a
> rough guess, that's up to 2^66 or 2^67, but we don't have any
> benchmarks yet.
Oh, but we do. George's factoring is not the only one out there. In
particular, I maintain, as part of the mers package, factoring
programs that use the freeLIP and gmp libraries to try arbitrarily
large factors. Since George's program uses the Intel CPU's 64 bit
mantissa floating point operations, it is limited to checking possible
factors up to about 2^63.
> Of course, trial factoring to 2^40 is very quick - I spent only about
> 2 (PII-350) CPU hours spread over all 159,975 candidate exponents in
> the range I selected. But that's enough to eliminate a third of them.
In fact, there was a problem with a particular version of George's
factorer such that it didn't always find factors _smaller_ than 2^32
or so. And this was discovered only when GIMPS was expanding to the
current high exponent of 20.5 million or so. So I ran mersfacgmp to
find all the factors less than about 2^33 for all prime exponents up
to about 21.5 million. It took a couple of days on my (then) 90MHz
Pentium.
Maybe we should start checking factors in (the range of prime
numbers used in your database) in 2^40 segments, between you and me
(and others?).
Others, including myself, have already done parts of this. The data
that I have collected from them all is significantly larger than the
web-accessible disk space I have. But feel free to send me more
factoring data and I'll send, in suitably sized chunks, whatever parts
of the data that I have that you want.
When you send me the source, I'll try to port it GCC (then maybe we
can make something useful out of it :-)
No need; mersfacgmp already supports GCC, since my primary machine is
RedHat Linux v5.2. But see below for reasons that another program,
independently developed, can be very useful.
What type of sieving did you do (if any) ?
Mersfacgmp does essentially the same sieving as George Woltman's code,
though in a different order so as to test possible factors in order.
Mersfacgmp tests possible factors in order so that the "checkpoint"
file is just the largest number attempted so far. George's factoring
checkpoint files are in binary and include the sieving pass number
(out of 16). George's code is organized that way for the speed
advantage.
Did you write the modpow routine, or was it included with some math
header?
George got the basic algorithm from Knuth, I believe, and pointed it
out to me not long after GIMPS started. It sped up my pre-GIMPS
factoring program by something over a factor of three, as I recall.
How much room for improvment in speed would you say is there in the
source?
Quite a bit, probably, but the primary loop is rather small and most
of the math is done by libgmp (or freeLIP in the case of mersfaclip).
I have limited computational resources, a PII233, a P100, but
because of my work, I have practically unlimited resources in the
486 department they could finish a 2^40 section in about a day or
so.
As mentioned above, feel free to send me any data that you want; I've
been saving this sort of data for a lot longer than GIMPS. E.g., I
have some pre-GIMPS data for certain exponents up to about 240
million. The results file, containing all the data that I have, is
now over 90 MB; the list of exponents alone is over 14 MB.
If nothing else, sending me your data will let me compare it to what I
already have for exponents and factoring ranges in commonn and check
to see if any of the programs have bugs. This sort of comparison has
found bugs in both the mers package programs and in George's programs
several times and is a big reason for doing double checking with
distinct programs on distinct hardware.
Will
http://www.garlic.com/~wedgingt/mersenne.html Brief web page w/ links
mers.tgz Mers package, tar'd, gzip'd
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
