Mainly Tech projects on Python and Electronic Design Automation.

Tuesday, September 30, 2008

Thursday, September 25, 2008

How Nerdy are you


I am nerdier than 93% of all people. Are you a nerd? Click here to find out!


They obviously have it wrong. I have a family, and, and ...

Tuesday, September 23, 2008

Python Fractions issue.

There
seems to be a problem/difference in calculating with the new fractions
module when comparing Python 26rc2 and 30rc1

I was
reading the paper " href="http://conference.scipy.org/proceedings/SciPy2008/paper_3/full_text.pdf">Interval
Arithmetic: Python Implementation and Applications" and
thought to try the first example function f(x,y), which needs more
precision than Python floating point provides (on my Windows PC), to
calculate a sensible answer.

Ahah, I thought, lets
try this with Fractions - so I first installed Python 30rc1, typed in
the Function - saw the rubbish result, then used Fractions and got the
'right' result.
I then wondered if fractions had been
back-ported to Python 2.6rc2, found that it had, but got different
results.

As you can see from the table, Python
2.6rc2 has a problem calculating t3 = F(11,2) * y**8 + x/(2*y), where F
 is Fraction.

I wonder where the problem
lies?

style="text-align: left; margin-left: auto; margin-right: auto; font-family: monospace;"
border="4" cellpadding="2" cellspacing="2"> style="white-space: nowrap; text-align: left; vertical-align: top;">Python
3.0rc1 (r30rc1:66507, Sep 18 2008, 14:47:08) [MSC v.1500 32 bit (Intel)]
on
win32
Type "help", "copyright", "credits" or "license" for
more information.
>>> from fractions
import Fraction as F
>>>
def f(x,y):
...     return
(
...            
(333.75 - x**2)* y**6 + x**2 *
...            
(11* x**2 * y**2 - 121 * y**4 - 2)
...            
+ 5.5 * y**8 + x/(2*y))
...
>>>
f(77617.0, 33096.0)
1.1726039400531787
>>>
def f2(x,y):
...    
return (
...            
(333 + F(3,4) - x**2)* y**6 + x**2 *
...            
(11* x**2 * y**2 - 121 * y**4 - 2)
...            
+ F(11,2) * y**8 + x/(2*y))
...
>>>
f2(77617.0, 33096.0)
1.1726039400531787
>>>
f2(77617, 33096)
-0.82739605994682131
>>>
x,y = 77617, 33096
>>> t1 = (333 + F(3,4)
- x**2)* y**6 + x**2
>>> t1
Fraction(-7917110903377385049079188231255750815,
1)
>>> t2 = (11* x**2 * y**2 - 121 * y**4
- 2)
>>> t2
-72586759091903445314
>>>
t3 = F(11,2) * y**8 + x/(2*y)
>>> t3
7.9171113406689609e+36
>>> style="white-space: nowrap; text-align: left; vertical-align: top; width: 50%;">Python
2.6rc2 (r26rc2:66507, Sep 18 2008, 14:27:33) [MSC v.1500 32 bit
(Intel)] on win32
Type "copyright", "credits" or "license()"
for more information.
IDLE
2.6rc2     
>>>
from fractions import Fraction as F
>>>
def f(x,y):
    return (
   
    (333.75 - x**2)* y**6 + x**2 *
   
    (11* x**2 * y**2 - 121 * y**4 - 2)
   
    + 5.5 * y**8 + x/(2*y))

>>>
f(77617.0, 33096.0)
1.1726039400531787
>>>
def f2(x,y):
    return (
   
    (333 + F(3,4) - x**2)* y**6 + x**2 *
   
    (11* x**2 * y**2 - 121 * y**4 - 2)
   
    + F(11,2) * y**8 + x/(2*y))

