Categories
C Programming Teaching Programming

Starting from Scratch – Part 1

About a month ago, someone I met asked me if I could give him C programming lessons. To protect his privacy I won’t talk about him much, besides saying that he is a serious guy and he doesn’t know programming at all.

The first thing I did was give him a general explanation of what C does, the compilation process and so on. I then showed him a simple program, and showed him how to compile it, and how to run it.
I think the first thing beginners see when they start to program with C is all the “unnecessary voodoo”. For someone just starting to program, “#include <stdio.h>” doesn’t make much sense, and he shouldn’t be bothered with it. The same applies to “int main(void)”. So I just told him to ignore that for now, it would be made clear later on.

The next thing I did was give him a C book, and telling him what to read, and more importantly, what not to read. Teaching books suffer from a kind of “split personality” problem – they try to be both a tutorial and a reference. They also cover things fully the first time around. For example, consider variable types.
A first timer doesn’t need to know about anything besides int. He really doesn’t need to know about size limitations. He shouldn’t be bothered by these issues in the first few lessons.

As I see it, the order of things to learn is:

  • General information such as how to compile, etc…
  • Meaning of variables, and variable assignments.
  • if-else, and then do-while.

So we covered these subjects in the first two lessons, and he was able to write some simple programs, such as compute the average of two numbers, and so on.

We wrote a simple ‘guess the number’ game together, and I used this opportunity to explain if-else by writing conditions for cases such as “warm” or “cold”, “too low” and “too high”. Simple while loops were explained as well: “keep playing as long as the number was not guessed”. We wrote some more programs after that.

As homework, I gave him the following problem:

Write a program to compute an average of numbers.
It will read numbers from the user, until the user gives the number -1.
After it finished reading the numbers, it will print their sum, and their average.
If the average is in the range, print: 0-55: failed, 56-72: could be better, 73-85: ok, 85-95: good, 95-100: excellent.

I knew this will be problematic, and indeed it was. He wrote a program that asked for three grades, and averaged them. It went on asking again until the grades 100, 100, 100 were entered – he thought that was nicer than -1.
Well, a few days ago we sat together, and I understood the problem:

He knew how to write C code, but he didn’t know how to program!

I simplified the problem. I asked him to write (during the lesson) a program that reads numbers from the user until a zero is entered. It will then output how many ones were encountered. He couldn’t write that as well, and that’s no surprise – he had a big concept to understand.

So I told him, let’s play this together. I will tell you numbers, and when I finish, you will tell me how many ones were there. I gave him ten numbers and I noticed he was counting on his fingers!

Grasping this opportunity, I told him to explain exactly what he does. Then I asked him to give me instructions on how to count numbers. The instructions were “read a number onto your left hand”, and “if the number on your left hand is one, set the number on your right hand to be the number on your right hand plus one”. It took some effort for him to understand this, but he did. I then asked him to do the same, but now summing the all of the numbers with the right hand.

I then showed him how I translate these instructions into C. I asked him for the definition of an average, and then, looking at the code on the screen, realization dawned on him. He was amazed – he managed to calculate the average of an unknown number of numbers!

It was amazing for me as well – it’s not often that you get to see someone understand a big concept such as programming.

After the averaging program I asked him to write a counter program – given a number, print all the numbers from zero up to this number. When he got stuck, I asked to turn off the screen, and again give me instructions on how to do the task. That he was able to do. Translating these instructions to C wasn’t that hard, and some 30 minutes later, he had a working program. Success!

Categories
Algorithms computer science Fractals Math Programming Python

Fractal Memory Usage and a Big Number

In a previous post I said I’d talk about 4**(4**(4**4)).
First, about the number. I first saw it mentioned in a math lesson back in high-school, when the teacher wanted to demonstrate estimation abilities.
He wrote it on the board, like so:

4444

and then asked students to estimate how big that number is. Turns out this number is much bigger than most students thought. (For comparison, the number of atoms in the observable universe is 1080.)

Given that this number is so big, it should come as no surprise that computing it will consume all available memory.
What is interesting is the way the memory is consumed:

(It died with a MemoryError just before the next “jump”.)

When I first saw this I was fascinated. To those interested it is generated by the long pow function in Python, implemented in longobject.c. According to the comment there, the algorithm is a left to right 5-ary exponentiation, taken from “Handbook of Applied Cryptography”.
In short, the simpler algorithm “left-to-right binary exponentiation” (used for smaller exponents) repeatedly squares the accumulator, and according to the binary digits of the exponents, multiplies it by the base. 5-ary exponentiation basically does the same thing, but in each iteration it ‘eats’ five digits of the exponent instead of just one.

It might be very interesting to study algorithms and code according to their memory usage. Once at work I used a similar memory usage graph to optimize the memory usage of some algorithm that was eating too much memory. I don’t remember the details as it happened a few years ago, but I do remember that I recognized the “type of the memory eating”, which helped me to narrow the problem down to a specific area of code, where indeed the problem was located. (I consider this a case of programming-fu :)

Notes:
1) The reason I’m talking about Python is because it has arbitrarily sized longs built-in.
2) This graph was generated using Windows’ task manager. On my Ubuntu machine it looks quite different, almost a straight line. Any guesses why?

Categories
Personal Programming Python Testing

My Bad Memory, High Load, and Python

