Math Origami

A new fold on the origami page: Qua Qua Egg

In Israel, we have a fold we call ‘qua-qua-de-la-oma” or for short, “qua-qua”. I believe in english it is called a ‘color changer’, but I’m not sure of that. In any case, this fold yields a 3D shape similar to two connected tetrahedrons. (It is only similar because the shape is not completely symmetric). I couldn’t find a name for this shape, and since the same fold yields a qua-qua, I called it a qua-qua-egg. This fold is very useful as a makeshift ball to throw around the office.

Origami Qua-Qua-Egg

Challenges Programming Python

Small Python Challenge No. 1

I bet I already wrote that sometime earlier, but I found myself today writing the following function:

def blocks(seq, block_len):
    """blocks(range(5),2) -> [[0, 1], [2, 3], [4]]"""
    seq_len = len(seq)
    if seq_len%block_len == 0:
        num_blocks = seq_len/block_len
        num_blocks = 1 + (seq_len/block_len)
    result = [[] for i in xrange(num_blocks)]
    for idx, obj in enumerate(seq):
    return result

I am not satisfied with this implementation.
The challenge is to write it in a more elegant and short manner. Functions from Python’s standard modules are considered valid solutions.

Ready? GO!

Origami web-design

Origami section added

I wanted to add this section for quite some time now. There are a few foldings I created, which I wanted to put online. Now the first page is ready.

I also wanted to create the web-page myself, so I had to learn a bit of JavaScript, html, css, and other cuss-words. Indeed, JavaScript seems to me a bad language. There is no printf equivalent! I tried looking for it on the web, and all I could find were partial implementations by people around the world. Did I say these implementations were partial?

Nevermind. So here is the new origami page, soon to be filled with many wondrous creatures.

Here is a preview of the first fold waiting there:

Group Theory Math

Understanding the Nyquist Limit

The Nyquist Limit of half the sampling rate, often seemed to me as a ‘magical limit’. After I read the proof I understood it better, and the graphical representation of the overlapping spectra (also seen on the wikipedia page of the proof) is quite convincing. Yet now I found a very interesting and ‘easy’ explanation, which I’m going to relate. The explanation may not be complete, but it certainly gave me a good feel of the limit.

It all started when some late night I was driving with my girlfriend from Haifa to Tel-Aviv. (In Israel, many mathematical school problems start that way :). As it sometimes happens, part of the road was under repairs, and there were ‘danger lights’ alongside the road. These danger lights were many beacons, spaced a few meters apart along the road, each blinking in its own time. Driving alongside them, you could see it as if the ‘light’ was going through them ( see illustration, 0 is unlighted, x is lighted):

… x 0 0 x 0 …

… 0 x 0 0 x …

… 0 0 x 0 0 …

and so on. To me it seemed as if the light was advancing. Let us assume now a light pattern of one lighted, two off, and so on, going forward, one beacon at a time. This is the pattern in the illustration. This pattern however, is identical to the pattern of one lighted, two off, going backwards, two beacons at a time. Just like watching a rotor – you could parse it either way, and both ways are correct. This could be interpreted as aliasing.

At this point – this will already start to ‘smell’ like something is going on with the sampling theorem… Come to think of it, watching a rotor is exactly an example of the application of the sampling theorem! Cool!

(Warning: this is very reminiscent of group theory. Every now and then I will use it a little. To the non-mathematically-inclined: bear with me :)

Let’s move on. Imagine now a finite number of beacons. Let’s say five. Now consider a single light traveling through the beacons. What is the maximum speed in which it can travel, where we still can discern the direction? (this is equivalent to an infinite number of beacons, with a pattern of 1 on, 4 off. Just like Z5 ~= Z/[5])

Let’s check it out. (note: since 5 is prime each speed will generate one pattern only and not more.) We will obviously ignore the zero speed, and move on to the speed of 1. At this speed, the pattern generated is:

x 0 0 0 0
0 x 0 0 0
0 0 x 0 0
0 0 0 x 0
0 0 0 0 x

or in reverse.

At the speed of 2, the pattern generated is:

x 0 0 0 0
0 0 x 0 0
0 0 0 0 x
0 x 0 0 0
0 0 0 x 0

or in reverse.

Notice that we can discern both cases which direction the pattern is going. But a speed of 3, will be exactly the reverse of the speed of two! Equivalently, a speed of four will not be discernible from a reverse of speed 1! If you don’t believe me, try to see it in the patterns above. This is equivalent of saying that over Z5, -1 == 4, and -2 == 3. We can carry on with this, and show it is the same for any n. (In the additive group Zn, it is easy to show that the inverses lie in the different halves of the group). To summarize – given a finite number N of beacons, we will be able to discern the directions of speeds up to floor((N-1)/2). Cool.