>>>
f2(77617.0, 33096.0)
1.1726039400531787
>>>
f2(77617, 33096)
style="background-color: rgb(255, 102, 102); font-weight: bold;">Fraction(-1,
1)
>>> x,y = 77617, 33096
>>>
t1 = (333 + F(3,4) - x**2)* y**6 + x**2
>>>
t1
Fraction(-7917110903377385049079188231255750815, 1)
>>>
t2 = (11* x**2 * y**2 - 121 * y**4 - 2)
>>>
t2
-72586759091903445314L
>>> t3
= F(11,2) * y**8 + x/(2*y)
>>> t3
style="background-color: rgb(255, 102, 102); font-weight: bold;">Fraction(7917111340668961361101134701524942849,
1)
>>>

Sunday, August 10, 2008

Monty Hall Problem Simulations

I
had started a href="http://www.rosettacode.org/wiki/Monty_Hall_simulation">new
topic on Rosetta Code on the Monty Hall problem, using an
example I had laying around that I had written in Python to simulate
the effects of different player strategies. The game goes like this:
  • The
    contestant in in front of three  doors that he cannot see
    behind.. 
  • The three doors conceal one
    prize and the rest being booby prizes, arranged randomly.
  • The
    Host asks the contestant to choose a door.
  • The host
    then goes behind the doors where only he can see what is concealed,
    then always
    opens one
    door, out of the other s not chosen  by the contestant, that
    must reveal a booby prize to the contestant.
  • The
    host then asks the contestant if he would like either to stick with his
    previous choice, or switch and choose the other remaining closed door.
It
turns out that if the contestant follows a strategy of always switching
when asked, then he will maximise his chances of winning..

I
then re-wrote the simulator in AWK  (gawk), so there are now
at least two implementations of the simulator on Rosetta Code.,

The
simulator results show that:
  • A strategy of
    never switching wins 1/3rd of the time.
  • A strategy
    of randomly switching wins 1/2 of the time.
  • A
    strategy of always switching wins 2/3rds of the time.
style="margin-left: 40px;">

Tuesday, August 05, 2008

Spiral

This
exercise I thought up myself after doing href="http://paddy3118.blogspot.com/2008/08/zig-zag.html">ZigZag.
"
Produce a spiral array.. A spiral array is a square arrangement of the
first N2 integers, where the numbers increase
sequentially as you go around  the edges of the array
spiralling inwards.

For example, given 5, produce
this array:
style="font-family: monospace;"> 0 
1  2  3  4 style="font-family: monospace;"> style="font-family: monospace;">15 16 17 18  5 style="font-family: monospace;"> style="font-family: monospace;">14 23 24 19  6 style="font-family: monospace;"> style="font-family: monospace;">13 22 21 20  7 style="font-family: monospace;"> style="font-family: monospace;">12 11 10 
9  8

The
Algorithm

Again I choose to define the x axis as the column
numbers increasing linearly left to right; and the y axis being the row
numbers increasing linearly top to bottom; and with the top left corner
being (0,0).
If you think of the outer part of the spiral, it
can be defined as how x and y change, i.e. deltas. First along the top
row dx,dy =
(1,0)
meaning that for successive places x changes by 1
and y does not.
Similarly
for the next straight run , down the RHS: style="font-family: monospace;"> dx,dy = (0,1).
Along
the bottom: dx,dy =
(-1,0)
.
And back to the top along the LHS: style="font-family: monospace;">dx,dy = (0,-1).
The
next time around the loop, dx,dy take on those same values.

When
to stop going in a straight line and change direction?
style="margin-left: 40px;">
  • When you
    would go off the edge of the array
  • If you are about
    to 'step' on a position that is already filled.
When
to stop?
  • When
    you have placed the last integer.


The Program

I have two ways of generating successive dx,dy
values; a formula in lines 19 and 34, and a commented out use of
itertools.cycle in lines 14,17,18 and 33 which could be used instead.
They generate the same sequence.
When to change direction is
done by initializing myarray with None values in line 22 and the
conditional statement at line 29
When to stop is handled by
the outer while loop at line 24.

