Can't wait.

Try it whilst it's fresh rather than waiting for a new year.

Mainly Tech projects on Python and Electronic Design Automation.

## Monday, December 31, 2012

## Tuesday, December 11, 2012

### Extensible sieve of Eratosthenes

I was creating a Carmichael triplets generator and needed a function to tell me if a number was prime. It wasn't immediately clear what the largest prime for checking would be so I decided to look into creating an extensible prime generator - If given a number to check for prime-ness that was outside its range, it would attempt to extend its range.

I stopped modifying the class as soon as it was working as the Carmichael generator task then ran in acceptable time.

class Isprime(): ''' Extensible sieve of Erastosthenes >>> isprime.check(11) True >>> isprime.multiples {2, 4, 6, 8, 9, 10} >>> isprime.primes [2, 3, 5, 7, 11] >>> isprime(13) True >>> isprime.multiples {2, 4, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22} >>> isprime.primes [2, 3, 5, 7, 11, 13, 17, 19] >>> isprime.nmax 22 >>> ''' multiples = {2} primes = [2] nmax = 2 def __init__(self, nmax): if nmax > self.nmax: self.check(nmax) def check(self, n): if type(n) == float: if not n.is_integer(): return False n = int(n) multiples = self.multiples if n <= self.nmax: return n not in multiples else: # Extend the sieve primes, nmax = self.primes, self.nmax newmax = max(nmax*2, n) for p in primes: multiples.update(range(p*((nmax + p + 1) // p), newmax+1, p)) for i in range(nmax+1, newmax+1): if i not in multiples: primes.append(i) multiples.update(range(i*2, newmax+1, i)) self.nmax = newmax return n not in multiples __call__ = check

Now I wouldn't be surprised if some of the loop indices are not optimum and are maybe recomputing a few values that don't need to be, and this code is only efficient enough for my purposes; (a couple of Rosetta Code entries in other languages state that they are based on the Python but make changes so that is an indication).

## Wednesday, December 05, 2012

### That grouping by zip/iter trick explained

In Python 2.7 you can get the following neat chunking of items in a list through application of zip and iter:

It is not as neat in Python 3.X as you have to wrap the expression in list(..) to see the final list.

I thought I had to think hard about what was going on here so here is my annottated Python 3.x session that explains what is going on:

For me it remains a curiosity as I doubt I will have a use for its functionality. (List-size must be a multiple of chunk-size; its functionality is obscure).

Python 2.7.3 (default, Apr 10 2012, 23:24:47) [MSC v.1500 64 bit (AMD64)] on win32 Type "copyright", "credits" or "license()" for more information. >>> items, chunk = [1,2,3,4,5,6,7,8,9], 3 >>> zip(*[iter(items)]*chunk) [(1, 2, 3), (4, 5, 6), (7, 8, 9)] >>>

It is not as neat in Python 3.X as you have to wrap the expression in list(..) to see the final list.

I thought I had to think hard about what was going on here so here is my annottated Python 3.x session that explains what is going on:

Python 3.3.0 (v3.3.0:bd8afb90ebf2, Sep 29 2012, 10:57:17) [MSC v.1600 64 bit (AMD64)] on win32 Type "copyright", "credits" or "license()" for more information. >>> from pprint import pprint as pp >>> items, chunk = [1,2,3,4,5,6,7,8,9], 3 >>> items [1, 2, 3, 4, 5, 6, 7, 8, 9] >>> chunk 3 >>> # A quick recap of what an iterator does >>> i = iter(items) >>> i.__next__() 1 >>> i.__next__() 2 >>> i.__next__() 3 >>> i.__next__() 4 >>> i.__next__() 5 >>> i.__next__() 6 >>> i.__next__() 7 >>> i.__next__() 8 >>> i.__next__() 9 >>> i.__next__() Traceback (most recent call last): File "" , line 1, ini.__next__() StopIteration >>> >>> # Three copies of theiterator >>> threei = [iter(items)] * chunk >>> pp(threei) [sameobject at 0x0000000003259D30>, object at 0x0000000003259D30>, object at 0x0000000003259D30>] >>> # (notice that the addresses above are the same) >>> >>> # Lets break-out the three copies >>> i, j, k = threei >>> i object at 0x0000000003259D30> >>> j object at 0x0000000003259D30> >>> k object at 0x0000000003259D30> >>> # i,j and k are the same iterator >>> i.__next__() 1 >>> j.__next__() 2 >>> k.__next__() 3 >>> # ... >>> >>> # Lets try that again with zip: >>> i, j, k = threei = [iter(items)] * chunk >>> list(zip(i, j, k)) [(1, 2, 3), (4, 5, 6), (7, 8, 9)] >>> # zip pulls from i, j, k once to form its first tuple of the list >>> # then pulls from i, j, k again to form its second tuple of the list >>> # and so on ... >>> # Because i,j, and k are names for the same iterator we get the >>> # given grouping action as output. >>> >>> # We could use *threei instead of i,j,k as the arguments to zip: >>> i, j, k = threei = [iter(items)] * chunk >>> list(zip(*threei)) [(1, 2, 3), (4, 5, 6), (7, 8, 9)] >>> >>> # Or we could use the expression generating threei: >>> i, j, k = threei = [iter(items)] * chunk >>> list(zip(*[iter(items)] * chunk)) [(1, 2, 3), (4, 5, 6), (7, 8, 9)] >>> # But note that we are relying on the unary '*' operator >>> # binding less strongly than binary '*' >>>

For me it remains a curiosity as I doubt I will have a use for its functionality. (List-size must be a multiple of chunk-size; its functionality is obscure).

Subscribe to:
Posts (Atom)