I know that for the mathematically inclined this might seem obvious, and for the rest of the world, this could seem a little cryptic. But I’m really happy with finding this connection, and such a simple example of the Nyquist Limit.

Mathematical note: I bet I got a few mathematical things wrong here. I didn’t write a rigorous proof (but I did proof read it). Tell me your corrections, and what you think. I’ll be glad to hear.

Programming Programming Philosophy Teaching Programming

Zen Programming – 2

I thought about this a long time ago with Erez:

To fully grasp structured control flow – you must first learn to program without it.

Saw it happen, with myself and with others. Only after writing some hand-written conditionals and loops in assembly, do you really learn what do they mean, and how to make the code do what you want it do.

Linux Programming

A quick note on fonts and Ubuntu

It has been about half a year since I switched to Ubuntu as my main working environment (longer article on the subject is upcoming, sometime in the future). The hardest part for me was getting back to programming productivity. Strangely enough, I found out that the thing that was preventing me from working well, was the fonts. It didn’t take me long to discover that I prefer white background to black while programming. This is true just for programming, not for other activities – I can’t use a white background command prompt…

Back to fonts. I tried to adjust them, and it was really slow progress. I downloaded some programming fonts, and it still didn’t feel right. Also, when I enlarged the fonts, or made them smaller, they looked really bad. I didn’t remember this ever happening to me on Windows. After some more back-and-fourth, I discovered I just like the plain old Courier New, at size 10. Currently my programming environment (for Python) is Eric, and its pretty much OK. I feel more or less at home.

This made me think on how important are the little things in a desktop environment. Good design seems to be important for other things however, for example, see Measuring Font Legibility. Usually, when I find a piece of human engineering that is really solid, and well thought, I stop for a moment of appreciation. This might be a good lesson for any programmer, let alone one trying to compete with already successful software.


Putting the keyboard in the dishwasher – it works

After reading about it in several places, I wanted to try it too.

I have some keyboards at my parents’ house, and these were really nasty. So nasty in fact, that they were not used. So, there was no real danger of losing them. So I picked them apart, and put the plastics in the dishwasher.

The keyboards came out clean, and a day later, were completely dry. After a little bit of work – and one keyboard was assembled. A note though, a little bit of work == I kept forgetting parts outside of the keyboard. So after repeatedly opening and closing the keyboard, it finally worked. The second keyboard was a bit more complicated. It had a little rubber thingy behind each key, and when I opened the keyboard those thingies fell out, as they weren’t attached to anything. It was a little annoying to put them back, but I managed. The problem was, there were about 6 thingies missing. The first three were easy – I gave up the ‘power’ ‘sleep’ and ‘wake up’ buttons. I never used those with that keyboard anyway. The next 3 keys were a little more problematic? Which keys should I give up?

I thought about it a little:

  1. The num-lock. I hate that key. No-one should use num-lock! Ever! Unless of-course, you are stuck in the ‘on’ state, and you want to turn it off… So num-lock was a no-no.
  2. Same goes for CAPS-LOCK. Mostly useless, but still…
  3. Although shift, ctrl, and alt have doubles, both sides are still in use.
  4. So I decided to give up the num-pad ‘/’, ‘*’, and ‘-‘. These have doubles, and are rarely used when over there. The only time I did use them was with Pythonwin, when I used the numpad + and – to open and close source folding

So that solved it, and the keyboard worked, sans 6 keys. I could have given up some of the Fxx keys, but by the time I thought of that, the keyboard was already closed, and I didn’t want to lose anymore thingies by opening it up again.

This made me think that the policy of giving up keys isn’t really dependent only on the use-level of the key: num-lock is rarely used but is critical, or only on having doubles: shift has a double, and yet I’d keep them both.

Which keys would you have given up?

computer science Design Programming Programming Philosophy Security

Browser visibility-security and invisibility-insecurity

Formal languages have a knack of giving some output, and then later doing something completely different. For example, take the “Halting Problem“, but this is probably too theoretical to be of any relevance… so read on for something a bit more practical. We are going to go down the rabbit hole, to the ‘in-between’ space…

My interest was first piqued when I encountered the following annoyance – some websites would use transparent layers to prevent you from:

  1. Marking and copying text.
  2. Left-clicking on anything, including:
    1. images, to save them,
    2. just the website, to view its source –
  3. and so on and so forth…