I added a flag at
line 15 that allows you to trace the calculation


 1 '''
color="#804040"> 2 Author: Donald 'Paddy' McCarthy
color="#804040"> 3 Email: paddy3118@gmail.com
color="#804040"> 4 File: spiral.py
color="#804040"> 5
color="#804040"> 6 Routine creates a square array filled with numbers that increase
color="#804040"> 7 in a spiral pattern into the center.
color="#804040"> 8
color="#804040"> 9 Note: for spiralling out just swap array[x,y] for n**2-1-array[x,y]
color="#804040">10 Note: Vim colourizing plus
color="#804040">11        :%s/\(  \)\?  / color="#6a5acd">\1\ \ /g
color="#804040">12 '''
color="#804040">13
color="#804040">14 #from itertools import cycle
color="#804040">15 explain = True
color="#804040">16 def color="#008080">spiral(n):
color="#804040">17      color="#0000ff">#deltas = cycle( ((1,0),(0,1),(-1,0),(0,-1)) )
color="#804040">18      color="#0000ff">#dx,dy = deltas.next() # Starting increments
color="#804040">19     dx,dy = 1,0             color="#0000ff"># Starting increments
color="#804040">20     x,y = 0,0               color="#0000ff"># Starting location
color="#804040">21     i = 0                   color="#0000ff"># starting value
color="#804040">22     myarray = [[None]* n color="#804040">for j color="#804040">in range(n)]
color="#804040">23      color="#804040">if explain: color="#804040">print " color="#ff00ff">dx,dy ->", dx,dy
color="#804040">24      color="#804040">while i < n**2:
color="#804040">25         myarray[x][y] = i
color="#804040">26          color="#804040">if explain: color="#804040">print " color="#ff00ff">x,y->[x,y]", x,y, myarray[x][y]
color="#804040">27         i += 1
color="#804040">28         nx,ny = x+dx, y+dy
color="#804040">29          color="#804040">if 0<=nx<n color="#804040">and 0<=ny<n color="#804040">and myarray[nx][ny] == None:
color="#804040">30             x,y = nx,ny
color="#804040">31              color="#804040">continue
color="#804040">32          color="#804040">else:
color="#804040">33              color="#0000ff">#dx,dy = deltas.next()
color="#804040">34             dx,dy = (-dy,dx) color="#804040">if dy color="#804040">else (dy,dx)
color="#804040">35              color="#804040">if explain: color="#804040">print " color="#ff00ff">dx,dy ->", dx,dy
color="#804040">36             x,y = x+dx, y+dy
color="#804040">37      color="#804040">return myarray
color="#804040">38 def color="#008080">printspiral(myarray):
color="#804040">39     n = range(len(myarray))
color="#804040">40      color="#804040">for y color="#804040">in n:
color="#804040">41          color="#804040">for x color="#804040">in n:
color="#804040">42              color="#804040">print " color="#ff00ff">%2i" % myarray[x][y],
color="#804040">43          color="#804040">print
color="#804040">44
color="#804040">45 printspiral(spiral(6))

Sample
output:

style="font-family: monospace;">>>>
printspiral(spiral(4)) style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 1 0 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 0 0 0 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 1 0 1 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 2 0 2 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 3 0 3 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 0 1 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 3 1 4 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 3 2 5 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 3 3 6 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> -1 0 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 2 3 7 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 1 3 8 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 0 3 9 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 0 -1 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 0 2 10 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 0 1 11 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 1 0 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 1 1 12 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 2 1 13 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 0 1 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 2 2 14 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> -1 0 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 1 2 15 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 0 -1 style="font-family: monospace;"> style="font-family: monospace;"> 0 
1  2  3 style="font-family: monospace;"> style="font-family: monospace;">11 12 13  4 style="font-family: monospace;"> style="font-family: monospace;">10 15 14  5 style="font-family: monospace;"> style="font-family: monospace;"> 9 
8  7  6 style="font-family: monospace;"> style="font-family: monospace;">>>>

