Category: Uncategorized

A friend of mine posted a link on Facebook to this story about an old lady who spent five years compiling a list of three-letter words for Scrabble. I thought this was a perfect example of applicability vs avoidability.

Scripting to the rescue 

$ wget http://www.zyzzyva.net/lexicons/CSW{06,07,12}.txt

$ grep "^...$" CSW12.txt

BEGIN {score="0D1G1B2C2M2P2F3H3V3W3Y3K4J7X7Q9Z9"} # score table
/^...$/ { # Match three-letter words
   s=0; # accumulator for scores
   for(i=1;i<=length($0);i++) {
      # Find the current character in the score table
      # move one down for the score and add one
      s += 1+substr(score, 1+index(score, substr($1, i, 1)))}; 
      print s, $1
   }
}

$ awk 'BEGIN {score="0D1G1B2C2M2P2F3H3V3W3Y3K4J7X7Q9Z9"} /^...$/ {s=0; for(i=1;i<=length($0);i++) {s+=1+substr(score, 1+index(score, substr($1, i, 1)))}; print s, $1}' CSW12.txt | sort -nr | head

table = {'A': 1, 'B': 3, 'C': 3, 'D': 2, 'E': 1, 'F': 4, 'G': 2, 'H': 4,
         'I': 1, 'J': 8, 'K': 5, 'L': 1, 'M': 3, 'N': 1, 'O': 1, 'P': 3,
         'Q': 10, 'R': 1, 'S': 1, 'T': 1, 'U': 1, 'V': 4, 'W': 4, 'X': 8,
         'Y': 4, 'Z': 1,
         }

wordsandscores = [(sum(table[c] for c in word), word) for word in
                  [w.strip() for w in open('CSW12.txt')] if len(word)==3]
wordsandscores.sort(reverse=True)

for s, w in wordsandscores[:10]:
    print s, w

I was reading a blog post about Numba vs Cython, which reported a huge speedup in using Numba with a simply Python code for calculating the pairwise distance between a number of points. The code they posted was as follows:

import numpy as np

def pairwise_python(X, D):
    M = X.shape[0]
    N = X.shape[1]
    for i in xrange(M):
        for j in xrange(M):
            d = 0.0
            for k in xrange(N):
                tmp = X[i, k] - X[j, k]
                d += tmp * tmp
            D[i, j] = np.sqrt(d)

They tested it with the following code:

N = 1000
X = np.random.random((N, 3))
D = np.empty((N, N))

%timeit pairwise_python(X, D)

 1 loops, best of 3: 8.3 s per loop

I thought I could probably do a bit better by making more use of the built-in numpy functions, so I rewrote it like thise:

def pairwise_numpy(X, D):
    M, N = X.shape
    for i in xrange(M):
        for j in xrange(M):
            D[i, j] = np.linalg.norm(X[i, :] - X[j, :])

%timeit pairwise_numpy(X, D)

1 loops, best of 3: 13.8 s per loop

Imagine my surprise. My “optimised” version takes almost twice as long! Shocked, I thought I shold try to go all the way

def pairwise_numpy_fast(X, D):
    for i, row in enumerate(X):
        D[i, :] = np.sqrt(np.sum((X - row)**2, 1))

%timeit pairwise_numpy_fast(X, D)

10 loops, best of 3: 46.9 ms per loop

That’s a much more satisfying result. Goes to show how much one can gain without even going too crazy with tricks.

Then there is my current approach, using Fortran for the tight loops. Notice how much the Fortran source resembles the Python ones. This is not your daddy’s Fortran, it’s Fortran 90.

subroutine pairwise(X, M, N, D)
  double precision, intent (IN) :: X(M, N)
  integer, intent(IN) :: M, N
  double precision, intent (OUT) :: D(M, M)
  integer :: i, j

  forall (i = 1:M, j = 1:M)
     D(i, j) = sqrt(sum((X(i, :) - X(j, :))**2))
  end forall
end subroutine pairwise

After compiling this file to a Python module with f2py (

f2py -c -m pairwise_fortran pairwise.f90

), we can check it with

from pairwise_fortran import pairwise as pairwise_fortran
%timeit pairwise_fortran(X, M, N)

100 loops, best of 3: 6.58 ms per loop

Now that’s more like it!

So, from 8.3 s down to 6.6 ms. That’s three orders of magnitude from the original naive Python code, but the “clever” numpy version is less than one order slower. My feeling is that the benefits gained from a language like Python more than make up for any speed deficits. Of course, there’s the distinct advantage of having a really quick way to incorporate the efficient compilers available for Fortran using a tool like f2py.

On Friday, 2012-11-09 I was mugged near my home. This is an account of the events of the night so that I don’t have to repeat the story as many times as I have already. It includes quite a lot of detail so that I can also capture them for later use.

The event