Now I bet most intelligent readers would know how to pass these minor hurdles – but mostly just taking the steps is usually deterrent enough to prevent the next lazy guy from doing anything. So I was thinking, why not write a browser – or just a Firefox plugin, that will allow us to view just the top-level of any website?

This should be easy enough to do, but if it bothered enough sites (which it probably won’t), and they fought back, there would be a pretty standard escalation war. However, since the issue is not that major, I suspect it wouldn’t matter much.

Now comes the more interesting part. Unlike preventing someone from copying text, html (plus any ‘sub-languages’ it may use) may be used to display one thing, and to be read like a different thing altogether. The most common example is with spam – displaying image spam instead of text. When that was countered by spam filters, animated gif files were used. Now you have it – your escalation war, par excellence. This property of html was also used by honeypots to filter comment-spam, as described in securiteam. In this the securiteam blog post by Aviram, the beginning of another escalation war is described. There are many more examples of this property of html.

All of these examples come from html’s basic ability to specify what do display, and being able to seem to display completely different things. There are actually two parsers at work here – one is the ‘filter’ – its goal is to filter out some ‘bad’ html, and the other is a bit more complicated – it is the person reading the browser’s output (it may be considered to be the ‘browser + person’ parser) . These two parsers operate on completely different levels of html. Now, I would like to point out that having to parsers reading the same language is a common insecurity pattern. HTML has a huge space between what is expressible, and what is visible. In that space – danger lies.

As another, simpler example, consider phishing sites. These are common enough nowadays. How does your browser decide if the site you are looking at is actually a phishing site? Among other things – reading the code behind the site. However, this code can point to something completely different then what is being displayed. In this ‘invisible’ space – any misleading code can live. In that way, the spammer may pretend to be a legitimate site for the filter, but your run-of-the-mill phishing site for the human viewer. This misleading code in the ‘invisible space’ may be used to good – like a honeypot against some comment-spammer, or it may be used for different purposes – by the spammer himself.

Now comes the interesting part. The “what to do part”. For now let me just describe it theoretically, and later work on its practicality. I suggest using a ‘visibility browser’. This browser will use some popular browser (Internet Explorer, Firefox, Safari, Opera, etc.. ) as its lower level. This lower level browser will render the website to some buffer, instead of the screen. Now, our ‘visibility browser’ will OCR all of the visible rendered data, and restructure it as valid HTML. This ‘purified’ html may now be used to filter any ‘bad’ sites – whichever criterion you would like to use for ‘bad’.

I know, I know, this is not practical, it is computationally intensive etc etc… However, it does present a method to close down that nagging ‘space’, this place between readability and visibility, where bad code lies. I also know that the ‘visible browser’ itself may be targeted, and probably quite easily. Those attacks will have to rely on implementation faults of the software, or some other flaw, as yet un-thought-of. We all know there will always be bugs. But it seems to me that the ‘visibility browser’ does close, or at least cover for a time, one nagging design flaw.

Algorithms Programming Python Sound

How PyTuner works

PyTuner is really quite simple. Here is the outline of the algorithm behind it:

  1. Record audio data with pymedia.
  2. Compute the FFT of the audio data – now we have the strength of each frequency in the sample.
  3. Find peaks in the result of the FFT. This means looking for the dominant frequencies.
  4. Find the lowest frequency that has a peak besides the zero frequency.
  5. Find the nearest ‘desired note’ (the notes we should tune to) to that frequency.
  6. Mark the difference between the actual frequency and the desired note frequency.

There is more to the algorithm. First, to find peaks, I used a simple algorithm – I computed the average strength of the frequencies in the sample, and looked at all the frequencies above two standard deviations above that average. This yields an array, where each frequency is marked by 0, or 1. (Instead of 1 you can mark it with its original strength). For each consecutive sequence of frequencies with 1 – I computed the average of the run, and that was the peak location. So for example, if the data was:
0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0,
The peak would be in the frequency matching index 5.
(If you used the original strength instead of 0 and 1, you can apply a weighted average to get a more accurate result)

To find the actual note of a given frequency, I used the fact that notes (half-tones) are separated by a ratio of 2^(1/12) . (the twelfth root of 2). So, if our base note is A, at 110 Hz, to compute the note we would use the following code snippet:

note_names = "A A# B C C# D D# E F F# G G#".split()
note_index = math.log(note_freq/base_freq, 2**(1.0/12))
note_name = note_names[note_index%12]

While writing PyTuner, at first I implemented the FFT on my own, just to know how to do it once. I found it helped me to better understand the nature of the algorithm, and its output. I find the practice of implementing various algorithms on your own, for educational purposes, quite healthy. I always like to know how things work ‘behind the scenes’.