Monday, August 04, 2008

Zig Zag


Yet another problem from Rosetta Code.
The problem statement is:
"
Produce a zig-zag array. A zig-zag array is a square arrangement of the first N2 integers, where the numbers increase sequentially as you zig-zag along the anti-diagonals of the array. For example:
 0  1  5  6
 2  4  7 12
 3  8 11 13
 9 10 14 15
Or take a look at this.
"
I read all the other answers and saw a very short  example in the J language, which looked like line noise to me, as well as a fairly short example in Haskel a programming language I don't know, but I got a hint as to how it is done by the mention of sorting indeces.

I printed a sheet of graph paper, drew a 6 by 6  grid and put in the zig-zag numbers, after a few false starts I realised that what distinguishes a diagonal is if the top left is coordinate 0,0; x increases to the right, and y increases  going down the rows, then the sum of the induces is constant for a diagonal.

If we are going to do some sorting then we need to sort first on the sum of the indeces. 

Next, you find that when the sum is odd you are 'going' down the diagonal so increasing y gives the sort order and vice versa, so secondly sort on  -y if the sum of the coordinates is even, otherwise +y.

The sort will give the order of the coordinates enumerate the order and you get what integer goes in which location et voila!.

The code:

The sort is split between the iterable which simply generates the coordinate pairs and the key function  which returns a tuple of the tho elements highlighted above for sorting the coordinates (Its equivalent to the decorate-sort-undecorate or Schwartzian sort method for any non-Pythoneers).  It is the main part of the program:

'''
zigzag algorithm
Description from: http://www.rosettacode.org/wiki/Zig_Zag
Code Author: Donald 'Paddy' McCarthy
'''
def zigzag(n):
 indexorder = sorted(((x,y) for x in range(n) for y in range(n)),
   key = lambda p: (p[0]+p[1], -p[1] if (p[0]+p[1]) % 2 else p[1]) )
 return dict((index,n) for n,index in enumerate(indexorder))
def printzz(myarray):
 n = int(len(myarray)** 0.5 +0.5)
 for x in range(n):
  for y in range(n):
   print "%2i" % myarray[(x,y)],
  print
printzz(zigzag(6)) 
Running the code produces:
 0  1  5  6 14 15
 2  4  7 13 16 25
 3  8 12 17 24 26
 9 11 18 23 27 32
10 19 22 28 31 33
20 21 29 30 34 35

Now to add it to Rosetta Code.

Sunday, August 03, 2008

SEDOL


Whilst browsing Rosetta Code, I came across a good algorithm for training students, SEDOL, so coded up a version in what I would call a very litteral translation of  itsexplanation.
I changed the Python example on Wikipedia, as it did not have a validation function as other examples have, and added my code to the Rosetta page.
'''
From: http://en.wikipedia.org/wiki/SEDOL
SEDOLs are seven characters in length, consisting of two parts:
 a six-place alphanumeric code and a trailing check digit. 
'''
import string
# constants
sedolchars = string.digits + string.ascii_uppercase
sedol2value = dict((ch, n) for n,ch in enumerate(sedolchars))
for ch in 'AEIOU':
    del sedol2value[ch]
sedolchars = sorted(sedol2value.keys())
sedolweight = [1,3,1,7,3,9,1]
def check(sedol):
    return len(sedol) == 7 and \
          &nbspall(ch in sedolchars for ch in sedol) and \
          &nbspsum(sedol2value[ch] * sedolweight[n]
               for n,ch in enumerate(sedol)
               ) % 10 == 0
def checksum(sedol):
   &nbsptmp = sum(sedol2value[ch] * sedolweight[n]
               for n,ch in enumerate(sedol[:6])
               )
    return sedolchars[ (10 - (tmp % 10)) % 10]