I had slipped away from our departmental final year braai to catch the last train home at 20:30. It was 21:05 when I started walking from the Sandton station, and on my way down Elizabeth Street (between 7th and 6th), I noticed two men in front of me. One was short and the other tall; the short one was wearing a black and white check hoodie. They started running and slammed into me, knocking me backward. They knocked off my glasses while pulling off my headphones, then started pulling on my backpack straps, getting irritated by the clips that held them together over my chest. A knife flashed in front of my eyes. At this time I became aware of a car which had pulled up next to us in the other lane (going uphil). It was a white hatchback. I heard some shouts of “get in!”, then one of them sprayed mace in my face and they left. They had taken pretty much everything I had on except for my rings (which they couldn’t get off) and my watch (which had been covered by the sleeves of my shirt). The whole incedent had a choreographed feeling to it. Looking back on it now, I am sure that they planned to approach from the front, pulling off the backpack and running away in a smooth motion. This was foiled by the clips, and once I was on the ground, they just tried to get what they could.

I made my way back home (thankfully just a couple of blocks) and climbed in the shower to get rid of the mace. At that point all I could think of was getting this stuff out of my eyes. While I showered, my wife fired up her laptop and went to “Find my iPhone” on iCloud. We could see the phone moving South on Oxford street. I phoned ADT and then the police. I mentioned that I could track the phone and they were very interested. About 15 minutes later, an inspector and some uniformed police were at my door. I filled in an initial statement quickly, as they could not arrest anyone before I had officially reported a crime. I described the items that had been taken and the assailants as well as I could. We could see the movement of the phone in near real-time while this was going on. The captain requested me to join them while they went to try and find the criminals.

The chase

It was like a cop show. I was in the car, shouting out the latest position, and the police were relaying it on the radio – everyone was converging on the phone. We had not yet reached the position where the signal had become stationary when the news came over the radio: they had found the car and arrested the occupants. When we arrived on the scene, the whole street had been cordoned off and five police vehicles with many armed officers were milling around the car. I recognised the guy with the checked hoodie immediately, then I saw my headphones and both my bags on the roof of the car. The one I recognised was lying next to one I didn’t – I assume that this was the driver of the getaway vehicle.

I looked up the position of the phone again and saw it was on the move – just around the corner from where we were. I showed the police, and we were off again. Now I was in a minibus with several armed officers. We drove quickly, but I could see the dot on the screen moving beyond the road over an embankment. After radioing this ahead to another unit, we had to circle around to get back to the road where the dot was now stationary. When we got to the new location, it started moving again – back the way we had come. Very frustrating. We circled back, and it appeared that the perpetrator was now in a block of flats. Unfortunately, I couldn’t give a vertical position, so the trail basically ended there.

We resigned ourselves to two out of three, and proceeded to the Hilbrow police station so that I could identify the objects from the car that had been stolen. After that, we went back to Sandton police station to finalise my statement.

It was 03:00 when I got home. While the chase had been going on, I had been kept awake by the excitement, but I was now very tired. Unfortunately, I was now known as the expert on finding iPhones, and I was called twice (on my wife’s phone) by the inspector to help people with finding their phones.

All in all, I am very happy with the level of support that I got from the police. It was clear that catching someone like this was not normal for them. I think normally the perpetrators simply disappear into Hilbrow, leaving little for them to do but deal with disgruntled victims who would like them to be able to do more. While we were filling in the statements, I also found out that they do not work in shifts, and that this case going on to 03:00 was just going to be overtime for them. I think few people appreciate how thankless and demanding law enforcement is, especially in Johannesburg.

More items recovered

On Monday morning I received a call from a man who had found my ID, passport and cards. He was working as a guard in a luxury estate in Parktown and had picked the items up on his way to work. I met him at the estate and gave him a lift to his Hilbrow apartment. I went up with him and saw a glimpe of “the other side”. He lives with his wife and brother in one room of the apartment, which seemed to be sublet so that three or four people lived in every room. His greatest concern appeared to be that someone would find the documents and think that he had stolen them. It appears that the block was raided from time to time. I got back all my cards and documents. From what we can reconstruct, the robbers must have chucked them out of the window on their way to Hilbrow, probably to get rid of any items which included my name.

Final word

Intermediate languages are often used when compiling computer code. In computer translation, this same concept is apparently known as a “pivot language”. I thought of this while I was thinking about the utility of money. I suspect that there is a deeper logic, driven by simple math, behind using intermediate forms, and that this pattern is applied widely.

Compilers

When you are writing a compiler for a computer programming, you are effectively writing a translater (T) from that computer language (L) to something that can run on the machine that you are targeting (M).

As there are many different machines, it may be necessary to write translators for all the different machines. Such is the life of the compiler writer.

However, if you were to add another language to your compiler’s repertoire, you suddenly face a daunting task – you need to write as many translators as machines.

If there are n languages and m machines, there are n×m translators required. This combinatorial problem is usually broken by introducing an intermediate language (IL), with a “frontend” which goes from each language to the intermediate form and a “backend” which goes from the IL to each machine.
Now, we only need n+m translators. If both n and m are large, introducing the intermediate form is worthwhile.

