Mersenne Digest Friday, July 23 1999 Volume 01 : Number 602 ---------------------------------------------------------------------- Date: Thu, 22 Jul 1999 11:26:03 -0400 From: Pierre Abbat <[EMAIL PROTECTED]> Subject: Mersenne: Computing noises; was Worth it? > (Off topic, when I computed that value in Landon's Calc program, my computer > PII/233 started making a weird humming noise. The noise stopped when the > calculation finished. Very strange indeed...) I'm running Prime95 on a computer at the office, and it emits faint cricketish noises from the speakers while it's working. phma _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 22 Jul 1999 16:50:34 +0100 From: Gordon Spence <[EMAIL PROTECTED]> Subject: Mersenne: Re: Allocation of Prize Fund I have watched with interest the ideas flowing around for the distribution of the prize money awarded by the EFF and how we should try and reach an equitable distribution. In fact the answer is simple, the person who discovers it is *entitled* to it, end of story. I would hope that they would *choose* to donate some to George and Scott, but if they decide not to well then that is up to them. Direct quote from eff page > > Through the EFF Cooperative Computing Awards, EFF will confer prizes of: > $50,000 to the first individual or group who discovers > a prime number with at least 1,000,000 decimal digits Seems clear to me, the GIMPS s/w is given away free to the individual who runs the test. If we want to amend that then George will (or have to get drawn up) a legally binding software license. Now of course if the next winner comes from a country who doesn't recognise US laws... Now that would be interesting, what would the EFF do then given that they are entirely about freedom and the rights of the infividual. As a Mersenne prime discoverer it would appear that I would be on the panel(s) that have been suggested, and my vote goes to allowing the discoverer to keep it and do what their conscience tells them is the right thing to do. I don't agree with Luke's sentiments about orderly progress, having already tested one number in the 20m range. As soon as V19 is available I'm jumping up into the 33-35m range. As long as they all get tested does it matter in what order? So a test will take my PII-300 about 3 years, so what, if I've got the patience....I can always switch the intermediate results over to faster processors as I get them. regards Gordon Spence (finder of M2976221 which earned me precisely $0.00 <G> ) _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 22 Jul 1999 10:47:39 -0600 From: "Blosser, Jeremy" <[EMAIL PROTECTED]> Subject: Mersenne: Squaring algorithm... Just was thinking the other day about this... Forgive me if its been discussed before etc. Aren't there other "better" algorithms for finding the square of a number besides using an FFT? Sure an FFT is great for multiplying two different numbers, but for squaring a number isn't the case a little different. Plus, going off what I've read on FFT's, it runs in O(n log n) time. So wouldn't a summation algorithm work better. For example, to find the square of a number k take the sum of n=1 to n=k of 2n-1. So 3**2 is 1+3+5 = 9 4**2 is 1+3+5+7 = 16 etc... So the sqaure performs in O(n) time. Plus, you could already throw in the sub 2 by starting at -1 instead of 1. And figuring out the mod is just as easy. k is the sum of n=2**p-1 to n=k of 2n-1 (This would give k**2 - 2**p-1). The only hassle is adding *big* numbers up, but I'm not sure how the ramifications of doing carries across boundaries and such would factor into the equation etc. Just a thought. - -Jeremy _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 22 Jul 1999 19:11:07 +0200 From: "Hoogendoorn, Sander" <[EMAIL PROTECTED]> Subject: RE: Mersenne: The sound of number searching Read the archives, this has been discussed 2 or 3 times before - -----Original Message----- From: burlington john [mailto:[EMAIL PROTECTED]] Sent: Wednesday, July 21, 1999 19:47 To: [EMAIL PROTECTED] Subject: Mersenne: The sound of number searching Hello Mersenne, Sorry for bad english its not my native language, thanks. I run mprime (or prime95 ntprime) on my laptop. When I start the programm on my notebook it makes a strange mechanical pulsing sound like an old damaged wheel or like an ill cricket. The sound doesn't come out of the speakers and is not the fan from the cpu. First I thought it is the fan probably it is getting hotter and then the spin is not perfect due the heat. But when I run other cpu stressing programms (rc5des) there's no sound. Then I thougth it is the harddisk but when the harddisk goes to sleep mode the noise is still there. Then I thought the speakers could be responsible. I removed the soundcarddrivers moved the volume control knob to 0: still hear the sound. When I press some areas on my notebook the sound disappers for a few seconds but then it comes back. The funniest thing is when I start other cpu stressing programms while (m)prime is running the sound is changing. Each programm plus (mp)prime changes the sound in a special way so I can recognize exactly on the noise which programms are currently runnig. Why the hell is my notebook making such strange noise when running this programm ? Any ideas ? I'm goning to get crazy listening that noise all the time. Best regards, Burlington mailto:[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 ------------------------------ Date: Thu, 22 Jul 1999 19:00:46 +0100 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: The sound of number searching On 21 Jul 99, at 21:46, Lucas Wiman wrote: > (Off topic, when I computed that value in Landon's Calc program, my computer > PII/233 started making a weird humming noise. The noise stopped when the > calculation finished. Very strange indeed...) Perhaps it was humming because it was happy ;-) Coincidentally, on 21 Jul 99, at 19:46, burlington john wrote: > I run mprime (or prime95 ntprime) on my laptop. > > When I start the programm on my notebook it makes a strange mechanical > pulsing sound like an old damaged wheel or like an ill cricket. > The sound doesn't come out of the speakers and is not the fan > from the cpu. Very recently I acquired a new Toshiba Satellite CDS4070 (Celeron Mobile 366 MHz), this is the first system I've had with Win 98 on it. (Actually I could have run Win 95 instead but decided to take the plunge) The power management is different to the other systems I've had - you can choose to either slow the CPU clock when it starts to get warm, or start the case fan first (then slow the CPU clock if it's still getting too hot). Obviously the sensible thing to do is to let the fan run if the system is on AC power, but it might make sense to let the CPU slow down if the system is running on its battery. Win 98 lets you configure the behaviour in these states seperately. The relevant fact about this is that the case fan is an axial fan set into the "back panel" of the case, which is only about an inch high. The fan is therefore quite small & needs to run quite fast to shift any significant volume of air. The "jet noise" is unexpectedly loud - certainly louder than a typical desktop system, but nowhere near the volume of my Alpha workstation. And it's _definitely_ fan, the HDD is almost silent, and in any case the jet of warm air can be felt. At "room temperature" (68F-75F, 20C-24C) the system is silent when idle, but the fan starts about 2 secs after starting Prime95, stopping a few seconds after Prime95 is stopped. I think the reason is that the FPU is normally inactive, when the FPU turns on because it's needed the CPU needs assistance with cooling. Neither John nor Lucas indicates which OS they're running, but I think most modern systems (even desktops) running an ACPI power management aware OS may behave in a similar fashion. Note that, even if you have fans running continuously, starting Prime95 (or any other program which drives the FPU hard) causes a CPU temperature rise of a few degrees, presumably due to the extra power draw when the FPU is active. Though on desktop systems with large heavy heat sinks, the temperature change is slow, i.e. of the order of minutes rather than seconds. > When I press some areas on my notebook the sound disappers for a > few seconds but then it comes back. Definitely sounds like fan to me. Maybe a loose wire or something is just touching the back of the fan blades? Distorting the case a bit by pressing on it moves the obstruction just far enough to be out of contact. > > The funniest thing is when I start other cpu stressing programms > while (m)prime is running the sound is changing. Each programm > plus (mp)prime changes the sound in a special way so I can recognize > exactly on the noise which programms are currently runnig. Maybe the system runs the fan at different speeds depending on the heat output. Usually when you run something else as well as Prime95 (or mprime - they're really the same program but packaged for different operating systems) the FPU is less busy than it would be if Prime95 was running on its own. So the fan might run slower, causing a different noise. The only other thing I can think of is that a piece of wiring - probably in the display - or a lump of foil EMF shielding resonating in sympathy with something driven by software. I don't think this is very likely, but such things are known. If this is what the problem is, then turning off the display whilst Prime95 is running might fix it, or the problem might not exist if Prime95 was running on a different exponent with a different FFT size. > > I'm goning to get crazy listening that noise all the time. Well, you could try configuring slow CPU speed instead of starting the fan, if that's what the trouble is. Or run factoring assignments instead - those don't use the FPU as much. Otherwise, either drop Prime95 8-( or go crazy, like the rest of us 8-) Regards Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 22 Jul 1999 14:55:45 -0400 From: Glenn McLaren <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: Allocation of Prize Fund > In fact the answer is simple, the person who discovers it is *entitled* to it, > end of story. I agree with Gordon. We need to get *real* here. Theres nothing like money to attract people to the search. I wouldn't mind betting that a large percentage of seti@home people would start searching for primes if they knew the amount of money on offer. It's a sad fact that many people are motivated by selfishness, but thats human nature. The moment you start splitting the prize is the moment someone else will release software in competion to us, and people will use it in the hope of gaining the whole prize for themselves. After all, why do you think when the lotto prize is large, more people buy lotto tickets ? Not because their chances are better, thats for sure. Greed is unfortunatly one of humankinds strongest motivations. Glenn _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 22 Jul 1999 15:06:38 -0400 From: Pierre Abbat <[EMAIL PROTECTED]> Subject: Re: Mersenne: Squaring algorithm... On Thu, 22 Jul 1999, Blosser, Jeremy wrote: > Just was thinking the other day about this... Forgive me if its been > discussed before etc. > > Aren't there other "better" algorithms for finding the square of a number > besides using an FFT? Sure an FFT is great for multiplying two different > numbers, but for squaring a number isn't the case a little different. Plus, > going off what I've read on FFT's, it runs in O(n log n) time. It runs in O(n log n) time where n is the number of digits in the number being squared, not the number being squared itself. Given any algorithm for squaring, there is an algorithm for multiplying that runs at the same speed to within a constant factor, and vice versa. Squaring is multiplying a number by itself, and multiplying can be done by subtracting the square of the difference from the square of the sum and dividing by 4. phma _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 22 Jul 1999 15:19:54 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: Squaring algorithm... > So the sqaure performs in O(n) time. Plus, you could already throw in the > sub 2 by starting at -1 instead of 1. And figuring out the mod is just as > easy. Yes, the runtime is proportional to some number, but that number is *not* the number of digits (as n usually means)! It is the number we are squaring! Unfortunatly, this would be quite inefficient compared even with traditional multiplying techniques. - -Lucas _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 22 Jul 1999 15:24:22 -0500 From: "Willmore, David" <[EMAIL PROTECTED]> Subject: RE: Mersenne: The sound of number searching All, There are several things in a computer which will have their operational parameters vary with CPU activity. The most likely ones are: audio subsystem receiving noise coupled either directly (magnetically) into its signal lines or via its power feed; or the load on the power regulation unit itself. Yes, coils do can make a buzzing sound. The name of the phenomina is 'magnetorestrictance' (who wants to be I spelled that one wrong?) which is the property of a material to change its physical dimensions under varying magnetic fields--it's the reason large power transformers 'hum' and how most high power sonar units generate their signals. If I remember correctly, this is an IFAQ, but could go in the FAQ so that the-word-which-will-go-unmentioned can get spelled correctly once and for all. Cheers, David _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 22 Jul 1999 14:26:42 -0600 From: "Blosser, Jeremy" <[EMAIL PROTECTED]> Subject: RE: Mersenne: Squaring algorithm... Ya, I didn't think *that* part through. :) When n=p (the LL test case with the size of the FFT and other things thrown in) as opposed to n=2^p (my case), then things are a *lot* different. > -----Original Message----- > From: Lucas Wiman [mailto:[EMAIL PROTECTED]] > Sent: Thursday, July 22, 1999 2:20 PM > To: [EMAIL PROTECTED] > Subject: Re: Mersenne: Squaring algorithm... > > > > So the sqaure performs in O(n) time. Plus, you could > already throw in the > > sub 2 by starting at -1 instead of 1. And figuring out the > mod is just as > > easy. > > Yes, the runtime is proportional to some number, but that > number is *not* > the number of digits (as n usually means)! It is the number > we are squaring! > > Unfortunatly, this would be quite inefficient compared even > with traditional > multiplying techniques. > > -Lucas > _________________________________________________________________ > 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: Thu, 22 Jul 1999 23:35:26 +0100 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: RE: Mersenne: The sound of number searching On 22 Jul 99, at 15:24, Willmore, David wrote: > There are several things in a computer which will have their operational > parameters vary with CPU activity. The most likely ones are: audio > subsystem receiving noise coupled either directly (magnetically) into its > signal lines or via its power feed; or the load on the power regulation unit > itself. I don't want to disagree with this. But computer systems almost invariably have switch-mode power supply units which operate in the 50 KHz - 200 KHz range, and are _most_ unlikely to have residual output in the audible range. I suppose you could get a "beat" resonance between a PSU residual and the scan frequency of the display, though. In my job (looking after network equipment) I've seen a lot of kit making "strange noises"; so far I haven't seen anything that wasn't easily explained by either debris contacting a revolving fan, loose wires or panels resonating from mechanical vibration, siezed fan bearings (which don't clear by changing the load a bit), or slipping drive belts (ditto). > Yes, coils do can make a buzzing sound. The name of the phenomina > is 'magnetorestrictance' (who wants to be I spelled that one wrong?) which > is the property of a material to change its physical dimensions under > varying magnetic fields--it's the reason large power transformers 'hum' and > how most high power sonar units generate their signals. I think you have it spelled right. Interesting about sonar - I just assumed they used piezoelectric crystals & a suitable diaphragm - that's the most efficient way I know to convert electrical energy into acoustic energy. Conventional moving-coil loudspeakers are a couple of orders of magnitude less efficient in dB/W terms. Yes, AC coils _do_ hum - at mains frequency - much to the annoyance of hi-fi enthusiasts, who refuse to sanction the use of switch mode power supplies because residual (supersonic) high frequencies can blur transient signals in the (wanted) audio output. Actually, the material in the coil doesn't change its dimensions, but the coil tries to ... the change in current creates a changing magnetic field, which tries to propel the wire in which the current is flowing due to the motor effect. The wire and its former are elastic to some extent, so there is some mechanical movement, which can be transmitted as vibration either through the surrounding fluid (air) or through the coil mounting. The way to deal with this (in extreme hi-fi) is to make the coil very, very large, so that the force per unit length of wire is small, and to embed the coil in something firm but compliant, like a huge lump of heat conductive solid grease, to absorb the mechanical vibration. Or, even more extreme but definitely better, run the kit from car batteries instead of directly off the mains. You may think I'm just being wierd, but I did used to know something about this, twenty years ago. Why does consumer electronic equipment tend to use switched mode power supplies? They're smaller, lighter, more efficient and cheaper, and, for most purposes, they do the job reasonably well. And they don't hum, though sometimes they can whistle - usually this means that overload has brought the operating frequency down into the audible range. The major _practical_ problem with switched mode power supplies, as opposed to the old-fashioned transformer & rectifier type, is that they're a lot more susceptible to being killed by transient overvolt surges on the supply. Back more or less to topic - when I was a computing neophyte, a quarter of a century ago, I was told a story by an engineer working for a major mainframe supplier. For a laugh, the development team wired up a loudspeaker (presumably through a buffer and amplifier of some sort) to one of the bits in a CPU shift register. (This was easily done in the days when everything was discrete components!) The trick was then to code your program so that it performed to specification, but, by insertion of extra instructions to tweak this particular bit at suitable times, played interesting tunes whilst doing so! Regards Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 22 Jul 1999 18:12:26 -0700 From: Luke Welsh <[EMAIL PROTECTED]> Subject: RE: Mersenne: The sound of number searching At 11:35 PM 7/22/99 +0100, Brian J. Beesley wrote: >Back more or less to topic - Oh, this is very much on topic! > when I was a computing neophyte, a >quarter of a century ago, I was told a story by an engineer working >for a major mainframe supplier. For a laugh, the development team >wired up a loudspeaker (presumably through a buffer and amplifier of >some sort) to one of the bits in a CPU shift register. (This was >easily done in the days when everything was discrete components!) >The trick was then to code your program so that it performed to >specification, but, by insertion of extra instructions to tweak this >particular bit at suitable times, played interesting tunes whilst >doing so! Alex Hurwitz loves this story. They did just that on the SWAC. It was captured for prosperity in the film 'Magnetic Monster'. I once made some MPegs and put them on the wwweb. I wonder if they are still there? Alex says the sounds in the movie were produced by LL tests. I recall the CDC 3150 was so wired from the factory. There was even a volume control on the operator's console. Probably a very helpful debug tool as you could not see the console when you were across the room with your head inside a 32 KB memory bank the size of a refrigerator, poking away looking for faulty a core memory. - --Luke _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 22 Jul 1999 21:26:57 -0700 From: "John R Pierce" <[EMAIL PROTECTED]> Subject: Re: Mersenne: The sound of number searching > > when I was a computing neophyte, a > >quarter of a century ago, I was told a story by an engineer working > >for a major mainframe supplier. For a laugh, the development team > >wired up a loudspeaker (presumably through a buffer and amplifier of > >some sort) to one of the bits in a CPU shift register. (This was > >easily done in the days when everything was discrete components!) > >The trick was then to code your program so that it performed to > >specification, but, by insertion of extra instructions to tweak this > >particular bit at suitable times, played interesting tunes whilst > >doing so! > > Alex Hurwitz loves this story. They did just that on the SWAC. It > was captured for prosperity in the film 'Magnetic Monster'. I once > made some MPegs and put them on the wwweb. I wonder if they are > still there? Alex says the sounds in the movie were produced by LL > tests. geez, in the early 70's when I was larnin' proggin', it was S.O.P. to keep a AM radio on top of the mainframe tuned between stations... you could get a REAL good idea exactly what the system was doing by the sounds it made on one of that vintage of multiprocessing batch machines. If it settled down on a steady warble, it was almost for sure cuz some student had looped his job, and it was time to get over to the console, find out who was hung and manually abort them. - -jrp _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 23 Jul 1999 01:27:39 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: Worth it? Here's something interesting, it *might* allow us to almost eliminate the x squarings in p-1 factoring. P-1 factoring is based upon Fermat's little theorem which states that with gcd(a,p)=1, p prime, a^(p-1)==1 mod p. Now, say we are factoring the number n, and p|n. We assume that (p-1)|q (hence q needs to have small factors), therefore a^q==1 mod p. Then we find (a^q-1) mod n, and then find gcd((a^q-1) mod n,n). If it is not equal to 0,1, or n then you have found a non-trivial factor (note, a result of zero would occur when (m-1)|q, and m was a base a Fermat prob. prime). (Now none of the variables in the previous paragraph carry over into the next :) What if we use 2 as a base? Well, for mersenne numbers, this might be to our advantage. Note that 2^n==1 mod Mn, hence 2^q==2^(q mod n) mod Mn. This would bring us down to (at most) log_2(n) squarings, which is insignificant. The possible problem (other than the required gcd) is this: Take 2^(a#)-1 has the factor (the product from 1 to a, p prime, of 2^p-1) Where # is the primorial function. Now, as I understand it, each prime number is "assigned" to a certain Mersenne, and this may or may not cause problems, I don't know. (Note that even after the removal of the trivial factors, there is still a very large number remaining). This would allow us to have huge, and I mean fricking huge B1 values, for no extra cost. Maybe even as high as 2^32. Using a linear approximation of my pseudo-primorial function in my previous posting, I get this number would have around 6.18*10^9 bits (627 megabytes), though it could be calculated indirectly (1.9*10^8 multiplications mod n). If this pans out, then P-1 would have decided advantages over trial factoring (past a certain point), even at lower exponent ranges. - -Lucas _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 23 Jul 1999 00:52:44 -0500 From: Ken Kriesel <[EMAIL PROTECTED]> Subject: Re: Mersenne: Squaring algorithm... Assuming you're talking about doing it on a conventional computer (1 or few processors, fixed word length, etc.), the method you propose is at least O(2^p * p ) per squaring. This is dominated by the first exponential term, which must be avoided at all costs. Huge constant factors can be accepted to get down from exponential time to polynomial time; brute-force ("schoolboy") multiplication is "only" O(p^2). (There squaring has about a 2:1 advantage over multiplication.) The minimum possible for fixed word length is bounded by the FFT approach at O(p * log(p) * log(log(p) ) from above, and O(P * log(p) / (log(log(p)))^2 ) from below under certain severe restrictions. These two limits are not far apart since log(log(p)) hardly moves at all; p ln(p) ln(ln(p)) 15 2.708050201102 0.9962288929514 1,000,000 13.81551055796 2.625791914476 5,260,000 15.47564158471 2.739267277143 33,000,000 17.31201811943 2.851400949303 800,000,000 20.50012228563 3.020430851279 The average length of the numbers to be added is p-1/2 bits; for a word length w, each addition takes O(log(n)/w) operations. And there are O(2^p) such operations. Each term must be generated, and the amount of memory that must be allocated for the counter is large. Take p around 33,000,000; the counter requires 33,000,000 bits storage. This will not fit in second level cache; 4MB cache PCs are rare. Storing the sum will take at least that, if you apply the modulo along the way; otherwise, twice that. The count n will take O(2^33,000,000) clocks. Compare that count, to the number of picoseconds since native Americans put the early pictographs on the rocks of Sedona Arizona: 7000 years *365.24 days/year *24 hours/day *(3600 * 10^12) picoseconds/hour =2.2*10^23 picoseconds =~ 2^77.55 picoseconds. A picosecond is the time it takes light to travel in vacuum the diameter of a 300 micron dot. At 10:47 AM 1999/07/22 -0600, <[EMAIL PROTECTED]> wrote: >Just was thinking the other day about this... Forgive me if its been >discussed before etc. > >Aren't there other "better" algorithms for finding the square of a number >besides using an FFT? Sure an FFT is great for multiplying two different >numbers, but for squaring a number isn't the case a little different. Plus, >going off what I've read on FFT's, it runs in O(n log n) time. > >So wouldn't a summation algorithm work better. > >For example, to find the square of a number k take the sum of n=1 to n=k of >2n-1. > >So 3**2 is 1+3+5 = 9 >4**2 is 1+3+5+7 = 16 >etc... > >So the sqaure performs in O(n) time. Plus, you could already throw in the >sub 2 by starting at -1 instead of 1. And figuring out the mod is just as >easy. > >k is the sum of n=2**p-1 to n=k of 2n-1 (This would give k**2 - 2**p-1). > >The only hassle is adding *big* numbers up, but I'm not sure how the >ramifications of doing carries across boundaries and such would factor into >the equation etc. > >Just a thought. > >-Jeremy >_________________________________________________________________ >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: Fri, 23 Jul 1999 00:49:17 -0500 From: Ken Kriesel <[EMAIL PROTECTED]> Subject: Re: Mersenne: Squaring algorithm... Assuming you're talking about doing it on a conventional computer (1 or few processors, fixed word length, etc.), the method you propose is at least O(2^p * p ) per squaring. This is dominated by the first exponential term, which must be avoided at all costs. Huge constant factors can be accepted to get down from exponential time to polynomial time; brute-force ("schoolboy") multiplication is "only" O(p^2). (There squaring has about a 2:1 advantage over multiplication.) The minimum possible for fixed word length is bounded by the FFT approach at O(p * log(p) * log(log(p) ) from above, and O(P * log(p) / (log(log(p)))^2 ) from below under certain severe restrictions. These two limits are not far apart since log(log(p)) hardly moves at all; p ln(p) ln(ln(p)) 15 2.708050201102 0.9962288929514 1,000,000 13.81551055796 2.625791914476 5,260,000 15.47564158471 2.739267277143 33,000,000 17.31201811943 2.851400949303 800,000,000 20.50012228563 3.020430851279 The average length of the numbers to be added is p-1/2 bits; for a word length w, each addition takes O(log(n)/w) operations. And there are O(2^p) such operations. Each term must be generated, and the amount of memory that must be allocated for the counter is large. Take p around 33,000,000; the counter requires 33,000,000 bits storage. This will not fit in second level cache; 4MB cache PCs are rare. Storing the sum will take at least that, if you apply the modulo along the way; otherwise, twice that. The count n will take O(2^33,000,000) clocks. Compare that count, to the number of picoseconds since native Americans put the early pictographs on the rocks of Sedona Arizona: 7000 years *365.24 days/year *24 hours/day *(3600 * 10^12) picoseconds/hour =2.2*10^23 picoseconds =~ 2^77.55 picoseconds. A picosecond is the time it takes light to travel in vacuum the diameter of a 300 micron dot. At 10:47 AM 1999/07/22 -0600, <[EMAIL PROTECTED]> wrote: >Just was thinking the other day about this... Forgive me if its been >discussed before etc. > >Aren't there other "better" algorithms for finding the square of a number >besides using an FFT? Sure an FFT is great for multiplying two different >numbers, but for squaring a number isn't the case a little different. Plus, >going off what I've read on FFT's, it runs in O(n log n) time. > >So wouldn't a summation algorithm work better. > >For example, to find the square of a number k take the sum of n=1 to n=k of >2n-1. > >So 3**2 is 1+3+5 = 9 >4**2 is 1+3+5+7 = 16 >etc... > >So the sqaure performs in O(n) time. Plus, you could already throw in the >sub 2 by starting at -1 instead of 1. And figuring out the mod is just as >easy. > >k is the sum of n=2**p-1 to n=k of 2n-1 (This would give k**2 - 2**p-1). > >The only hassle is adding *big* numbers up, but I'm not sure how the >ramifications of doing carries across boundaries and such would factor into >the equation etc. > >Just a thought. > >-Jeremy >_________________________________________________________________ >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: Fri, 23 Jul 1999 02:16:04 -0500 From: Ken Kriesel <[EMAIL PROTECTED]> Subject: RE: Mersenne: The sound of number searching Magnetostriction is about a bulk material changing dimensionally with varying magnetic field; this is probably not occurring or not the prime mechanism. More likely, it's simply that the magnetic fields generate forces acting on the currents in the coils, and the coils and neighboring structures are not infinitely stiff, instead acting as a low efficiency speaker. Another mechanism is piezoelectricity: the ability of materials to undergo dimensional change as a result of static electrical fields. I've seen high voltage capacitors piezoelectric enough to damage their own leads over time. Thermal effects in thin board traces can be fast enough also to be audible. If you really want to find out what area of your PC is producing the sound, use the auto mechanics trick of putting one end of a flexible hose to your ear and the other end near a suspected sound source, taking the usual precautions for your safety and your PC's. This is a FAQ item though lesser priority. Checking the archives at January 28, 1999 gives some discussion of hardware-specific symptoms, and suggestions. Earlier mentions are at August 15, 1996; December 9 1996; January 25 1997; April 14, 1998. At 03:24 PM 1999/07/22 -0500, "Willmore, David" <[EMAIL PROTECTED]> wrote: >All, > >There are several things in a computer which will have their operational >parameters vary with CPU activity. The most likely ones are: audio >subsystem receiving noise coupled either directly (magnetically) into its >signal lines or via its power feed; or the load on the power regulation unit >itself. Yes, coils do can make a buzzing sound. The name of the phenomina >is 'magnetorestrictance' (who wants to be I spelled that one wrong?) which >is the property of a material to change its physical dimensions under >varying magnetic fields--it's the reason large power transformers 'hum' and >how most high power sonar units generate their signals. > >If I remember correctly, this is an IFAQ, but could go in the FAQ so that >the-word-which-will-go-unmentioned can get spelled correctly once and for >all. > >Cheers, >David >_________________________________________________________________ >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: Fri, 23 Jul 1999 05:34:03 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Mersenne: Links in the FAQ I added a supplemental resources, and references section to the FAQ. Feel free to send me any links/books that you think should go in there. I'm trying to keep everything at least tangentaly related to the FAQ's on this list (and yes, the sites about general primality proving, and factoring are supposed to be there)... Thank you, - -Lucas _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 23 Jul 1999 08:17:29 -0500 From: Kipton Moravec <[EMAIL PROTECTED]> Subject: Re: Mersenne: The sound of number searching Back in 1974 I got a summer job as a night time computer operator for a NCR Century-101 (32K core memory) with two 5 MB 14" Disk Drives. Most things were on cards. The programmer had programs that would play simple tunes on the radio if the radio was on or very near the computer. He had about a dozen different programs in COBOL for different tunes, like Dixie, Swanie River, etc. He would also use the radio as feedback as to whether his program was running correctly or not. He could then monitor the progress from across the room, without looking at the console. Kip Luke Welsh wrote: > > At 11:35 PM 7/22/99 +0100, Brian J. Beesley wrote: > > >Back more or less to topic - > > Oh, this is very much on topic! > > > when I was a computing neophyte, a > >quarter of a century ago, I was told a story by an engineer working > >for a major mainframe supplier. For a laugh, the development team > >wired up a loudspeaker (presumably through a buffer and amplifier of > >some sort) to one of the bits in a CPU shift register. (This was > >easily done in the days when everything was discrete components!) > >The trick was then to code your program so that it performed to > >specification, but, by insertion of extra instructions to tweak this > >particular bit at suitable times, played interesting tunes whilst > >doing so! > > Alex Hurwitz loves this story. They did just that on the SWAC. It > was captured for prosperity in the film 'Magnetic Monster'. I once > made some MPegs and put them on the wwweb. I wonder if they are > still there? Alex says the sounds in the movie were produced by LL > tests. > > I recall the CDC 3150 was so wired from the factory. There was > even a volume control on the operator's console. Probably a very > helpful debug tool as you could not see the console when you were > across the room with your head inside a 32 KB memory bank the size > of a refrigerator, poking away looking for faulty a core memory. > > --Luke > > _________________________________________________________________ > 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 ------------------------------ End of Mersenne Digest V1 #602 ******************************
