Dual CPU usage (was: Re: Mersenne: Best chance to make a real contribution?)
On 22 Jan 00, at 15:44, St. Dee wrote: This brings up something I've been wondering about. I have a dual Celeron setup running 2 instances of mprime under Linux. With both processors crunching on LL tests, I get iteration times for each processor of around .263 for exponents around 899 (where they are presently cranking). However, if one of them factors while the other does LL testing, the processor doing the LL testing takes about .220 seconds per iteration, while the one factoring also shows a factoring speed more consistent with the speed I would expect for the processor speed. The "problem" here is that the two processors are sharing access to the memory bus. Trial factoring actually uses very little memory access (actually it runs more or less from the L1 cache!) whereas LL testing really does thrash the memory subsystem (unless you have a Xeon with 2MB L2 cache, and even then only if you're testing an exponent less than 10,320,000). I presume you have BX chipset and PC100 memory. Even so, asking for twice the 66 MHz bandwidth of each Celeron CPU is going to congest the memory subsystem, which explains the slowdown. However, the problem is not unique to dual Celeron systems. Unless you have a multi-processor system with a seperate memory bus for each processor - and some means of intercommunication e.g. multiporting - the same problem is going to strike. To the best of my knowledge, only very expensive server motherboards use this technology. (Compaq did have a dual CPU workstation MB based on this technology but they seem to have dropped it when 100 MHz systems came in.) For systems using large clock multipliers, increasing the throughput of the memory bus will help mprime/Prime95 performance substantially - even for uniprocessor systems. In my experience, systems running the VIA chipset using PC133 memory are very disappointing - my PIII- 533 is turning in times very similar to the PII-400 benchmarks. I get the impression that there is a 100 MHz bottleneck inside the chipset, even when CPU and memory buses are both set to 133 MHz. Or it's actually driving the CPU at 100 MHz irrespective of the board jumpers and setup. Intel's Rambus technology looks interesting from this point of view - and boards which use it are starting to filter on to the market. A practical problem is that Rambus memory is extortionately expensive - at least 4 times the price of SDRAM, and you can't even get modules smaller than 64 MB. Intel recently released a version of some boards using the 820 chipset (designed for Rambus) which can take 133 MHz SDRAM, but there is a "gearbox" between the SDRAM and the chipset which reduces the memory bus throughput compared with the native Rambus version - though whether it's any worse than you'd expect projecting from the benchmarks based on a 100 MHz BX chipset is unknown. My question is: Do I get more "work" done by having both doing LL testing, or would this box contribute more to the effort by having one CPU performing factoring while the other does LL testing? Personally I think you get better value by running 1 LL test 1 "something else" which doesn't make big claims on the memory bus. ECM factoring is quite light on the memory bus (though "larger" exponents i.e. above about 2,000 might have difficulty fitting well into the Celeron L2 cache, which is only 128K) and might make an interesting alternative to trial factoring. There are a considerable number of exponents which have been double- checked but have not been trial-factored to the full depth suggested by v19, running some of these would find a number of "first factors", though I don't think PrimeNet would credit you with the CPU time. Factoring (of any kind) will not find primes; trial factoring larger exponents which will be LL tested later will eliminate some candidates, and be credited by PrimeNet (if you use the "automatic" method of reporting assignment results); other types of factoring would be done out of pure interest, to find new or first factors only. Also, the PrimeNet rankings for LL testing factoring are seperate rather than cumulative. If you split your work, your LL testing effort will be reduced compared with what it would be if you ran LL tests on both CPUs. As a compensation, you would zoom up the factoring rankings! Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Best chance to make a real contribution?
On 22 Jan 00, at 11:35, Gerry Snyder wrote: But finding a factor (or another factor) of a Mersenne number would seem more real. Is there any significant probability that two 500 MHz Celerons and one 333 MHz Celeron could accomplish such a feat in a couple of years? Depends where you look - last summer I found tens of thousands of smallish factors of Mersenne numbers in the 10 million digit range in a few minutes on a PII-350. On the other hand, many, many CPU years have been spent by various people trying to find any factor of the relatively small composite Mersenne number 2^727-1 without success. You get kudos in proportion to the "difficulty" of the task you achieve (essentially this depends on luck, though you can help it along by supplying as much "horsepower" as possible). However, so far as I'm concerned, the main idea is to have fun. Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring beyond ECM
LiDIA is a free package for long number arithmetic. It includes a demo-program for factoring numbers with trial factoring, ECM and MPQS successive. See here: http://www.informatik.tu-darmstadt.de/TI/LiDIA/Welcome.html regards Martin -Ursprüngliche Nachricht- Von: Foghorn Leghorn [EMAIL PROTECTED] An: [EMAIL PROTECTED] Gesendet: Samstag, 22. Januar 2000 23:24 Betreff: Mersenne: Factoring beyond ECM I'm interested in trying to factor composite numbers with 100 to 200 digits. ECM becomes impractical for numbers without any factors below 50 digits or so. I have heard of algorithms such as MPQS which are used to tackle larger numbers. Are there any (preferably free) implementations of this method (or another) that would be feasible to run on a home PC or Unix workstations? Foghorn Leghorn [EMAIL PROTECTED] _ 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
Mersenne: Odds on finding a factor ?
Dear List-reader, I've been running Prime95 on my PII-400 at work, since December, and I'm currently on my second LL test ! And I've also been running it on my Celeron366 Laptop at home (When my wife isn't playing Settlers 3). I decided to make the Laptop do Factoring, and I've factored five numbers, all in the 1165-1166 range, as allocated by Primenet, without finding a factor. So my question is, What are the odds on finding a factor ? I've looked in all the FAQ's, including the mailing list one, and can't find it anywhere. I know that the odds for a LL test are 1 in 6, but I can't find out what the odds on finding a factor are ? Presumably all the non-prime numbers have a factor so the odds should be 1 in 5, but most of these factors must be higher than 2^64 (Yes/No) ? So what are the odds on a factor that prime95 will find ? Alex Phillips Campaign for Unmetered Telecommunications http://www.unmetered.org.uk Campaigning for a fair choice in telecommunications _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Odds on finding a factor ?
From a quick browse through the top 101-500 producer list (it's the one I'm in:) it looks like the odds say you can expect 10-15 factors per P90 year spent on factoring. Based on my own stats, I've got 13.959 P90 years spent factoring, with 177 factors found. That's 12-13 per P90 year, so you're estimate fits in my case at least. Currently, I'm #8 in the factoring, but slipping fast. :-) My quick checks on the top 10 factorers show that *usually*, the ratio is the same, but for some of those top factorers, the ratios are much higher (20-23 per P90 year). I would guess that since those folks concentrate more on factoring, they got some numbers that were not tested even up to 52-55 bits yet, so probably found more small factors than the rest of us will. Aaron _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Odds on finding a factor ?
Hi, At 02:28 PM 1/23/00 -, Alex Phillips wrote: I've factored five numbers, all in the 1165-1166 range, as allocated by Primenet, without finding a factor. So my question is, What are the odds on finding a factor ? Since these exponents are already factored to 2^52 and you will be factoring to 2^64, your chance of NOT finding a factor is about 52/64. Thus, your chance of finding a factor is about 1 in 5.3. Regards, George _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Size of largest prime factor
If I pick a huge number n at random, how much smaller than n, on average, is its largest prime factor? phma _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Size of largest prime factor
At 03:48 PM 1/23/00 -0500, Pierre Abbat wrote: If I pick a huge number n at random, how much smaller than n, on average, is its largest prime factor? On the average, the largest prime factor of n is n^0.6065, and the second largest is n^0.2117. Reference: Knuth, the Art of Computer Programming, vol 2, section 4.5.4. ++ | Jud McCranie | || | 137*2^197783+1 is prime! (59,541 digits, 11/11/99)| | 137*2^224879+1 is prime! (67,687 digits, 1/00)| ++ _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: NFSNET
On Sat, 22 Jan 2000, George Woltman wrote: Finding new factors of small Mersennes, so called Cunningham factors, is getting more difficult. ECMNet and GIMPS have picked off most of the "easy" factors. I have two CPUs running ECM full-time. The last Cunningham factor I found was last summer. I do occasionally find new factors of medium-sized (1200 to 10) Mersenne numbers. If finding factors by ECM is becoming more difficult we need to start factoring these numbers by NFS. Even if a factor is found by ECM it may not completely factor the number. Unlike ECM, NFS is guaranteed to factor the number. Of the Mersenne numbers, NFSNET is doing M629 and M641. M641 has a 148 digit composite cofactor. Enough ECM has been done to make it unlikely to have a factor of less than 45 digits. NFS can't take advantage of the known primitive factors, it must be used on the whole 193 digit number. It will be the second most difficult SNFS factorization done and is one of the Cunningham projects most wanted. There are many "easier" 2^p+1 numbers that NFS can factor. It would be more productive to use NFS than ECM on these numbers. The NFSNET page is at http://orca.st.usm.edu/~cwcurry/nfs/nfs.html We are currently working on M641 and 2,1542M (a factor of 2^1542+1). _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Size of largest prime factor
But (assuming n is composite) no prime factor of n can be greater than n^0.5. So how can n^0.6065 be the average? (I hope I'm not showing my idiocy here! :) Kyle Evans (newbie on this list) -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]]On Behalf Of Jud McCranie Sent: Sunday, January 23, 2000 4:00 PM To: Pierre Abbat Cc: [EMAIL PROTECTED] Subject: Re: Mersenne: Size of largest prime factor At 03:48 PM 1/23/00 -0500, Pierre Abbat wrote: If I pick a huge number n at random, how much smaller than n, on average, is its largest prime factor? On the average, the largest prime factor of n is n^0.6065, and the second largest is n^0.2117. Reference: Knuth, the Art of Computer Programming, vol 2, section 4.5.4. ++ | Jud McCranie | || | 137*2^197783+1 is prime! (59,541 digits, 11/11/99)| | 137*2^224879+1 is prime! (67,687 digits, 1/00)| ++ _ 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
RE: Mersenne: Size of largest prime factor
Never mind. My idiocy is admitted. :) It's the LOWEST prime factor that can't exceed n^0.5. Sorry for the trouble. Kyle E. -Original Message- From: Kyle Evans [mailto:[EMAIL PROTECTED]] Sent: Sunday, January 23, 2000 4:51 PM To: Jud McCranie; Pierre Abbat Cc: [EMAIL PROTECTED] Subject: RE: Mersenne: Size of largest prime factor But (assuming n is composite) no prime factor of n can be greater than n^0.5. So how can n^0.6065 be the average? (I hope I'm not showing my idiocy here! :) Kyle Evans (newbie on this list) -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]]On Behalf Of Jud McCranie Sent: Sunday, January 23, 2000 4:00 PM To: Pierre Abbat Cc: [EMAIL PROTECTED] Subject: Re: Mersenne: Size of largest prime factor At 03:48 PM 1/23/00 -0500, Pierre Abbat wrote: If I pick a huge number n at random, how much smaller than n, on average, is its largest prime factor? On the average, the largest prime factor of n is n^0.6065, and the second largest is n^0.2117. Reference: Knuth, the Art of Computer Programming, vol 2, section 4.5.4. ++ | Jud McCranie | || | 137*2^197783+1 is prime! (59,541 digits, 11/11/99)| | 137*2^224879+1 is prime! (67,687 digits, 1/00)| ++ _ 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
Re: Mersenne: Size of largest prime factor
But (assuming n is composite) no prime factor of n can be greater than n^0.5. So how can n^0.6065 be the average? (I hope I'm not showing my idiocy here! :) No, that's not correct. If n is composite, then it *must have* a prime factor n^.5, but it can (though not always) have one larger e.g. 217=7*31 sqrt(217)~=14.737, but 3114.73. -Lucas Wiman _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Size of largest prime factor
At 04:51 PM 1/23/00 -0600, Kyle Evans wrote: But (assuming n is composite) no prime factor of n can be greater than n^0.5. So how can n^0.6065 be the average? I'm not assuming that n is composite. Some of them are prime, and in that case the largest prime number is the number itself, and that brings up the average. ++ | Jud McCranie | || | 137*2^197783+1 is prime! (59,541 digits, 11/11/99)| | 137*2^224879+1 is prime! (67,687 digits, 1/00)| ++ _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: L-L Performance On PII/PIII XEON With 1M or 2M Cache
Team M: Has there been a reported run of MPrime on a PII/PIII XEON with at least 1M cache? If so what, if any, was the improvement? Regards, Stefan S. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Re: Mersenne: Odds on finding a factor ?
If you're factoring numbers in the 1165-1166 (bit) range, the first factor could be anywhere in the root(1165) - root(1166) range i.e. 3413 - 3414 bits long !! George's system prechecks to 2^52, and you are checking 2^52 - 2^64. There's still a long way from 2^64 to 2^3413 !! I'd have thought your odds of finding a factor are a lot smaller than 12 / 64 - probably closer to 12/3361 - and that's only if we pretend that the power series 2^n is a linear series he he he. Ala UBASIC, I estimate your real odds might be 4096 / 32989426643240701483986993770935879632714536463200834099702279000990323400845506277491238625469065799538799279719128688693415406076675530724056704926101784285634753285319263538813063962473878985845765797845382055337410440541344284339559168809418760420390481478282631414197807485742686389211555474213360120263991042780466426554289607050263290603052932269781896923601167447335692297055310057722218974401098206912973223458043228893199068964860334959883380891047401094866827202436849064674042859442415444909323924665551800675608529710402787571709270778808353338056583984539214599795637132555384173747564573799652452887403289984970168150936830142761015018525288690378571739745875603105853883771805379459256782614783580420623573859821949368686420256825421270831663687631501030074365192655752808545130451931636125256136601341096259794595447757151468551319326463387407612700784225723686398209046372801607655715856866505731790293078961776887506795295596160507661321192454505544316814816212744874172554054248307360609913496327637545196093414411166298407300058885128192 Sorry to be the Grim Reaper, but I've spent months with UBASIC eliminating factors in the 32,000,000 to 48,000,000 range - I'm only on about 24% eliminated using multiples 2pk+1 where k is 1 to 2^16 - and there's no doubt that the density of factors decreases as the multiplier increases. Finding the first few % is easy - finding the last 1% might take forever !! However I am using DaveNET - One P133 Laptop only, shared with the wife's chatting and E-Mail, and the kid's games !! Dave
Re: Re: Mersenne: Odds on finding a factor ?
If you're factoring numbers in the 1165-1166 (bit) range, the first factor could be anywhere in the root(1165) - root(1166) range i.e. 3413 - 3414 bits long !! No, in the x-y bit range (remember that n bit integers are about 2^n) the first factor could be x/2 to y/2 bits long (powers of a power multiply). I'd have thought your odds of finding a factor are a lot smaller than 12 / 64 - probably closer to 12/3361 - and that's only if we pretend that the power series 2^n is a linear series he he he. see http://www.utm.edu/research/primes/glossary/MertensTheorem.html Ala UBASIC, I estimate your real odds might be 4096 / 3298942664324070148398699377093587963271453646320083409970227900099032340084550 [...] Abreviate! Use scientific notation... Sorry to be the Grim Reaper, but I've spent months with UBASIC eliminating factors in the 32,000,000 to 48,000,000 range - I'm only on about 24% eliminated using multiples 2pk+1 where k is 1 to 2^16 - and there's no doubt that the density of factors decreases as the multiplier increases. Finding the first few % is easy - finding the last 1% might take forever !! Why are you only setting k==1 mod 2^16? (I'm probably missing something obvious) I think under windows that dos windows only run when they are "up". (I could be wrong, I've stopped using windows again) You would probably get better results with Will Edgington's mersfacgmp program, and DJGPP (a port of g++ to dos). -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Re : Odd's on finding a factor (part 2)
Sorry, I'm no mathematician, and new to the Mersenne field. No, in the x-y bit range (remember that n bit integers are about 2^n) thefirst factor could be x/2 to y/2 bits long (powers of a power multiply). What I was trying to say in my disjointed way was ... (Example) M11 = 2047 (11 bits long). Now 2047 has only 2 factors (23 x 89) and the square root of 2047 is approx 45. 45 is 6 bits long, therefore the factor lower than the square root must have = 6 bits, and the factor higher than the square root must have =6 bits. 23 is 5 bits long, and 89 is 7 bits long. Thus for the exponent 1165 bits long, if it only has 2 factors , then the first factor must be between 2 and 3413 bits long, and the second factor must be between 3413 and 1164 bits long. Note that the bit lengths of the 2 factors added together must equal the bit length of the Prime (or bit length of the Prime + 1) !! Abreviate! Use scientific notation... Ooops. Why are you only setting k==1 mod 2^16?(I'm probably missing something obvious) Yes, my failure to express myself properly - I meant I test each exponent with all k multipliers in the range 1 to 2^16. I think under windows that dos windows only run when they are up. Under Win 98, they chug along quite happily in the background, unless you're running some other DOS box in Full Screen mode (I think). You would probably get better results with Will Edgington's mersfacgmpprogram, and DJGPP (a port of g++ to dos). I'll check it out. I'm using UBASIC because for testing factors of large Mersenne, I don't need to actually represent the full Mersenne Prime. If you're familiar with UBASIC try ... Result = MODPOW(2,MersenneExponent,TrialFactor) where TrialFactor is the MersenneExponent * 2 * (some k in range 1 to 2^16) + 1. If Result = 1 then TrialFactor divides the Mersenne Prime. As UBASIC can handle around 2600 decimal digits, in theory (and with a lot of time), I could check all factors up to 2600 decimal digits for any given exponent. It's a damn sight faster than filling 16MB+ of memory with 1's and then trial dividing.
