# Go deh!

Mainly Tech projects on Python and Electronic Design Automation.

## Monday, December 31, 2012

### New years resolutions

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

## 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:

```Python 2.7.3 (default, Apr 10 2012, 23:24:47) [MSC v.1500 64 bit (AMD64)] on win32
>>> 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
>>> 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, in
i.__next__()
StopIteration
>>>
>>> # Three copies of the same iterator
>>> threei = [iter(items)] * chunk
>>> pp(threei)
[object 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).