RE: Re: RE: Notebook for Primes
- To: mathgroup at smc.vnet.net
- Subject: [mg36069] RE: [mg36056] Re: [mg36023] RE: [mg35992] Notebook for Primes
- From: "DrBob" <majort at cox-internet.com>
- Date: Thu, 15 Aug 2002 02:36:20 -0400 (EDT)
- Reply-to: <drbob at bigfoot.com>
- Sender: owner-wri-mathgroup at wolfram.com
I wrote a very slow implementation of the new algorithm... not the kind of implementation they had in mind. I slapped it together quickly. The first step of the algorithm, for instance, says something like, "If n is of the form a^b for b>1, then return COMPOSITE". Well, I looped through b from 2 to Log[2,n], calculated root=IntegerPart[n^(1/b)] for each, and checked whether Mod[n,root]==0. There is undoubtedly a more efficient method, and I haven't studied the paper at length to see if they describe one. Possibly my larger mistake has to do with taking (x-a)^r. I need to check binomial coefficients one at a time instead, to avoid calculating the ones I don't need. So... I don't have a good implementation. Still, my implementation took 17 seconds on my 2.2GHz machine to check odd numbers up to only 70. It needs to be a thousand times that fast to compete with the Sieve of Eratosthenes. (But maybe my implementation IS that bad!) Also... despite all the smarter algorithms today, the Sieve is still a great (perhaps necessary) component of a real strategy to identify primes. The Great Internet Mersenne Prime Search, for instance, uses a modified Sieve. I don't know the details but, at the very least, software using idle cycles on my machine doesn't have to worry about numbers that have already been checked elsewhere. Bobby Treat -----Original Message----- From: Andrzej Kozlowski [mailto:andrzej at tuins.ac.jp] To: mathgroup at smc.vnet.net Subject: [mg36069] Re: [mg36056] Re: [mg36023] RE: [mg35992] Notebook for Primes I was much too simple minded in my assessments of all the algorithms mentioned below .I should have known it's not as simple as it seemed but after all its only a hobby:). The complexity of the Sieve of Erasthoteness is well known to be O(n) (this is stated, for example, in Knuth, "The Art of Computer Programming", vol 3, p. 617). The Miller-Rabin algorithm has complexity O(log(n)^5) (not log(n)^2), assuming the GRH is true. (It is also deterministic). The Agrawal, Kayal and Saxenaalgorithm has a proven complexity of O(log(n)^12) and a conjectured running time of O(log(n)^6). The the sieve is certainly not even a contender. However, as for practical implementation, it seems to me that Miller-Rabin is clearly preferable. If the GRH is true it is faster than the new one. And if you find it running slow ... well that's even better ... Andrzej On Wednesday, August 14, 2002, at 06:35 PM, Andrzej Kozlowski wrote: > Well, this depends on the meaning of "polynomial" time. The running time > of the Sieve of Eratosthenes is Sqt[n], but time complexity in the case > of prime testing is always expressed in terms of log[n], so the sieve is > considered exponential. I think the fastest deterministic test is the > Rabin-Miller which is (I am not quite sure of that) Log[n]^2, but it > depends on the unproved Generalized Riemann Hypothesis. Agrawal, Kayal > and Saxena give a Log[n]^12 algorithm, but they also give a complete > proof of its correctness. I have not read their paper but assuming that > it is correct, the algorithm is certainly much faster than the sieve. On > the other hand the GRH is most probably true... > > On Tuesday, August 13, 2002, at 06:22 PM, DrBob wrote: > >> The oldest algorithm for testing primes... the Sieve of Eratosthenes... >> is polynomial and deterministic. It's simply too slow to use, just >> like >> the one at the attachment. >> >> Bobby >> >> -----Original Message----- >> From: Jeff Dillon [mailto:jeffdi at fidalgo.net] To: mathgroup at smc.vnet.net >> Subject: [mg36069] [mg36056] [mg36023] [mg35992] Notebook for Primes >> >> >> Is there a publicly available Mathematica 3.0 notebook that implements >> the Primes is in P? >> >> http://www.msnbc.com/news/792126.asp >> >> >> >> >> > > > > Andrzej Kozlowski Toyama International University JAPAN