Mersenne Digest Wednesday, February 16 2000 Volume 01 : Number 694 ---------------------------------------------------------------------- Date: Sun, 13 Feb 2000 14:55:46 EST From: [EMAIL PROTECTED] Subject: Mersenne: Re: Mersenne Digest V1 #693 Please make this go away. Stop sending me this stuff _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 13 Feb 2000 16:12:25 EST From: [EMAIL PROTECTED] Subject: Mersenne: Re: the flaw in the ointment Jeremy Blosser wrote: >So for each squaring, we have x left shifts and adds, where x is no larger >that p. Hi, Jeremy: A couple years ago I discussed the same issue with an old schoolfriend of mine, who is a specialist in microelectronics. He said, sure, with a giant binary shifter (perhaps implemented via a programmable logic array) one could do this, but after crunching the numbers some more we both concluded that for large Mersennes, this is not an effective alternative to a fast- tranform-based squaring. Here's one way to think about it: imagine you have two microprocessors, one doing general-purpose math (i.e. a typical 64-bit RISC) and doing Mersenne-mod multiply via FFT, the other a dedicated shift-and-accumulate unit. Both will be assumed to operate at the same clock frequency. The general-purpose unit might do an FFT-based squaring using 64-bit floats, which allows input digits of nearly 20 bits (for p up to the several millions), and will thus do around 10*(p/20)*log(p/20) floating-point operations (the multiplier of 10 is a typical figure, based on the cost of doing both a forward and an inverse FFT per squaring. Now, for the shift-based chip, there are two ways to approach the squaring: 1) Distribute the multi-million-bit operands across many smaller memory units (e.g. 64-bit memory fields) and have one or a few arithmetic units shift each of these and accumulate the results. Even if we can do a full shift-accumulate step (including any carry bit from the previous digit) per cycle, this will need p*(p/64)/[nshifter] (i.e. O(p^2)) cycles, where [nshifter] is the number of 64-bit shitf-accumulate units and these are assumed to be executing in parallel. So, unless [nshifter] is very large, it's going to be really slow. So, you say, let's just make [nshifter] very large, and in the limit where [nshifter] is so large that all the operand bits get shifted every cycle, one has 2) A giant shift-and-accumulate register, which needs just p cycles to do the modular squaring irrespective of the size of p. i.e. beats even the FFT-based squaring by a factor of O(log p) in terms of speed. The thing that kills this approach is power consumption - even if it needs just O(p) cycles to do a squaring, it's still doing O(p^2) bitwise operations per squaring, and thus has a power dissipation that is O(p). The FFT-based scheme, on the other hand, even assuming one is keeping a 64-bit floating adder and multiplier completely busy, spreads O(p log p) operations over the same order of cycles, i.e. has a constant power dissipation that is order of unity. Just imagine: if the O(1) power dissipation of the FFT-based scheme still translates into a piece of silicon about 1 cm^2 dissipating (say) 30 watts, how hot is a similar-sized piece of silicon dissipating O(p)*30 watts going to get? Now, if (or when) commodity hi-temperature-superconductor-based microprocessors become available, the power draw becomes negligible, and then scheme (2) perhaps becomes attractive. It certainly looks easier to code! - -Ernst _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 14 Feb 2000 11:18:39 +0100 From: Paul Landon <[EMAIL PROTECTED]> Subject: Mersenne: Who was the first to use a computer to tests Mersennes? Part 1 As I was guilty of starting something by hastily and provocatively writing:- > The first real computer was the Manchester Mark 1 aka > the SSEM or the "Baby". ...I had best define "real computer". Apologies for the length of this mail, it grew whilst I carried on following various paths of inquiry. Whilst sorting out my own mind, I came to the conclusion that the best definition of "real computer" has to be one where the computer is capable of running a respected benchmark. Therefore my definition is that it should be capable of running a primality test, preferably on a Mersenne :-) Last but least, it not only should be capable of doing it, but it should have done it. It is not valid if the hypothetical Left sisters had belatedly announced that they had built a flying machine, but never flew it. Therefore I was just about to award the honour of First Real Computer to SWAC (built late 1950) which found for Robinson (assisted by D. H. & E. Lehmer) M521, M607, M1279, M2203 & M2281 in 1952, but... [Structuring my thoughts chronologically] In reply to Luke Welsh, Ernst Mayer wrote:- > The stored-program idea goea back at least to 1805, when Jacquard used > strung-together sequences of hole-punched wooden cards to control the > weaving patterns of his famous loom. A few years later, Babbage used > the same stored-program idea (also with puched cards) for his difference > engine. Von Neumann himself usually credited the idea to Turing, who > advocated its use years before. The Jacquard cards were just an input, not a storage media. For the loom to be a computer it needed at least a card punch and for the output to be looped back to the input. Even with a stored programme this still isn't a real computer. There also needs to be some decision making that alters the path of execution of the control programme. Charles Babbage whilst building the Difference Engine in 1832 was greatly assisted and inspired by Ada Byron, Countess of Lovelace. Ada was the true visionary who foresaw the magic of viewing the numeric representation as symbols of operations, where the symbols themselves could be operated on by the engine. > "It may be desirable to explain, that by the word operation, we mean > any process which alters the mutual relation of two or more things, > be this relation of what kind it may. This is the most general > definition, and would include all subjects in the universe . . . They > will also be aware that one main reason why the separate nature of > the science of operations has been little felt, and in general little > dwelt on, is the shifting meaning of many of the symbols used in > mathematical notation. First, the symbols of operation are frequently > also the symbols of the results of operations . . . Secondly, figures, > the symbols of numerical magnitude, are frequently also the symbols > of operations, as when they are the indices of powers [e.g., 2 and 32] > . . . [In] the Analytical Engine . . . whenever numbers meaning > operations and not quantities (such as indices of powers), are > inscribed on any column or set of columns, those columns immediately > act in a wholly separate and independent manner . . . " Babbage's Analytical Engine was meant to be a mechanical stored programme machine, with separate data and programme, but it was never built. Andrew Hodges, author of the book "Alan Turing: The Enigma" and also the Alan Turing Internet Scrapbook at http://www.turing.org.uk/turing/ wrote > I wouldn't even call Charles Babbage's 1840s Analytical Engine > the design for a computer. It didn't incorporate the vital idea > which is now exploited by the computer in the modern sense, the > idea of storing programs in the same form as data and > intermediate working. Luke Welsh wrote about the Atanasoff Berry Computer from Why Computers Are Computers: The SWAC and the PC by David Rutland > "The machine was not really a general purpose computer as > it was more like Babbage's Difference Engine than the Analytical > Engine. Its control circuits were wired to do one and only one > important task: the solution of simultaneous algebraic equations. > > Although parts of the machine were built and proven, it was never > put into full operation." I don't think that this was capable of testing primality, even though it worked in binary so calculating modulo 2^p-1 is convenient. Whilst this machine was deemed to be "prior discovery" to Eckert's and Mauchly's ENIAC, there were earlier (slower & simpler) automatic electronic calculators. The court case did not prove that the ABC was the first. There is no legal or commercial motivation for earlier calculators or later superior designs to debate in a US Court that they were the first. Vincent J. Mooney Jr. wrote:- > the judge, Earl R. Larsen, ruled "Eckert and Mauchly did not > themselves first invent the automatic electronic digital computer, but > instead derived that subject matter from one Dr. John Vincent Atanasoff". In 1940 George Stibitz demonstrated the Complex Number Calculator. As I work for them I had best mention Bell Labs. "Bell Labs" - there I've done it. This has been called the first working Automatic Electronic Computer, but it had no stored programme. The intended application for all of these were the calculations for military ballistics such as bombing tables. The Zuse Z3 was a relay based electromechanical floating point calculator - neat! One application for it was ironically anti-aircraft calculations. It's usefulness (and Zuse's Berlin apartment) was ended towards the end of the war by an application of American or British military ballistics. Zuse himself continued with the valve based Z4 and went on to develop commercial computers for Siemens. ENIAC was completed on 15th February 1946, but it was basically a Numeric Integrator, a very very good one, but was barely programmable. I have recently learnt that at the end of 1948 a programme store was added but this was not manipulable like data. Before then reprogramming could take days and involved recabling and even moving cabinets. Up to and including this point X modulo m was possible, but would have been calculated by the inefficient r := X - ( (X DIV m) * m ) continued..... Paul Landon _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 14 Feb 2000 11:26:37 +0100 From: Paul Landon <[EMAIL PROTECTED]> Subject: Mersenne: Who was the first to use a computer to tests Mersennes? Part 2 ...continued In Raphael M. Robinson,"Mersenne and Fermat numbers," Proc. Amer. math. Soc., 5 (1954) 842-846. (Announces the discovery of the 13th through 17th Mersenne primes --the first Mersenne primes found by electronic computer), Robinson credits Turing (presumably on "Baby" - - the Manchester Mark 1) as being the first to test Mersennes! > In 1951, the first application of an electronic computer to testing > Mersenne numbers for primeness was made by A. M. Turing at the > University of Manchester; however, no new primes were found, and no > remainders were saved for purposes of comparison. > In 1952, a program for testing Mersenne numbers for primeness on > the SWAC (the National Bureau of Standards' Western Automatic > Computer, at the Institute for Numerical Analysis in Los Angeles), > planned and coded by the author, using Lucas's test, was carried > out, with the cooperation of D. H. Lehmer and the staff of the > I. N. A. My thanks are due especially to Emma Lehmer, who did > various auxiliary computations, including checking some of the > results obtained against earlier results. The program was first > tried on the SWAC on January 30, and two new primes were found that > day; three other primes were found on June 25, October 7, and > October 9. > > At that time, the total memory of the SWAC consisted of 256 > words of 36 binary digits each, exclusive of the sign. For the > Mersenne test, half of this memory was reserved for commands. Since > successive squarings of numbers less than the modulus 2n-1 are required, > this modulus was restricted to 64 words, so that the condition > n < 64 * 36 = 2304 was imposed. The estimated running time for the > program was 0.25n3+125n2 microseconds, and the actual time was in fair > agreement with this. Thus, roughly speaking, the testing time was a > minute for the first and an hour for the last of the five new primes. > Each minute of machine time is equivalent to more than a year's work > for a person using a desk calculator. The full text is hosted by Luke Welsh at http://www.scruznet.com/~luke/lit/lit_024s.htm (That has O(n^3), more than George's great implementation of the LL test. The Lucas-Lehmer algorithm was created in 1930, but they must have used Grammar School multiplication as the Karatsuba method or Fourier Transforms had not been invented yet). Ribenboim in The New Book of Prime Number Records also states that the first was Turing in 1951 (I believe incorrectly). Turing's designs (1945-46) for the Pilot ACE, which was finally built in 1950 at the National Physics Laboratory after Turing's resignation, were not incorporated directly into "Baby" - the Manchester Mark 1. The NPL is in Teddington, south of London. Turing started work in Manchester in March 1948, by which time "Baby" was nearly completed. It was completed on June 21st 1948. The computer that Turing was working on from June 1948 onwards was the "Baby", not his Pilot ACE. But, Chris Caldwell's excellent Prime Pages at http://www.utm.edu/research/primes/notes/by_year.html#MW > It is interesting to note that in 1949 the topologist M. H. A Newman > used the prototype Manchester electronic computer (with 1024 bits of > storage) to make the first attempt to find Mersenne primes by computer. > Perhaps because Alan Turing worked on this machine from 1948 to 1950, > and improved the program by Newman, this first attempt at finding > primes by (electronic) computers is sometimes attributed to him (e.g., > [Robinson54] and [Ribenboim95, p93]). The excellent Alan Turing > Internet Scrapbook has a picture of this machine. The Scrapbook has links to pictures of the Pilot ACE and "Baby". The Cambridge University EDSAC, based on EDVAC, was operational on May 6th 1949 (not 1948 as erroneously reported in some sources), but still before EDVAC, which wasn't working until late 1951. So before SWAC or EDVAC there were already 3 working electronic stored programme computers, which although slower had a couple of superior concepts. The ERA Atlas I (or, 1101 in its commercial designation) which was delivered to the Navy in December 1950 had a drum memory of 16,384 24-bit words, but no stored programme. http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Newman.html says of Professor Newman:- > In 1942 he joined the Government Code and Cipher School and worked > there with Turing. At the end of the War he was appointed to a chair > at Manchester and, 3 years later, he appointed Turing to the post of > Reader in Mathematics at Manchester. Andrew Hodges in the Alan Turing Internet Scrapbook writes:- > In February 1946, as you can read more about in my book, Newman wrote > to von Neumann that he was > hoping to embark on a computing machine section here, having > got very interested in electronic devices of this kind during > the last two or three years. By about 18 months ago [i.e. soon > after D-Day, and a year before von Neumann's EDVAC report] I > had decided to try my hand at starting up a machine unit when > I got out. It was indeed one of my reasons for coming to > Manchester that the set-up here is favourable in several > ways... I am of course in close touch with Turing... > Note that at this date, Turing had not even had his ACE proposal > accepted by the National Physical Laboratory; these were very early > days. > > Newman's intention was that the machine would be used for pure > mathematical work in algebra and topology, for instance the Four > Colour Theorem. The Royal Society approved the project and allocated > a grant to Newman for salaries and construction totally �35,000 > (about a million pounds in real terms now), with the comment that > 'Newman himself, because of his mathematical background and wartime > experience, is particularly well qualified for directing this project.' > At that stage, early 1946, Newman expected that that the American > Iconoscope would become available as the storage system. But it didn't > work. Meanwhile at the radar establishment, TRE, the top electronic > engineers had found themselves suddenly out of a job in August 1945. > F. C. Williams looked around for a leading-edge project. He soon > heard that the possibility of building electronic computers was in > the air and that creating a storage system was the main technological > bottle-neck. continued... Paul Landon _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 14 Feb 2000 11:34:03 +0100 From: Paul Landon <[EMAIL PROTECTED]> Subject: Mersenne: Who was the first to use a computer to tests Mersennes? FINAL PART ...continued Alan Hodges continues with the section Using The World's First Computer http://www.turing.org.uk/turing/scrapbook/manmach.html > Using the world's first computer > F. C. Williams himself had no interest in the use of the machine > he had built. Speaking in an oral history of Pioneers of Computing, > Science Museum, 1976, he said: > > Well let's be clear right from the start, I never have been > interested in computing, and I'm still not interested in > computing. What I'm interested in is computers. I'm an engineer, > I define the computer right from square one as a device which > was designed to facilitate the performance of mathematics, the > greater part of which would be very much better not done, and > I've never changed that view really... > > Users were seen as rather a nuisance while the machine was in > development, but Newman immediately found a genuine mathematical > problem that could be run on the prototype Manchester computer, and > thereby rescued a little of the originally intended function for the > machine in pure mathematics. > This was the problem of finding Mersenne primes. > At that time the largest known prime was 2^127 - 1, and had been so > since 1876, when Lucas discovered a test for primality of numbers > of this type, a test which was extremely well suited to a computer. > They ran a program successfully, and then Turing coded a faster > version of it, but even so did not discover the next prime, which > was out of range at 2^521 - 1, and found only in 1952. > > The largest known prime now is again a Mersenne prime, and found > by exactly the same method, only on a somewhat larger and faster > computer). [snip] > The 1949 programme gained newspaper publicity for the Manchester > computer, although (or because) readers of the day would have > assumed prime numbers to be the epitome of pure mathematical > uselessness. Nowadays these investigations are seen rather > differently because of the connection between large primes and > cryptographic security. As usual the mathematicians were ahead of > their time. !!! I like Williams! Note that it is claimed that the 1949 search for Mersenne Primes was documented in a newspaper. In conclusion, it is strongly probable that:- Prof. Newman at Manchester University was the first person to use a computer to test Mersennes using "Baby" the Manchester Mark 1 in 1949. Please have a read about "Baby" - The First Real Computer on:- http://www.computer50.org/mark1/index.html Regards, Paul Landon As an off-topic footnote, anyone interested in History or Biographies should look up the some of the flowery characters mentioned above. Some biographies have been "ethically cleansed" and have missing data, data that should never be allowed to detract from their Mathematical and Engineering greatness but is still fascinating. Some of those stories could cause tittering schoolboys to find Maths interesting or sniggering schoolgirls to enjoy Computing. They could even be used to justify increased Federal funding; so that this century's Ada doesn't have to finance herself that way ;-) _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 14 Feb 2000 11:52:16 -0600 From: "Robert G. Wilson v" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: Smooth and hairy numbers I would think that 2^727 -1 would qualify as hairy. [EMAIL PROTECTED] wrote: > If smooth numbers are ones whose prime factors are all small, > what then are hairy numbers? Is there an official definition? > > "And Jacob said to Rebekah his mother, Behold, Esau my > brother is a hairy man, and I am a smooth man:" (Gen. 27:11) > > George S. > > _________________________________________________________________ > Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm > Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 14 Feb 2000 14:14:47 -0500 From: "Frank_A_L_I_N_Y" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: Smooth and hairy numbers I would be more worried about a more exact definition of the word small. - -----Original Message----- From: Robert G. Wilson v <[EMAIL PROTECTED]> To: [EMAIL PROTECTED] <[EMAIL PROTECTED]> Cc: [EMAIL PROTECTED] <[EMAIL PROTECTED]>; [EMAIL PROTECTED] <[EMAIL PROTECTED]>; [EMAIL PROTECTED] <[EMAIL PROTECTED]>; [EMAIL PROTECTED] <[EMAIL PROTECTED]> Date: Monday, February 14, 2000 1:14 PM Subject: Re: Mersenne: Re: Smooth and hairy numbers >I would think that 2^727 -1 would qualify as hairy. > >[EMAIL PROTECTED] wrote: > >> If smooth numbers are ones whose prime factors are all small, >> what then are hairy numbers? Is there an official definition? >> >> "And Jacob said to Rebekah his mother, Behold, Esau my >> brother is a hairy man, and I am a smooth man:" (Gen. 27:11) >> >> George S. >> >> _________________________________________________________________ >> Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm >> Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers > >_________________________________________________________________ >Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm >Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 16 Feb 2000 22:25:57 +0900 From: "Kotera Hiroshi"<[EMAIL PROTECTED]> (Kotera Hiroshi) Subject: Mersenne: 23-digit numbers Hi all Is a decimal 23-digit numbers 11111111111111111111111 prime ? Could you tell me the answer with proof? 24-digit numbers 11111111111111111111 = 101*1100110011001100110011 regards ++++++++++++++++++++++++++++++++++++++++++ $B>.;{!!M5(B 630-8144$B!!F`NI;TEl6e>rD.(B1014-4 phone : 0742-61-8521 email : [EMAIL PROTECTED] URL : http://www.asahi-net.or.jp/~nj7h-ktr/ ++++++++++++++++++++++++++++++++++++++++++ _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ End of Mersenne Digest V1 #694 ******************************
