Mersenne Digest Tuesday, 16 February 1999 Volume 01 : Number 510
----------------------------------------------------------------------
From: [EMAIL PROTECTED]
Date: Mon, 15 Feb 1999 06:51:47 EST
Subject: Re: Mersenne: Link from Knuth's Home Page
> So, what the hell's he planning to put in V4?
>From Knuth's web page at:
http://www-cs-faculty.stanford.edu/~knuth/taocp.html#vol4
his plans for upcoming volumes are:
Volume 4
Combinatorial Algorithms, in preparation.
Present plans are to publish ``Volume 4'' as three separate subvolumes:
Volume 4A, Enumeration and Backtracking
7.1. Boolean techniques (aka bit fiddling)
7.2. Generating all possibilities
7.2.1. Combinatorial generators
7.2.2. Basic backtrack
7.2.3. Efficient backtracking
7.3. Shortest paths
Volume 4B, Graph and Network Algorithms
7.4. Graph algorithms
7.4.1. Components and traversal
7.4.2. Special classes of graphs
7.4.3. Expander graphs
7.4.4. Random graphs
7.5. Network algorithms
7.5.1. Distinct representatives
7.5.2. The assignment problem
7.5.3. Network flows
7.5.4. Optimum subtrees
7.5.5. Optimum matching
7.5.6. Optimum orderings
7.6. Independence theory
7.6.1. Independence structures
7.6.2. Efficient matroid algorithms
Volume 4C, Optimization and Recursion
7.7. Discrete dynamic programming
7.8. Branch-and-bound techniques
7.9. Herculean tasks (aka NP-hard problems)
7.10. Near-optimization
8. Recursion
The material will first appear in beta-test form as fascicles of approximately
128 pages each, issued approximately twice per year beginning in 1999. These
fascicles will represent my best attempt to write a comprehensive account, but
computer science has grown to the point where I cannot hope to be an authority
on all the material covered in these books. Therefore I'll need feedback from
readers in order to prepare the official volumes later. The publishers have
pledged to make the fascicles available in an inexpensive form, essentially at
cost. (Of course, the paper and binding will probably be designed to self-
destruct in a few years, so that you will have to buy the real book after it
is debugged:-)
If all goes as planned, Volumes 4A, 4B, and 4C will be ready in the year 2004.
Volume 5
Syntactic Algorithms, in preparation.
9. Lexical scanning (includes also string search and data compression)
10. Parsing techniques
Estimated to be ready in 2009.
Future plans
As I write Volumes 4 and 5, I'll need to refer to topics that belong logically
in Volumes 1--3 but weren't invented yet when I wrote those books. Instead of
putting such material artificially into Volumes 4 or 5, I'll put it into
fascicle form. One of the first such fascicles will be a description of MMIX,
a RISC machine that will take the place of MIX.
After Volume 5 has been completed, I will revise Volumes 1--3 again to bring
them up to date. In particular, the new material for those volumes that has
been issued in beta-test fascicles will be incorporated at that time.
Then I will publish a ``reader's digest'' edition of Volumes 1--5, condensing
the most important material into a single book.
And after Volumes 1--5 are done, God willing, I plan to publish Volume 6 (the
theory of context-free languages) and Volume 7 (Compiler techniques), but only
if the things I want to say about those topics are still relevant and still
haven't been said. Volumes 1--5 represent the central core of computer
programming for sequential machines; the subjects of Volumes 6 and 7 are
important but more specialized.
------------------------------
From: "Sander Hoogendoorn" <[EMAIL PROTECTED]>
Date: Mon, 15 Feb 1999 10:48:16 PST
Subject: Mersenne: Factoring
Hi,
Last weekend when i was testing Prime 95 i noticed that factoring low
numbers took much longer as high numbers.
Factoring M17XXX from 2^52 to 2^54 took minutes per pass while factoring
M9XXXXXX from 2^52 to 2^54 took about one minute to complete the whole
factoring. How is this possible?
Greetz
Sander
______________________________________________________
Get Your Private, Free Email at http://www.hotmail.com
------------------------------
From: "Glenn Maitz" <[EMAIL PROTECTED]>
Date: Mon, 15 Feb 1999 14:03:58 -0500
Subject: Mersenne: Missing exponent
One of my computers returned a result via Primenet for an exponent on
Feb. 6th. But although my personal account report shows that it was
received, there was no increase in number of exponents (should have been
my 31st) or CPU years. There must be a glitch in the new server
software. I hope it is not being reassigned to someone else.
Glenn
------------------------------
From: "Scott Kurowski" <[EMAIL PROTECTED]>
Date: Mon, 15 Feb 1999 13:17:53 -0800
Subject: Mersenne: RE: Mersenne Digest V1 #509
Hi all,
If you have a PrimeNet question, you'll get a faster answer if you email us at
<[EMAIL PROTECTED]> instead of the list. I receive the Mersenne digests
much later than your messages. I'm also concerned about people dumping a lot of
PrimeNet operational traffic on a list meant primarily for technical discussions
of number theory and related algorithms.
If you must use a list as a general PrimeNet issues forum, please use the
primenet list at <[EMAIL PROTECTED]>.
> The last time I sent results in my total exponents tested was 7 and Cpu years
> were 1.670. Since then my account has been updated to 8 exponents and 1.929
years.
> This happened after the new server went on line. I'm sure I have checked only
> seven exponents so is there a problem with the servers information?
> Yeah! I've also have had some problems, but I've lost one exponent.
> God knows who was the lucky to have it assigned and if I will be capable
> of having it again!
If there's a discrepancy, please email me directly. It takes only a few moments
to set an account to the correct state.
For some accounts that submitted results between 5 and 7 February inclusive,
PrimeNet's 3.1 database required a set of roll-forward transactions to correct a
table corruption before the upgrade to 4.0. We have a complete 3.1 transaction
history, though checking it directly against the 4.0 server is not easy. We have
endeavored to be as thorough as possible, and have restored almost all affected
accounts to normal.
A symptom related to this is that your program may have switched userids because
of a built in automatic fail-safe feature. In most cases, simply changing the
userid/pw back again resolves this (including errors that an exponent is still
assigned to your primary account ID). Use the User Information settings - do not
edit the ini file.
> The ONLY mention of the contest is at the bottom of the page, What
> should we make of this?
>
> 1) it's a glitch.
> 2) there is no more prize.
> 3) somebody as won the previous prize !!!
The contest link is two lines below. Attention to the contest is updated
whenever necessary, but it's a motivating factor for participation, not the
basis of the project.
> If a automatic statistics history file containing a log of
> daily throughput rates was put up, one of us could probably
> write a script to produce an automatically updated graph
> similar to the one on http://entropia.com/ips/stats.html
This was on our to do list, but ok. Let's try it. I'll make it even easier.
Assume you have an input text file with two comma-separated text values per
line: total CPU time for a given day (float 7.4f), and the date for that day
(DD/MM/YYYY). Make up some test input.
Send me a script that outputs a GIF image of the chart made from the input file.
I prefer Perl 5 and MS Excel, so please check with me first before you
substitute software tools to see if we have it or want to get it.
Regards,
scott
------------------------------
From: [EMAIL PROTECTED]
Date: Mon, 15 Feb 1999 22:35:06 +0100 (MET)
Subject: Re: Mersenne: Factoring
"Sander Hoogendoorn" <[EMAIL PROTECTED]> asks
> Last weekend when i was testing Prime 95 i noticed that factoring low
> numbers took much longer as high numbers.
> Factoring M17XXX from 2^52 to 2^54 took minutes per pass while factoring
> M9XXXXXX from 2^52 to 2^54 took about one minute to complete the whole
> factoring. How is this possible?
>
Only primes in [2^52, 2^54] which are congruent to
1 modulo 17XXX (or modulo 9XXXXXX) need be checked. [There are other
restrictions, such as the prime being == +- 1 modulo 8.]
For the larger exponent, the density of candidate divisors
is 17XXX / 9XXXXXX ~= 1/50 times as large.
For the larger exponent, the cost of testing each divisor
(using the binary method of exponentiation) is
log_2(9XXXXXX) / log_2(17XXX) ~= 23/14 times as long.
Overall, when the interval [2^52, 2^54] is fixed,
the checking for the larger exponent proceeds
50 * (14/23) ~= 30 times as fast.
On the other hand LL testing for the larger
exponent takes 50 times as many iterations, and each
iteration takes about 50 * (23/14) ~= 80 times as long,
so this cost grows by a factor of 4000.
Keeping the (LL costs)/(factoring costs) ratio constant,
the factoring could search an interval
30 * 4000 ~= 2^17 times as long. Alas, [2^69, 2^71]
needs more than 64 bits of precision to store candidate
divisors, so you probably stop factoring at 2^64 or switch to
other algorithms.
------------------------------
From: Will Edgington <[EMAIL PROTECTED]>
Date: Mon, 15 Feb 1999 13:59:45 -0800
Subject: Mersenne: Factoring
Sander Hoogendoorn writes:
Last weekend when i was testing Prime 95 i noticed that factoring
low numbers took much longer as high numbers.
Factoring M17XXX from 2^52 to 2^54 took minutes per pass while
factoring M9XXXXXX from 2^52 to 2^54 took about one minute to
complete the whole factoring. How is this possible?
All factors of a Mersenne number with a prime exponent, p, are of the
form 2*k*p + 1 where k is a natural number (positive integer). So the
larger p is, the fewer the number of possible factors between two
constants like 2^52 and 2^54. In this case, 17XXX divided by 9XXXXXX
is at most 0.2%, so checking all the possible factors of M17XXX takes
about 500 times as much CPU as checking all the possible factors of
M9XXXXXX within the same range of numbers.
This a large part of why higher exponent Mersennes are trial factored
farther than lower exponent Mersennes.
While I'm here, I'll mention for the newcomers that I collect all
sorts of factoring data on Mersenne numbers, including George
Woltman's ECM & GIMPS data, the Cunningham Project ftp site data
maintained by Paul Leyland, Conrad Curry's Factor98 data, and directly
from interested individuals like yourself; just send it to me in
email, plain text or as MIME attachment(s). The data I've collected
for exponents under 200,000 is available below. I have data for many
larger exponents, including all primes thru 21.5 million or so, but do
not have room on my ISP's web server to upload it.
Will
http://www.garlic.com/~wedgingt/mersenne.html (proofs, links, etc.)
mersfmt.txt (data format description)
mersdata.zip (data, zip'd)
mersdata.tgz (same data, different packing)
factoredM.txt (completely factored Mersennes)
...
------------------------------
From: "Todd Lewis" <[EMAIL PROTECTED]>
Date: Mon, 15 Feb 1999 16:35:51 -0600
Subject: Re: Mersenne: Missing exponent
I'm noticing the same thing. I recently turned in about 4 or 5
exponents in the 6mil range a few weeks back. Georges combined
results has me at about 4.68 years while Entropia has me at 1.86
years. I had no more than 6 or 7 months on my account before
Entropia came on line.
>
> One of my computers returned a result via Primenet for an exponent on
> Feb. 6th. But although my personal account report shows that it was
> received, there was no increase in number of exponents (should have been
> my 31st) or CPU years. There must be a glitch in the new server
> software. I hope it is not being reassigned to someone else.
>
> Glenn
------------------------------
From: Spike Jones <[EMAIL PROTECTED]>
Date: Mon, 15 Feb 1999 18:47:35 -0800
Subject: Mersenne: Re: Mersenne Digest V1 #509
If a automatic statistics history file containing a log of
daily throughput rates was put up, one of us could probably
write a script to produce an automatically updated graph
similar to the one on http://entropia.com/ips/stats.html
Kevin Sexton
kevin, i asked entropia.com for this data a couple weeks ago, but they
are playing their cards close to the vest. the concern is that we will
scoop them with scientific papers, etc. i think i recall a newer
version of that graph that went up to the end of november, but the
current one only goes to the first of october. with the understanding
that we will not scoop entropia.com, has anyone logged the gimps
thruput for the past several months? and would be willing to share,
just for our own use, with no commercial aspirations? spike
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: [EMAIL PROTECTED] (T.Shakushi)
Date: Tue, 16 Feb 1999 19:44:21 +0900 (JST)
Subject: Re: Mersenne: Missing exponent
Some of my NTprimes 16.x did the same thing.
I found "Exponent not assigned to us" in log files.
So I checked user information dialog, and found my ID and PW were changed.
One of the CPUs is located in security area, and is protected by
administrator's password, so nobody can operate that machine.
I manually correct my user information, and it works well, but does the new
Primenet server change client's user information via network???
At 2:03 PM 99.2.15 -0500, Glenn Maitz wrote:
> One of my computers returned a result via Primenet for an exponent on
>Feb. 6th. But although my personal account report shows that it was
>received, there was no increase in number of exponents (should have been
>my 31st) or CPU years. There must be a glitch in the new server
>software. I hope it is not being reassigned to someone else.
>
>Glenn
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: Paul Derbyshire <[EMAIL PROTECTED]>
Date: Tue, 16 Feb 1999 07:31:32 -0500
Subject: Re: Mersenne: Link from Knuth's Home Page
At 06:51 AM 2/15/99 EST, you wrote:
>fascicles
What the devil is a "fascicle"? What you get when you mix liquid nitrogen,
Stalin, Mussolini, and Hitler?
- --
.*. "Clouds are not spheres, mountains are not cones, coastlines are not
- -() < circles, and bark is not smooth, nor does lightning travel in a
`*' straight line." -------------------------------------------------
-- B. Mandelbrot |http://surf.to/pgd.net
_____________________ ____|________ Paul Derbyshire [EMAIL PROTECTED]
Programmer & Humanist|ICQ: 10423848|
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: Todd Sauke <[EMAIL PROTECTED]>
Date: Tue, 16 Feb 1999 13:27:56 -0800
Subject: Re: Mersenne: Link from Knuth's Home Page
Paul Derbyshire wrote:
>What the devil is a "fascicle"?
My first thought was "Why not just look it up in the dictionary?"
I was amused that my Webster's New Collegiate Dictionary's first definition
of fascicle is "an inflorescence consisting of a compacted cyme less
capitate than a glomerule"
. . . Okaayyyy
Todd Sauke
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: David Nunn <[EMAIL PROTECTED]>
Date: Tue, 16 Feb 1999 21:27:50 -0600
Subject: RE: Mersenne: Link from Knuth's Home Page
from http://www.m-w.com/dictionary.htm
Main Entry: fas·ci·cle
Pronunciation: 'fa-si-k&l
Function: noun
Etymology: Latin fasciculus, diminutive of fascis
Date: 15th century
1 : a small or slender bundle (as of pine needles or nerve
fibers)
2 : one of the divisions of a book published in parts
slightly more understandable :)
> -----Original Message-----
> From: Todd Sauke [SMTP:[EMAIL PROTECTED]]
> Sent: Tuesday, February 16, 1999 3:28 PM
> To: [EMAIL PROTECTED]
> Subject: Re: Mersenne: Link from Knuth's Home Page
>
> Paul Derbyshire wrote:
>
> >What the devil is a "fascicle"?
>
> My first thought was "Why not just look it up in the dictionary?"
> I was amused that my Webster's New Collegiate Dictionary's first
> definition
> of fascicle is "an inflorescence consisting of a compacted cyme less
> capitate than a glomerule"
> . . . Okaayyyy
>
> Todd Sauke
> ________________________________________________________________
> Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
From: LEBLANC ERIC <[EMAIL PROTECTED]>
Date: Wed, 17 Feb 1999 00:49:35 -0500 (EST)
Subject: Re: Mersenne: Link from Knuth's Home Page
> At 06:51 AM 2/15/99 EST, you wrote:
> >fascicles
>
> What the devil is a "fascicle"? What you get when you mix liquid nitrogen,
> Stalin, Mussolini, and Hitler?
>From dictd:
root@riverdale:/home/jughead/slash-0.2# dict fascicle
3 definitions found
>From Webster's Revised Unabridged Dictionary (1913) [webster]:
Fascicle \Fas"ci*cle\, n.
One of the divisions of a book published in parts;
fasciculus.
>From Webster's Revised Unabridged Dictionary (1913) [webster]:
Fascicle \Fas"ci*cle\, n. [L. fasciculus, dim. of fascis. See
{Fasces}.]
A small bundle or collection; a compact cluster; as, a
fascicle of fibers; a fascicle of flowers or roots.
>From WordNet (r) 1.6 [wn]:
fascicle
n : an installment of a printed work [syn: {fascicule},
{fasiculus}]
regards
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
End of Mersenne Digest V1 #510
******************************