About a month ago the new Ubuntu 8.04 was released and I wanted a clean install. I downloaded an image and burned it to a CD. Just before installing, I tried “check CD for defects” and found a few. Turns out (*) this was because of bad memory – and memtest confirmed it.
So I went to the shop, replaced the bad memory, and also bought two new sticks. I went home to install the new Ubuntu, and after the installation, Firefox crashed. After rebooting back to memtest, I saw this:

memory errors in memtest

Back at the computer shop, they asked me to reproduce the errors. Just firing up the computer and booting directly into memtest didn’t seem to do the trick, so I suspected that I had to overwork my computer a bit to reproduce this.

Since I was at the lab, I didn’t want to muck around too much.
So I thought, “what’s the quickest way to give your CPU a run around the block?”
That’s right – a tight loop:

while True:
    pass

However, this snippet doesn’t really play with the memory.

The next simplest thing to do, that also jiggles some ram is the following (and one of my favorites):

In [1]: x = 4**(4**4)
In [2]: y = 4**x

I will talk about this peculiar piece of code at a later post.

In any case, this snippet also didn’t reproduce the error. It is also quite unwieldy, as it raises a MemoryError after some time. Later at home I tried two more scripts.
The first is a variation on the one above:

x = 4**(4**4)
while True:
    try:
        y = 4**x
    except MemoryError:
        pass

I ran a few of those in parallel. However, my Ubuntu machine actually killed the processes running this one by one.

The second is smarter. It allocates some memory and then just copies it around:

import sys
import copy
megabytes = int(sys.argv[1])
 
x1 = [["a"*1000 + str(i) for i in range(1000)] for j in range(megabytes)]
while True:
    x2 = copy.deepcopy(x1)

After both of these scripts didn’t reproduce the problem and it still persisted arbitrarily, I returned the computer to the lab. Turns out that the two replacement sticks and the two new sticks weren’t exactly identical, and that was the cause of the problem. So now my memory is well again.

As for the scripts above, I once wrote a similar script at work. I was asked to help with testing some software in some stress testing. The goal was to simulate a heavily used computer. A few lines of Python later and the testing environment was ready.

Footnotes:
(*) – Finding out that it was a memory issue wasn’t as easy as it sounds. I didn’t think of running memtest. I checked the image on my HD with md5, and the hash didn’t match. I downloaded a second image, and again the hash didn’t match. I checked twice.
At this point I was really surprised: not only the second check didn’t match the published md5, it also didn’t match the first check. Some hours and plenty of voodoo later, a friend suggested running memtest, and the culprit was found.

Categories
Game Development Math Programming Projects Python

PyKoan – The Logic Game

As you can probably tell, I’m back from my undeclared hiatus. I’ve got lots of stuff to talk about, and I’ll be starting with PyKoan, one small project I’ve been working on lately in my spare time.

A few weeks ago I stumbled upon an article in wikipedia, regarding a logic game. This game fascinated me, especially because of the “Godel Escher Bach” connection. Quoting from Wikipedia:

Zendo is a game of inductive logic designed by Kory Heath in which one player (the “Master”) creates a rule for structures (“koans”) to follow, and the other players (the “Students”) try to discover it by building and studying various koans which follow or break the rule. The first student to correctly state the rule wins.

As it happens I’m also taking a mathematical logic course this semester. Having read about the game, I wanted to write a similar computer game. Hence – PyKoan.

PyKoan is a game where the goal is to discover some logical rule, for example, “For each x holds x%2 == 0”. This rule is applied to a koan – a list of integers. An example koan that “has Buddha nature” (follows the rule) is [0,2,8]. One which doesn’t is [1].

To implement this idea, I wrote an implementation of an expression tree very similar to the one used in vial, but with a different implemented language. I also did some experimentation with the design. Since I’ve been talking a lot about expression trees without giving a full explanation, in a future post I’ll write about the implementation used in PyKoan.

So far I didn’t code a lot of the game, just the expression tree framework, and a simple rule builder. When using Python’s interactive prompt, one can get a taste of how the game might feel:

In [19]: r = rulegen.create_rule(rulegen.easy_grammer, rulegen.easy_grammer_start)
 
In [20]: r.eval([])
Out[20]: False
 
In [21]: r.eval([0])
Out[21]: False
 
In [22]: r.eval([1])
Out[22]: False
 
In [23]: r.eval([2])
Out[23]: True
 
In [24]: r.eval([2,2])
Out[24]: True
 
In [25]: r.eval([2,2,3])
Out[25]: True
 
In [26]: r.eval([3])
Out[26]: False
 
In [27]: r.eval([4])
Out[27]: False
 
In [28]: print r
x exists such that x == 2

Here is how I would generate such an expression manually:

In [3]: from exptree import exps
 
In [4]: exps.Exists('x',exps.Eq('x',2))
Out[4]: exps.Exists(exps.Var(x), exps.Eq(exps.Var(x), exps.Imm(2)))
 
In [5]: print _
x exists such that x == 2

The game has many interesting possibilities for research, for example, computer players. Other possibilities include “just” guessing koans (not the rule itself), creating interesting and playable rules, and so on. There’s a lot to do.

This time, instead of just publishing the (unfinished) code, I decided to do something different. I’ve opened a space in assembla, with public read access. I’m opening this project for participation: if you want to join then leave a comment, or send me an email.

(Since Assembla seems to be going through some connectivity issues right now, here’s a link to a copy).