Translation

It doesn’t take much of a stretch to see how similar this situation is to machine translation of human languages. They call it a “pivot language” or “bridge language” and it supplies exactly the same benefits as with the computer language case.  Of course, if you are trying to build a translator from k languages into every other one, the previous n×m sum reduces to k(k-1)=k²-k translators without a pivot language and 2k with one.

 That looks like a bargain to me. Notice that there are no arrows (or that they are effectively pointing in both directions), unlike the one-way nature of the previous case. The same problem also pops up in communication between entities, and is solved in the same way.

Money

Money appears to solve a similar problem as the translation (among many others). If you had to rely on  barter with k products, you would need to know k²-k exchange rates.

Now, intuitively, you can’t choose all those rates completely independently. You would need constraints so that there weren’t positive cycles. By that I mean that a situation where you could trade one pig for two goats, two goats for five chickens and five chickens for two pigs would lead to problems in the market. Finding similar cycles between markets is called arbitrage, and is actually possible in current markets. I suspect this is largely due to the proliferation of currencies. The lack of a central currency (although the dollar or the euro get pretty close) means that there are some extra exchange rates.

Having only 2k exchange rates (k selling prices and k buying prices) reduces the flexibility of the market, but also completely eliminates the possibility of positive cycles as long as buying prices are lower than selling prices. In fact, if buying prices were the same as selling prices, we would only need k rates. This is what happens with commodities.

Is money socially constructed?

My thinking on this got started (as seems to happen quite often lately) by a Facebook conversation about the socially constructed nature of money. For those of you reading who don’t have degrees in philosophy, I think it is useful to point out that Ian Hacking (quoted in the Wikipedia article on Social Constructionism) argues that when something is said to be “socially constructed”, this is shorthand for at least the following two claims:

(0) In the present state of affairs, X is taken for granted; X appears to be inevitable.

(1) X need not have existed, or need not be at all as it is. X, or X as it is at present, is not determined by the nature of things; it is not inevitable.

Now, all this build-up was done so that I can argue that the idea of an intermediate form is actually not completely arbitrary. In effect, I am arguing against point (1) above. I’m saying that the mathematical reality of the combinatorial problems I discussed would lead to a very similar situation to the one we have now as long as we have the need to exchange goods.

This post is about the Apple vs Samsung case. OK, so it’s late to the party, but I had a couple of comments thrown together and the Apple-hate that is being tossed around the internet lately made me rethink a couple of them.

Let’s consider why people are upset. It turns out Wikipedia has a pretty good factual summary of the legal battle, which started in 2011 and is actually still being fought in a couple of different countries. The gist is that Apple sued Samsung for a variety of infringements: “patent infringement, false designation of origin, unfair competition, and trademark infringement” (from the Wikipedia article). What many people are getting from this is that Apple acted unreasonably and most are outraged that they would sue over things that appear as petty as the rounded corners on their icons. To a certain extent, many people also see this behaviour as bullying, because Apple is the biggest-ever US company.

Remember, however, that companies are not individuals, but rather that they are made up of many individuals. In fact, Apple has over 60000 employees. Many of the daily operational decisions will be made by largely unconnected departments, which includes Apple’s legal department. I can only assume that they employ very good ones.  It is inevitable these lawyers will apply the law. The fact that a judge awarded damages shows that the legal team who thought they should go for it had a pretty good legal case. The fact that everyone agrees they are douches for bringing the suit shows that the law does not correspond with what most people regard as fair.

The real problem here is the US patent system. Most of the things that are most contentious in these cases are not even patentable in South Africa. I think this is an excellent argument against patents in general, as it is clear how this is harming innovation, but I’m a bit biased.

Every tech company on the planet has a patent arsenal, and most of them seem to have active lawsuits against one another at the moment.

A common argument for patents is the old “why would a company invest billions in research if a competitor could just copy their stuff”. I think they will for the same reasons companies did so before tech patents: first to market and competitive advantage. If an “innovation” is so obvious that just seeing it allows you to code it into your product over a weekend, I doubt it is worth billions in R&D – the hard things are hard to copy. In fact, consider that patents actually make it easier to copy stuff, as you actually have to disclose details of implementation.

Also consider this argument by Michele Boldrin and David K. Levine in Against Intellectual Monopoly:

The crucial fact, though, is that the following causal sequence never took place, either in the US or anywhere in the world. The legislative branch passed a bill saying “patent protection is extended to inventions carried out in the area X”, where X was a yet un-developed area of economic activity. A few months, years, or even decades after the bill was passed, inventions surged in area X, which quickly turned into a new, innovative and booming industry. In fact, patentability always came after the industry had already emerged and matured on its own terms.

So much then, for the idea that no-one will invest in an emerging field without protection.

PS: Try to avoid the overly general term “Intellectual Property” when discussing this kind of stuff.