sedol = '0263494'
print sedol, checksum(sedol)
print
# From: http://www.rosettacode.org/wiki/SEDOL
for sedol in '''
 710889
 B0YBKJ
 406566
 B0YBLH
 228276
 B0YBKL
 557910
 B0YBKR
 585284
 B0YBKT
 '''.split():
    print sedol + checksum(sedol)
Note:
 I came back to the code after a few hours of sleep and thought initially that I would have trouble in the return statement of  checksum() as I thought I would need a dictionary doing the full reverse matching of what sedol2value, from ints to characters. sedolchars nolonger includes the vowels so using that method for a value over 9 will not work.
Luckily, the result of the calculation is always in the range 0<= n >=9, and within that range, sedolchars[n] works.

Saturday, July 26, 2008

Ranking Modelsim Coverage results using Python for Speed? !


I have a problem with ranking tests at work -it just takes too long and the 'obvious algorithm' should be much quicker. 

The Task

I should explain that we use modelsim for simulating a processor described in Verilog RTL and create PSL assertions and cover statements to help with the verification. Periodically we run coverage simulations and create coverage databases for each test that contains the coverage information for each PSL cover or assert statement.

Our test suite consists of ~2000 'froven' randomly generated tests with seeds we have used before and want to use again, because they give good coverage; and a few thousand newly randomly generated tests.

We want to continue keeping tests that worked well in the past, and add to the kept set of tests any new tests that contribute to the overall coverage of the design.

The Problem

 We have a problem however with the Modelsim 'vcover ranktest' command that we use to perform the ranking. It takes around ten hours to rank ~5000 tests when we were hoping for around one hour.

Around 5000 coverage databases to rank each with around 5000 coverage points (of which less than halk are covered), shouldn't be that big a deal. 

Initial Thoughts

