Mersenne Digest Tuesday, June 15 1999 Volume 01 : Number 579
----------------------------------------------------------------------
Date: Tue, 15 Jun 1999 00:08:58 +0200
From: "Lars Lindley" <[EMAIL PROTECTED]>
Subject: Mersenne: NTPrime and proth
Hi, all.
I've been sitting idly reading all the annoying mails in the poaching-thread.
I must say tat the list was far mor enjoyable before that thread came up.
I think George and Scott is doing a remarkable job in this whole project and I hope
that the poaching thread will cool down now after Aarons last mail with subject "to
poach or not..."
Leave the handling of exponents to George and Scott, please!?!
But that is not why I'm writing...
I wonder if there is any way to tell winNT to give NTprime six times as much cpu-time
as proth and still have them both to be idle-priority so they dont disturb my other
activities??
I can't figure out a way, but I'm no Guru like many people on this list.
I also wonder if there is anyway to tell NT to give a certain process a certain
percentage of cpu-time no matter what the system is doing otherwise.
Ex. 33% of cpu-power regardless if the load on the system is otherwise 0% or 100%
Thanx for a nice project, George and Scott!
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 14 Jun 1999 15:21:52 -0700
From: Will Edgington <[EMAIL PROTECTED]>
Subject: Mersenne: Re: factoring 10^7 digits (was LL and factoring & quitting)
>>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
------------------------------
Date: Mon, 14 Jun 1999 15:31:06 -0700
From: Will Edgington <[EMAIL PROTECTED]>
Subject: Mersenne: Re: Mersenne Digest V1 #576
Daren Scot Wilson writes:
I've switched from Linux to BeOS - entirely, not even dual-booting
both. Same hardware as before - PII 400 MHz. BeOS is POSIX
compatible, has TCP/IP, but the file system is offbeat, and from
what I hear most linux software needs a little bit of tweaking to
compile for Be.
Is there any Mersenne testing software that can run on BeOS? Or
other interesting math crunching software?
See the mers package code that I maintain. It is ANSI C source code
plus a shell script. There are also pointers to other programs,
notably Ernst Mayer's Fortran90 LL tester, on my mersenne.html page.
Will
http://www.garlic.com/~wedgingt/mersenne.html
mers.tgz
mers.tar.gz
Two different names for the mers source tar file since some web
browsers don't realize that '.tgz' is binary and some operating
systems don't like two dots in file names.
If you need a zip or shar file or other format, just ask.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 14 Jun 1999 15:26:16 -0700 (PDT)
From: Ashton Vaz <[EMAIL PROTECTED]>
Subject: Mersenne: Poaching
Hi all,
I'll call a truce. I'm sure it's clear to George and Scott where
most people's opinions lie on the issue of poaching. I'll leave the
discussion where it's at since we've seem to have come to a consensus.
Summarizng:
1) I do see and agree with (as do the other members of the
anti-poaching camp) Jeremy's and Aaron's concerns regarding regarding
exponent hoarding. What annoyed most of the anti-poachers is that the
poachers decided to do it unofficially even though George has exponent
reassignment in place.
A suggestion to prevent exponent hoarding: For v19, if the
machine seems to be taking too much time for an exponent, let it warn
the user (and email her/him) that she/he could loose any rights to the
assignment. This would discourage hoarders.
2) Lots of statements were tongue-in-cheek, (I picked them up
Jeremy, just decided to not respond to them! :) ) and I hope no one
has taken any of the comments *too* seriously. Speaking for myself, I
haven't taken any of yours remarks personally, Jeremy. Don't worry
about it, I'm done crying <sniff, sniff>....my mom's coming over to
talk to yours some time soon! LOL!
3) I do understand your point of view about d.net Jeremy...just
that EFF was a different group and we had no right to whine or
complain about them getting through DES-II first. That is exactly the
kind of feeling ("cheated" out of their reserved exponent) that I
hoped to avoid here in GIMPS, which is why I responded so stronly to
Aaron's poaching comments.
I'm out!
Peace!
Ashton
P.S. - Nice to see that GIMPSers aren't cold calculating
mathematicians only!
_________________________________________________________
DO YOU YAHOO!?
Get your free @yahoo.com address at http://mail.yahoo.com
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: 14 Jun 99 16:59:54 MDT
From: Paul Derbyshire <[EMAIL PROTECTED]>
Subject: Mersenne: Re: Mersenne Digest V1 #575
Yvan Dutil <[EMAIL PROTECTED]> wrote:
> One weird bahavior: 5292757. Which as appear to have been resetted
> recently by its 'owner' to an duration as long as the initial one!
Obviously, someone got dinged with the v17-v18 upgrade. I pity them...
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
____________________________________________________________________
Get free e-mail and a permanent address at http://www.netaddress.com/?N=1
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 1999 00:52:08 +0000 (GMT)
From: Henrik Olsen <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Re: Mersenne Digest V1 #575
On Mon, 14 Jun 1999, Steinar H. Gunderson wrote:
> >I thought that if no check-in was done in 60 days, the number was put back in
> >the pool.
>
> No, if no check-in has been done in 60 days _after the exponent was expected
> to complete_, it is put back into the pool. Of course, once in a while,
> the software will report `new expected completion dates' to the server, and
> this date will be moved.
George did a post earlier telling about this, the policy you're describing
is the one used for version 15. In the later versions it's 60 days after
last check-in, unless you've reported a vacation.
- --
Henrik Olsen, Dawn Solutions I/S URL=http://www.iaeste.dk/~henrik/
Do not meddle in the affairs of dragons,
for you are crunchy and taste good with ketchup.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 14 Jun 1999 20:06:45 -0500
From: Gary Diehl <[EMAIL PROTECTED]>
Subject: Mersenne: Ideas : maybe no new ones...
All you GIMPS-ers...
Today while I was mindlessly working my body on a treadmill to attempt
to maintain some kind of decent physical condition, I had a thought (it
wasn't intentional... it just happened, honest!).
Has anybody tracked the value of "S" in the LL test?
When you square S over and over and over in one LL test, does that same
value of S come up in a test for another exponent? Is there a pattern
of S values that can help us shorten the LL test? If there is a
pattern, and it can be used to calculate a certain S value for some
other (untested?) exponent at some given iteration, then it could cut
weeks off of testing exponents.
Maybe just wishful thinking... But seriously, has somebody tracked this
kind of data to look for repeating patterns that can be made into
formulas?
Gary Diehl
- --If curiosity killed the cat, then M38 brought him back!
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 14 Jun 1999 21:45:52 -0400
From: George Woltman <[EMAIL PROTECTED]>
Subject: Mersenne: Final (hopefully) comments on poaching
Hi all,
1) The problem is solved for all v16 and later clients. In other
words it is 99% solved. Even if you check out a first time LL test on a
P-75 the existing system will not time you out as long as you are running
the program regularly. The Primenet status reports will show the world
that you are indeed working diligently on your exponent.
2) The only good idea to come out of this thread is to
allow users to send an I'm-still-working message in the manual web forms,
along with a more generous initial timeout of 120 days. It is up
to Scott to decide if he is willing to spend the time to implement this.
3) Other ideas for reassigning exponents that were assigned to
v15 clients or by email included setting a firm policy, sending emails,
waiting for responses, etc. etc. While a good idea it is more time-consuming
for me.
4) M#37 was a recycled assignment. BTW, there are 9000 double-checks
required before the ? is removed from M#37.
5) One of GIMPS greatest features is the lack of rigid rules. However,
as this thread points out, this feature has a downside too.
Since my time is limited and I've been entrusted by default with
inventing GIMPS' official poaching rules, here it is:
1) Do not poach exponents.
2) I will apply the existing ad hoc policy for reassigning stale v15
exponents and email-reserved exponents. They will be recycled on an
infrequent basis when I find the time. The server will then hand them out
to random
lucky users. I'm more aggresive with smaller exponents than larger exponents
so that we will march steadily onwards. I'm more aggresive with people I
don't know. If you reserved a range by email and report results every 5
months then you are safe.
Have a nice day,
George
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 14 Jun 1999 22:00:47 -0400
From: Jud McCranie <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Ideas : maybe no new ones...
At 08:06 PM 6/14/99 -0500, Gary Diehl wrote:
>When you square S over and over and over in one LL test, does that same
>value of S come up in a test for another exponent?
It could, but I don't think that helps since for each exponent the calculations
are done to a different modulus.
+----------------------------------------------+
| Jud "program first and think later" McCranie |
+----------------------------------------------+
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 14 Jun 1999 23:17:08 -0400 (EDT)
From: lrwiman <[EMAIL PROTECTED]>
Subject: Mersenne: Power supplies (was poaching was digest whatever)
>> *never ever* cheap out on power supplies.
> This is good advice, but personally I have never seen the
> point of giving every machine in a rack of computers its own
> power supply rather than having one big one and just running
> DC all the way up the rack. The fact that it is not done
> that way seems to be about politics of having AC wall current
> rather than engineering efficiency.
> Why not have a single (redundant) big 24VDC power supply for
> all the boards instead of supplying them all 120VAC?
Well, I would guess that this is a catch-22. This is a good idea,
which could actually produce cheaper, high quality power. But this
is non-standard. The logistics of creating a new case design, and power
supply designs are more than most corporations are willing to stomach on
something as cheap as electric power, and equipment that is going to be
upgraded in 2 years anyway.
- -Lucas Wiman
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 14 Jun 1999 23:29:28 -0400 (EDT)
From: lrwiman <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Factoring
> I was just wondering, could anyone give me any info on how factoring is
> done, is there a preliminary factoring before numbers send out, how high
> we factor, what possible factors are, etc. and also, I would really like
> to see the maths behind it as well. I need something to study over summmer
> vac :)
Well, the two biggies are that factors of 2^p-1 (for prime p)
must be of the form 2*k*p+1, and such factors must be be congruent to
1 or -1 (7) mod 8,
(or in other words) they must be of the form
8*n+1, or 8*n-1.
For proofs (I don't have time right now :( ), see
http://www.utm.edu/research/primes,
and look at the section on mersenne numbers.
Also, you can find a marvelous discussion in the archives for this list.
- -Lucas Wiman
________________________________________________
5 years without a sig file, and going strong...
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: 14 Jun 99 21:42:08 MDT
From: Paul Derbyshire <[EMAIL PROTECTED]>
Subject: Re: [Mersenne: Re: factoring 10^7 digits (was LL and factoring & quitting)]
> Sounds about right for a SWAG estimate.
SWAG?
____________________________________________________________________
Get free e-mail and a permanent address at http://www.netaddress.com/?N=1
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 1999 00:21:23 -0400 (EDT)
From: lrwiman <[EMAIL PROTECTED]>
Subject: Re: Mersenne: factoring 10^7 digits
>> Sounds about right for a SWAG estimate.
> SWAG?
SWAG stands for Scientific Wild-Assed Guess - translation: educated guess
- -Lucas Wiman
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 1999 02:04:21 -0500
From: Ken Kriesel <[EMAIL PROTECTED]>
Subject: Re: Mersenne: status of exponents
At 09:01 PM 1999/06/10 -0400, you wrote:
>The status page shows that for exponents in the range 3,310,000-3,960,000,
>there are 225 exponents for which 2 L-L tests have been done, yet there are
>40 exponents for which no factor is known, and no LL test has been done. I
>have 2 questions:
>
>1. Why have 2nd LL tests been done in many cases when there are still
>exponents whose status is unknown?
>
>2. Exponents over 6,000,000 have been assigned for a couple of months or
>so. Why are large exponents being assigned when there are still smaller
>ones in need of a LL test?
The Internet Primenet Server is not the only pool of exponents.
Some people are getting exponents manually assigned via the webpage; I get
mine by email from George.
I request exponents below 5,260,000 because that's what I'm mostly set up
to run, with a separate primenet V2.x server and numerous v14.4 clients.
One of the blocks I've been assigned by George includes 3,960,000, which is
currently issuing rapidly. When an exponent gets put on a slow machine and
nears the bottom of the untested-once list, I move its intermediate result
files to a fast box to accelerate achievement of the next GIMPS milestone.
Several other Intel cpus I run which are 200Mhz and up are busy running
1 or 2 full LLtests in each run length, also reserved by email from George.
After all, the IPS won't issue in the upper ranges yet, so testing ahead
of the pack for QA purposes requires other means.
Ken
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 1999 02:15:33 -0500
From: Ken Kriesel <[EMAIL PROTECTED]>
Subject: Mersenne: Re: 386's
At 01:00 PM 1999/06/14 -0600, Jeremy Blosser wrote:
>Note: I find it really odd that when the Java client was brought up, people
>were saying "It'll be too slow" (which it really wasn't) or "Its not worth
>it", and now people are saying its okay for some 386 to do LL testing...
A 386, even one with a Cyrix 83d87 which is significantly faster than
the Intel 80387 of the same vintage, is painfully slow, even back when
double checks were in the 1.2M range. This is why George no longer supports
it in the CPU check boxes. I wonder how long it will be before he drops
486's.
Mine takes about 15 seconds/iteration in 7.8M. (Don't worry, it's just
giving a faster processor a head start. It's getting so slow it isn't worth
the cost of electricity.)
Jeremy, if you find a Java client fun, go for it.
Ken
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 1999 01:02:53 -0700
From: "Scott Kurowski" <[EMAIL PROTECTED]>
Subject: Mersenne: RE: Mersenne Digest V1 #578
We added an assignments extension form to the manual testing page at:
http://entropia.com/ips/manualtests.html
Regards,
scott
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 1999 10:07:53 GMT
From: "Brian J Beesley" <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Etiquette (was Poaching)
Ashton Vaz <[EMAIL PROTECTED]> writes:
> I'll call a truce. I'm sure it's clear to George and Scott where
> most people's opinions lie on the issue of poaching. I'll leave the
> discussion where it's at since we've seem to have come to a consensus.
Could I respectfully suggest that, in future, list members flame
each other in private (at any rate, after they've posted their views
once). I don't much like the smell of toasting flesh.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 99 11:19:01 CES
From: "Cornelius Caesar" <[EMAIL PROTECTED]>
Subject: Mersenne: TeraFLOP/s
Just curious: Is anyone else waiting for PrimeNet to achieve 1 TeraFLOP/s
(except Scott, of course :-))?
Scott, do you have a time estimate for that when extrapolating the
current growth?
Cornelius Caesar
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 1999 03:09:48 -0700
From: "Scott Kurowski" <[EMAIL PROTECTED]>
Subject: Mersenne: RE: Mersenne Digest V1 #576
> I just started my second machine on double-checking and am curious on
> whether I would expect to see my LL P90 year total increase when a
> double-checking assignment is turned in.
Yes. PrimeNet credits double-checking work.
> Also, I notice that one can disable "Request whatever type of work makes
> the most sense" and then proceed to select *two* types of work that you
> want. How does the server decide which to send?
The server uses simple preference biasing rules provided by George. If there is
no exponent available matching the first rule, a second-order rule is engaged
(if defined), or failing that, tertiary rule. If no match is found for any
rule, 'No Assignment' is returned.
> I assume that it'll choose
> factoring over double-checking, double-checking over primality testing,
> and factoring over primality testing. Is this correct? If so, the windows
> versions might better be served wait radio-buttons so that only one can be
> selected.
You can select any combination of test types you will accept. There's a server
rule for each combination. The rules are further modified by test eligibility
functions of the program type, version, exponent and factoring state.
Here's PrimeNet's current assignment rule table:
Checkboxes Assignment by
Selected Rule1 Rule2 Rule3
- ---------- ----- ----- -----
F F - - factoring or bust
P P F - prefer LL, fall back is factoring
P+F P F - ditto
D D F - prefer double-check, fall back is factoring
D+F D F - ditto
D+P D P F etc.
D+P+F D P F
Allowing the user to specify a set of acceptable assignment types gives us some
wiggle room in managing the exponent 'flow' through PrimeNet while letting
people choose what they want to do.
There's a second more rigid type of rule system upstream of this, in the part of
PrimeNet that internally normalizes all program packet versions into a
transaction object. This is where we set rules like, 'give all v17 clients
double-checking work', 'set the factoring capability to 64 bits for NTPrime
v16.3', or 'return error 37 (obsolete DLL) to all v15 clients'.
Regards,
scott
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 1999 11:17:20 GMT
From: "Brian J Beesley" <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Ideas : maybe no new ones...
> When you square S over and over and over in one LL test, does that same
> value of S come up in a test for another exponent?
Well, the first few values are the same ... until the remaindering
kicks in. And we know that S(n) = 2 for all terms >= n, if 2^n-1
happens to be prime (since S(n-2) = 0).
> Is there a pattern
> of S values that can help us shorten the LL test?
Find one & tell us about it ;-)
> If there is a
> pattern, and it can be used to calculate a certain S value for some
> other (untested?) exponent at some given iteration, then it could cut
> weeks off of testing exponents
Indeed.
I had a semi-crackpot idea like this, that we know what S(n) is for
n>=p-2 if 2^p-1 happens to be prime. So, searching for larger
exponents, if we can find a set of (smaller) p(i) such that the sum
of the p(i)'s is at least equal to the exponent we want to test, then
we should be able to get the residual directly using the Chinese
Remainder Theorem.
Of course, it doesn't work, the modulo operation fouls things up.
The reason I call the idea "semi-crackpot" instead of completely
stupid is that there is _some_ mileage in it. I managed to find a
"new" (well, different) way of doing a LL test, as follows:
Find a set of about 16 p(i) such that the product of the 2^p(i)-1 is
greater than or equal to (2^P-1)^2. The p(i) need to be prime but
2^p(i)-1 doesn't need to be, the fact that the p(i) are all prime
guarantees that the gcd of any pair of the 2^p(i)-1 is 1.
Then we can compute the LL sequence for each of the p(i) by
some normal method. Each time it the next iteration _could_
exceed (2^P-1)^2 (we can work mod 2^p(i)-1 so long as we bear
this in mind), use the CRT to get the residual, reduce it modulo
2^P-1 (easy, just shift & add) then regenerate the residuals for the
p(i)'s from the result.
If you take about 16 p(i), then you will only have to do the CRT
reduction about every 4 iterations ... a big saving on having to do it
every time.
This method can be applied recursively until the 2^p(i)-1's are small
enough to deal with in CPU registers.
Compared with the DWT, this method has some disadvantages
(memory usage is probably one) but some advantages too (no fear
about rounding errors, etc, also suited to systems with no/slow
floating point). The idea _does_ work, but it's not well suited to Intel
processors (not enough named CPU registers, integer multiply is
too slow). Anyone who wants to develop this idea is welcome to do
so ... the "intellectual property" involved in writing efficient code is
huge compared with that in the (rather simple) idea.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 1999 12:22:34 +0100 (BST)
From: Chris Jefferson <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Factoring
Hmm... Thanks for all the advice on factoring!
Just one question / comment.
We want to find 2^p mod n where n is in form 2kp + 1
If we KNOW 2kp + 1 is prime, then the euler totient fn. of n is 2kp, call
this T
Also, if a is co-prime to n, a^T=1 mod n
2 is obviously co-prime to n, so 2^T=1 mod n
So another way of working out if a factor would be to work out
So if 2kp + 1 is prime, 2^(2kp)=1 mod (2kp + 1)
Herein lies my problem:
I know that if p is prime, 'mod p' is a group under muliplication.
I know that 2*(2^(p-2))=1 mod p
so 2^(p-2) is the inverse of 2 and only by multilplying by 2^(p-2) can I
get 1.
Now, this implies that for no 0<N<2kp, 2^N=1 mod (2kp + 1)
so 2^p cannot be 1 mod (2kp + 1)
?????
Sorry to bother you again
Chris Jefferson, Cambridge
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 1999 13:46:18 +0200
From: Marcel Baatsen <[EMAIL PROTECTED]>
Subject: Mersenne: Version 1.6 versus 1.8
Just entered the discussion/mail-list two weeks ago, though checking my
third number already for some time.
I guess I missed several thousand interesting mails.
My prime95 version is 1.6. Should I upgrade to 1.8 or not ?
Bye,
Marcel
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 1999 09:20:47 -0400 (EDT)
From: "St. Dee" <[EMAIL PROTECTED]>
Subject: Mersenne: Interesting behavior?
Hi,
I've been playing with the settings on one of my machines (reclaimed from
the stalled SETI project) and found something interesting. It is a
P5-200MMX running Prime95 24x7. However, when I set up Prime95, I
indicated that it was only going to be running 6 hours per day. As
expected, the machine originally requested factoring assignments. Also as
expected, since it was really running 24x7, it raced through the factoring
assignments much more quickly than PrimeNet expected. After 4 or 5
factoring assignments, PrimeNet started assigning double-checking to the
machine. Now it's going quickly through double-checking assignments.
Last night, I noticed that the PrimeNet server assigned this machine an LL
test of an exponent in the 7,400,000+ range! My question is, does the
PrimeNet server look at the actual speed a machine is achieving to
determine what it should assign?
Kel
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 1999 11:15:46 -0400
From: Jeff Woods <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Ideas : maybe no new ones...
I think what he's getting at is that some individual exponent MIGHT fall
into it's own "pattern of division", much the same was the very simple
repeating decimals (such as 1/11) turn into a repetitive pattern in long
division (i.e. 0.0909090909090.....forever). One doesn't need to KEEP
dividing to know with certainty that the "09" pattern will repeat forever.
If the value of "s" were tracked, it may be that the value of "S" at some
point in a LL test falls into a pattern as well. A fictititous example
for a much smaller Mersenne number might look like this:
.
.
.
S = 23875123789498
S = 1289358913467911
S = 902356809248560249856
S = 134578613667
S = 23875123789498
S = 1289358913467911
S = 902356809248560249856
S = 134578613667
S = 23875123789498
S = 1289358913467911
S = 902356809248560249856
S = 134578613667
S = 23875123789498
S = 1289358913467911
S = 902356809248560249856
S = 134578613667
.
.
.
.
If we found something like this in a test for 2^35,673,121-1 while testing
for a 10 million digit prime, and found it at iteration 126,112, we could
discard the remaining 35 million interations, and just use a simple modulus
calculation to determine WHICH of the values of "S" seen in the early
repetition is the true residue of the LAST iteration.
Likewise, if we see S hit zero at some intermediary point, and that pattern
repeats as well, we might be able to KNOW a number is prime if that modulus
calculation shows that the repetitive zero falls on the last iteration --
without doing the entire 35 million calculations.
If "S" turns out to repeat in the manner of 0.09090909090909.... then the
overhead it takes to check such "might" be worth performing for the first
hundred thousand iterations (or some magic threshhold where it becomes less
than optimal).
I understand where the poster is coming from, as described above, but I
don't think anything will come of it -- the overhead WOULD be horrendous at
these levels....
At 10:00 PM 6/14/99 -0400, you wrote:
>At 08:06 PM 6/14/99 -0500, Gary Diehl wrote:
>
> >When you square S over and over and over in one LL test, does that same
> >value of S come up in a test for another exponent?
>
>
>It could, but I don't think that helps since for each exponent the
>calculations
>are done to a different modulus.
>
>+----------------------------------------------+
>| Jud "program first and think later" McCranie |
>+----------------------------------------------+
>
>
>________________________________________________________________
>Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 1999 09:27:04 -0600
From: "Blosser, Jeremy" <[EMAIL PROTECTED]>
Subject: RE: Mersenne: Ideas : maybe no new ones...
> -----Original Message-----
> From: Jud McCranie [mailto:[EMAIL PROTECTED]]
> Sent: Monday, June 14, 1999 9:01 PM
> To: Gary Diehl
> Cc: [EMAIL PROTECTED]
> Subject: Re: Mersenne: Ideas : maybe no new ones...
>
>
> At 08:06 PM 6/14/99 -0500, Gary Diehl wrote:
>
> >When you square S over and over and over in one LL test,
> does that same
> >value of S come up in a test for another exponent?
>
>
> It could, but I don't think that helps since for each
> exponent the calculations
> are done to a different modulus.
>
I was thinking about this last night. If you could keep track of the
divisions for the last Mersenne, you could keep that as a starting point. So
for example, take M37, and keep track of how many times you did your modulo
and what the divisor was. Then you could conceptually get back to what
S(M37) was w/o the modulo by multiplying M37*(sum of divisors) or something
along those lines. It would at least save you some time, sure there's a big
modulo calculation in the beginning, and I'm sure the number is friggin'
huge, but it can be represented as (2^p-1)*(some number).
I originally was trying to think if there was an easy way to get there from
any number's residual, but then it becomes a hassle.
On another note, I was thinking last night about a totally different
approach, and would appreciate it if some math modulo guru out there could
explain how to go from something like:
(2^7+2^6+2)%(2^5-1) = 2^3
or how
(2^12+2^8+2^7+2^2+2+1)%(2^7-1) = 2^5+2^3+2
without actually figuring out the number represented. I know that 2^7+2^6+2
= 194 and could then take the modulus from there... but that defeats the
purpose. :)
Thanks
Jeremy
P.S. Sorry for my part in the poaching thread.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 1999 11:39:43 EDT
From: [EMAIL PROTECTED]
Subject: Re: Mersenne: TeraFLOP/s
> Just curious: Is anyone else waiting for PrimeNet to achieve 1 TeraFLOP/s
> (except Scott, of course :-))?
>
> Scott, do you have a time estimate for that when extrapolating the
> current growth?
Scott has the official numbers, but based on the past
six months, it looks like it will occur by year end.
Randy Given
[EMAIL PROTECTED]
http://members.aol.com/GivenRandy
public key at http://members.aol.com/GivenRandy/pgpkey.asc
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 1999 09:05:27 -0700
From: "John R Pierce" <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Power supplies (was poaching was digest whatever)
> > Why not have a single (redundant) big 24VDC power supply for
> > all the boards instead of supplying them all 120VAC?
>
> Well, I would guess that this is a catch-22. This is a good idea,
> which could actually produce cheaper, high quality power. But this
> is non-standard. The logistics of creating a new case design, and power
> supply designs are more than most corporations are willing to stomach on
> something as cheap as electric power, and equipment that is going to be
> upgraded in 2 years anyway.
actually, -48VDC is used by telephone equipment, and I've heard you can get
industrial grade PC power supplies that run on 48V DC so that they can be
run directly off of telephone style batteries. This is done at some
internet providers.
>From an electrical standpoint, the standard switching power supply used in a
PC just takes the 115VAC, full wave rectifies it to 120VDC, then runs this
through a 400khz oscillator en route to the toroidal transformer. Theres no
real savings to be had from going all DC here.
- -jrp
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 15 Jun 1999 10:49:23 -0600
From: "Blosser, Jeremy" <[EMAIL PROTECTED]>
Subject: RE: Mersenne: Ideas : maybe no new ones... (doh!)
<snip>
>
> I originally was trying to think if there was an easy way to
> get there from
> any number's residual, but then it becomes a hassle.
>
> On another note, I was thinking last night about a totally different
> approach, and would appreciate it if some math modulo guru
> out there could
> explain how to go from something like:
>
> (2^7+2^6+2)%(2^5-1) = 2^3
> or how
> (2^12+2^8+2^7+2^2+2+1)%(2^7-1) = 2^5+2^3+2
>
> without actually figuring out the number represented. I know
> that 2^7+2^6+2
> = 194 and could then take the modulus from there... but that
> defeats the
> purpose. :)
>
Okay, so I got out my pen and paper and actually put some thought into it.
(2^7+2^6+2)%(2^5-1) = 2+6
(2^7+2^6)/2^5 = 2^2+2 = 6
Thus (2^7+2^6+2)-6(2^5-1) = 2+6
and:
(2^12+2^8+2^7+2^2+2+1)%(2^7-1) = 2^2+2+35
(2^12+2^8+2^7)/2^7 = 2^5+2^1+2^0 = 35
Thus (2^12+2^8+2^7+2^2+2+1)-35(2^7-1) = 2^2+2+1+35
Any thoughts as to doing the modulo a different way would be appreciated.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
End of Mersenne Digest V1 #579
******************************
