Sieve of Zakiya
Update: 2008/11/03 Architecture & coding improvements. Renamed generators. I am 90% finished writing up a mathematical analysis of my method. In the process I found an architectural optimization to the sieve process which is incorporated in the new code. Complexity analysis showing other interesting stuff for each generator. When I finish I will post paper here with the code: www.4shared.com/account/dir/7467736/97bd7b71/sharing Jabari -- http://mail.python.org/mailman/listinfo/python-list
Python IF THEN chain equivalence
I'm translating a program in Python that has this IF Then chain IF x1 < limit: --- do a --- IF x2 < limit: --- do b --- IF x3 < limit: --- do c --- .- -- IF x10 < limt: --- do j --- THEN THEN - THEN THEN THEN In other words, as long as'xi' is less than 'limit' keep going down the chain, and when 'xi' isn't less than 'limit' jump to end of chain a continue. Is this the equivalence in Python? IF x1 < limit: --- do a --- elif x2 < limit: --- do b --- elif x10 < limit: --- do j --- -- http://mail.python.org/mailman/listinfo/python-list
Re: Python IF THEN chain equivalence
On Nov 13, 5:21 pm, Alan Baljeu <[EMAIL PROTECTED]> wrote: > I think you should rethink your post. The first case you posted makes no > sense in any language I know. Also, a whole lot of nested IF's is a bad idea > in any language. In Python, you will end up with code indented 40+ > characters if you keep going. > > - Original Message > From: jzakiya <[EMAIL PROTECTED]> > To: [EMAIL PROTECTED] > Sent: Thursday, November 13, 2008 5:06:53 PM > Subject: Python IF THEN chain equivalence > > I'm translating a program in Python that has this IF Then chain > > IF x1 < limit: --- do a --- > IF x2 < limit: --- do b --- > IF x3 < limit: --- do c --- > .- > -- > IF x10 < limt: --- do j --- > THEN > THEN > - > THEN > THEN > THEN > > In other words, as long as 'xi' is less than 'limit' keep going > down the chain, and when 'xi' isn't less than 'limit' jump to end of > chain a continue. > > Is this the equivalence in Python? > > IF x1 < limit: > --- do a --- > elif x2 < limit: > --- do b --- > > > elif x10 < limit: > --- do j --- > > --http://mail.python.org/mailman/listinfo/python-list > > __ > Ask a question on any topic and get answers from real people. Go to Yahoo! > Answers and share what you know athttp://ca.answers.yahoo.com > > In the code the 'xi's and 'limit' are variables and the --- do letters --- phrases are simply writes to any array: an_array[xi]=0 Actually, the code makes perfectly good sense, and is a necessity of the algorithm I'm implementing, and works perfectly good in Forth, and can be written quite nicely within a normal page width. I was just hoping I could perform the equivalent chain in Python without having to grossly indent the source code past the normal width of a printed page. But if that's the only way to do it in Python, then so be it. -- http://mail.python.org/mailman/listinfo/python-list
Re: Python IF THEN chain equivalence
On Nov 13, 5:48 pm, "M.-A. Lemburg" <[EMAIL PROTECTED]> wrote: > On 2008-11-13 23:31, jzakiya wrote: > > > > > On Nov 13, 5:21 pm, Alan Baljeu <[EMAIL PROTECTED]> wrote: > >> I think you should rethink your post. The first case you posted makes no > >> sense in any language I know. Also, a whole lot of nested IF's is a bad > >> idea in any language. In Python, you will end up with code indented 40+ > >> characters if you keep going. > > >> - Original Message > >> From: jzakiya <[EMAIL PROTECTED]> > >> To: [EMAIL PROTECTED] > >> Sent: Thursday, November 13, 2008 5:06:53 PM > >> Subject: Python IF THEN chain equivalence > > >> I'm translating a program in Python that has this IF Then chain > > >> IF x1 < limit: --- do a --- > >> IF x2 < limit: --- do b --- > >> IF x3 < limit: --- do c --- > >> .- > >> -- > >> IF x10 < limt: --- do j --- > >> THEN > >> THEN > >> - > >> THEN > >> THEN > >> THEN > > >> In other words, as long as 'xi' is less than 'limit' keep going > >> down the chain, and when 'xi' isn't less than 'limit' jump to end of > >> chain a continue. > > >> Is this the equivalence in Python? > > >> IF x1 < limit: > >> --- do a --- > >> elif x2 < limit: > >> --- do b --- > >> > >> > >> elif x10 < limit: > >> --- do j --- > > >> --http://mail.python.org/mailman/listinfo/python-list > > >> __ > >> Ask a question on any topic and get answers from real people. Go to Yahoo! > >> Answers and share what you know athttp://ca.answers.yahoo.com > > > In the code the 'xi's and 'limit' are variables and the --- do letters > > --- > > phrases are simply writes to any array: an_array[xi]=0 > > > Actually, the code makes perfectly good sense, and is a necessity of > > the algorithm I'm implementing, and works perfectly good in Forth, and > > can be > > written quite nicely within a normal page width. > > > I was just hoping I could perform the equivalent chain in Python > > without > > having to grossly indent the source code past the normal width of a > > printed page. > > But if that's the only way to do it in Python, then so be it. > > You should probably consider using a function and then > convert the conditions to define return points: > > def do_something(...args...): > > if x1 >= limit: > return > ...do a... > if x2 >= limit: > return > ...do b... > etc. > > That is provided I understand the flow of control in your > example... it's kind of strange to have THEN mark the *end* > of the then-branch in an if-then-else construct. > > -- > Marc-Andre Lemburg > eGenix.com > > Professional Python Services directly from the Source (#1, Nov 13 2008)>>> > Python/Zope Consulting and Support ... http://www.egenix.com/ > >>> mxODBC.Zope.Database.Adapter ... http://zope.egenix.com/ > >>> mxODBC, mxDateTime, mxTextTools ... http://python.egenix.com/ > > > 2008-11-12: Released mxODBC Connect 0.9.3 http://python.egenix.com/ > > Try mxODBC.Zope.DA for Windows,Linux,Solaris,MacOSX for free ! > > eGenix.com Software, Skills and Services GmbH Pastor-Loeh-Str.48 > D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg > Registered at Amtsgericht Duesseldorf: HRB 46611 It's interesting to see people think it's strange to have code that has multiple nested levels of IF THEN. Apparently you haven't seen any Forth, assembly, et al code. All you're doing is having the branch point for each conditional be the end of the chain, otherwise it falls through to the code after the conditional. This is done all the time in languages that let you actually manipulate the hardware. Just as a suggestion :-) a little humility would go a long way toward being open minded and receptive to different paradigms. I've written this program I'm doing now in Python in 3 other languages (including Python, which I'm trying to make more efficient) and I seek to be flexible in my software linguistic capabilities. I asked a very narrow question about a very specific language mechanism, and I know exactly what and why I'm doing what I'm doing. I'll try some of the suggestions and see if they make the routine faster in Python. -- http://mail.python.org/mailman/listinfo/python-list
Multiple equates
I looked online and in books, but couldn't find a definitive answer to this. I have an array and set multiple elements to either True or False at one time. Question: Which way is faster (or does it matter)? 1) array[x1]=array[x2]== array[x10] = \ array[x11]=array[x12]=... = array[x20] = \ .. .. array[x40]=array[x41]== array[x50] = False (or True) 2) array[x1]=array[x2]== array[x10] = False array[x11]=array[x12]=... = array[x20] = False .. .. array[x40]=array[x41]== array[x50] = False -- http://mail.python.org/mailman/listinfo/python-list
Re: Multiple equates
On Nov 17, 2:10 pm, Arnaud Delobelle <[EMAIL PROTECTED]> wrote: > jzakiya <[EMAIL PROTECTED]> writes: > > I looked online and in books, but couldn't find a definitive answer to > > this. > > > I have an array and set multiple elements to either True or False at > > one time. > > > Question: Which way is faster (or does it matter)? > > > 1) > > > array[x1]=array[x2]== array[x10] = \ > > array[x11]=array[x12]=... = array[x20] = \ > > .. > > .. > > array[x40]=array[x41]== array[x50] = False (or True) > > > 2) > > > array[x1]=array[x2]== array[x10] = False > > array[x11]=array[x12]=... = array[x20] = False > > .. > > .. > > array[x40]=array[x41]== array[x50] = False > > It doesn't matter as none of this is valid Python. In Python you have to > write > > array[x1] = False > array[x2] = False > > Etc... > > -- > Arnaud Could you explain please. Python allows this, so is it just not considered good idiomatic python? jz -- http://mail.python.org/mailman/listinfo/python-list
Re: Sieve of Zakiya
On Nov 4, 4:12 pm, jzakiya <[EMAIL PROTECTED]> wrote: > Update: 2008/11/03 > > Architecture & coding improvements. Renamed generators. > > I am 90% finished writing up a mathematical analysis of my method. > In the process I found an architectural optimization to the sieve > process which is incorporated in the new code. Complexity analysis > showing other interesting stuff for each generator. > > When I finish I will post paper here with the code: > > www.4shared.com/account/dir/7467736/97bd7b71/sharing > > Jabari Another update to SoZ code. Fixed coding "oversight" which caused the SoZ code running under psyco to be slower than SoA, though SoZ was faster than SoA without psyco. Now SoZ is consistently faster by an appreciable amount either way. Some other coding enhancements to optimize algorithmic performance. Enjoy! :-) Jabari -- http://mail.python.org/mailman/listinfo/python-list
Re: Sieve of Zakiya
On Nov 18, 5:01 am, Mark Dickinson <[EMAIL PROTECTED]> wrote: > On Nov 18, 7:53 am, jzakiya <[EMAIL PROTECTED]> wrote: > > >www.4shared.com/account/dir/7467736/97bd7b71/sharing > > From the introduction to the paper: > > "Thus began a process that culminated in my developing a new class > of Number Theory Sieves (NTS) to generate prime numbers, and test > primality of numbers, that use minimum memory, are simple to code, > and are much faster than all previously known methods." > > That's quite a claim! You might consider toning this down > a little if you want to be taken seriously. :-) > > How does your prime-generating algorithm stack up against > Bernstein's primegen package? > > http://cr.yp.to/primegen.html > > Mark Hi Mark, Someone has done a multi-core C implementation (for AMD-X2 and Intel quad and 8-core systems using Intel and GCC compilers) and the SoZ prime generators are faster than the Sieve of Atkin (SoA) and Sieve of Eratosthenes (SoE). I think(?) he tried to run Bernstein's primegen, but its old code written before multi-core and widely used 64-bit systems, so he wrote his own multi-core/threaded version for his systems. The SoZs again, are faster. I've implemented the SoZ generators in Forth, Ruby, and Python, and all show the same results, to be faster than the SoA and SoE in those languages, along with C. Now that I've corrected the Python code (I am NOT a native Python programmer) it now beats the SoA implementation included in the code using psyco too (for 2.4.3, I don't have it for other versions). Run the code and see for yourself! :-) I am writing another paper explaining some of the mathematical basis for the SoZ, with complexity analysis, but I keep finding "interesting" features about the underlying math, which I hope real mathematicians will investigate and reveal what's going on here. I want to release at least a first version before December. But the proof is in the pudding, and the results speak for themselves. It's an amazingly simple algorithm, so tear it apart. Jabari -- http://mail.python.org/mailman/listinfo/python-list
Re: Sieve of Zakiya
On Nov 18, 6:15 pm, Mark Dickinson <[EMAIL PROTECTED]> wrote: > On Nov 18, 3:58 pm, jzakiya <[EMAIL PROTECTED]> wrote: > > > I am writing another paper explaining some of the mathematical basis > > for the SoZ, with complexity analysis, but I keep finding > > "interesting" features about the underlying math, which I hope real > > mathematicians will investigate and reveal what's going on here. > > Well, what's going on here is that you've rediscovered the idea > of a wheel. I don't know who first came up with the idea of > speeding up the sieve of Eratosthenes with a wheel, but it's > certainly been around for a while. So unfortunately your > ideas, while interesting, aren't new. Don't be put off, > though: finding that your amazing new discovery is already > well known is a pretty common activity when doing mathematics. :-) > > A good reference for this and related topics is the book > "Prime Numbers: A Computational Perspective", by Crandall > and Pomerance. See Chapter 3, especially section 3.1. > > > Run the code and see for yourself! :-) > > Using Python to measure algorithm performance is kinda > crazy, but since you insist, here's a version of the sieve > of Eratosthenes that I wrote a while back. On my machine, > the function wheelSieve comes out around 60% faster than > your 'SoZP11', for inputs of around 10**6 or so. > > Mark > > from math import sqrt > from bisect import bisect_left > > def basicSieve(n): > """Given a positive integer n, generate the primes < n.""" > s = [1]*n > for p in xrange(2, 1+int(sqrt(n-1))): > if s[p]: > a = p*p > s[a::p] = [0] * -((a-n)//p) > for p in xrange(2, n): > if s[p]: > yield p > > class Wheel(object): > """Class representing a wheel. > > Attributes: > primelimit -> wheel covers primes < primelimit. > For example, given a primelimit of 6 > the wheel primes are 2, 3, and 5. > primes -> list of primes less than primelimit > size -> product of the primes in primes; the modulus of the > wheel > units -> list of units modulo size > phi -> number of units > > """ > def __init__(self, primelimit): > self.primelimit = primelimit > self.primes = list(basicSieve(primelimit)) > > # compute the size of the wheel > size = 1 > for p in self.primes: > size *= p > self.size = size > > # find the units by sieving > units = [1] * self.size > for p in self.primes: > units[::p] = [0]*(self.size//p) > self.units = [i for i in xrange(self.size) if units[i]] > > # number of units > self.phi = len(self.units) > > def to_index(self, n): > """Compute alpha(n), where alpha is an order preserving map > from the set of units modulo self.size to the nonnegative > integers. > > If n is not a unit, the index of the first unit greater than n > is given.""" > return bisect_left(self.units, n % self.size) + n // self.size > * self.phi > > def from_index(self, i): > """Inverse of to_index.""" > > return self.units[i % self.phi] + i // self.phi * self.size > > def wheelSieveInner(n, wheel): > """Given a positive integer n and a wheel, find the wheel indices > of > all primes that are less than n, and that are units modulo the > wheel modulus. > """ > > # renaming to avoid the overhead of attribute lookups > U = wheel.units > wS = wheel.size > # inverse of unit map > UI = dict((u, i) for i, u in enumerate(U)) > nU = len(wheel.units) > > sqroot = 1+int(sqrt(n-1)) # ceiling of square root of n > > # corresponding index (index of next unit up) > sqrti = bisect_left(U, sqroot % wS) + sqroot//wS*nU > upper = bisect_left(U, n % wS) + n//wS*nU > ind2 = bisect_left(U, 2 % wS) + 2//wS*nU > > s = [1]*upper > for i in xrange(ind2, sqrti): > if s[i]: > q = i//nU > u = U[i%nU] > p = q*wS+u > u2 = u*u > aq, au = (p+u)*q+u2//wS, u2%wS > wp = p * nU > for v in U: > # eliminate entries corresponding to integers > # congruent to p*v modulo p*wS > uvr = u*v%wS
Re: Sieve of Zakiya
On Nov 18, 6:15 pm, Mark Dickinson <[EMAIL PROTECTED]> wrote: > On Nov 18, 3:58 pm, jzakiya <[EMAIL PROTECTED]> wrote: > > > I am writing another paper explaining some of the mathematical basis > > for the SoZ, with complexity analysis, but I keep finding > > "interesting" features about the underlying math, which I hope real > > mathematicians will investigate and reveal what's going on here. > > Well, what's going on here is that you've rediscovered the idea > of a wheel. I don't know who first came up with the idea of > speeding up the sieve of Eratosthenes with a wheel, but it's > certainly been around for a while. So unfortunately your > ideas, while interesting, aren't new. Don't be put off, > though: finding that your amazing new discovery is already > well known is a pretty common activity when doing mathematics. :-) > > A good reference for this and related topics is the book > "Prime Numbers: A Computational Perspective", by Crandall > and Pomerance. See Chapter 3, especially section 3.1. > > > Run the code and see for yourself! :-) > > Using Python to measure algorithm performance is kinda > crazy, but since you insist, here's a version of the sieve > of Eratosthenes that I wrote a while back. On my machine, > the function wheelSieve comes out around 60% faster than > your 'SoZP11', for inputs of around 10**6 or so. > > Mark > > from math import sqrt > from bisect import bisect_left > > def basicSieve(n): > """Given a positive integer n, generate the primes < n.""" > s = [1]*n > for p in xrange(2, 1+int(sqrt(n-1))): > if s[p]: > a = p*p > s[a::p] = [0] * -((a-n)//p) > for p in xrange(2, n): > if s[p]: > yield p > > class Wheel(object): > """Class representing a wheel. > > Attributes: > primelimit -> wheel covers primes < primelimit. > For example, given a primelimit of 6 > the wheel primes are 2, 3, and 5. > primes -> list of primes less than primelimit > size -> product of the primes in primes; the modulus of the > wheel > units -> list of units modulo size > phi -> number of units > > """ > def __init__(self, primelimit): > self.primelimit = primelimit > self.primes = list(basicSieve(primelimit)) > > # compute the size of the wheel > size = 1 > for p in self.primes: > size *= p > self.size = size > > # find the units by sieving > units = [1] * self.size > for p in self.primes: > units[::p] = [0]*(self.size//p) > self.units = [i for i in xrange(self.size) if units[i]] > > # number of units > self.phi = len(self.units) > > def to_index(self, n): > """Compute alpha(n), where alpha is an order preserving map > from the set of units modulo self.size to the nonnegative > integers. > > If n is not a unit, the index of the first unit greater than n > is given.""" > return bisect_left(self.units, n % self.size) + n // self.size > * self.phi > > def from_index(self, i): > """Inverse of to_index.""" > > return self.units[i % self.phi] + i // self.phi * self.size > > def wheelSieveInner(n, wheel): > """Given a positive integer n and a wheel, find the wheel indices > of > all primes that are less than n, and that are units modulo the > wheel modulus. > """ > > # renaming to avoid the overhead of attribute lookups > U = wheel.units > wS = wheel.size > # inverse of unit map > UI = dict((u, i) for i, u in enumerate(U)) > nU = len(wheel.units) > > sqroot = 1+int(sqrt(n-1)) # ceiling of square root of n > > # corresponding index (index of next unit up) > sqrti = bisect_left(U, sqroot % wS) + sqroot//wS*nU > upper = bisect_left(U, n % wS) + n//wS*nU > ind2 = bisect_left(U, 2 % wS) + 2//wS*nU > > s = [1]*upper > for i in xrange(ind2, sqrti): > if s[i]: > q = i//nU > u = U[i%nU] > p = q*wS+u > u2 = u*u > aq, au = (p+u)*q+u2//wS, u2%wS > wp = p * nU > for v in U: > # eliminate entries corresponding to integers > # congruent to p*v modulo p*wS > uvr = u*v%wS
Ultimate Prime Sieve -- Sieve Of Zakiya (SoZ)
This is to announce the release of my paper "Ultimate Prime Sieve --
Sieve of Zakiiya (SoZ)" in which I show and explain the development of
a class of Number Theory Sieves to generate prime numbers. I used
Ruby 1.9.0-1 as my development environment on a P4 2.8 Ghz laptop.
You can get the pdf of my paper and Ruby and Python source from here:
http://www.4shared.com/dir/7467736/97bd7b71/sharing.html
Below is a sample of one of the simple prime generators. I did a
Python version of this in my paper (see Python source too). The Ruby
version below is the minimum array size version, while the Python has
array of size N (I made no attempt to optimize its implementation,
it's to show the method).
class Integer
def primesP3a
# all prime candidates > 3 are of form 6*k+1 and 6*k+5
# initialize sieve array with only these candidate values
# where sieve contains the odd integers representatives
# convert integers to array indices/vals by i = (n-3)>>1 =
(n>>1)-1
n1, n2 = -1, 1; lndx= (self-1) >>1; sieve = []
while n2 < lndx
n1 +=3; n2 += 3; sieve[n1] = n1; sieve[n2] = n2
end
#now initialize sieve array with (odd) primes < 6, resize array
sieve[0] =0; sieve[1]=1; sieve=sieve[0..lndx-1]
5.step(Math.sqrt(self).to_i, 2) do |i|
next unless sieve[(i>>1) - 1]
# p5= 5*i, k = 6*i, p7 = 7*i
# p1 = (5*i-3)>>1; p2 = (7*i-3)>>1; k = (6*i)>>1
i6 = 6*i; p1 = (i6-i-3)>>1; p2 = (i6+i-3)>>1; k = i6>>1
while p1 < lndx
sieve[p1] = nil; sieve[p2] = nil; p1 += k; p2 += k
end
end
return [2] if self < 3
[2]+([nil]+sieve).compact!.map {|i| (i<<1) +3 }
end
end
def primesP3(val):
# all prime candidates > 3 are of form 6*k+(1,5)
# initialize sieve array with only these candidate values
n1, n2 = 1, 5
sieve = [False]*(val+6)
while n2 < val:
n1 += 6; n2 += 6; sieve[n1] = n1; sieve[n2] = n2
# now load sieve with seed primes 3 < pi < 6, in this case just 5
sieve[5] = 5
for i in range( 5, int(ceil(sqrt(val))), 2) :
if not sieve[i]: continue
# p1= 5*i, k = 6*i, p2 = 7*i,
p1 = 5*i; k = p1+i; p2 = k+i
while p2 <= val:
sieve[p1] = False; sieve[p2] = False; p1 += k; p2 += k
if p1 <= val: sieve[p1] = False
primes = [2,3]
if val < 3 : return [2]
primes.extend( i for i in range(5, val+(val&1), 2) if sieve[i] )
return primes
Now to generate an array of the primes up to some N just do:
Ruby:1001.primesP3a
Python: primesP3a(1001)
The paper presents benchmarks with Ruby 1.9.0-1 (YARV). I would love
to see my various prime generators benchmarked with optimized
implementations in other languages. I'm hoping Python gurus will do
better than I, though the methodology is very very simple, since all I
do is additions, multiplications, and array reads/writes.
Have fun with the code. ;-)
Jabari Zakiya
--
http://mail.python.org/mailman/listinfo/python-list
Re: Ultimate Prime Sieve -- Sieve Of Zakiya (SoZ)
On Jun 13, 1:12 pm, jzakiya <[EMAIL PROTECTED]> wrote:
> This is to announce the release of my paper "Ultimate Prime Sieve --
> Sieve of Zakiiya (SoZ)" in which I show and explain the development of
> a class of Number Theory Sieves to generate prime numbers. I used
> Ruby 1.9.0-1 as my development environment on a P4 2.8 Ghz laptop.
>
> You can get the pdf of my paper and Ruby and Python source from here:
>
> http://www.4shared.com/dir/7467736/97bd7b71/sharing.html
>
> Below is a sample of one of the simple prime generators. I did a
> Python version of this in my paper (see Python source too). The Ruby
> version below is the minimum array size version, while the Python has
> array of size N (I made no attempt to optimize its implementation,
> it's to show the method).
>
> class Integer
> def primesP3a
> # all prime candidates > 3 are of form 6*k+1 and 6*k+5
> # initialize sieve array with only these candidate values
> # where sieve contains the odd integers representatives
> # convert integers to array indices/vals by i = (n-3)>>1 =
> (n>>1)-1
> n1, n2 = -1, 1; lndx= (self-1) >>1; sieve = []
> while n2 < lndx
> n1 +=3; n2 += 3; sieve[n1] = n1; sieve[n2] = n2
> end
> #now initialize sieve array with (odd) primes < 6, resize array
> sieve[0] =0; sieve[1]=1; sieve=sieve[0..lndx-1]
>
> 5.step(Math.sqrt(self).to_i, 2) do |i|
> next unless sieve[(i>>1) - 1]
> # p5= 5*i, k = 6*i, p7 = 7*i
> # p1 = (5*i-3)>>1; p2 = (7*i-3)>>1; k = (6*i)>>1
> i6 = 6*i; p1 = (i6-i-3)>>1; p2 = (i6+i-3)>>1; k = i6>>1
> while p1 < lndx
> sieve[p1] = nil; sieve[p2] = nil; p1 += k; p2 += k
> end
> end
> return [2] if self < 3
> [2]+([nil]+sieve).compact!.map {|i| (i<<1) +3 }
> end
> end
>
> def primesP3(val):
> # all prime candidates > 3 are of form 6*k+(1,5)
> # initialize sieve array with only these candidate values
> n1, n2 = 1, 5
> sieve = [False]*(val+6)
> while n2 < val:
> n1 += 6; n2 += 6; sieve[n1] = n1; sieve[n2] = n2
> # now load sieve with seed primes 3 < pi < 6, in this case just 5
> sieve[5] = 5
>
> for i in range( 5, int(ceil(sqrt(val))), 2) :
> if not sieve[i]: continue
> # p1= 5*i, k = 6*i, p2 = 7*i,
> p1 = 5*i; k = p1+i; p2 = k+i
> while p2 <= val:
> sieve[p1] = False; sieve[p2] = False; p1 += k; p2 += k
> if p1 <= val: sieve[p1] = False
>
> primes = [2,3]
> if val < 3 : return [2]
> primes.extend( i for i in range(5, val+(val&1), 2) if sieve[i] )
>
> return primes
>
> Now to generate an array of the primes up to some N just do:
>
> Ruby: 1001.primesP3a
> Python: primesP3a(1001)
>
> The paper presents benchmarks with Ruby 1.9.0-1 (YARV). I would love
> to see my various prime generators benchmarked with optimized
> implementations in other languages. I'm hoping Python gurus will do
> better than I, though the methodology is very very simple, since all I
> do is additions, multiplications, and array reads/writes.
>
> Have fun with the code. ;-)
>
CORRECTION:
http://cr.yp.to/primegen.html NOT "primesgen"
Jabari Zakiya
--
http://mail.python.org/mailman/listinfo/python-list
Re: Ultimate Prime Sieve -- Sieve Of Zakiya (SoZ)
On Jun 18, 7:58 pm, George Sakkis <[EMAIL PROTECTED]> wrote: > On Jun 13, 1:12 pm, jzakiya <[EMAIL PROTECTED]> wrote: > > > The paper presents benchmarks with Ruby 1.9.0-1 (YARV). I would love > > to see my variousprimegenerators benchmarked with optimized > > implementations in other languages. I'm hoping Python gurus will do > > better than I, though the methodology is very very simple, since all I > > do is additions, multiplications, and array reads/writes. > > After playing a little with it, I managed to get a 32-47% improvement > on average for the pure Python version, and a 230-650% improvement > with an extra "import psyco; psyco.full()" (pasted > athttp://codepad.org/C2nQ8syr) > The changes are: > > - Replaced range() with xrange() > - Replaced x**2 with x*x > - Replaced (a,b) = (c,d) with a=c; b=d > - Replaced generator expressions with list comprehensions. This was > the big one for letting psyco do its magic. > > I also tried adding type declarations and running it through Cython > but the improvement was much less impressive than Psyco. I'm not a > Pyrex/Cython expert though so I may have missed something obvious. > > George George, I took your code and included more efficient/optimized versions of SoZ versions P3, P5, P7, and P11. I ran the code on my PCLinuxOS, Intel P4, Python 2.4.3 system and noted this. The SoZ code run much faster than the SoA in pure Python. When psyco is used the SoA is significantly faster than the pure Python version. The SoZ versions are faster too, but now they are slower than the SoA. You can download the code from http://www.4shared.com/dir/7467736/97bd7b71/sharing.html It would be interesting to see how this code runs in newer versions of Python (Psyco). FYI, someone else coded P7 in C on a QuadCore Intel 9650 3.67GHz overclocked cpu, using multiple threads, and got it to be faster than the SoA, SoE, Here's some of his results (times in seconds). Case nPrime7x nPrime7x nPrime7x nPrime7x Atkin Zakiya Eratosthenes Zakiya (8 core 2.5ghz) 100 billion 52.58 44.27 50.56 200 b 110.14 92.38108.99 88.01 300 b 169.81140.92167.47 400 b 232.34190.84228.08177.72 500 b 297.44241.84291.28 600 b 364.84293.92355.27273.04 700 b 434.33346.97420.41 800 b 506.67400.97486.72373.29 900 b 579.58456.53555.09 1 trillion 654.03513.11624.00479.22 Jabari -- http://mail.python.org/mailman/listinfo/python-list
integer nth roots for arbitrary sized integer
FYI for people who need this. I was looking here http://www.codecodex.com/wiki/Calculate_an_integer_square_root for an efficient/fast algorithm for computing integer squareroots. Based on one of the C version examples, I think this is the most efficient/fastest that always produces correct results for arbitrary sized integers. >>> def isqrt(n): ... root, bitn_mask = 0, (1 << (n.bit_length() // 2 + 1)) ... while bitn_mask != 0: ... root |= bitn_mask ... if (root * root) > n: root ^= bitn_mask ... bitn_mask >>= 1 ... return root ... >>> n = 10**35; isqrt(n) 316227766016837933 >>> n = 10**111 >>> isqrt(n) 31622776601683793319988935444327185337195551393252168268L >>> n = 10**110; isqrt(n) 1000L >>> n = 10**210; isqrt(n) 10L >>> n = 10**211; isqrt(n) 3162277660168379331998893544432718533719555139325216826857504852792594438639238221344248108379300295187347L With a small modification, the algorithm will find the exact integer nth root for arbitrary sized integers. >>> def irootn(num, n): ... root, bitn_mask = 0, (1 << (num.bit_length() // n + 1)) ... while bitn_mask != 0: ... root |= bitn_mask ... if root**n > num: root ^= bitn_mask ... bitn_mask >>= 1 ... return root ... >>> n = 10**35; isqrt(n) 316227766016837933 >>> n = 10**35; irootn(n, 2) 316227766016837933 >>> n = 10**39; irootn(n, 2) 31622776601683793319L >>> n = 10**39; irootn(n, 3) 10 >>> n = 10**39; irootn(n, 4) 5623413251 >>> n = 10**144; irootn(n, 2) 1L >>> n = 10**144; irootn(n, 3) 1L >>> n = 10**144; irootn(n, 4) 1L >>> n = 10**144; irootn(n, 6) 1L >>> n = 10**144; irootn(n, 8) 100 >>> n = 10**144; irootn(n, 11) 12328467394420 >>> n = 10**144; irootn(n, 12) 1 >>> -- https://mail.python.org/mailman/listinfo/python-list