I came up with the following algorithm that I thought would do a good job of ranking tests - it gets around the  size problems of trying every possible permutation of tests for coverage by using a greedy algorithm: choose the test giving most coverage, then the test giving the most incremental additional coverage ...
I put it in an email as:
My algorithm for Ranking tests by coverage.
  • Read in and convert each tests coverage data into its set of coverage points that the test contributes to
  • sum all the contributions of all tests marked as compulsory to form ranking set and remove the tests from the pool
    • keep note of tests added to the ranking set and the order they are added. (for compulsory tests order within compulsory tests is un-important. They all come 'first')
  •  Repeat until pool is empty:
    • pool_max = (0, "" )
    • for test in pool:
      • contribution = number of cover points in test that are not covered already in ranking_set
      • if contribution == 0:
        • drop test from pool into the non-contributory list
      • else if contribution > pool_max.contribution:
        • pool_max = (contribution, test)
    • if pool_max.contribution > 0:
      • add the pool_max test into the ranking set
      • remove the pool_max test from the pool
    • else:
      • empty everything from the pool into the non-contributory list
        (They don't add anything)
  • You end with:
    •  an ordered list of the ranking tests.
    • An (ordered) list of the non-contributing tests.
    • All tests marked as compulsory are in the ranking tests.
By only comparing against the sum of the already contributing tests, and removing non-contributing tests ASAP, I hope to get reasonable run times.
I'd write it myself if their was a python interface to UCDB files. I won't touch it with C though.

Scratching the Itch

I did decide to create my own ranking program last night.

The flow was to dump the PSL assertion coverage from Modelsims Universal Coverage DB, (UCDB) , files. a total of 1701 ucdb files generating 1701 separate textual report files. Then I would create a Python script to broadly follow the algorithm above to create a ranked list of tests from the report files.

Dumping the data from the UCDB's to reports took tenminutes to run.

A little experimentation lead me to read in test names and instance names for coverage points and substitute unique integers for these ASAP in the program as  I had memory problems trying to create 25 million sets keeping set members as long instance names of around 130 chars each.
I found ways to remove tests from the ranking just as soon as they contributed nothing.

My program, is 120 lines of Python and took a minute to run!

So Fast. Must Check.

I did some checks against the 'vcover ranktest' results:
  • One gives an extra 39 new contributing tests, the other an extra 40.
  • Of the extra tests 30 are the same in both programs.
Now I need to get my team-mates to check the Python code.

I would expect some variation in ranked tests as, for example, if two tests are equally contributing the most new coverage, how do you choose? I chose to select first on maximum contribution to coverage; then on minumum simulation  cycles; then on test name.
Once the algorithms make a different choice then there is no mechanism to make them converge.

Endpoint

My flow gets the data from the database at the beginning, then uses it in a n efficient manner. If Modelsims algorithm constantly goes to the UCDB for data then that could be the source of the bottleneck., as just getting the data once takes ten minutes.

- Paddy.

Friday, July 04, 2008

Essence of Duck

A distillation of duck typing

style="margin-left: 40px;"> style="font-family: Comic Sans MS; font-style: italic;">"Substitution
of an object with regard only of the function and signature style="font-family: Comic Sans MS; font-style: italic;">of
its run-time methods style="font-family: Comic Sans MS; font-style: italic;">"

Lets
break it down:
style="font-family: Comic Sans MS; font-style: italic;">Substitution
Its
about the later use of a new object type instead of another .
style="font-family: Comic Sans MS; font-style: italic;">object
Its
about the use of data types.
style="font-family: Comic Sans MS; font-style: italic;">regard
What
needs to be in place for things to work.
style="font-family: Comic Sans MS; font-style: italic;">function
what
the substituting object has to do to fit in.
style="font-family: Comic Sans MS; font-style: italic;">signature
the
substituting objects method signature  needed for
compatability.
style="font-family: Comic Sans MS; font-style: italic;">run-time
It
is what actually happens at run time that matters without the
constraint of what can be determened at compile time.
style="margin-left: 40px;">There is purposefully no mention
of type-checking, class hierarchy checking, in fact any 'look before
you leap' checks. Note too, that I purposefully put function before
signature - too many comments on duck typing  focus on issues
of signature and assume
programmer checks for correct substitutable function are style="font-style: italic;">not part of duck
typing.
- Paddy.

Saturday, June 21, 2008

More Fizz than Buzz

I
downloaded the first beta release of Python 3 which corresponded with
another href="http://groups.google.com/group/comp.lang.python/msg/e7acbdd108a0ea05">thread
on FizzBuzz in c.l.p that featured some slick maths using href="http://en.wikipedia.org/wiki/Fermats_little_theorem">Fermats
little theorem, (yep it's really called that). I learnt a
little about the theorem, did a quick spreadsheet to show that it
worked, but could not grasp how they made it work in their examples.

It
did however get me toying with Py3K where I came up with this snippet
of code from the description of the problem.

The
Problem:
face="Courier, Monospaced">Write a program that prints the
numbers from 1 to 100. But for
multiples of three print
"Fizz" instead of the number and for the
multiples of five
print "Buzz". For numbers which are multiples of
both three
and five print class="fixed_width"> " style="font-family: monospace;">FizzBuzz"
 
My
Py3K solution:
style="margin-left: 40px; font-family: monospace;">
print( ' color="#ff00ff"> '.join(
    ' color="#ff00ff">FizzBuzz' color="#804040">if i%15 == 0
     color="#804040">else ' color="#ff00ff">Buzz' if i%5 == 0
     color="#804040">else ' color="#ff00ff">Fizz' if i%3 == 0
     color="#804040">else str(i)
     color="#804040">for i color="#804040">in range(1,101)))

What
I like about this
solution is it applies the constraints from the problem description in
the (reverse) order that they are given, and does not rely on the
elementary (to pythoneers), knowledge that a test for not(X) is
equivalent to a test of whether X==0. I'd be happy to put this in, say
a Wikipedia type article on FizzBuzz, or teach it to newbies ready for
immersion into gencomps (as maybe the second or third
example). 

- One for trainers.

-
Paddy.
Newer Posts Older Posts Home

About Me

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive